Codeforces Round #673 (Div. 1)

A.k-Amazing Numbers http://codeforces.com/contest/1416/problem/A 给定一个长为$n$的数组a[]，定义“k-Amazing Number”是最小的、满足在数组a[]中的任意连续k个数字中出现至少一次的数字。 现在给定数组a[]，依次求"1…n-Amazing Number"，不存在则输出-1。 （多组数据）

#include<stdio.h> #include<map> #include<queue> #include<iostream> #include<algorithm> #include<vector> const long long MOD=1000000007; using namespace std; int t,n; long long a[300005],b[300005]; long long pre[300005],ans[300005]; int main() { scanf("%d",&t); while(t--) { scanf("%d",&n); for(int i=1;i<=n;i++)ans[i]=1e9,pre[i]=0,b[i]=0; for(int i=1;i<=n;i++) scanf("%d",&a[i]); for(int i=1;i<=n;i++) { b[a[i]]=max(b[a[i]],i-pre[a[i]]); pre[a[i]]=i; } for(int i=1;i<=n;i++) { b[i]=max(b[i],(n+1)-pre[i]); } for(int i=1;i<=n;i++)if(b[i]<=n) { if(i<ans[b[i]])ans[b[i]]=i; } for(int i=2;i<=n;i++) if(ans[i-1]<ans[i]) ans[i]=ans[i-1]; for(int i=1;i<=n;i++) { if(ans[i]>n)printf("-1 ");else printf("%d ",ans[i]); } printf("\n"); } return 0; }

B.Make Them Equal

http://codeforces.com/contest/1416/problem/B 题目给定一个长为n的数组a[]，保证$a_i\ge i$ 题目允许的操作是选取$i,j$使得$a_i=a_i-i\ast x,a_j=a_j+i\ast x$，其中x可以为0或任意正数。 要求每次操作过后a[]中任何一个元素不得小于0。问能否在3n次操作内使得数组a[]中每个元素相等。可以则输出操作步骤数和步骤，不能则输出-1。

#include<stdio.h> #include<map> #include<queue> #include<iostream> #include<algorithm> #include<vector> const long long MOD=1000000007; using namespace std; long long a[10005]; long long op[233333][3],opcnt; int main() { int t; int n; scanf("%d",&t); while(t--) { scanf("%d",&n); long long su=0; for(int i=1;i<=n;i++) { scanf("%lld",&a[i]); su+=a[i]; } if(su%n) { printf("-1\n");continue; }else { opcnt=0; for(int i=2;i<=n;i++) { int temp=(i-(a[i]%i))%i; opcnt++; op[opcnt][0]=1; op[opcnt][1]=i; op[opcnt][2]=temp; a[i]+=temp;a[1]-=temp; opcnt++; op[opcnt][0]=i; op[opcnt][1]=1; op[opcnt][2]=a[i]/i; a[1]+=a[i];a[i]=0; } for(int i=2;i<=n;i++) { opcnt++; op[opcnt][0]=1; op[opcnt][1]=i; op[opcnt][2]=su/n; } printf("%d\n",opcnt); for(int i=1;i<=opcnt;i++) printf("%lld %lld %lld\n",op[i][0],op[i][1],op[i][2]); } } return 0; }

C. XOR Inverse http://codeforces.com/contest/1416/problem/C 给定一个长为n的数组a[]，若存在$i<j$且$a_i>a_j$则算作一个逆序对，选取一个$x$，对所有$a_i$使得$a_i=a_{i}xorx$，找出能使逆序对数量最少的所有$x$中最小的一个并输出。

#include<bits/stdc++.h> using namespace std; int n; long long *a; long long ans,tz; long long su[2][64]; void calc(long long *a,int len,int now) { if(!len){ free(a);return; } if(now<0){ free(a);return; } long long temp[2][2]; for(int i=0;i<2;i++) for(int j=0;j<2;j++) temp[i][j]=0; for(int i=0;i<len;i++) { long long tz=a[i]>>now; temp[0][tz%2]+=temp[1][(tz+1)%2]; temp[1][tz%2]++; } su[1][now]+=temp[0][0];su[0][now]+=temp[0][1]; long long *b,*c; b=(long long*)malloc(temp[1][0]*sizeof(long long)); c=(long long*)malloc(temp[1][1]*sizeof(long long)); int cot[2];cot[0]=cot[1]=0; for(int i=0;i<len;i++) { long long tz=a[i]>>now; if(tz%2) { c[cot[1]++]=a[i]; }else { b[cot[0]++]=a[i]; } } free(a); calc(b,cot[0],now-1); calc(c,cot[1],now-1); } int main() { scanf("%d",&n); a=(long long*)malloc(n*sizeof(long long)); for(int i=0;i<n;i++)scanf("%lld",&a[i]); calc(a,n,35); ans=0; for(int i=0;i<35;i++) { tz+=min(su[1][i],su[0][i]); if(su[1][i]>su[0][i])ans+=((long long)1<<i); } printf("%lld %lld",tz,ans); }