Codeforces Round #646 (Div. 2)【ABCDE】（题解）涵盖知识点：树上dp、树上博弈、二分

比赛链接：传送门

A - Odd Selection

题意： (n)张牌中选(k)张使得和为奇数
题解： 奇偶判断直接上代码。
Accept Code：

#include <bits/stdc++.h>
using namespace std;

int main(){
    int t;cin>>t;
    while(t--){
        int n,x;
        int odd=0,even=0;
        cin>>n>>x;
        for(int i=0,v;i<n;i++){
            cin>>v;
            if(v&1)odd++;
            else even++;
        }
        if(odd&&even){
            if(n==x){
                if(odd&1)puts("YES");
                else puts("NO");
            }
            else puts("YES");
        }
        else{
            if((x&1)&&odd)puts("YES");
            else puts("NO");
        }
    }
    return 0;
}

B - Subsequence Hate

题意： 给定(01)串，问最少改变几个字符可以使得不存在(010)或(101)的子序列。
题解： 利用前缀和顺序扫描一遍。
Accept Code：

#include <bits/stdc++.h>
using namespace std;
char s[1010];
int pre[1010];
const int inf=0x3f3f3f3f;
int main(){
    int t;cin>>t;
    while(t--){
        scanf("%s",s+1);
        int n=strlen(s+1);
        for(int i=1;i<=n;i++)pre[i]=pre[i-1]+(s[i]=='1');
        int ans=inf;
        for(int i=0;i<=n;i++){
            ans=min(ans,pre[i]+(n-i-(pre[n]-pre[i])));
            ans=min(ans,i-pre[i]+pre[n]-pre[i]);
        }
        cout<<ans<<"
";
    }
    return 0;
}

C - Game On Leaves

题意： AB博弈，每次从树上取下一个叶子节点。谁先拿到树上标记为(x)的节点赢。
题解： 特判(x)为叶子节点的情况。其他情况一定会拿到只剩三个节点且(x)为中间节点。判断奇偶性即可。
Accept Code：

#include <bits/stdc++.h>
using namespace std;
char s[1010];
int pre[1010];
const int inf=0x3f3f3f3f;
int main(){
    int t;cin>>t;
    while(t--){
        int n,x;
        cin>>n>>x;
        int deg=0;
        for(int i=1,u,v;i<=n-1;i++){
            cin>>u>>v;
            if(u==x||v==x)deg++;
        }
        if(deg<=1)puts("Ayush");
        else{
            if(n&1)puts("Ashish");
            else puts("Ayush");
        }
    }
    return 0;
}

题意： 互动。有一个长度为(n)（1000以内）的数组(a)（未知），长度为(k)的不等长二维子集数组(s)（给出），且这(k)个数组完全不存在相同元素。所求密码的长度同样为(k)。现规定每位密码的值为(a)中的下标不在对应(s)中出现的最大值。形式上，((S_i underset{i eq j} cap S_j = emptyset)),(P_i = maxlimits_{j otin S_i} A[j])。现在每次询问可以给出一系列的下标，我们会得到所查询的所有下标的数组中值的最大值。要求在(12)次询问后得到正确的密码
题解： 既然所有(s)独立，那么最多就只存在一个位置的密码不是(a)的最大值。（有可能全是最大值，因为(s)中可能不含最大值对应的下标。）所以我们先花(1)次来查询(n)个位置的最大值。然后二分搜索最大值所出现的位置。这里最多花费10次（(2^{10}=1024)）。最后一次我们用来查询这个位置的最大值就行了。
Accept Code：

#include <bits/stdc++.h>
using namespace std;
typedef vector<int> vi;
int query(vi q){
    cout<<"? "<<q.size()<<" ";
    for(auto i:q){
        cout<<i<<" ";
    }
    cout<<"
";
    cout.flush();
    int x;
    cin>>x;
    return x;
}
int main(){
    int t;cin>>t;
    while(t--){
        int n,k;
        cin>>n>>k;
        vector<vi> s(k);
        vi ans(k);
        for(int i=0,c;i<k;i++){
            cin>>c;
            s[i].resize(c);
            for(int j=0;j<c;j++)cin>>s[i][j];
        }
        vi q;
        for(int i=1;i<=n;i++)q.push_back(i);
        int mx=query(q);
        int l=0,r=k-1;
        while(l<r){
            int mid=(l+r)/2;
            q.clear();
            for(int i=0;i<=mid;i++){
                for(auto j:s[i])q.push_back(j);
            }
            int x=query(q);
            if(x==mx)r=mid;
            else l=mid+1;
        }
        q.clear();
        vi vis(n+1);
        for(auto i:s[l])vis[i]=1;
        for(int i=1;i<=n;i++){
            if(!vis[i])q.push_back(i);
        }
        for(int i=0;i<k;i++){
            if(i==l)ans[i]=query(q);
            else ans[i]=mx;
        }
        cout<<"! ";
        for(auto i:ans){
            cout<<i<<" ";
        }
        cout<<"
";
        cout.flush();
        string correct;
        cin>>correct;
    }
    return 0;
}

E - Tree Shuffling

题意： (n)结点的树编号为(1到n)，根为(1)。每个节点的选取代价、当前值、目标值分别为(a_i,b_i,c_i)。当前值和目标值为(01)值。每次操作可以选取一个结点(u)，在该节点的子树中任意选取(k)个结点重拍这些节点里面的数字，花费(k imes a_u)。求所有节点是否可达目标并求最小花费。
题解： 首先处理一下数组(a)。它的值是他的所有可能祖先节点中的最小值。然后计算每一棵子树所需要交换的数量。多出来的丢给父亲节点来处理即可。
Accept Code：

#include <bits/stdc++.h>
using namespace std;
typedef vector<int> vi;
const int maxn=2e5+10;
vi edg[maxn];
int a[maxn],b[maxn],c[maxn];
typedef long long ll;
ll ans=0;
int dp[maxn][2];
void dfs(int u,int p){
    if(p)a[u]=min(a[u],a[p]);
    for(auto v:edg[u]){
        if(v!=p){
            dfs(v,u);
            dp[u][0]+=dp[v][0];
            dp[u][1]+=dp[v][1];
        }
    }
    if(b[u]!=c[u])dp[u][b[u]]++;
    int mn=min(dp[u][0],dp[u][1]);
    ans+=2ll*mn*a[u];
    dp[u][0]-=mn;
    dp[u][1]-=mn;
}
int main(){
    int n;
    cin>>n;
    for(int i=1;i<=n;i++)cin>>a[i]>>b[i]>>c[i];
    for(int i=1,u,v;i<=n-1;i++){
        cin>>u>>v;
        edg[u].push_back(v);
        edg[v].push_back(u);
    }
    dfs(1,0);
    if(dp[1][0]||dp[1][1])cout<<-1<<"
";
    else cout<<ans<<"
";
    return 0;
}

Codeforces Round #646 (Div. 2)【ABCDE】（题解） 涵盖知识点：树上dp、树上博弈、二分