Codeforces Round #646 (Div. 2) 1363 ABCE题解一只酷酷光儿的博客-

首先

Cue一下队友链接：

核心选手：https://me.csdn.net/qq_43559193

核心选手：https://me.csdn.net/weixin_43916298

比赛链接:https://codeforces.ml/contest/1363

小总结：

3题..，原因在于C题都错题了(具体下文种指出，不过延伸了一种新题)，从开始看了3分钟就交..一直wa3。

最后重新读了一遍题,C题过了已经一个小时了(好久没这么晚过了)。

然后开始写E—— 树链剖分+贪心？

上来思路错了导致我调树剖调了45分钟。

最后样例没过。

最后换了一下思路，感觉树上贪心就可以。于是写了21分钟左右就写完了(已经超过比赛7分钟）

总体来说，还可以 C题研究了新题，E巩固了树链剖分归根还是不亏。

A. Odd Selection

时间：30min （slow）

题目大意：

给出n个数问能否选出x个数，使得这x个数的和是奇数

题目思路：

疯狂讨论即可(if else题)：

1.没有奇数一定不可以

2.存在奇数，考虑m的奇偶性

(1）如果m是偶数，并且没有偶数存在，那么此时偶数个奇数一定是偶数，所以不可以。

(2）其他情况，此时，所以发现当a是个奇数就行，所以要求 a取一个小于m的奇数，让b凑齐x即可。

根据上面判断b一定存在并且a+b==n ,首先，a是奇数一定成立 ，a是偶数只需要a-1即可变为奇数，但此时就需要a-1+b>=m

所以a-1+b>=n-1，所以当m<=n-1时恒成立，只需要特判m==n的情况即可：

Code：

 /*** keep hungry and calm CoolGuang!***/ #pragma GCC optimize(2) #pragma GCC optimize("Ofast","unroll-loops","omit-frame-pointer","inline") #include <bits/stdc++.h> #include<stdio.h> #include<queue> #include<algorithm> #include<string.h> #include<iostream> #define debug(x) cout<<#x<<":"<<x<<endl; using namespace std; typedef long long ll; typedef unsigned long long ull; const ll INF=1e18; const int maxn=1e6+6; const int mod=998244353; const double eps=1e-15; inline bool read(ll &num) {char in;bool IsN=false;     in=getchar();if(in==EOF) return false;while(in!='-'&&(in<'0'||in>'9')) in=getchar();if(in=='-'){ IsN=true;num=0;}else num=in-'0';while(in=getchar(),in>='0'&&in<='9'){num*=10,num+=in-'0';}if(IsN) num=-num;return true;} ll n,m,p,x,y; ll num[maxn]; char str[maxn]; int main(){     int T;scanf("%d",&T);     while(T--){         read(n);read(m);         int a = 0,b = 0;         for(int i=1;i<=n;i++){             ll x;read(num[i]);             num[i]%=2;             if(num[i]) a++;             else b++;         }         if(!a) printf("Non");         else{             if(m==n){                 if(a%2==0) printf("Non");                 else printf("Yesn");             }             else{                 if(m%2==0&&!b) printf("Non");                 else printf("Yesn");             }         }     }     return 0; } /** 1 3 4 5 ->2 2 4 -> 1 **/

B. Subsequence Hate

时间：4min （quick）

题目大意:

给你一串01字符串，问最少修改多少次(0变1，1变0)，使得该序列没有101与010的子序列。

题目思路：

老掉牙的套路题了。

考虑最后不含有 101 与 010 子序列的字符串满足的要求:11110000 , 00001111,000000,111111

四种状态每种状态都可以以其中任意一个作为分隔符，所以直接On求出就可以啦

手速流登场

Code:

 /*** keep hungry and calm CoolGuang!***/ #pragma GCC optimize(2) #include <bits/stdc++.h> #include<stdio.h> #include<queue> #include<algorithm> #include<string.h> #include<iostream> #define debug(x) cout<<#x<<":"<<x<<endl; using namespace std; typedef long long ll; typedef unsigned long long ull; const ll INF=1e18; const int maxn=1e6+6; const int mod=1e9+7; const double eps=1e-3; inline bool read(ll &num) {char in;bool IsN=false;     in=getchar();if(in==EOF) return false;while(in!='-'&&(in<'0'||in>'9')) in=getchar();if(in=='-'){ IsN=true;num=0;}else num=in-'0';while(in=getchar(),in>='0'&&in<='9'){num*=10,num+=in-'0';}if(IsN) num=-num;return true;} ll n,m,p; ll num[maxn]; char str[maxn]; int pre0[maxn],pre1[maxn]; int cur0[maxn],cur1[maxn]; int main(){     int T;scanf("%d",&T);     while(T--){         scanf("%s",str+1);         int len = strlen(str+1);         for(int i=1;i<=len;i++){             pre0[i] = pre0[i-1];             pre1[i] = pre1[i-1];             if(str[i]=='0') pre0[i]++;             else pre1[i]++;         }         cur0[len+1]=cur1[len+1]=0;         for(int i=len;i>=1;i--){             cur0[i] = cur0[i+1];             cur1[i] = cur1[i+1];             if(str[i]=='0') cur0[i]++;             else cur1[i]++;         }         int res = 1e9+7;         for(int i=1;i<=len;i++){             res = min(res,pre0[i]+cur0[i+1]);             res = min(res,pre1[i]+cur1[i+1]);             res = min(res,pre0[i]+cur1[i+1]);             res = min(res,pre1[i]+cur0[i+1]);         }         printf("%dn",res);     }     return 0; } /*** 4 abacc ***/

C. Game On Leaves

时间：30min （slow）

题目大意：

两个人玩游戏，每次每个人都要删除一个叶子节点，给出节点x，输出最后删除x节点的玩家。

题目思路：

一个博弈水题，被我搞砸了。

刚开始读题还发现了这个叶子节点，后面写题的时候被自己的样例给坑到了：

一直觉得删除5之后，面临的就是必胜态了 (不可饶恕)….

所以判断时 一直判断的是 n-in[x] – 1 的奇偶性，in[x] 代表x的度数

所以此时延伸到一个新的题：如果不删除叶子节点该为 确定一个节点为根，每次只能删除外围节点，那就是判断n-in[x]-1的奇偶性了。

然而这个题并不是，考虑这个x成为叶子节点必然是所有点都被拿了。

所以考虑n的奇偶性即可。

Code:

 /*** keep hungry and calm CoolGuang!***/ #pragma GCC optimize(2) #pragma GCC optimize("Ofast","unroll-loops","omit-frame-pointer","inline") #include <bits/stdc++.h> #include<stdio.h> #include<queue> #include<algorithm> #include<string.h> #include<iostream> #define debug(x) cout<<#x<<":"<<x<<endl; using namespace std; typedef long long ll; typedef unsigned long long ull; const ll INF=1e18; const int maxn=1e6+6; const int mod=998244353; const double eps=1e-15; inline bool read(ll &num) {char in;bool IsN=false;     in=getchar();if(in==EOF) return false;while(in!='-'&&(in<'0'||in>'9')) in=getchar();if(in=='-'){ IsN=true;num=0;}else num=in-'0';while(in=getchar(),in>='0'&&in<='9'){num*=10,num+=in-'0';}if(IsN) num=-num;return true;} ll n,m,p,x,y; ll num[maxn]; ll minl = INF; int f = 0; int in[maxn]; int main(){     int T;scanf("%d",&T);     while(T--){         a = b = 0;         read(n);read(m);         for(int i=1;i<=n;i++){             v[i].clear();             in[i] = 0;         }         for(int i=1;i<=n-1;i++){             int x,y;scanf("%d%d",&x,&y);             in[x]++;in[y]++;         }         if(n==1){             printf("Ayushn");             continue;         }         if(in[m] == 1) printf("Ayushn");         else{             ll temp = n ;             if(temp%2==0) printf("Ayushn");             else printf("Ashishn");         }     }     return 0; } /** 1 3 4 5 ->2 2 4 -> 1 **/ 

E. Tree Shuffling

时间：57min （slow）

题目大意：

给出一个树，每棵树每个点都有一个点权a[i],含有进制位b[i],目标进制位c[i],每次可以对一个节点的子树，选择任意k个节点，使得其重新排序，花费k*a[i]，问最少花费多少使得每个点都可以达到目标c[i]

题目思路：

这个题写了个树剖也是绝了。

但是思路是对的：

首先，要记录一下每个节点下的 1->0 和 0->1

其次这种转换的题目必定是，从下往上去操作：因为无论如何，你都要操作下面的。

所以说，考虑对节点u进行操作，那么节点u有多少个 想从1->0 和 0->1的，取一下这两个最小值就可以 让这些重新组合回到原位，此时u下的1->0,1->0下的数量都要减少最小值，花费是多少呢，那绝对是从当前节点u到根节点路径下的最小值，也就是这k个节点祖先中花费最小的：所以我就想到了树剖…绝了。

调树剖的bug调了很久很久…不打算调了，就接了个水（战术接水hhh）

突然想到 u -> root 的最小值可以回溯实现。

然后就写了一遍AC的思路，不过已经超出7分钟去了..

不过深度总结一下还是不亏，毕竟又复习了树剖。

Code:

 /*** keep hungry and calm CoolGuang!***/ #pragma GCC optimize(2) #pragma GCC optimize("Ofast","unroll-loops","omit-frame-pointer","inline") #include <bits/stdc++.h> #include<stdio.h> #include<queue> #include<algorithm> #include<string.h> #include<iostream> #define debug(x) cout<<#x<<":"<<x<<endl; using namespace std; typedef long long ll; typedef unsigned long long ull; const ll INF=1e18; const int maxn=1e6+6; const int mod=998244353; const double eps=1e-15; inline bool read(ll &num) {char in;bool IsN=false;     in=getchar();if(in==EOF) return false;while(in!='-'&&(in<'0'||in>'9')) in=getchar();if(in=='-'){ IsN=true;num=0;}else num=in-'0';while(in=getchar(),in>='0'&&in<='9'){num*=10,num+=in-'0';}if(IsN) num=-num;return true;} ll n,m,p,x,y; ll a[maxn],b[maxn],c[maxn]; ll one[maxn],zero[maxn]; vector<int>v[maxn]; ll ans = 0; void dfs(int u,int fa,ll minl){     if(!b[u]&&c[u]) one[u]++;     if(b[u]&&!c[u]) zero[u]++;     for(int e:v[u]){         if(e==fa) continue;         dfs(e,u,min(minl,a[e]));         zero[u] += zero[e];         one[u] += one[e];     }     ll temp = min(one[u],zero[u]);     ans+=minl*temp*2ll;     one[u]-=temp;     zero[u]-=temp; } int main(){     read(n);     for(int i=1;i<=n;i++){         read(a[i]);         read(b[i]);         read(c[i]);     }     for(int i=1;i<=n-1;i++){         int x,y;scanf("%d%d",&x,&y);         v[x].push_back(y);         v[y].push_back(x);     }     dfs(1,1,a[1]);     if(one[1]||zero[1]) printf("-1n");     else printf("%lldn",ans);     return 0; } /** 1 3 4 5 ->2 2 4 -> 1 **/ 

至于这个D(交互体一般都不太想做），能不鸽就不鸽尽量更新。