Codeforces 891 div3 A-G
A. Array Coloring
分析
元素和为偶数才可以让两种颜色的元素的奇偶性相同(奇+奇=偶，偶+偶=偶)
奇=奇+偶
C++代码
#include using namespace std; int main(){ int t; cin>>t; while(t--){ int n,sum=0; cin>>n; for(int i=0;i>x; sum+=x; } if(sum&1)puts("NO"); else puts("YES"); } return 0; } B. Maximum Rounding
分析
从大到小枚举数的每一位，如果当前位置可以进位，则一直往前进位直到不能进位，然后break，每次记录当前在哪里进位的，它后面的所有数都变成0，前面的不变
C++代码
#include using namespace std; int main(){ int t; cin>>t; while(t--){ string s; cin>>s; s='0'+s; int flag=1e9;//flag记录最后一次进位的位置 for(int i=1;i='5'){ int j=i; while(j>=1&&s[j]>='5'){//当前位置可以进位，则一直往前进，直到不能进位 s[j-1]++; flag=j; j--; } break; } } if(flag==1)cout<=flag)cout<<0;//最后一次进位的位置往后的数字全都变成0 else cout< C. Assembly via Minimums
分析
由题意，最小的数在序列中一定出现了n-1次，第二小的数出现n-2次，以此类推...
最大的数出现了0次，但是可以发现，如果最大的数等于次大的数，不会影响结果
然后用小根堆记录每个数，然后最小的数出队n-1次，因为一共有n-1个最小的数，第二小的数出队n-2次，...，把每个数存下来就OK了，然后记得加一个最大的数，直接加上次大的数就可以了
C++代码
#include #include using namespace std; int main(){ int t; cin>>t; while(t--){ int n,x; cin>>n; int a[n+5]={0}; int m=n*(n-1)/2; priority_queue,greater> heap;//小根堆 for(int i=1;i<=m;i++){ cin>>x; heap.push(x); } vector ans; for(int i=n-1;i>0;i--){ int t=heap.top(),j=i; while(j--)heap.pop(); ans.push_back(t); } ans.push_back(ans.back());//加上最大的数 for(int i=0;i D. Strong Vertices
分析
a[i]-b[i]>=a[j]-b[j]，则i~j有一条边
令c[i]=a[i]-b[i]，即c[i]>=c[j]则表示i~j有一条边
所以找出数组c中最大的数，最大的数一定可以向其他的所有点连一条边，即为题中所说强顶点，找出最大的数有几个即可
C++代码
#include #include using namespace std; const int N=200010; int a[N],b[N],c[N]; void solve(){ int n,maxx=-2e9; cin>>n; for(int i=1;i<=n;i++)cin>>a[i]; for(int j=1;j<=n;j++)cin>>b[j]; for(int i=1;i<=n;i++){ c[i]=a[i]-b[i]; maxx=max(maxx,c[i]); } vector ans; for(int i=1;i<=n;i++){ if(c[i]==maxx)ans.push_back(i); } cout<>t; while(t--){ solve(); } return 0; } E. Power of Points
分析
每个点的fp就是以该点为一个端点与其他所有点组成的区间覆盖的点数之和
然后要挖掘性质了，举例子：1，2，5，7（有序序列）
每个点为端点与它本身都有一个区间覆盖的点数为1，所以先不算这个1
以2为一个端点，区间为[1,2],[2,5],[2,7]
点数之和为2+4+6=12
下一个数是5，以5为一个端点的区间为[1,5],[2,5],[5,7]
点数之和为5+4+3=12，与上式对比发现，2前面所有点覆盖的点数+3，5后面所有点覆盖的点数-3
观察一下这两个式子，发现每次以一个数a[i]为端点时，假设当前点与上一个点a[i-1]的差距为gap
则sum[i]=sum[i-1]+(i-2)*gap-(n-i)*gap;
C++代码
#include #include #include F. Sum and Product
分析
a[i]+a[j]=x,a[i]*a[j]=y
即a[i]*(x-a[i])=y，化简得a[i]^2-x*a[i]+y=0，即a^2-x*a+y=0
问题就变成了该方程组有几组解
delta=x^2-4*y
记录数组a中每个数的个数，用cnt记录
如果delta<0，则无解
否则有解，求出a1和a2
1、a1==a2，答案就是cnt[a1]*(cnt[a1]-1)/2
2、a1!=a2，答案就是cnt[a1]*cnt[a2]
C++代码
#include #include G. Counting Graphs
分析
将所有边按照权值进行从小到大排序
然后按顺序枚举所有边，每次找到当前边连接的两点a,b所在连通块中分别有多少个点cnt[a],cnt[b]
此时可以加的边数为cnt[a]*cnt[b]-1(减去a-b本身)
边的权值有S-w+1种情况，首先是[w+1,s]，其次还可以不加边，所以有s-w+1种情况
所以对于条边，对答案的贡献为(S-w+1)^(cnt[a]*cnt[b]-1)
枚举完每条边，就要将两个点合并到一个连通块中
C++代码
#include #include #define int long long using namespace std; const int N=200010,mod=998244353; int p[N],cnt[N]; int n,S; struct Node{ int u,v,w; bool operator<(const Node &W)const { return w>=1; } return res; } void solve(){ scanf("%d%d",&n,&S); for(int i=1;i<=n;i++)p[i]=i,cnt[i]=1;//并查集 idx=0; for(int i=1;i>u>>v>>w; edges[idx++]={u,v,w}; } sort(edges,edges+idx); int ans=1; for(int i=0;i