锐客网

  1. 首页 > it技术 > >

CodeForces CF #499 Div.2 赛后补题

cf

非常痛苦，在做第一题的时候有一点小问题，结果居然一开始提交过了。。。闭着眼睛锁了题目就去往后做了，结果被hack了，流下痛苦的泪水。赛时真是好水的数据啊。。。
A.Stage
这就是一道签到题。题意是给你一串长度为N的字符串，要求选取M个组装成一个新的字符串，并且这个新的字符串单调增（‘b’>‘a’）且字典上相邻的字母不能相邻（‘a’后面不能是’b’），求字符串的和最小值，不存在就返回-1。数据规模也不大，模拟一下就行了：记录还需保存k个字母，从a一直推到z；用一个hash记录哪些字母可用。推完以后如果k！=0那么说明不存在，否则返回ans。

int n,k; int exist[30]; memset(exist,0,sizeof(exist)); string str; cin>>n>>k>>str; for(int i=0; i< str.size(); i++)exist[str[i]-'a']=1; int ans=0; int pnt=0; while(k&&pnt<26) { if(exist[pnt]==1)ans+=pnt+1,pnt++,k--; pnt++; } if(k>=1)cout<<"-1"<< endl; else cout<< ans; return 0;

B.Planning the expedition
题意是有N个人，M个食物，每种食物有一个编号。每个人只能吃一种编号的食物，且每天消耗一个食物，请问这帮人能活多久。
看到这道题，觉得正面做比较棘手，马上想到把求解问题变成可行性检验问题。想到可行性检验就想到二分。
然后我们会发现，就算是食物编号全部是一样的，这帮人也至多活n/m天，然后n和m的取值范围都是[1,100]。得，不二分了，闭着眼睛从n/m推到1。
接下来的问题就是怎么检验了。那还不简单吗，设每个人要活k天，那么对于编号为i的食物，记录它的个数是wi，那么i食物可以给wi/k个人提供食物。对i∈[1,100]求wi/kd 和，可以检验是否大于等于n。若是，那么说明k天是可行的。
int n,m,a[105]; memset(a,0,sizeof(a)); cin>>n>>m; for(int i=1; i<=m; i++) { int temp; cin>>temp; a[temp]++; } int T=m/n; while(T) { int need=n; for(int i=1; i<=100; i++)need-=a[i]/T; if(need<=0)break; T-- ; } cout << T << endl; return 0;

要想优化打个二分就可以了
C. Fly
C就是一道思维题。给你i个星球，每个星球有一个起飞油效和一个降落油效，在一个星球上起飞或降落需要消耗（double）（飞机含油总质量）/（油效），这里的总质量表示在花掉这些油之前的质量。飞机本身质量为m，让你求从1起飞，遍历每个星球，再回到1需要的油最少是多少。如果不存在，那么返回-1。
那我就纳闷了，你说我一个能带无限油的小飞机，怎么就可能回不来呢？我们分析数据，输入的只有星球数n，飞机质量m，油效ai（i=1，2，3…）。那么如果有问题，那么只能出在ai上。再进一步想，如果存在某一个ai为1，那么就意味着，飞机需要等同于自身含油质量的油来完成操作，那么这样是不可能成立的。
显然，飞机在1上落地是最好的结果是油全部用完，那么这就意味着我们知道飞机的末状态，我们希望去反推它的初状态。
然后我们进一步分析一个有关耗油的方程。假设完成一次操作后剩下w1的油（已知），设进行操作前有x的油（这是未知数），然后操作前就有w2的油（未知），油效为k（已知）。两个方程求两个未知数，讲究。
w1+x=w2 （1）
x*k=w2 （2）
联立解得
w2=[k/(k-1)]*w1
哇塞，这居然是个按比例推的式子。。。得，不用管先后了，一通乘法，求出结果。
int n,m; double lift[1005]; double land[1005]; cin>>n>>m; double fuel=m; bool flag=0; for(int i=1; i<=n; i++) { cin>>lift[i]; if(lift[i]==1) { flag=1; break; } } for(int i=1; i<=n; i++) { cin>>land[i]; if(land[i]==1) { flag=1; break; } } if(flag)cout << "-1" << endl; else { for(int i=1; i<=n; i++)fuel*=(lift[i]/(lift[i]-1))*(land[i]/(land[i]-1)); fuel=fuel-double(m); printf("%.10lf",fuel); }

BTW：做的时候没怎么动脑子，把起飞后降落的油效分开算了，其实没必要。我还因为这个WA了两次。。。所以说良好的编程习惯（能动脑别动手）很重要。
D.ROCKET
这题没看懂题目，容我会了再来。
E.border
纯数论题。给你n个数，每种数可以用任意次。选取你之前的那些数组成多少种不超过k的数（mod k）。
看到第一眼毫无头绪，分析一下数据规模，OK，100000。那么可能的算法复杂度最多只有n2了。但是这里用n2，只能讨论两种相加的情况，绝不可能算出来的。log也不太像这种题目该出现的复杂度，所以我猜测是O(N)甚至是O(1)。
那么我们把问题简化，假设k是10。那么显然，给出1的时候，1是可以全覆盖的。那么给出2的时候，偶数是可以全覆盖的。给出3的时候，3n可以全覆盖，但是因为k是10的原因，所以试一下也可以全覆盖。以此类推。
这个时候我们不再考虑k等于10，我们发现，不管k取什么值，如果给出1，那么同样是全覆盖。给出2，那么在k & 1 = = 1 k\&1==1 k&1==1 时可以全覆盖，否则不行。给出3，在k = = 3 x k==3x k==3x 时只能覆盖3x，否则可以全覆盖。如果给出2和3，总是全覆盖。
把给出的数以及k放在左边，可以覆盖的数放在右边。。。。。
发现。。。。。
这不就是GCD吗。。。
【CodeForces CF #499 Div.2 赛后补题】那就完事了呗
int gcd(int a,int b) { return b==0?a:gcd(b,a%b); }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*10+ch-'0'; ch=getchar(); } return x*f; }int n,k,aa; int main() { n=read(); k=read(); aa=k; for(int i=0 ; i

    推荐阅读


    上一篇：多态和对象的转型

    下一篇：蛇精，蜈蚣