Codeforces Round #702 (Div. 3)
为什么CD比AB还简单啊(#`O′)
A. Dense Array
题意：给你一个数列，数列合法当且仅当相邻的数中较大值除以较小值小于等于(2)，你可以添加一些数，让数列合法，问最少添加多少数。
如果相邻位置合法就过，否则一定是不断除以(2)或不断乘(2)，判断一下不合法的位置哪边大然后加数即可。
#include<iostream>
#include<cstdio>
#include<cstring>
#define N 200005
using namespace std;
int read()
{
int x=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=(x<<3)+(x<<1)+(ch^48);ch=getchar();}
return x*f;
}
int T,n,a[N];
int main()
{
T=read();
while(T--)
{
n=read();
int ans=0;
for(int i=1;i<=n;i++)
{
a[i]=read();
if(i==1)continue;
if(a[i-1]>a[i]&&a[i]*2<a[i-1])
{
while(a[i-1]>a[i]*2)
{
a[i-1]=(a[i-1]+1)/2;
ans++;
}
}
if(a[i-1]<a[i]&&a[i-1]*2<a[i])
{
while(a[i-1]*2<a[i])
{
a[i-1]*=2;
ans++;
}
}
}
printf("%d
",ans);
}
return 0;
}
B. Balanced Remainders
题意：给(n)个数（(n)为(3)的倍数），每次可以让其中的某一个数加(1)，你要让(\%3)后余数为(0,1,2)的个数相等，问最少多少次操作。
大力分类讨论即可。
#include<iostream>
#include<cstdio>
#include<cstring>
#define N 200005
using namespace std;
int read()
{
int x=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=(x<<3)+(x<<1)+(ch^48);ch=getchar();}
return x*f;
}
int T,n,ave,a[3];
int main()
{
T=read();
while(T--)
{
n=read();ave=n/3;
a[0]=a[1]=a[2]=0;
for(int i=1;i<=n;i++)a[read()%3]++;
if(a[0]==ave&&a[1]==ave)
{
puts("0");
continue;
}
int sum=0;
if(a[0]==ave)
{
if(a[1]<a[2])printf("%d
",a[2]-a[1]);
else printf("%d
",(a[1]-a[2])/2);
continue;
}
if(a[1]==ave)
{
if(a[0]<a[2])printf("%d
",(a[2]-a[0])/2);
else printf("%d
",a[0]-a[2]);
continue;
}
if(a[2]==ave)
{
if(a[0]<a[1])printf("%d
",a[1]-a[0]);
else printf("%d
",(a[0]-a[1])/2);
continue;
}
if(a[0]>ave&&a[1]>ave)
{
printf("%d
",(a[0]-ave)*2+a[1]-ave);
continue;
}
if(a[0]>ave&&a[2]>ave)
{
printf("%d
",(a[2]-ave)*2+a[0]-ave);
continue;
}
if(a[1]>ave&&a[2]>ave)
{
printf("%d
",(a[1]-ave)*2+a[2]-ave);
continue;
}
if(a[0]>ave)
{
printf("%d
",(ave-a[2])*2+ave-a[1]);
continue;
}
if(a[1]>ave)
{
printf("%d
",(ave-a[0])*2+ave-a[2]);
continue;
}
if(a[2]>ave)
{
printf("%d
",(ave-a[1])*2+ave-a[0]);
continue;
}
}
return 0;
}
C. Sum of Cubes
题意：给一个(10^{12})以内的数，问能否拆成两个正整数的立方和的形式，多组数据。
由于(10000^3)就已经是(10^{12})了，因此(a)和(b)都不会大于(10000)，可以把(1-10000)内所有数的立方处理出来，然后枚举(a)，在这个数组里二分(b)即可。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define N 200005
#define int long long
#define MAXN 10000
using namespace std;
int read()
{
int x=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=(x<<3)+(x<<1)+(ch^48);ch=getchar();}
return x*f;
}
int T,n,a[N];
signed main()
{
T=read();
for(int i=1;i<=MAXN;i++)a[i]=i*i*i;
while(T--)
{
n=read();int ff=0;
for(int i=1;i<=MAXN;i++)
{
int x=n-a[i];
if(x<=0)break;
int pos=lower_bound(a+1,a+MAXN+1,x)-a;
//cout<<x<<" "<<pos<<endl;
if(a[pos]==x)
{
puts("YES");
ff=1;
break;
}
}
if(!ff)puts("NO");
}
}
D. Permutation Transformation
题意：给一个排列，每次找这个区间内的最大值的位置作为树根，其左边的区间和右边的区间分别建树，问最后每个点的深度。
按题意模拟即可，每次找出最大值之后递归建树，最后(dfs)一遍。
应该有(O(nlog^2 n))的做法，就是用线段树优化找最大值？不过(nleq100)，无所谓了。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<vector>
#define N 105
#define pb push_back
using namespace std;
int read()
{
int x=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=(x<<3)+(x<<1)+(ch^48);ch=getchar();}
return x*f;
}
int T,n,dep[N],a[N];
vector<int>G[N];
void divide(int l,int r,int fa)
{
//cout<<l<<" "<<r<<" "<<fa<<endl;
if(l>r)return;
int pos=l;
for(int i=l+1;i<=r;i++)if(a[i]>a[pos])pos=i;
G[fa].pb(pos);
divide(l,pos-1,pos);divide(pos+1,r,pos);
}
void dfs(int x)
{
int siz=G[x].size();
for(int i=0;i<siz;i++)
{
dep[G[x][i]]=dep[x]+1;
dfs(G[x][i]);
}
}
int main()
{
T=read();
while(T--)
{
n=read();
int pos=1;
for(int i=1;i<=n;i++)a[i]=read(),G[i].clear();
for(int i=2;i<=n;i++)if(a[i]>a[pos])pos=i;
divide(1,pos-1,pos);divide(pos+1,n,pos);
dep[pos]=0;dfs(pos);
for(int i=1;i<=n;i++)printf("%d ",dep[i]);
puts("");
}
return 0;
}
E. Accidental Victory
题意：(n)个人做游戏，第(i)个人最开始有(a_i)个金币，每次抽出两个人，把金币少的金币给金币多的，金币少的出局，如果一样的话就随机给一个人，问那些人可能留到最后。
按(a_i)值排序后，如果有一个位置(i)，(sum ^{i-1} _{j=1} a[j]<a[i])的话，那么所有在(i)之前的位置一定不合法，那么只需要找到最后一个这样的位置即可，前缀和优化一下。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<map>
#include<algorithm>
#define N 200005
#define mp make_pair
#define int long long
using namespace std;
int read()
{
int x=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=(x<<3)+(x<<1)+(ch^48);ch=getchar();}
return x*f;
}
int T,n,pre[N],a[N],b[N];
pair<int,int>A[N];
signed main()
{
T=read();
while(T--)
{
n=read();
for(int i=1;i<=n;i++)a[i]=read(),b[i]=0,A[i]=mp(a[i],i);
sort(a+1,a+1+n);sort(A+1,A+1+n);
for(int i=1;i<=n;i++)pre[i]=pre[i-1]+a[i];
int pos=0;
for(int i=n;i>=1;i--)
{
if(a[i]>pre[i-1])
{
pos=i;
break;
}
}
for(int i=pos;i<=n;i++)b[A[i].second]=1;
int ans=0;
for(int i=1;i<=n;i++)if(b[i])ans++;
printf("%d
",ans);
for(int i=1;i<=n;i++)if(b[i])printf("%d ",i);
puts("");
}
}
F. Equalize the Array
题意：给一些数，你要删掉一些数使得剩下的数出现次数相同，问最少删几个。
一个比较显然的思路就是枚举剩下的数每个出现了几次。
假设我们考虑最终结果是每个数出现了(i)次，那么出现次数小于(i)的一定都被删了，大于(i)的一定都变成了(i)个，设(pre_i)表示出现次数小于等于(i)的数的个数，(sum_i)表示出现次数小于等于(i)的数的种数，那么剩下的数每个出现(i)次的答案数即为：
[pre[i-1]+(n-pre[i-1])-(sum[n]-sum[i-1])*i
]
前边是计算直接删掉的，后边是用剩下的个数减去要保留的个数。
用(map)预处理一下(pre)和(sum)后枚举(i)即可。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<map>
#define N 200005
using namespace std;
int read()
{
int x=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=(x<<3)+(x<<1)+(ch^48);ch=getchar();}
return x*f;
}
int T,n,a[N],pre[N],sum[N];
map<int,int>mp;
int main()
{
T=read();
while(T--)
{
n=read();
for(int i=1;i<=n;i++)a[i]=read(),mp[a[i]]++,pre[i]=sum[i]=0;
for(int i=1;i<=n;i++)
{
if(mp[a[i]])
{
pre[mp[a[i]]]++;
sum[mp[a[i]]]++;
mp[a[i]]=0;
}
}
//for(int i=1;i<=n;i++)printf("######%d %d
",sum[i],pre[i]);
for(int i=1;i<=n;i++)pre[i]=pre[i-1]+pre[i]*i,sum[i]+=sum[i-1];
int ans=n;
for(int i=0;i<=n;i++)
{
//cout<<"!!!!"<<sum[i]<<" "<<pre[i]<<endl;
ans=min(ans,pre[i-1]+(n-pre[i-1])-(sum[n]-sum[i-1])*i);
//cout<<i<<" "<<pre[i-1]+(n-pre[i-1])-(sum[n]-sum[i-1])*i<<endl;
}
printf("%d
",ans);
}
}
G. Old Floppy Drive
题意：有一个环，每个位置上有一个数，计数器最开始停在第一个数上，每走到一个新位置上计数器就会加上这个位置上的数，最后一个位置再走一步就是第一个位置，如果计数器的数大于了给定的(x)就会停下，问会走多少步，或者永远也走不完，每次回答一个给定的(x)的答案。
把询问离线处理，考虑走的过程，实际上在走这么多步之前可以停下的数是一段区间，设走一圈的权值和为(k)，由于所有询问都是正数，那么当(kleq0)时，如果第一圈停不下了，那么之后也一定不行，因此直接处理一下即可。
当(k>0)时，考虑我们这个(x)很大的时候，一定是走很多圈之后在停下来，设前缀和最大值为(maxn),可以发现，如果有一个数(y(y>maxn))满足(xequiv y(mod k))，那么(x)和(y)走到的位置是一样的，只不过多走了几圈而已，那么我们考虑找到第一个比(maxn)大的满足条件的(y)，我们发现这个(y)一定能在两圈之内走完，先算完被减掉的值，排序后直接指针维护即可。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<map>
#define N 200005
#define mp make_pair
#define int long long
using namespace std;
int read()
{
int x=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=(x<<3)+(x<<1)+(ch^48);ch=getchar();}
return x*f;
}
int T,n,m,a[N],b[N],ans[N],pre[N],tag[N];
pair<int,int>B[N];
signed main()
{
T=read();
while(T--)
{
n=read();m=read();
for(int i=1;i<=n;i++)a[i]=read();
for(int i=1;i<=m;i++)b[i]=read(),B[i]=mp(b[i],i),ans[i]=-1,tag[i]=0;
sort(b+1,b+1+m);sort(B+1,B+1+m);
int minn=1e15,maxn=-1e15,now=0,pos=1;
for(int i=1;i<=n;i++)
{
now+=a[i];
pre[i]=now;
if(minn>now)minn=now;
if(maxn<now)maxn=now;
}
if(now<=0)
{
now=0;
for(int i=1;i<=n;i++)
{
now+=a[i];
while(now>=b[pos]&&pos<=m)ans[B[pos].second]=i,pos++;
}
for(int i=1;i<=m;i++)
{
if(ans[i]!=-1)printf("%lld ",ans[i]+tag[i]-1);
else printf("-1 ");
}
continue;
}
for(int i=1;i<=m;i++)
{
if(b[i]>=maxn)
{
int xx=b[i];
b[i]=(b[i]-maxn)%now+maxn;
tag[B[i].second]=((xx-b[i])/now)*n;
B[i]=mp(b[i],B[i].second);
}
}
sort(b+1,b+1+m);sort(B+1,B+1+m);
now=0;
//cout<<"!!"<<b[1]<<endl;
for(int i=1;i<=n;i++)
{
now+=a[i];
while(now>=b[pos]&&pos<=m)ans[B[pos].second]=i,pos++;
}
for(int i=1;i<=n;i++)
{
now+=a[i];
while(now>=b[pos]&&pos<=m)ans[B[pos].second]=i+n,pos++;
}
for(int i=1;i<=m;i++)
{
if(ans[i]!=-1)printf("%lld ",ans[i]+tag[i]-1);
else printf("-1 ");
}
puts("");
}
}
/*
1
2 1
10000 -5005
100000000
*/