2017 EC-Final 部分题解——————HPU ICPC国庆训练2

我会带着你远行 2023-06-02 10:58 42阅读 0赞

### 目录，点击即可跳转到相应题解 ###

*  \[A. Chat Group\](https://codeforces.com/gym/101775/problem/A)
 *  \[C. Traffic Light\](https://codeforces.com/gym/101775/problem/C)
 *  \[L. SOS\](https://codeforces.com/gym/101775/problem/L)

题目链接在CF上的

# [A. Chat Group][] #

刚开始想的时候想错了，一直想打出来 C n k C\_n^k Cnk到 C n n C\_n^n Cnn的表，然后把他们加起来  
后来想到，从 C n k C\_n^k Cnk到 C n k + 1 C\_n^\{k+1\} Cnk\+1就是 C n k ∗ ( n − k + 1 ) / ( k + 1 ) C\_n^k \*(n-k+1)/(k+1) Cnk∗(n−k\+1)/(k\+1)  
所以直接递推出来了，不过要注意溢出

#include<bits/stdc++.h>
    using namespace std;
    typedef long long ll;
    const ll MOD = 1000000007;
    
    ll pow_mod(ll a, ll b, ll c){
        
            ll ans = 1;
            a %= MOD;
            while(b) {
        
                    if(b&1) ans = ans*a%c;
                    a = a*a%c;
                    b>>=1;
            }
            return ans;
    }
    
    int main() {
        
            int t,Case = 0;
            ll n,k;
            scanf("%d",&t);
            while(t--) {
        
                    scanf("%I64d %I64d",&n,&k);
                    ll ans = pow_mod(2,n,MOD)-1;
                    ll num = n;
                    for(int i=2;i<k;++i) {
        
                            ans = ((ans-num+MOD)%MOD+MOD)%MOD;
                            num = (num*(n-i+1)%MOD)*(pow_mod(i,MOD-2,MOD))%MOD;
                    }
                    ans = ((ans-num+MOD)%MOD+MOD)%MOD;
    
                    printf("Case #%d: %I64d\n",++Case, ans%MOD);
            }
            return 0;
    }

# [C. Traffic Light][] #

就是找红灯最大值(看样例猜题意，敢交就敢过)

#include<bits/stdc++.h>
    using namespace std;
    typedef long long ll;
    
    
    int main() {
        
            int t,Case = 0;
            int n;
            scanf("%d",&t);
            while(t--) {
        
                    scanf("%d",&n);
                    double ans = 0,x,a,b,tmp=0;
                    for(int i=0;i<=n;++i) {
        
                            scanf("%lf",&x);
                            ans += x;
                    }
                    for(int i=0;i<n;++i) {
        
                            scanf("%lf %lf",&a,&b);
                            if(b>tmp)       tmp = b;
                    }
                    printf("Case #%d: %.6f\n",++Case,tmp+ans);
            }
            return 0;
    }

# [L. SOS][] #

队友玩了半个小时游戏玩儿出来的  
必胜态 S \_ \_ S

#include<bits/stdc++.h>
    using namespace std;
    
    int main() {
        
            int t,Case = 0;
            int n;
            scanf("%d",&t);
            while(t--) {
        
                    scanf("%d",&n);
                    printf("Case #%d: ",++Case);
                    if(n<=6)        puts("Draw");
                    else if(n%2)    puts("Panda");
                    else if(n>=16)  puts("Sheep");
                    else            puts("Draw");   
            }
            return 0;
    }

[A. Chat Group]: https://codeforces.com/gym/101775/problem/A
[C. Traffic Light]: https://codeforces.com/gym/101775/problem/C
[L. SOS]: https://codeforces.com/gym/101775/problem/L