题面：https://codeforces.com/gym/101775
- A. Chat Group
此题的题意很简单：就是给一个N和K让你计算(C(N,K)+C(N,K+1),+C(N,K+2)+...+C(N,N-1)+C(N,N))%1e9+7. 一种思路是写一个C(N,K)的函数，从K一直遍历到N一个一个计算，共1e5次，
而每次计算又需要1e5次循环，所以时间复杂度为1e10，肯定会超时。还好我队友聪明，提供了一个公式，能够根据C(N,K)再乘上一个系数计算出C(N,K+1).很牛逼。
这个公式为：C(N,K)*(N-K)/(K+1) = C(N,K+1)
所以：我们可以得出一个结论：要计算的答案 = (2N - (C(N,0)+C(N,1)+....+C(N,K-1)))%1e9+7,
2N 可以用快速幂计算出来
(C(N,0)+C(N,1)+....+C(N,K-1)) 可以用公式递推，而公式中的除法需要改成乘以逆元，而1e9+7是一个质数就可以用费马小定理来求逆元，也就是用快速幂求逆元 = ksm(a,P-2)
#include <iostream> #include <cstring> using namespace std; typedef long long ll; const int maxn = 1e6+10; const ll mod = 1000000007; int T; ll N,K; ll ksm(ll a,ll b){ ll res = 1; while(b){ if(b&1) res = res*a%mod; a = a*a%mod; b>>=1; } return res; } ll solve(){ ll pre = 1,ck = 1; for(ll k = 0;k<=K-2;k++){ ck = ck*(N-k)%mod*ksm(k+1,mod-2)%mod; pre = (pre+ck)%mod; } return (ksm(2,N)-pre+mod)%mod; } int main(){ cin>>T; int kase = 0; while(T--){ cin>>N>>K; printf("Case #%d: %lld ",++kase,solve()); } return 0; }
- C. Traffic Light
这题比赛时没有想出来，是一道构造思维题。当等待过一个红灯过后，可以控制偏移量让之后过红绿灯的时候都是绿灯。说实话到现在还没怎么懂，再问问其他人再来补题解
#include <iostream> using namespace std; const int maxn = 1e6+10; int T,N; int tmp1,tmp2; int main(){ cin>>T; int kase = 0; while(T--){ cin>>N; int length = 0,mx = 0; for(int i = 0;i<N+1;i++) scanf("%d",&tmp1),length += tmp1; for(int i = 0;i<N;i++){ scanf("%d%d",&tmp1,&tmp2); mx = max(mx,tmp2); } printf("Case #%d: %.6f ",++kase,(double)(length+mx)); } return 0; }
- J. Straight Master
#include <iostream> #include <cstring> using namespace std; typedef long long ll; const int maxn = 1e6+10; int T,N; int a[maxn],b[maxn];//原数组，差分数组 bool judge(){ ll sum = 0; for(int i = 1;i<=N+1;i++){ if(b[i]>0) sum+=b[i]; if(i+3<=N+1 && b[i+3]<0) sum += b[i+3]; if(sum<0) return false; } return sum == 0; } int main(){ cin>>T; int kase = 0; while(T--){ memset(a,0,sizeof a);memset(b,0,sizeof b); cin>>N; for(int i = 1;i<=N;i++) scanf("%d",&a[i]); for(int i = 1;i<=N+1;i++) b[i] = a[i]-a[i-1]; if(judge()) printf("Case #%d: Yes ",++kase); else printf("Case #%d: No ",++kase); } return 0; }
- K. Downgrade
#include <iostream> #include <cstring> using namespace std; typedef long long ll; const int maxn = 1e6+10; const ll mod = 1000000007; ll T,A,B,N; int a[maxn]; ll pre[maxn]; int main(){ cin>>T; int kase = 0; while(T--){ cin>>A>>B>>N; for(int i = 1;i<=A;i++) scanf("%d",&a[i]); for(int i = 1;i<=A;i++) pre[i] = pre[i-1]+a[i]; int total = A; while(N--){ int t = lower_bound(pre+1,pre+1+total,A)-pre; B = A-pre[t-1]; if(A == t) break; A = t; } printf("Case #%d: %lld-%lld ",++kase,A,B); } return 0; }
- L. SOS
#include <iostream> #include <cstring> using namespace std; typedef long long ll; const int maxn = 1e6+10; const ll mod = 1000000007; int T,N; int main(){ cin>>T; int kase = 0; while(T--){ printf("Case #%d: ",++kase); cin>>N; if(N<7) puts("Draw"); else if(N%2 == 1) puts("Panda"); else if(N%2 == 0 && N>=16) puts("Sheep"); else puts("Draw"); } return 0; }
- M. World Cup
#include <iostream> #include <cstring> using namespace std; typedef long long ll; const int maxn = 1e6+10; const ll mod = 1000000007; int T,Q,x; int money[10],p[100]; void init(){ for(int i = 1;i<=48;i++) p[i] = money[1]; for(int i = 49;i<=56;i++) p[i] = money[2]; for(int i = 57;i<=60;i++) p[i] = money[3]; for(int i = 61;i<=62;i++) p[i] = money[4]; for(int i = 63;i<=63;i++) p[i] = money[5]; } int main(){ cin>>T; int kase = 0; while(T--){ for(int i = 1;i<=5;i++) cin>>money[i]; init(); cin>>Q; ll y = 0; while(Q--){ scanf("%d",&x); y += p[x]; } printf("Case #%d: %lld ",++kase,y*10000); } return 0; }