cfRounddiv3--CDEF题解

C-Assembly via Remainders

思路：因为xi最大只有500，而构造的ai最大可以到1e9，直接从501开始构造即可。

void solve(){           //C  简单构造
    int n; cin>>n;
    vector<int> vct;
    vct.emplace_back(501);
    for(int i=2;i<=n;i++){
        int x; cin>>x;
        vct.emplace_back(vct[i-2]+x);
    }
    for(int i=0;i<n;i++) cout<<vct[i]<<" ";
    cout<<endl;
}

D-Permutation Game

思路：按着顺序枚举即可。枚举每一个位置，可以计算出此后一直拿这个位置可以得到的最终的值。取max即可

int p[200005];
int arr[200005];
void solve(){               //D         枚举n，贪心
    int n,k,sa,sb; cin>>n>>k>>sa>>sb;
    for(int i=1;i<=n;i++) cin>>p[i];
    for(int i=1;i<=n;i++) cin>>arr[i];
//    vector<int> pa,pb;
//    pa.emplace_back(sa);
//    pb.emplace_back(sb);
//    for(int i=2;i<=n;i++) pa.emplace_back(p[pa[i-2]]);
//    for(int i=2;i<=n;i++) pb.emplace_back(p[pb[i-2]]);
    int maxa=INT_MIN,suma=0,maxb=INT_MIN,sumb=0;
    for(int i=1;i<=k&&i<=n;i++){
        suma+=arr[sa];
        maxa=max(maxa,suma+(k-i)*arr[sa]);
        sa=p[sa];
        sumb+=arr[sb];
        maxb=max(maxb,sumb+(k-i)*arr[sb]);
        sb=p[sb];
    }
    if(maxa>maxb) cout<<"Bodya"<<endl;
    else if(maxb>maxa) cout<<"Sasha"<<endl;
    else cout<<"Draw"<<endl;
}

E-Cells Arrangement

思路：集合最大的值为(n-1+n-1).选了(1,1)和(1,2)可以贡献0,1;两个值.再选(n,n)可以贡献(n-1+n-1)和(n-1+n-1-1). 再选(n-1,n-1)可以贡献(n-1-1+n-1-1)和(n-1-1+n-1-1-1)都是会贡献两个不重复的，没出现过的值。

举例：n=4; 

选择(1,1)和(1,2)-->S={0,1};

选择(4,4)-->S={0,1,6,5};

再选择(3,3)-->S={0,1,6,5,4,3};

可是为什么不会存在一个点，选了这个点可以贡献3个没出现过的值的呢？..

void solve(){               //E   巧妙构造题，如果想歪了的话，将会一直卡死  30分钟
    int n; cin>>n;
    cout<<"1 1"<<endl;
    cout<<"1 2"<<endl;
    for(int i=n;i>=3;i--) cout<<i<<" "<<i<<endl;
    cout<<endl;
}

F-Equal XOR Segments