阅读量:0
A. Array Coloring
分析
元素和为偶数才可以让两种颜色的元素的奇偶性相同(奇+奇=偶，偶+偶=偶)
奇=奇+偶
C++代码
#include<iostream> using namespace std; int main(){ int t; cin>>t; while(t--){ int n,sum=0; cin>>n; for(int i=0;i<n;i++){ int x; cin>>x; sum+=x; } if(sum&1)puts("NO"); else puts("YES"); } return 0; } B. Maximum Rounding
分析
从大到小枚举数的每一位，如果当前位置可以进位，则一直往前进位直到不能进位，然后break，每次记录当前在哪里进位的，它后面的所有数都变成0，前面的不变
C++代码
#include<iostream> 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<s.size();i++){ if(s[i]>='5'){ int j=i; while(j>=1&&s[j]>='5'){//当前位置可以进位，则一直往前进，直到不能进位 s[j-1]++; flag=j; j--; } break; } } if(flag==1)cout<<s[0];//最后一次进位在最高位 for(int i=1;i<s.size();i++){ if(i>=flag)cout<<0;//最后一次进位的位置往后的数字全都变成0 else cout<<s[i];//否则就直接输出 } cout<<endl; } return 0; }C. Assembly via Minimums
分析
由题意，最小的数在序列中一定出现了n-1次，第二小的数出现n-2次，以此类推...
最大的数出现了0次，但是可以发现，如果最大的数等于次大的数，不会影响结果
然后用小根堆记录每个数，然后最小的数出队n-1次，因为一共有n-1个最小的数，第二小的数出队n-2次，...，把每个数存下来就OK了，然后记得加一个最大的数，直接加上次大的数就可以了
C++代码
#include<iostream> #include<queue> 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<int,vector<int>,greater<int>> heap;//小根堆 for(int i=1;i<=m;i++){ cin>>x; heap.push(x); } vector<int> 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<ans.size();i++)cout<<ans[i]<<" "; cout<<endl; } return 0; }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<iostream> #include<vector> 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<int> ans; for(int i=1;i<=n;i++){ if(c[i]==maxx)ans.push_back(i); } cout<<ans.size()<<endl; for(int i=0;i<ans.size();i++)cout<<ans[i]<<" "; cout<<endl; } int main(){ int t; cin>>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<iostream> #include<algorithm> #include<map> using namespace std; const int N=200010; typedef long long LL; int a[N],b[N]; int n; void solve(){ cin>>n; for(int i=1;i<=n;i++)cin>>a[i],b[i]=a[i];//b[i]把原始的a[i]存起来 sort(a+1,a+1+n);//从小到大排序 LL sum=1;//sum初始化为1，每个数为端点首先覆盖自己这个点 for(int i=2;i<=n;i++)sum+=a[i]-a[1]+1;//先把第一个数为一个端点的sum算出来 map<int,LL> mp;//map记录答案 mp[a[1]]=sum; for(int i=2;i<=n;i++){ int gap=a[i]-a[i-1]; sum=sum+(LL)(i-2)*gap-(LL)(n-i)*gap; mp[a[i]]=sum; } for(int i=1;i<=n;i++)cout<<mp[b[i]]<<" "; cout<<endl; } int main(){ int t; cin>>t; while(t--){ solve(); } return 0; }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<iostream> #include<map> #include<vector> #include<cmath> using namespace std; const int N=200010; typedef long long LL; LL a[N]; void solve(){ map<LL,LL> cnt; int n,q; cin>>n; for(int i=1;i<=n;i++){ int x; cin>>x; cnt[x]++; } cin>>q; while(q--){ LL x,y; cin>>x>>y; LL delta=x*x-4*y; if(delta<0){ cout<<0<<" "; continue; } LL s=sqrtl(delta); LL x1=(x-s)/2,x2=(x+s)/2; if(x1+x2!=x||x1*x2!=y){ cout<<0<<" "; continue; } if(x1==x2)cout<<cnt[x1]*(cnt[x1]-1)/2<<" "; else cout<<cnt[x1]*cnt[x2]<<" "; } cout<<endl; } int main(){ int t; cin>>t; while(t--){ solve(); } return 0; }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<iostream> #include<algorithm> #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<W.w;//按照w的值进行排序 } }edges[N]; int idx; int find(int x){ if(p[x]!=x)p[x]=find(p[x]); return p[x]; } int qmi(int a,int k,int p){//快速幂求a^k%p的值 int res=1; while(k){ if(k&1)res=res*a%p; a=a*a%p; k>>=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<n;i++){ int u,v,w; cin>>u>>v>>w; edges[idx++]={u,v,w}; } sort(edges,edges+idx); int ans=1; for(int i=0;i<idx;i++){ int a=edges[i].u,b=edges[i].v,w=edges[i].w; a=find(a),b=find(b); ans=ans*qmi(S-w+1,cnt[a]*cnt[b]-1,mod)%mod; //将a,b所在连通块合并 p[a]=b,cnt[b]+=cnt[a]; } printf("%d\n",ans); } signed main(){ int t; scanf("%d",&t); while(t--){ solve(); } return 0; }