Codeforces Round #572 (Div. 2)

题目链接：http://codeforces.com/contest/1189

A. Keanu Reeves

给一个01串，让你切成多个串，使得每个串0、1个数不同

#include using namespace std; int main() { int n; char s[110]; while(~scanf("%d",&n)){ scanf("%s",s); int f0=0,f1=0; for(int i=0;i<n;i++) if(s[i]=='0') f0++; else f1++; if(f0!=f1){ printf("1\n%s\n",s); }else{ char c=s[n-1]; s[n-1]='\0'; printf("2\n%s %c\n",s,c); } } return 0; } 

B. Number Circle

给n个数，求n个数的序列，使得相邻元素相加和大于当前元素，即a[id+1]+a[id-1]>a[id] 题解：排序，将序列按大到小，a[n]、a[n-2]、a[n-3]、…a[1]、a[n-2]，这样a[n-2]、a[n-2]、a[n-3]、…a[1]每个数，周围都有比他大的数，对于a[n]，我们取邻近最大的数a[n-1]、a[n-2]和他比较。

#include using namespace std; const int maxn=300010; int a[maxn]; int main() { int n; while(~scanf("%d",&n)){ for(int i=0;i<n;i++) scanf("%d",&a[i]); sort(a,a+n); if(a[n-3]+a[n-2]<=a[n-1]){ printf("NO\n"); continue; } printf("YES\n"); printf("%d",a[n-1]); for(int i=n-3;i>=0;i--) printf(" %d",a[i]); printf(" %d\n",a[n-2]); } return 0; } 

C. Candies!

给n个数，q个询问，每次询问一个区间[l,r]，其中r-l+1保证是2的幂次方，问这个区间有多少个candy。candy的定义是，我们每次把区间上的相邻数相加，如果其值大于10，那么candy数+1，合并区间上的数到只剩一个数为止，得到的总candy数就是区间上的candy值。 题解：对于每个区间，合并过程，本质上就是区间上数的加法，每个candy其实就是一个进位，答案就是sum[l,r]/10。

PS:这道题也可以用倍增做，附上大佬链接：https://www.cnblogs.com/wyboooo/p/11153973.html dp[l][k]表示从l开始，长度为 2 k 2^k 2k组成的candy数，那么dp[l][k]=dp[l+ 2 k − 1 2^{k-1} 2k−1][k-1]+dp[l][k-1]+(sum[l+ 2 k − 1 2^{k-1} 2k−1][k-1]+sum[l][k-1] )/10

#include using namespace std; const int maxn=200010; #define ll long long int sum[maxn],n; int main() { while(~scanf("%d",&n)){ sum[0]=0; for(int i=1;i<=n;i++){ scanf("%d",&sum[i]); sum[i]+=sum[i-1]; } int q,l,r; scanf("%d",&q); while(q--){ scanf("%d%d",&l,&r); printf("%d\n",(sum[r]-sum[l-1])/10); } } return 0; } 

D1. Add on a Tree

给一棵树，初始边权都为0，你可以选任意两个叶子结点，把这2个结点的上的边的边权都加上同一个值（可为负），对于一棵树，我们是否可以通过以上操作，得到任意我们想要的边权组合。可以则输出YES。 题解：对于一条边，要给它加边权，我们可以通过以下途径，所以对于非叶子结点，其度数要大于2。

#include using namespace std; const int maxn=200010; #define ll long long int in[maxn],n; int main() { while(~scanf("%d",&n)){ memset(in,0,sizeof(in)); int u,v; for(int i=1;i<n;i++){ scanf("%d%d",&u,&v); in[u]++;in[v]++; } bool flag=1; for(int i=1;i<=n;i++) if(in[i]==2){ flag=0;break; } if(flag) printf("YES\n"); else printf("NO\n"); } return 0; } 

D2. Add on a Tree: Revolution

在问题D1的基础上，多了边权，要输出可行解。 我们可以对于含有叶子结点的边，我们只需3次加边操作即可； 对于不含叶子结点的边，我们要add(u,t,w) add(v,t,-w)，需要6次加边操作。 构树参考：https://www.e-learn.cn/content/qita/2465332 对于每个度数有3以上的边，我们需要给他们增加叶子结点，在dfs中，对于找到u的以v为根结点的子树，我们取v的第一个结点给u的叶子结点；对于叶子结点，其leaf值就是本身。 除此之外，如果度数>2的v不能找到3个叶子结点，则需要往父亲结点上找另外一个叶子结点。

#include using namespace std; const int maxn=1010; #define mp make_pair vector<pair<int,int>> ve[maxn]; struct edge{ int u,v,w; }e[maxn],ans[maxn*10]; vector<int> leaf[maxn]; int in[maxn],tot; int p[maxn],n; void dfs(int u) { if(in[u]==1){ leaf[u].push_back(u);return; } for(auto& tmp:ve[u]){ int v=tmp.first; if(v==p[u]) continue; p[v]=u; dfs(v); leaf[u].push_back(leaf[v][0]); } } void pre() { for(int i=1;i<=n;i++) if(in[i]>2){ dfs(i);break; } for(int i=1;i<=n;i++){ if(ve[i].size()>2&&leaf[i].size()<=2){ int u=p[i]; /*
			for(int j=0;j