这场比赛的题目感觉还是不错的. 但是因为忘了一个公式d题没有A掉还是很可惜的.
乘着在家的时间多做些cf，到了学校就没有那么好的条件做了.
a. 要注意的是题目中要求输出的他可以出数的总数，一开始我以为是他可以出的数，然后就wa了两次.
b. 这题开始拿到时，还被吓了一下，后面推了下好像每个f（n） 都对应了一个确定的数，然后就知道了，先记录每个数n对应的f（n）为多少， 然后再算所有的情况.
因为求每个数的f（n）时相当于log的运算，所有对应的f（n）也不会很大， 然后知道有多少个数对应的是相同的，再用等差数列求和公式就可以得出.
#include <stdio.h> #include <string.h> #include <string> #include <iostream> using namespace std; int g[100100]; int mark[1001000]; int fuc(int s) { if(s==0) return 0; if(s%2==0) return fuc(s/2); else return fuc((s-1)/2)+1; } int main() { int n; scanf("%d",&n); for(int i=0;i<n;i++) { int tmp; scanf("%d",&tmp); mark[fuc(tmp)]++; } __int64 cnt=0; for(int i=0;i<1001000;i++) { if(mark[i]!=0) { cnt+=((__int64)(mark[i]-1)*mark[i])/2; } } printf("%I64d",cnt); return 0; }
c. 这题考的是读题， 我读了20多分钟的题才读懂， 写就用了几分钟。 这题意太坑爹了.
大致的题意是： 有一个楼梯，往上放方块，方块只能横着放（wi的地方接触）放在楼梯上或者其他的方块上， 还有一个要求就是每块方块只能放在第wi（他的宽）个台阶上。 然后在结合题目给的Note就可以知道了题目的意思了。 知道后就非常简单了,只要记录一下他前面方块的最高的高度.
#include <stdio.h> #include <string.h> #include <string> #include <iostream> using namespace std; __int64 h[100100]; int main() { int n; scanf("%d",&n); for(int i=1;i<=n;i++) { scanf("%I64d",&h[i]); } int m; scanf("%d",&m); __int64 mx=-1; for(int i=0;i<m;i++) { __int64 x,y; scanf("%I64d%I64d",&x,&y); __int64 tmp=max(mx,h[x]); printf("%I64d\n",tmp); mx=tmp+y; } return 0; }
d. 这题嘛，感觉就是考高中的排列组合公式。 会了其实也就很好做的。
#include <stdio.h> #include <string.h> #include <algorithm> #include <string> #include <iostream> using namespace std; typedef __int64 ll; struct node { int x,y; }g[1001000]; ll sum; int n; ll MOD; int cmp(node x,node y) { if(x.x!=y.x) return x.x<y.x; else return x.y<y.y; } void fuc(int s,int t) { if(t-s==1) return ; ll cnt=0; for(int i=s;i<t;i++) { if(i==t-1) { cnt++; break; } if(g[i].y==g[i+1].y) { i++; } cnt++; } ll tmp=t-s-cnt; ll ttmp=1; for(int i=1;i<=t-s;i++) { ll ti=i; if(i%2==0&&tmp!=0) { ti=i/2; tmp--; } ttmp=(ttmp*ti)%MOD; } sum=(sum*ttmp)%MOD; } int main() { sum=1; int cnt=0; scanf("%d",&n); for(int i=1;i<=n;i++) { int tmp; scanf("%d",&tmp); g[cnt].x=tmp; g[cnt++].y=i; } for(int i=1;i<=n;i++) { int tmp; scanf("%d",&tmp); g[cnt].x=tmp; g[cnt++].y=i; } scanf("%I64d",&MOD); sort(g,g+cnt,cmp); int tmp=g[0].x; int f=0; for(int i=1;i<=cnt;i++) { if(g[i].x!=tmp||i==cnt) { fuc(f,i); if(i==cnt) break; f=i; tmp=g[i].x; } } printf("%I64d",sum); return 0; }