CF 1355

CF1355

A

题意：给一个数A，取它的所有位中最小的（记为minA）和最大的(记为maxA)，A = A + minA * maxA，如此往复K次，求所得到的值。
题解：1000次以内必然出现minA * maxA = 0，然后就不变了。
P.S. 附了一组数据，试试……

#include
#include
#include
#include
#include
#include
using namespace std;
long long f[20];
int main()
{int i,T,j;long long maxa,mina,n,k,t;f[0]=1;for(i=1;i<=18;i++)f[i]=f[i-1]*(long long)10;scanf("%d",&T);while(T){T--;scanf("%lld%lld",&n,&k);for(j=1;j<k;j++){maxa=n%10;mina=n%10;for(i=1;i<=18;i++){if(n/f[i]==0)break; t=(n/f[i])%10;maxa=max(t,maxa);mina=min(t,mina);}n=n+maxa*mina;if(mina==0)break;}printf("%lld\n",n);}return 0;
}
/*
23
1 4
487 1
487 2
487 3
487 4
487 5
487 6
487 7 
487 8 
487 9 
487 11 
487 12
487 13
487 14
487 16
487 17
487 18
487 19
487 20
487 21
487 10000000000
*/ 

B

题意：N个人，每个人有一个经验值E_i，如果选择某个人加入队伍，必须满足他和至少E_i个人组成一组，要求组成尽可能多的组。
题解：贪心

#include
#include
#include
#include
#include
#include
using namespace std;
const int N=2e5+10;
int cnt[N];
int main()
{int T,n,i,ans,tmp,x;scanf("%d",&T);while(T){T--;ans=0;tmp=0;scanf("%d",&n);for(i=1;i<=n;i++)cnt[i]=0;for(i=1;i<=n;i++){scanf("%d",&x);cnt[x]++;}for(i=1;i<=n;i++){tmp+=cnt[i];ans+=cnt[i]/i;tmp=tmp%i;}printf("%d\n",ans);}return 0;
}

C

题意：给定A，B，C，D，统计（x, y, z）三元组的个数，满足A$\le$x$\le$B$\le$y$\le$C$\le$z$\le$D
题解：枚举z-x，统计每个长度z-x的个数。统计B$\le$z-x$\le$C的部分即为所求。

#include
#include
#include
#include
#include
#include
using namespace std;
const int N=5e5+10;
long long f[N];
int main()
{int a,b,c,d,i,l,r;long long ans=0;scanf("%d%d%d%d",&a,&b,&c,&d);for(i=c-b;i<=d-a;i++){l=max(a,c-i);r=min(b,d-i);f[i]=r-l+1;}for(i=1;i<=c;i++)f[i]+=f[i-1];for(i=b;i<=c;i++)ans=ans+f[i-1];printf("%lld",ans);return 0;
}

D

题意：给定N，S，要求构造一个长度为N的序列，总和为S，并且存在K（0 $\le$ K $\le$ S），使得任取元素，和不能为K。
题解：
如果S $\ge$ 2N，则可以；否则不行

#include
#include
#include
#include
#include
#include
using namespace std;
int main()
{int n,s,i;scanf("%d%d",&n,&s);if(s/n>=2){printf("YES\n");for(i=1;i<=s%n;i++)printf("%d ",s/n+1);for(i=s%n+1;i<=n;i++)printf("%d ",s/n);printf("\n1\n");}elseprintf("NO\n");return 0;
}

E

题意：给一些高度的塔，进行以下操作使得所有的塔高度统一：

1. 某座塔高度+1，花费a
2. 某座塔高度-1，花费b
3. 把某座塔高度+1，另一座塔高度-1，花费m

题解：三分+贪心
考场WA：爆int了……
以及，CF不要用lld！！！

#include
#include
#include
#include
#include
#include
using namespace std;
const int N=1e5+10;
long long a[N];
int n;
long long A,B,M;
long long get_ans(long long hi)
{long long ans=0,tmp=0,now;int i;for(i=1;i<=n;i++)if(a[i]>hi){tmp+=a[i]-hi;ans+=B*(a[i]-hi);}for(i=1;i<=n;i++){if(a[i]<hi){if(A+B<=M)ans+=A*(hi-a[i]);else{now=min(tmp,hi-a[i]);ans+=A*(hi-a[i]-now)+(M-B)*now;tmp-=now;}}}return ans;
}
int main()
{int i;long long l,r=0,p1,p2,mid1,mid2,mid;//注意l,r的初始化 !!!scanf("%d%lld%lld%lld",&n,&A,&B,&M);for(i=1;i<=n;i++){cin>>a[i];r=max(r,a[i]); }l=0;while(r-l>1){mid=(r+l)>>1;mid1=(mid+l)>>1;mid2=(r+mid)>>1;p1=get_ans(mid1);p2=get_ans(mid2);if(p1>p2)l=mid1+1;elser=mid2;}p1=get_ans(l);p2=get_ans(r);cout<<min(p1,p2);//不要用lld!!! return 0;} 

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！