Codeforces Round 817 (Div. 4) 6

A.A. Spell Check

两个串是否可以通过排列变成一样的

优雅写法直接排序判断是否一样即可

string ans="Timur";
void solve()
{
    sort(ans.begin(),ans.end());
    cin>>n;
    string s; cin>>s;
    sort(s.begin(),s.end());
    cout<<(s==ans ? "YES" : "NO")<<endl;
    return ;
}

B. Colourblindness

考虑是否一样抓住性质

只要一个位置只有一个R就是不合理的

void solve()
{
    cin>>n;
    bool ok=false;
    string a,b;
    cin>>a>>b;
    for(int i=0;i<n;i++){
        ok |= (a[i]=='R' && b[i]!='R') || (a[i]!='R' && b[i]=='R');
    }
    cout<<(ok ? "NO" : "YES")<<endl;
    return ;
}

C. Word Game

对于每一个位置进行暴力check即可可以考虑用map存下来每一个串

map<string,int> mp[4],mmp;
int t,n,m;
int a,b,c;
string s[4][N];
void solve()
{
    a=b=c=0;
    cin>>n;
    for(int i=1;i<=3;i++) mp[i].clear();
    mmp.clear();
    for(int i=1;i<=3;i++){
        string s;
        for(int j=1;j<=n;j++){
         cin>>s;
         mp[i][s]++;
         mmp[s]++;
        }
    }
    for(auto &[s,v]:mmp){
        if(mp[1][s]&&mp[2][s]&&mp[3][s]) continue;
        else if(mp[1][s]&&!mp[2][s]&&!mp[3][s]) a+=3;
        else if(!mp[1][s]&&mp[2][s]&&!mp[3][s]) b+=3;
        else if(!mp[1][s]&&!mp[2][s]&&mp[3][s]) c+=3;
        else {
            if(mp[1][s]) a++;
            if(mp[2][s]) b++;
            if(mp[3][s]) c++;
        }   
    }
    cout<<a<<" "<<b<<" "<<c<<endl;

        return ;
}

D. Line

对于每个位置我们的改变他带来的收益是多少也就是对贡献的增加值

按照贡献最大的排序即可

bool cmp(PII a,PII b)
{
    return  a.first-a.second>b.first-b.second;
}
void solve()
{
    string s;
    cin>>n>>s; s=' '+s;
    LL ans=0;
    for(int i=1;i<=n;i++){
        if(s[i]=='L') ans+=i-1;
        else ans+=n-i;
        if(s[i]=='L'){
            a[i]={n-i,i-1};
        }
        else a[i]={i-1,n-i};
    }
    sort(a+1,a+1+n,cmp);
    for(int i=1;i<=n;i++){
            auto [x,y]=a[i];
            if(x-y>=0) ans=ans-y+x;
            else {
                for(int j=i;j<=n;j++) cout<<ans<<" ";
                cout<<endl;
                return ;
            }
            cout<<ans<<" ";
    }
    cout<<endl;
        return ;
}

E. Counting Rectangles

对于每一个位置我们要求的是在这个矩阵中间的数量我们查看数据范围可以知道
需要的就是做一个二维前缀和接着o1的查询在给定的盒子里面的数量

LL g[M][M];
void solve()
{
    cin>>n>>m;
    memset(g,0,sizeof g);
    for(int i=1;i<=n;i++){
        LL a,b; cin>>a>>b;
        g[a][b]+=a*b;
    }
    for(int i=1;i<M-5;i++)
    for(int j=1;j<M-5;j++){
        g[i][j]+=g[i-1][j]+g[i][j-1]-g[i-1][j-1];
    }

    while(m--){
        LL a,b,x,y; cin>>a>>b>>x>>y;
        a++,b++,x--,y--;
        cout<<g[x][y]-g[x][b-1]-g[a-1][y]+g[a-1][b-1]<<endl;
    }

F. L-shapes

一道很抽象的模拟题,我们发现数据范围很小

我们可以先把每一个L形的bfs出来,然后我们直接对他进行检查是不是L的,然后直接通过暴力的方式去看是不是任意的两个有相邻的

int dx[]={0,0,1,-1},dy[]={1,-1,0,0};
bool st[55][55];
void bfs(int x,int y,vector<PII>&a)
{
    a.push_back({x,y});
    st[x][y]=true;
    queue<PII> q; q.push({x,y});

    while(!q.empty()){
        auto [x,y]=q.front(); q.pop();
        for(int i=0;i<4;i++){
        int xx=x+dx[i],yy=y+dy[i];
        if(xx<1||xx>n||yy<1||yy>m) continue;
        if(g[xx][yy]!='*') continue;
        if(st[xx][yy]) continue;
        st[xx][yy]=true;
        a.push_back({xx,yy});
        q.push({xx,yy});
        }
    }
    return ;
}
bool check1(vector<PII>&v)
{
    if(v.size()!=3)  return false;
    if(v[0].first==v[1].first&&v[1].first==v[2].first) return  false;
    if(v[0].second==v[1].second&&v[1].second==v[2].second) return false;
    return true;
}

bool check2(vector<PII> &a,vector<PII> &b)
{
    for(auto &[x,y]:a){
        for(auto &[xx,yy]:b){
            if(abs(x-xx)<=1&&abs(y-yy)<=1){
                return false;
            }
        }
    }
    return true;
}
void solve()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    for(int j=1;j<=m;j++)
    st[i][j]=false;

    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++)
        cin>>g[i][j];
    }

    cnt=0;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            if(g[i][j]=='*'&&!st[i][j]){
                bfs(i,j,v[++cnt]);
            }
        }
    }
    bool ok=false;
    for(int i=1;i<=cnt;i++){
        if(!check1(v[i])){
            ok=true;
        }
        if(ok) break;
    } 

    for(int i=1;i<=cnt;i++){
        if(ok) break;
        for(int j=i+1;j<=cnt;j++){
            if(!check2(v[i],v[j])){
                ok=true;
                break;
            }
        }
    }
   for(int i=1;i<=cnt;i++) v[i].clear();

   if(!ok) cout<<"YES"<<endl;
   else cout<<"NO"<<endl;
        return ;
}

G. Even-Odd XOR

关于位运算的不过就是拆位，但是我们要注意^是具有前缀和性质的我们可以做这样一个操作,对于实在构造不出来的题目是想一下有没有什么万金油的写法比如这道题我们看到要求数不能太大如果我们利用异或的性质相等就是异或为0的话就十分巧妙

void solve()
{
    cin>>n;
    LL sum=0;
    for(int i=1;i<n-2;i++){
        cout<<i<<" ";
        sum^=i;
    }
    cout<<(1<<29)<<" "<<(1<<30)<<"  "<<(sum^(1<<29)^(1<<30))<<endl;
        return ;
}