D.Defuse the Bombs（二分答案）

思路：直接二分答案K，判断能不能在K次操作以内，把所有的数都变成 >= K就行了。最后答案等于K+1

AC代码：

#include <bits/stdc++.h>
#define int long long
#define showcase cout<<"Case #"<<cas++<<": ";
using namespace std;
int a[100050];
int T,cas = 1;
int n,m;
bool check(int k){ 
    int res = 0;
    for(int i = 0 ; i < n ; i ++){ 
        if(k<=a[i]) continue;
        res += max((int)0,k-a[i]);
        if(res > k ) return false;
    }
    return res <= k;
}

signed main(){ 
    cin>>T;
    while(T--){ 
        cin>>n;
        for(int i = 0 ; i < n ; i ++)
            cin>>a[i];
        int l = 0,r = 1e18;
        int res = 0;
        while(l <= r){ 
            int mid = (l+r)>>1;
            if(check(mid)){ 
                res = max(res,mid);
                l = mid+1;
            }else{ 
                r = mid-1;
            }
        }
        cout<<"Case #"<<cas++<<": "<<res+1<<endl;
    }
}

G.Game of Cards（博弈）

思路：比赛时还是没有想出来。后来仔细推了一下感觉也不是很难。但是分很多很多种情况。首先可以很容易的发现，答案和 cnt1%3 的值有关，并且和 cnt0%2 的值有关，与cnt3无关。

• 首先考虑 cnt0 == 0 的情况，那就是如下图所示的情况了。显然当cnt2 等于0 或者 不等于0 时都是一个关于3的循环（但是两者不相同）。那就直接按规律输出就好了。
• 对于cnt0 != 0 的情况。还得特判，如果后面三个都是0，那么只能 0+0 了，也就是每次减少一张 0卡牌 的数量。那么答案和 cnt0 的奇偶性有关。
• 对于cnt0 != 0 且 后面不全为0的情况，还要判断，cnt2 是 0 还是1，因为对于 cnt2 >= 2 ,那么所有的转移都是相同的。而当cnt2 == 1 和cnt2 == 0 时，转移方向虽然是相同的，但是转移的结果不相同。所以还得区分。（反正就是一堆特判）
• 对于剩下的规则的状态，就判断能不能找到一个状态使得转移之后还是必胜态了。

AC代码：

#include <bits/stdc++.h>
#define int long long
using namespace std;
int cas = 1;
int tt1[3] = { 0,0,1};       // 2号卡牌数量为0 的胜负情况
int tt2[3] = { 0,1,1};       // 2号卡牌数量非0 的胜负情况

void show(int x){ 
    cout<<"Case #"<<cas++<<": ";
    if(x) cout<<"Rabbit"<<endl;
    else  cout<<"Horse"<<endl;
}

signed main(){ 
    int t;
    cin>>t;
    while(t--){ 
        int cnt0,cnt1,cnt2,cnt3;
        cin>>cnt0>>cnt1>>cnt2>>cnt3;
        if(cnt1 + cnt2 + cnt3 == 0){ 
            if(cnt0 <= 1)
                show(0);
            else
                show(cnt0%2 == 0);
        }else{ 
            int flag1 = cnt0%2;
            cnt1 %= 3;
            if(cnt0 == 0){               // 没有0号卡牌的情况，直接按规律输出
                if(cnt2 == 0){           // 没有2号卡牌的情况，特判
                    show(tt1[cnt1]);
                }else{ 
                    show(tt2[cnt1]);
                }
            }else if(cnt2 == 0){         // 没有2号卡牌的情况，特判，又因为存在0号卡牌，要异或一下
                show(tt1[cnt1]^flag1);
            }else if(flag1){             // 如果可以转移到对手的必胜态，则自己可以获胜
                if(cnt1 == 2 || cnt1 == 0){ 
                    show(1);
                }else{ 
                    show(0);
                }
            }else{ 
                if(cnt1 == 2 || cnt1 == 1){  // 如果可以转移到自己的必胜态，则可以获胜
                    show(1);
                }else{ 
                    show(0);
                }
            }
        }
    }
    return 0;
}

J.Joy of Handcraft（线段树）

思路：稍微预处理一下，然后直接线段树暴力模拟就好了，因为题目给的t可能是相同的，那么对于相同的t，只保存最大的那个。因为最多只有n种t，那么总的复杂度就是 log(n)*n*log(n)，因为 (n/1+n/2+n/3+n/4+…+n/n) = n*log(n)

AC代码:

#include <bits/stdc++.h>
#define int long long
#define showcase cout<<"Case #"<<cas++<<": ";
using namespace std;
int T,cas = 1;
int n,m;
struct node{ 
    int t,x;
    node(){ }
}a[100050];
int tree[100050<<8];
int lazy[100050<<8];
void push_down(int pos){ 
    int lson = pos<<1;
    int rson = pos<<1|1;
    lazy[lson] = max(lazy[lson],lazy[pos]);
    lazy[rson] = max(lazy[rson],lazy[pos]);
    tree[lson] = max(tree[lson],lazy[pos]);
    tree[rson] = max(tree[rson],lazy[pos]);
    lazy[pos] = 0;
}

void push_up(int pos){ 
    tree[pos>>1] = max(tree[pos>>1],tree[pos]);
}

void build(int pos,int l,int r){ 
    tree[pos] = lazy[pos] = 0;
    if(l == r) return;
    int lson = pos<<1;
    int rson = pos<<1|1;
    int mid = (l+r)>>1;
    build(lson,l,mid);
    build(rson,mid+1,r);
}

void update(int pos,int x,int l,int r,int ll,int rr){ 
    if(ll <= l && rr >= r){ 
        lazy[pos] = max(lazy[pos],x);
        tree[pos] = max(tree[pos],x);
        return;
    }
    int lson = pos<<1;
    int rson = pos<<1|1;
    int mid = (l+r)>>1;
    if(lazy[pos]) push_down(pos);
    if(ll <= mid) update(lson,x,l,mid,ll,rr);
    if(rr > mid)  update(rson,x,mid+1,r,ll,rr);
}

int ask(int pos,int l,int r,int x){ 
    if(l == r){ 
        if(l == x)  return tree[pos];
        else return 0;
    }
    int lson = pos<<1;
    int rson = pos<<1|1;
    int mid = (l+r)>>1;
    if(lazy[pos]) push_down(pos);
    if(x <= mid) return ask(lson,l,mid,x);
    if(x > mid)  return ask(rson,mid+1,r,x);
}

bool cmp(node a1,node a2){ 
    if(a1.t == a2.t) return a1.x > a2.x;
    return a1.t < a2.t;
}


signed main(){ 
    cin>>T;
    a[0].t = 0;
    while(T--){ 
        cin>>n>>m;
        for(int i = 1 ; i <= n ; i ++){ 
            cin>>a[i].t>>a[i].x;
        }
        sort(a+1,a+n+1,cmp);
        build(1,1,m);
        for(int i = 1 ; i <= n; i ++){ 
            if(a[i].t != a[i-1].t){ 
                for(int j = min(m,a[i].t),pre = 1; j <= m ; j = min(m,j+2*a[i].t)){ 
                    //cout<<pre<<"--"<<j<<endl;
                    update(1,a[i].x,1,m,pre,j);
                    pre = j+a[i].t+1;
                    if(j == m) break;
                }
            }
        }
        showcase;
        for(int i = 1 ; i < m ; i ++){ 
            cout<<ask(1,1,m,i)<<" ";
        }
        cout<<ask(1,1,m,m)<<endl;
    }
}

K.Knowledge is Power（打表，找规律）

思路：找规律。分类讨论也可以。但是比赛的时候分了半天还分错了。最后DFS打表发现了36个一次循环，直接水过了。

AC代码：

#include <bits/stdc++.h>
#define int long long
#define showcase cout<<"Case #"<<cas++<<": ";
using namespace std;
int a[100050];
int T,cas = 1;
int n,m;
int res1[] = { 1,-1,1,2,1,3,1,2,1,4};
int res2[] = { 4,1,2,1,2,1,2,1,4,1,2,1,3,1,2,1,2,1,2,1,3,1,2,1,3,1,2,1,2,1,2,1,3,1,2,1};
int maxx = 0;
vector<int> res;
int gcd(int x,int y){ 
    if(x < y) swap(x,y);
    return y == 0 ? x : gcd(y,x%y);
}

void dfs(int x,int sum,vector<int> nums){ 
    if(sum > n) return;
    if(sum == n){ 
        for(int i = 0 ; i < nums.size() ; i ++){ 
            for(int j = 0 ; j < nums.size() ; j ++){ 
                if(i == j) continue;
                if(gcd(nums[i],nums[j]) != 1){ 
                    return;
                }
            }
        }
        if(nums[nums.size()-1]-nums[0] < maxx){ 
            maxx = nums[nums.size()-1]-nums[0];
            res.clear();
            for(int i = 0 ; i < nums.size() ; i ++){ 
                res.push_back(nums[i]);
            }
        }
    }
    if(nums.size() >= 3) return;
    nums.push_back(x);
    dfs(x+1,sum+x,nums);
    dfs(x+2,sum+x,nums);
    dfs(x+3,sum+x,nums);
    dfs(x+4,sum+x,nums);
    nums.pop_back();
}

signed main(){ 
    cin>>T;
    while(T--){ 
        cin>>n;
        n -= 5;
        showcase;
        if(n > 9) cout<<res2[(n-9)%36]<<endl;
        else cout<<res1[n]<<endl;
// n += 5;
 for(n = 5 ; n <= 10000 ; n ++){ 
// if(n == 6){cout<<-1<<endl;continue;}
// maxx = 10;
// for(int i = 2; i < n ; i ++){ 
// vector<int> nums;
// dfs(i,0,nums);
// }
// cout<<res[res.size()-1]-res[0]<<endl;
// if((n-13)%36 == 0) cout<<endl;
// for(int i = 0 ; i < res.size(); i++){ 
// cout<<res[i]<<" ";
// }
// cout<<endl;
// }
        //showcase;
    }
}

L.Lottery（思维，二进制）

思路：首先对于每一位，最多只要留下2个就好了。剩下的往后一直进位就好了。然后就预处理成了很多连续的非零的块。 对于每个块， 都是相互独立不影响的，因为每个位上最大是2，对于一个块，最多只能往最高位进位一位。 如果一个位上是1，那么就有0，1两种方案，而如果一个位置上是2，就有0，1，进位，三种方案。如果进位的话，增加的方案数，就是在他后面连续的非0个数。

更一般的解释：如果一个块 1122112 从左往右数。对于第一个2增加 2²种方案，对于第二个2增加2³种方案。对于第三个2增加2⁶种方案。 可以想象，令当前位进位，那么当前位为往后都是0，最高位为1，而前面的位可以选择0，1两种状态，按112212举例：如果第一个2进位：xx000001，x两种状态，所以就是2²种。

最后把每个块的方案数相乘就好了，因为互不影响

AC代码：

#include <bits/stdc++.h>
#define int long long
#define showcase cout<<"Case #"<<cas++<<": ";
using namespace std;
const int mod = 1e9+7;
int T,cas = 1;
int n,m;

struct node{ 
    int x,cnt;
    node(){ }
    node(int xx,int cc){ 
        x = xx;
        cnt = cc;
    }
}a[100050],que[3200050];

int qpow(int a,int b){ 
    int res = 1;
    int tmp = a;
    while(b){ 
        if(b&1) res = res*tmp%mod;
        b >>= 1;
        tmp = tmp*tmp%mod;
    }
    return res%mod;
}

bool cmp(node a1,node a2){ 
    return a1.x < a2.x;
}

signed main(){ 
    //rand_test(); return 0;
    //freopen("in.txt","r",stdin);
    //freopen("out.txt","w",stdout);
    //freopen("out3.txt","w",stdout);
    scanf("%lld",&T);
    while(T--){ 
        scanf("%lld",&n);
        for(int i = 0 ; i < n ; i ++){ 
            scanf("%lld%lld",&a[i].x,&a[i].cnt);
        }
        sort(a,a+n,cmp);
        int tail = 0;
        for(int i = 0 ; i < n; i ++){ 
            que[tail] = a[i];
            while(que[tail].cnt > 2){ 
                int tmp = (que[tail].cnt-1)>>1;
                if(i+1 >= n || que[tail].x+1 != a[i+1].x){ 
                    que[tail+1] = node(que[tail].x+1,tmp);
                    que[tail].cnt -= tmp<<1;
                    ++ tail;
                }else{ 
                    a[i+1].cnt += tmp;
                    que[tail].cnt -= tmp<<1;
                }
            }
            ++ tail;
        }
        int pre = 0,now = 0,res = 1,tmp = 1;
        for(int i = 0 ; i < tail ; i ++){ 
            if(i >= 1){ 
                if(que[i].x != que[i-1].x+1){ 
                    res = (res*(qpow(2,now)+pre)%mod)%mod;
                    pre = 0;
                    now = 0;
                    tmp = 1;
                }
            }
            ++ now;
            pre += (que[i].cnt&1) ? 0 : tmp;
            pre %= mod;
            tmp = (tmp<<1)%mod;
        }
        res = (res*(qpow(2,now)+pre)%mod)%mod;
        printf("Case #%lld: %lld\n",cas++,res);
    }
}

小结：前一天没睡好，打比赛完全不在状态，纯属摸鱼。靠着队友的快速三题混进了铜牌区。最后两小时博弈也没推出来。不过依然还是打星。等于花钱训练了一波