A - Chat Group

题目链接：https://vjudge.net/contest/331810#problem/A

题意：

给出n和k，让你输出C(n,k) + C(n,k+1) + C(n,k+2) +....+ C(n,n)的和(%1000000007);n<=1e9,k<=1e5

题解:

看到n的范围，肯定不能枚举n，我们发现一个式子C(n,0) + C(n,1) + c(n,2) + .... + C(n,n) = 2^n,所以我们就可以计算从C(n,0)到C(n,k-1)的和，然后用2^n减去这个和，就是答案。注意，这里求C(x,y)的时候最好用逆元，保证不会爆long long

#include <stdio.h>
#include <string.h>
#include <iostream>
#include <algorithm>
#include <math.h>
#include <map>
#include <stack>
#include <queue>
#include <vector>
#include <set>
#include <string>
using namespace std;
#define ll long long
const ll mod = 1e9+7;
ll pow_mod(ll a,ll b)
{
    ll ans = 1;
    while(b){
        if(b&1)
           ans = ans*a%mod;
        a = a*a%mod;
        b>>=1;
    }
    return ans;
}
int main()
{
    ll t,n,k;
    int tt = 0;
    cin>>t;
    while(t--)
    {
        cin>>n>>k;
        if(n < k){
            printf("Case #%d: 0\n",++tt);
            continue ;
        }
        ll ans = pow_mod(2 , n);
        //cout<<ans<<endl;
        ll sum = 1,now = 1;
        for(ll i = 1; i < k ;i++)
        {
            now = ((now*(n-i+1)%mod)*(pow_mod(i,mod-2)))%mod;
            sum = (sum + now)%mod;
        }
        printf("Case #%d: %lld\n",++tt,(ans - sum + mod)%mod);
    }
    return 0;
}

I - Ice Cream Tower

题目链接：https://vjudge.net/contest/331810#problem/I

题意：

给出n个无序的数字和一个数字k，问你最多可以构成多少组数组，每一组数字包含k个数，且排序后，第i个数要大于等于第i-1个数的二倍

题解：

二分答案，在solve(x)里，我们将排好序的前x个数赋值给a数组，定义一个下标从第x+1位置处往后查询，更新a数组，如果更新完了k-1次下标没有到达n+1，那么此时的答案肯定满足，否则不满足

#include <stdio.h>
#include <string.h>
#include <iostream>
#include <algorithm>
#include <math.h>
#include <map>
#include <stack>
#include <queue>
#include <vector>
#include <set>
#include <string>
using namespace std;
#define ll long long
const int maxx = 300005;
ll n;
int k;
ll a[maxx],b[maxx];
int solve(int x)
{
    for(int i=1;i<=x;i++){
        b[i] = a[i];
    }
    int pre = x+1;
    for(int i=1;i<k;i++)
    {
        for(int j=1;j<=x;j++){
            while(b[j]*2 > a[pre] && pre <= n)
                pre++;
            if(pre == n+1)
                return 0;
            b[j] = a[pre++];
        }
    }
    return 1;
}
int main()
{
    int t;
    cin>>t;
    for(int cas=1;cas<=t;cas++)
    {
        scanf("%lld %d",&n,&k);
        for(int i=1;i<=n;i++){
            scanf("%lld",&a[i]);
        }
        sort(a+1,a+1+n);
        int r = n/k,l = 0,ans = 0;
        while(l <= r)
        {
            //cout<<l<<" "<<r<<" ";
            int mid = (l+r)>>1;
            //cout<<solve(mid)<<endl;
            if(solve(mid)){
                ans = mid;
                l = mid + 1;
            }else{
                r = mid - 1;
            }
        }
        //cout<<l<<" "<<r<<endl;
        printf("Case #%d: %d\n",cas,ans);
    }
    return 0;
}

K - World Cup

题目链接：https://vjudge.net/contest/331810#problem/K

题意：

有4支队伍，每俩支队伍都要进行一场比赛，即有6场比赛，每一场比赛，赢的一方加3分，输的一方不加分，平局各加1分。给出4支队伍最后的得分情况，问你比赛的战况是否唯一，或者得分情况不存在

题解：

暴力打表

#include <stdio.h>
#include <string.h>
#include <iostream>
#include <algorithm>
#include <math.h>
#include <map>
#include <stack>
#include <queue>
#include <vector>
#include <set>
#include <string>
using namespace std;
#define ll long long

int dp[20][20][20][20];
int sx[4] = { 0 , 3 , 0 , 1};
int sy[4] = { 0 , 0 , 3 , 1};

void init()
{
    //i j n m
    // ij in im jn jm nm
    for(int ij=1;ij<=3;ij++){
        for(int in=1;in<=3;in++){
            for(int im=1;im<=3;im++){
                for(int jn=1;jn<=3;jn++){
                    for(int jm=1;jm<=3;jm++){
                        for(int nm=1;nm<=3;nm++){
                            int i = sx[ij] + sx[in] + sx[im];
                            int j = sy[ij] + sx[jn] + sx[jm];
                            int n = sy[in] + sy[jn] + sx[nm];
                            int m = sy[im] + sy[jm] + sy[nm];
                            dp[i][j][n][m] += 1;
                        }
                    }
                }
            }
        }
    }
    return ;
}
int main()
{
    int t;
    init();
    cin>>t;
    for(int cas = 1;cas <= t;cas++)
    {
        int a,b,c,d;
        cin>>a>>b>>c>>d;
        printf("Case #%d: ",cas);
        if(dp[a][b][c][d] == 0){
            printf("Wrong Scoreboard\n");
        }
        else if(dp[a][b][c][d] == 1){
            printf("Yes\n");
        }
        else{
            printf("No\n");
        }

    }
    return 0;
}