cf1490 这。。。这就是div3嘛
A:Dense array 对每个间隔统计即可
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 per(){ int n;cin >>n; for (int i=1 ;i<=n;++i){ cin >>in[i]; } int ans=0 ; for (int i=2 ;i<=n;++i){ int ma=max(in[i-1 ],in[i]); int mi=min(in[i-1 ],in[i]); int cnt=0 ; while (mi*2 <ma){ cnt++; mi*=2 ; } ans+=cnt; } cout <<ans<<endl ; }
B:Balanced Remainders 从0到1到2,再到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 31 32 33 34 35 36 37 38 39 per(){ int n;cin >>n; int tmp; int n0=0 ,n1=0 ,n2=0 ; for (int i=1 ;i<=n;++i){ cin >>tmp; if (tmp%3 ==1 )n1++; else if (tmp%3 ==0 )n0++; else n2++; } int num=n/3 ; int ans=0 ; if (n0>num){ n1+=n0-num; ans+=n0-num; n0=num; } if (n1>num){ n2+=n1-num; ans+=n1-num; n1=num; } if (n2>num){ n0+=n2-num; ans+=n2-num; n2=num; } if (n0>num){ n1+=n0-num; ans+=n0-num; n0=num; } if (n1>num){ n2+=n1-num; ans+=n1-num; n1=num; } cout <<ans<<endl ; }
C:Sum of Cubes 范围很小,把1-10000打表,同时计入map中,然后遍历之,查$n-i^3$是否在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 const int maxn=1005 ;ll in[12000 ]; int main () { std ::ios::sync_with_stdio(false );std ::cin .tie(0 ); map <ll,int > ma; for (ll i=1 ;i<=10000 ;++i){ ma[i*i*i]=1 ; in[i]=i*i*i; } per(){ ll n;cin >>n; int tag=0 ; for (ll i=1 ;i<=10000 ;++i){ if (n<=in[i])break ; if (ma[n-in[i]]==1 ){ tag=1 ;break ; } } if (tag){ cout <<"YES" <<endl ; }else cout <<"NO" <<endl ; } }
建树,建st表然后递归即可
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 int f[maxn][maxn],in[maxn];void STinit (int n) { for (int i=1 ;i<=n;++i){ f[i][0 ]=in[i]; } int t=log (n)/log (2 )+1 ; for (int j=1 ;j<t;j++){ for (int i=1 ;i<=n-(1 <<j)+1 ;i++ ){ f[i][j]=max(f[i][j-1 ],f[i+(1 <<(j-1 ))][j-1 ]); } } } int STQ (int l,int r) { int k=log (r-l+1 )/log (2 ); return max(f[l][k],f[r-(1 <<k)+1 ][k]); } int ans[maxn];void dfs (map <int ,int >&ma,int l,int r,int lv) { if (l==r){ ans[r]=lv; return ; } int nr=ma[STQ(l,r)]; ans[nr]=lv; if (l<=nr-1 )dfs(ma,l,nr-1 ,lv+1 ); if (r>=nr+1 )dfs(ma,nr+1 ,r,lv+1 ); return ; } int main () { std ::ios::sync_with_stdio(false );std ::cin .tie(0 ); per(){ int n;cin >>n; map <int ,int > ma; for (int i=1 ;i<=n;++i){ cin >>in[i]; ma[in[i]]=i; } STinit(n); dfs(ma,1 ,n,0 ); for (int i=1 ;i<=n;++i){ cout <<ans[i]<<' ' ; }cout <<endl ; } return 0 ; }
E:Accidental Victory input时将index和数字关联起来,然后处理数字。将其从小到大排序,求前缀和,然后遍历,如果前面加起来都没这个数大,此处中断,找到最后的一个中断位置即可,其后是能赢的。注意输出时要排序。
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 struct ui { ll val;int pos;bool operator <(const ui b)const {return this ->val<b.val;}};const int maxn=2e5 +10 ;ui in[maxn]; ll d[maxn]; int main () { std ::ios::sync_with_stdio(false );std ::cin .tie(0 ); per(){ int n;cin >>n; map <ll,int > ma; for (int i=1 ;i<=n;++i){ cin >>in[i].val; in[i].pos=i; } sort(in+1 ,in+1 +n); d[0 ]=0 ;int lp=-1 ; for (int i=1 ;i<=n;++i){ d[i]=d[i-1 ]+in[i].val; if (d[i-1 ]<in[i].val)lp=i; } vector <int > ans; for (int i=lp;i<=n;++i){ ans.push_back(in[i].pos); } sort(ans.begin(),ans.end()); cout <<ans.size()<<endl ; for (auto i:ans)cout <<i<<' ' ; cout <<endl ; } }
F:Equalize the Array 你不可能将少的变多,但可以将5次的变4次,所以排序,前缀和。 遍历,可能的答案是次数大于等于当前次数的数字个数乘当前次数。求最大值,然后用n减即可。 (排序范围搞错,wa#2*5)
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 struct ui {int times;int num;bool operator <(const ui b)const {return this ->times>b.times;}};const int maxn=2e5 +1000 ;ui in[maxn]; int main () { std ::ios::sync_with_stdio(false );std ::cin .tie(0 ); per(){ int n;cin >>n; int tmp; map <int ,int > ma; for (int i=1 ;i<=n;++i){ cin >>tmp; ma[tmp]++; } int tot=0 ; int sz=ma.size(); map <int ,int > mb; for (auto i:ma){ mb[i.second]++; } for (auto i:mb){ in[++tot]={i.first,i.second}; } sort(in+1 ,in+1 +tot); int ans=-1 ; int now=0 ; for (int i=1 ;i<=tot;++i){ now+=in[i].num; ans=max(ans,now*in[i].times); } cout <<n-ans<<endl ; } }