526互联

Educational Codeforces Round 155 (Rated for Div. 2)

发布时间 2023-10-04 11:51:13作者: EdGrass

\(A. Rigged!\)

直接取第一个人能举起的最大重量看他是否是冠军即可。

void solve(){
    int n=read();
    int fx=read(),ft=read();
    int ans=fx;
    for(int i=1;i<n;i++){
        int x=read(),t=read();
        if(x>=fx&&t>=ft)ans=-1;
    }
    cout<<ans<<'\n';
    //puts(ans>0?"YES":"NO");
    //puts(ans>0?"Yes":"No");
}

\(B. Chips on the Board\)

那么要么是每行都有一个，要么是每列都有一个（每列每行都有包括在里面）。
那么显然的取铺满的方向和，和另一方向的最小值，看看哪个方向更小即可。

void solve(){
    int n=read();
    vector<int>a(n),b(n);
    int minna=inf,minnb=inf;
    for(int i=1;i<=n;i++){
        a[i-1]=read();
        minna=min(minna,a[i-1]);
    }
    for(int i=1;i<=n;i++){
        b[i-1]=read();
        minnb=min(minnb,b[i-1]);
    }
    int ans1=0,ans2=0;
    for(int i=0;i<n;i++){
        ans1+=minna+b[i];
        ans2+=minnb+a[i];
    }
    cout<<min(ans1,ans2)<<'\n';
    //puts(ans>0?"YES":"NO");
    //puts(ans>0?"Yes":"No");
}

\(C. Make it Alternating\)

对每个区间的删掉的元素数量统计，首先统计可选择的方案数，然后选择顺序。方案数显然是乘法原理，顺序就是删除的个数的 \(A\) 。

vector<mint>fac(N);
void init(){
    fac[0]=1;
    for(int i=1;i<=200000;i++){
        fac[i]=(mint)i*fac[i-1];
    }
}
void solve(){
    string s;
    cin>>s;
    vector<int>vec;
    for(int i=0,tmp=0;i<s.size();i++){
        if(s[i-1]==s[i]||i==0)tmp++;
        else{
            vec.push_back(tmp);
            tmp=1;
        }
        if(i==s.size()-1)
            vec.push_back(tmp);
    }
    mint ans=1;
    int sum=0;
    for(auto x:vec){
        if(x-1>0){
            sum+=(x-1);
            ans*=x;
        }
    }
    cout<<sum<<" "<<(mint)fac[sum]*ans<<'\n';
    //puts(ans>0?"YES":"NO");
    //puts(ans>0?"Yes":"No");
}

\(D. Sum of XOR Functions\)

这道题的做法也比较有意思。异或有个性质是出现奇数次有贡献，偶数次无贡献。那么对于求所有区间的区间异或和乘上区间长度的和，分别统计二进制位上的出现次数为奇数的区间长度和即可，不过这个统计没有那么显然。若当前和的位置上有 \(1\) ，那么他可以与前面所有位置上为 \(0\) 的位置组成贡献区间，反之相同，详情看代码即可。

void solve(){
    int n=read();
    vector<int>sum(n+1);
    for(int i=1;i<=n;i++){
        sum[i]=sum[i-1]^read();
    }
    mint ans=0;
    mint s1[30][2],s2[30][2];
    for(int i=0;i<30;i++){
        for(int j=0;j<=n;j++){
            int x=(sum[j]>>i)&1;
            ans+=(s1[i][!x]*(mint)j-s2[i][!x])*(mint)(1<<i);
            s1[i][x]+=1;
            s2[i][x]+=j;
        }
    }
    cout<<ans<<'\n';
    //puts(ans>0?"YES":"NO");
    //puts(ans>0?"Yes":"No");
}

\(E. Interactive Game with Coloring\)

首先对于一个节点，如果有多个子节点，可以将通向子节点的边全部赋为一种颜色，通向父节点的边赋为另一种颜色。这样整个树只需要两种颜色。但是若出现节点只有一个子节点，那么若所有这样的节点都是深度都是相同的奇偶形，那么可以统一记录哪个颜色是向上的，否则我们需要引入第三种颜色，构建一个循环寻找父节点，比如出现 \(1,2\) 两种颜色，那么 \(2\) 是通向父节点，出现 \(1,3\) 两种颜色，那么 \(1\) 是通向父节点，出现 \(3,2\) 两种颜色，那么 \(3\) 是通向父节点。同时需要注意到，如果这样的奇偶性不同的特殊节点不在同一颗子树上，我们可以通过改变 \(root\) 节点的边的颜色，转换其子树的边的奇偶性，这样所有节点的奇偶性不同造成的影响将被反转为相同，因为 \(root\) 节点不需要子节点的颜色相同。

int fa[N],dep[N],d[N],maxdep=0,cnt[3];
vector<int>G[N],col(N);
void dfs_dep(int u){
    for(auto v:G[u]){
        dep[v]=dep[u]+1;
        maxdep=max(maxdep,dep[v]);
        dfs_dep(v);
    }
}
void check(int u){
    if(G[u].size()==1) cnt[dep[u]%2]++;
    for(auto v:G[u]){
        check(v);
    }
}
void dfs_col(int u){
    for(auto v:G[u]){
        col[v]=col[u]^1;
        dfs_col(v);
    }
}
void solve(){
    int n=read();
    for(int i=1;i<n;i++){
        fa[i]=read()-1;
        G[fa[i]].push_back(i);
    }
    dfs_dep(0);
    if(maxdep==1){
        cout<<1<<endl;
        for(int i=1;i<n;i++){
            cout<<1<<' ';
        }
        cout<<endl;
        int op=read(),x=read();
        cout<<1<<'\n';
        return ;
    }
    int ok=1;
    for(auto i:G[0]){
        cnt[0]=cnt[1]=0;
        check(i);
        if(cnt[1]&&cnt[0]){
            ok=0;
            break;
        }
        col[i]=cnt[0]?1:0;
        dfs_col(i);
    }
    int k=0;
    if(!ok){
        k=3;
        cout<<3<<endl;
        for(int i=1;i<n;i++){
            cout<<dep[i]%3+1<<" ";
        }
        cout<<endl;
    }else{
        k=2;
        cout<<2<<endl;
        for(int i=1;i<n;i++){
            cout<<col[i]+1<<" ";
        }
        cout<<endl;
    }
    while(true){
        int op=read();
        if(op==1||op==-1)break;
        vector<int>u;
        for(int i=0;i<k;i++){
            int x=read();
            if(x==1)u.push_back(i);
        }
        int res;
        if(u.size()>1){
            if(k==2){
                res=1;
            }else{
                if((u[0]+1)%3!=u[1]){
                    res=u[1]+1;
                }else{
                    res=u[0]+1;
                }
            }
        }else{
            res=u[0]+1;
        }
        cout<<res<<endl;
    }
    //puts(ans>0?"YES":"NO");
    //puts(ans>0?"Yes":"No");
}