Codeforces Round #572
A. Keanu Reeves
题意
要将一个仅包含 \(01\) 的字符串分割成尽可能少的段,使得每一段中的 \(0\) 和 \(1\) 数量不同。
分析
做一个简单的分类讨论即可:
- 如果原串中 \(0\) 和 \(1\) 数量不同,直接输出;
- 如果相同的话,我们只需要取出任意一个字符,即将第一个字符分割出,显然这样就不同了。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 |
#include<bits/stdc++.h> using namespace std; #define LL long long #define inf 0x3fffffff using namespace std; int n; char s[200]; int main() { scanf("%d%s",&n,s+1); int sum=0; for (int i=1;i<=n;i++) if (s[i]=='1') sum++; if (sum*2==n) { printf("2\n"); putchar(s[1]),putchar(' '); for (int i=2;i<=n;i++) putchar(s[i]); puts(""); } else { printf("1\n%s\n",s+1); } return 0; } |
B. Number Circle
题意
要求将给定的数构造成一个环数列,满足任意一个数都要小于其两边数的和。
分析
考虑最大的数,一定会用次大的和第三大的数来围起来。
于是我们将最大的数放在第一位,次大的放在第二位,第三大的放在最后。
接下来,可以发现,将剩下的数倒序的填入从第三位到倒数第二位的位置即可,因为每一个数都显然满足小于下一个数,而因为每个数都是正的,所以显然满足任意一个数都要小于其两边数的和。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 |
#include<bits/stdc++.h> using namespace std; #define LL long long #define inf 0x3fffffff using namespace std; int n,a[100010]; bool check() { for (int i=2;i<n;i++) if (a[i]>=a[i-1]+a[i+1]) return false; if (a[1]>=a[n]+a[2]) return false; if (a[n]>=a[n-1]+a[1]) return false; return true; } bool cmp(int x,int y) { return x>y; } int main() { scanf("%d",&n); for (int i=1;i<=n;i++) scanf("%d",&a[i]); sort(a+1,a+1+n,cmp); int t=a[3]; for (int i=3;i<n;i++) a[i]=a[i+1]; a[n]=t; if (check()) { puts("YES"); for (int i=1;i<=n;i++) printf("%d ",a[i]); puts(""); } else puts("NO"); return 0; } |
C. Candies!
题意
将给定的一个区间数列,每次两两合并,大于等于 \(10\) 的计数 \(+1\) 后取模,不断进行这样的合并,直到只剩下一个数,求计数次数。
分析
我们可以考虑合并的过程:
- 如果两个数相加 \(\le 9\) ,显然数字和不变;
- 如果两个数相加 \(\ge 10\) ,计数依次,数字和减小了 \(10\) 。
而合并后的最后结果其实就是所有数的数字和,那么显然计数个数也就是本来数字和除以 \(10\) 取整的结果。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 |
#include<bits/stdc++.h> using namespace std; #define LL long long #define inf 0x3fffffff int n,q,a[100010],sum[100010]; int main() { scanf("%d",&n); memset(sum,0,sizeof(sum)); for (int i=1;i<=n;i++) scanf("%d",&a[i]),sum[i]=sum[i-1]+a[i]; int x,y; scanf("%d",&q); while(q--) { scanf("%d%d",&x,&y); printf("%d\n",(sum[y]-sum[x-1])/10); } return 0; } |
D1. Add on a Tree
题意
给出一棵树,每次可以选择任意的两个不同的叶子结点,将两个叶子结点路径上的所有边都加上任意的权值 \(x\) ,\(x\) 是实数,询问这棵树的边权是否可以是任意的。
分析
先给出结论:边权可以是任意的,当且仅当不存在度数为 \(2\) 的结点。
证明:
必要性:显然,如果存在度数为 \(2\) 的结点,那么这个结点所连接的两条边的权值在任何时刻都必须是一样的,无法达到边权任意。
充分性:我们要尝试说明在度数均不为 \(2\) 的情况下,一定存在一种方式能够完成。
我们考虑对于任意的两个结点 \(x,y\) 所构成的边 \((x,y)\) ,需要使他的边权变成 \(z\) 。假设当前的根为 \(root\) ,且结点 \(root\) 是一个叶子结点(为了方便,后面的构造方式会有所体现),于是 \(x,y\) 必为父子关系,假设 \(x\) 是 \(y\) 的父结点。
对于将边 \((x,y)\) 变成 \(z\) ,我们分成两步:路径 \(root\)->\(y\) 加上 \(z\) , 路径 \(root\)->\(x\) 加上 \(-z\) 。
而对于任意的路径 \(root\)->\(x\) 加上 \(z\) ,我们可以通过 \(x\) 结点不同子树中的叶子结点 \(u,v\) 达到 (\(u,v\) 是 \(x\) 为根的不同子树中的叶子结点,显然需要满足 \(x\) 的度数至少为 \(3\)):
- 路径 \(root\)->\(u\) 加上 \(\frac{z}{2}\) ;
- 路径 \(root\)->\(v\) 加上 \(\frac{z}{2}\) ;
- 路径 \(v\)->\(u\) 加上 \(-\frac{z}{2}\) 。
显然这样就完成了路径 \(root\)->\(x\) 加上 \(z\) 的操作。
于是可以证明充分性是成立的。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 |
#include<bits/stdc++.h> using namespace std; #define LL long long #define inf 0x3fffffff int n,d[100010]; vector<int> e[100010]; bool check() { for (int i=1;i<=n;i++) if (d[i]==2) return false; return true; } int main() { scanf("%d",&n); int x,y; for (int i=1;i<n;i++) scanf("%d%d",&x,&y), e[x].push_back(y), e[y].push_back(x), d[x]++,d[y]++; if (!check()) puts("NO"); else puts("YES"); return 0; } |
D2. Add on a Tree: Revolution
题意
给出一棵树,每次可以选择任意的两个不同的叶子结点,将两个叶子结点路径上的所有边都加上任意的权值 \(x\) ,\(x\) 是整数,构造一种方案使得变成给定的树。
分析
给定树的边权一定是偶数,于是不需要考虑 \(\frac{z}{2}\) 的情况。
于是直接借用 D1 中充分性证明中的构造方式构造即可。
最多只需要 \(6(n-1)\) 次操作,而显然由于某些叶子结点的关系,实际操作次数是不到这个数的。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 |
#include<bits/stdc++.h> using namespace std; #define LL long long #define inf 0x3fffffff int n,ans,d[100010],a[1010][1010],leaf[1010][2],f[1010],dep[1010],b[1010][1010]; vector<int> e[100010]; struct data { int x,y,z; data(int a=0,int b=0,int c=0):x(a),y(b),z(c){} }p[100010]; bool check() { for (int i=1;i<=n;i++) for (int j=1;j<=n;j++) if (a[i][j]!=b[i][j]) return false; return true; } void solve(int x,int y,int z) { if (x==y) return ; p[++ans]=data(x,y,z); if (dep[x]<dep[y]) swap(x,y); while(dep[x]>dep[y]) { int fa=f[x]; b[x][fa]+=z; b[fa][x]+=z; x=fa; } while(x!=y) { int fa=f[x]; b[x][fa]+=z; b[fa][x]+=z; x=fa; fa=f[y]; b[y][fa]+=z; b[fa][y]+=z; y=fa; } } void dfs(int x,int fa) { int flag=0; set<int> s; for (auto y:e[x]) if (y!=fa) { dep[y]=dep[x]+1; dfs(y,x); f[y]=x; flag=1; //if (leaf[y][1]>0) s.insert(leaf[y][1]); if (leaf[y][0]>0) s.insert(leaf[y][0]); } if (flag==0) leaf[x][0]=x; if (s.size()==1) leaf[x][0]=*s.begin(); else if (s.size()>1) { auto z=s.begin(); leaf[x][0]=*z; z++; leaf[x][1]=*z; } if (leaf[x][1]==0) leaf[x][1]=leaf[x][0]; } int main() { scanf("%d",&n); int x,y,z; for (int i=1;i<n;i++) scanf("%d%d%d",&x,&y,&z), a[x][y]=z,a[y][x]=z, e[x].push_back(y), e[y].push_back(x), d[x]++,d[y]++; int root; for (int i=1;i<=n;i++) if (d[i]==1) {root=i;break;} //cout<<root<<endl; dep[root]=1; dfs(root,0); ans=0; for (int i=1;i<=n;i++) if (i!=root) { int fa=f[i],z=a[f[i]][i]; solve(leaf[i][0],root,z/2); solve(leaf[i][1],root,z/2); solve(leaf[i][0],leaf[i][1],-z/2); if (fa!=root) { solve(leaf[fa][0],root,-z/2); solve(leaf[fa][1],root,-z/2); solve(leaf[fa][0],leaf[fa][1],z/2); } } if (check()) { puts("YES"); printf("%d\n",ans); for (int i=1;i<=ans;i++) printf("%d %d %d\n",p[i].x,p[i].y,p[i].z); }else puts("NO"); /*for (int i=1;i<=n;i++,puts("")) for (int j=1;j<=n;j++) printf("%d ",b[i][j]);*/ return 0; } |
E. Count Pairs
题意
给出一个数列,求其中满足 \((a_i + a_j)(a_i^2 + a_j^2) \equiv k \bmod p\) 的数对数量。
分析
这个式子如果在高中数学中,还是算非常明显的了。
\((a_i + a_j)(a_i^2 + a_j^2) \equiv k \Leftrightarrow (a_i + a_j)(a_i – a_j)(a_i^2 + a_j^2) \equiv k\cdot (a_i – a_j) \Leftrightarrow a_i^4-a_j^4\equiv ka_i – ka_j \Leftrightarrow a_i^4-ka_i\equiv a_j^4-ka_j\)
于是我们只需要算每一个数 \((a_i^4-ka_i)\; mod \; p\) 的结果,用 map 维护相同的数,计算贡献即可。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 |
#include<bits/stdc++.h> using namespace std; #define LL long long #define inf 0x3fffffff int n; LL p,k,a[300010]; map<LL,LL> m; LL calc(LL x) { LL y=x*x%p*x%p*x%p; LL z=k*x%p; return (y+p-z)%p; } int main() { scanf("%d%lld%lld",&n,&p,&k); m.clear(); for (int i=1;i<=n;i++) { scanf("%lld",&a[i]); m[calc(a[i])]++; } LL ans=0; for (auto y:m) { LL z=y.second; ans+=z*(z-1)/2; } cout<<ans<<endl; return 0; } |
F. Array Beauty
题意
一个数列的 beauty 值是任意两个数绝对值的最小值。
给出一个数列,求其所有子数列的 beauty 值。
分析
很经典的套路。
对于求所有子数列的 beauty 值,可以转换成求所有 \(\ge beauty (beauty\ge 1)\) 的子数列数量。
考虑枚举 beauty 值,设状态 \(f[i][j]\) 表示当前子数列的长度为 \(i\) ,以 \(j\) 结尾的 beauty 值 \(\ge beauty\) 的数量。
转移方程是显然的,\(f[i][j]=\sum f[i-1][k] (|a_j-a_k|\ge beauty)\) 。
于是我们考虑将数列排序(因为是子数列,排序显然不会影响答案),然后就可以用前缀和来优化方程的转移了。
这样的时间复杂度是 \(O(nk\cdot beauty)\) ,而显然 \(beauty=\left \lfloor \frac{max\{a_i\}}{k-1}\right \rfloor\) ,于是复杂度是近似 \(O(n\cdot max\{a_i\})\) 。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 |
#include<bits/stdc++.h> using namespace std; #define LL long long #define inf 0x3fffffff int n,k,a[1010]; LL f[1010][1010]; const LL mo=998244353LL; void add(LL &x,LL y) { x+=y; if (x>mo) x%=mo; } int main() { scanf("%d%d",&n,&k); int Max=0; for (int i=1;i<=n;i++) scanf("%d",&a[i]),Max=max(Max,a[i]); sort(a+1,a+1+n); Max/=k-1; LL ans=0; for (int bea=1;bea<=Max;bea++) { for (int i=1;i<=k;i++) for (int j=1;j<=n;j++) f[i][j]=0; for (int i=1;i<=n;i++) f[1][i]=1; for (int i=2;i<=k;i++) { LL sum=0;int l=1; for (int j=1;j<=n;j++) { while(l<j&&a[j]-a[l]>=bea) add(sum,f[i-1][l]),l++; add(f[i][j],sum); } } for (int i=1;i<=n;i++) add(ans,f[k][i]); } cout<<ans<<endl; return 0; } |