CSP 202206 T1-T5题解

0 views · 2024-03-15

T1 归一化处理

用了一下方差的变形：

D (x) = E (x^{2}) - [E (x)]^{2}

C++

#include <iostream>
#include <cmath>
using namespace std;
int n,a[1005];
double avg,avg_sq;
int main()
{
    cin>>n;
    for(int i=0;i<n;i++)
    {
        cin>>a[i];
        avg+=a[i];
        avg_sq+=a[i]*a[i];
    }
    avg/=n,avg_sq/=n;
    for(int i=0;i<n;i++)
    {
        cout<<(a[i]-avg)/sqrt(avg_sq-avg*avg)<<endl;
    }
    return 0;
}
/*
in:
7
-4 293 0 -22 12 654 1000

out:
-0.7485510379073613
0.04504284674812264
-0.7378629047806881
-0.7966476369773906
-0.7057985054006686
1.0096468614303775
1.9341703768876082
*/

T2 寻宝！大冒险！

C++

#include <iostream>
#include <unordered_set>
using namespace std;
int n,l,s,ans;
int t[1005][2];//树的坐标
int g[55][55];//藏宝图
unordered_set<long long> st;//用一个long long存储坐标x*(1e9+1)+y
bool check(int x,int y)
{
    for(int i=0;i<=s;i++)
    {
        for(int j=0;j<=s;j++)
        {
            long long p=(1e9L+1)*(x+i)+y+j;
            //绿化图坐标(x+i,y+j)与藏宝图上坐标(i,j)不对应，匹配失败
            if((st.find(p)!=st.end())^g[s-i][j])
            {
                return false;
            }
        }
    }
    return true;
}
int main()
{
    cin>>n>>l>>s;
    for(int i=0;i<n;i++)
    {
        cin>>t[i][0]>>t[i][1];
        long long p=(1e9L+1)*t[i][0]+t[i][1];
        st.insert(p);
    }
    for(int i=0;i<=s;i++)
    {
        for(int j=0;j<=s;j++)
        {
            cin>>g[i][j];
        }
    }
    for(int i=0;i<n;i++)
    {
        int x=t[i][0],y=t[i][1];
        if(x+s<=l&&y+s<=l)
        {
            ans+=check(x,y);
        }
    }
    cout<<ans<<endl;
    return 0;
}
/*
in:
5 100 2
0 0
1 1
2 2
3 3
4 4
0 0 1
0 1 0
1 0 0

out:
3
*/

T3 角色授权

C++

#include <iostream>
#include <unordered_set>
#include <unordered_map>
#define N 505
using namespace std;
int n,m,q;
string s;
struct USER{
    string username;
    int ng;
    unordered_set<string> gset;
};
struct ROLE{
    string rolename;
    int nv,no,nn;//操作、资源种类、资源名称
    unordered_set<string> vset,oset,nset;
    bool vadmin,oadmin;//允许的操作/资源是否含有"*"
}role[N];
struct RBAC{
    string rolename;
    int ns;
    unordered_set<string> sset_user;
    unordered_set<string> sset_group;
}rbac[N];//role-based access control
struct QUERY{
    USER user;
    string v,o,n;
};
unordered_map<string,int> rolemap;//角色名--id
//判断一个角色能否对某个资源执行某个操作
bool check(int &roleid,string &qv,string &qo,string &qn)
{
    bool ok=true;
    ROLE &r=role[roleid];
    ok&=r.vadmin||r.vset.find(qv)!=r.vset.end();
    if(!ok) return false;
    ok&=r.oadmin||r.oset.find(qo)!=r.oset.end();
    if(!ok) return false;
    if(r.nn==0) return true;
    ok&=r.nset.find(qn)!=r.nset.end();
    return ok;
}
bool query(QUERY &q)
{
    for(int i=0;i<m;i++)
    {
        RBAC &ac=rbac[i];
        int roleid=rolemap[ac.rolename];
        if(ac.sset_user.find(q.user.username)==ac.sset_user.end())//q.user.username不在ac.sset_user中
        {
            bool ok=false;
            for(auto &elem:ac.sset_group)
            {
                if(q.user.gset.find(elem)!=ac.sset_group.end())
                {
                    ok=true;
                    break;
                }
            }
            if(!ok) continue;//且q.user.gset与ac.sset_group没有交集，就跳过对这个角色检查
        }
        if(check(roleid,q.v,q.o,q.n)) return true;
    }
    return false;
}
int main()
{
    ios::sync_with_stdio(false);
    cin>>n>>m>>q;
    for(int i=0;i<n;i++)
    {
        cin>>role[i].rolename;
        rolemap[role[i].rolename]=i;
        cin>>role[i].nv;
        for(int j=0;j<role[i].nv;j++)
        {
            cin>>s;
            role[i].vset.emplace(s);
            if(s=="*") role[i].vadmin=true;
        }
        cin>>role[i].no;
        for(int j=0;j<role[i].no;j++)
        {
            cin>>s;
            role[i].oset.emplace(s);
            if(s=="*") role[i].oadmin=true;
        }
        cin>>role[i].nn;
        for(int j=0;j<role[i].nn;j++)
        {
            cin>>s;
            role[i].nset.emplace(s);
        }
    }
    for(int i=0;i<m;i++)
    {
        cin>>rbac[i].rolename;
        cin>>rbac[i].ns;
        for(int j=0;j<rbac[i].ns;j++)
        {
            char typ;
            cin>>typ>>s;
            if(typ=='u')
            {
                rbac[i].sset_user.emplace(s);
            }
            else
            {
                rbac[i].sset_group.emplace(s);
            }
        }
    }
    for(int i=0;i<q;i++)
    {
        QUERY q;
        cin>>q.user.username;
        cin>>q.user.ng;
        for(int j=0;j<q.user.ng;j++)
        {
            cin>>s;
            q.user.gset.emplace(s);
        }
        cin>>q.v>>q.o>>q.n;
        cout<<query(q)<<endl;
    }
    return 0;
}
/*
in:
1 2 3
op 1 open 1 door 0
op 1 g sre
op 1 u xiaop
xiaoc 2 sre ops open door room302
xiaop 1 ops open door room501
xiaoc 2 sre ops remove door room302

out:
1
1
0
*/

T4 光线追踪

因为反射面的总长度 $< 3 \times 1 0^{5}$ ，可以用map存整数格点，注意不存端点。

C++

#include <iostream>
#include <map>
#include <unordered_map>
#define N 100005
using namespace std;
int m,mirrors[N][4];
struct RPOINT{
    //反射面上的点
    int k;
    double a;
};
struct RAYPOS{
    int x,y,d;
    double I;
    int ttl;
};
unordered_map<int,map<int,RPOINT>> px,py;
int abs(int x){return x>0?x:-x;}
void add(int x1,int y1,int x2,int y2,double a)
{
    for(int x=x1,y=y1,dx=abs(x2-x1)/(x2-x1),dy=abs(y2-y1)/(y2-y1);;x+=dx,y+=dy)
    {
        if(x==x1) continue;
        if(x==x2) break;
        px[x][y]=(RPOINT){dy/dx,a};
        py[y][x]=(RPOINT){dy/dx,a};
    }
    return;
}
void del(int k)
{
    int x1=mirrors[k][0];
    int y1=mirrors[k][1];
    int x2=mirrors[k][2];
    int y2=mirrors[k][3];
    for(int x=x1,y=y1,dx=abs(x2-x1)/(x2-x1),dy=abs(y2-y1)/(y2-y1);;x+=dx,y+=dy)
    {
        if(x==x1) continue;
        if(x==x2) break;
        px[x].erase(y);
        py[y].erase(x);
    }
    return;
}
RAYPOS query(RAYPOS p)
{
    int x=p.x,y=p.y,d=p.d,ttl=p.ttl;
    double I=p.I;
    if(I<1) return (RAYPOS){0,0,0,0,0};
    if(d==0)
    {
        auto it=py[y].upper_bound(x);
        if(it!=py[y].end())
        {
            int nx=it->first;
            int dt=nx-x;
            if(ttl<dt) return (RAYPOS){x+ttl,y,0,I,0};
            else
            {
                int k=it->second.k;
                double a=it->second.a;
                if(k==1) return query((RAYPOS){nx,y,1,I*a,ttl-dt});
                else return query((RAYPOS){nx,y,3,I*a,ttl-dt});
            }
        }
        else return (RAYPOS){x+ttl,y,0,I,0};
    }
    else if(d==1)
    {
        auto it=px[x].upper_bound(y);
        if(it!=px[x].end())
        {
            int ny=it->first;
            int dt=ny-y;
            if(ttl<dt) return (RAYPOS){x,y+ttl,0,I,0};
            else
            {
                int k=it->second.k;
                double a=it->second.a;
                if(k==1) return query((RAYPOS){x,ny,0,I*a,ttl-dt});
                else return query((RAYPOS){x,ny,2,I*a,ttl-dt});
            }
        }
        else return (RAYPOS){x,y+ttl,0,I,0};
    }
    else if(d==2)
    {
        auto it=py[y].lower_bound(x);
        if(it!=py[y].begin())
        {
            it--;
            int nx=it->first;
            int dt=x-nx;
            if(ttl<dt) return (RAYPOS){x-ttl,y,0,I,0};
            else
            {
                int k=it->second.k;
                double a=it->second.a;
                if(k==1) return query((RAYPOS){nx,y,3,I*a,ttl-dt});
                else return query((RAYPOS){nx,y,1,I*a,ttl-dt});
            }
        }
        else return (RAYPOS){x-ttl,y,0,I,0};
    }
    else if(d==3)
    {
        auto it=px[x].lower_bound(y);
        if(it!=px[x].begin())
        {
            it--;
            int ny=it->first;
            int dt=y-ny;
            if(ttl<dt) return (RAYPOS){x,y-ttl,0,I,0};
            else
            {
                int k=it->second.k;
                double a=it->second.a;
                if(k==1) return query((RAYPOS){x,ny,2,I*a,ttl-dt});
                else return query((RAYPOS){x,ny,0,I*a,ttl-dt});
            }
        }
        else return (RAYPOS){x,y-ttl,0,I,0};
    }
}
int main()
{
    ios::sync_with_stdio(false);
    cin>>m;
    for(int i=0;i<m;i++)
    {
        int opt;
        cin>>opt;
        if(opt==1)
        {
            int x1,y1,x2,y2;
            double a;
            cin>>x1>>y1>>x2>>y2>>a;
            mirrors[i][0]=x1;
            mirrors[i][1]=y1;
            mirrors[i][2]=x2;
            mirrors[i][3]=y2;
            add(x1,y1,x2,y2,a);
        }
        else if(opt==2)
        {
            int k;
            cin>>k;
            del(k-1);
        }
        else if(opt==3)
        {
            int x,y,d,t;
            double I;
            cin>>x>>y>>d>>I>>t;
            RAYPOS ans=query((RAYPOS){x,y,d,I,t});
            cout<<ans.x<<' '<<ans.y<<' '<<int(ans.I)<<endl;
        }
    }
    return 0;
}
/*
in:
7
1 0 4 2 2 0.4
1 2 2 0 0 0.45
3 -1 3 0 6 5
3 1 5 3 2.4 5
3 0 2 0 3 4
2 1
3 1 5 3 2.4 5

out:
0 1 1
0 0 0
4 2 3
0 1 1
*/

T5 PS无限版

线段树题，因为涉及到查询平方和，还需要额外维护乘积交叉项；题目中涉及的二维坐标变换可以在齐次坐标下使用三阶矩阵表示，由于第三行总是 $[0, 0, 1]$ ，在下面代码中省略，只用mat[6]表示一个三阶矩阵。

C++