考试前

呃呃也没怎么太复习，考完普及匆匆吃了个饭就去考提高了。。。

考试时

进了考场，当然是先看T1......

刚开始以为T1是签到题，就死杠。没想到啊...

当时的思路是先计算年，再计算月再计算日。

并没有想到能够二分年份。是我太菜了。

死杠了一个半小时，自闭了。去看 T2 了。

结果眼前一亮，30min 就过了大样例。

具体的思路就是直接或一下，再或一下，在异或个与，再左移。

代码长这样：

#include<cstdio>
#include<cstdio>
#include<algorithm>
typedef unsigned long long ull;
int n,m,c,k;ull a,sum,vis;
int countb(ull x){int ret=0;while(x)ret++,x&=(x-1);return ret;}
int main(){
    freopen("zoo.in","r",stdin);
    freopen("zoo.out","w",stdout);
    scanf("%d%d%d%d",&n,&m,&c,&k);
    for(int i=1;i<=n;i++)scanf("%llu",&a),sum|=a;
    for(int i=1;i<=m;i++){int p,q;scanf("%d%d",&p,&q),vis|=(1<<p);}vis^=(sum&vis);
    if(k-countb(vis)<64)printf("%llu\n",(1ull<<(k-countb(vis)))-n);
    else if(n==0)printf("18446744073709551616\n");
    else printf("%llu\n",(18446744073709551615ull)-n+1);
    return 0;
}

没想到啊，这个大样例这么水。


for(int i=1;i<=m;i++){int p,q;scanf("%d%d",&p,&q),vis|=(1<<p);}vis^=(sum&vis);

int p,q;scanf("%d%d",&p,&q),vis|=(1<<p);

vis|=(1<<p);

1<<p

挂了 40 分。

然后看了 T4。

现在想想不看 T3真是明智（

当时看 T4 也是一头雾水，直到后面推大样例的时候偶然发现了一个有意思的规律：如果一条蛇吃了最弱的一条蛇，那么下一条蛇要么不吃，决斗结束；要么吃了，但是吃完后总比上一条蛇要弱。

也就是说如果一条蛇吃完后实力不是垫底的，那么它之后就永远不会被吃；如果实力垫底了，那就得判断后面的蛇会不会吃它（仔细想想只要判断剩下的蛇的数量就可以了）。

然后朴素的做法是 $\textsf{O}(n^2)$ 的，需要优化。

一种方法是用 set 维护，复杂度是 $\textsf{O}(n\log n)$ 的，但这还是不够；然后再仔细想想，其实 $\textsf{O}(n)$ 就可以了。

小样例良心，给了个答案是 1 的数据。

代码长这样

#include<cstdio>
#include<cstdio>
#include<queue>
#include<cassert>
int a[1000005],T,n,k;
std::queue<int> q;
int Max(int x,int y){return x>y?x:y;}
int main(){
    freopen("snakes.in","r",stdin);
    freopen("snakes.out","w",stdout);
    scanf("%d",&T);T--;
    scanf("%d",&n);
    for(int i=1;i<=n;i++)scanf("%d",a+i);
    int l=1,r=n,ans=n;while(l<=r){
        if((!q.empty())&&a[r]<=q.front()&&q.front()-a[l]>=a[l+1]){q.push(q.front()-a[l]),q.pop(),l++,ans--;}
        else if(l!=r&&a[r]-a[l]>=a[l+1]){q.push(a[r]-a[l]),ans--,l++,r--;}
        else {ans-=!((r-l+1+q.size())&1);break;}
    }printf("%d\n",ans-(ans==2));
    while(T--){scanf("%d",&k);
        for(int i=1;i<=k;i++){int x,y;scanf("%d%d",&x,&y),a[x]=y;}
        while(!q.empty())q.pop();l=1,r=n,ans=0;
        int l=1,r=n,ans=n;while(l<=r){
            if((!q.empty())&&a[r]<=q.front()&&q.front()-a[l]>=a[l+1]){q.push(q.front()-a[l]),q.pop(),l++,ans--;}
            else if(l!=r&&a[r]-a[l]>=a[l+1]){q.push(a[r]-a[l]),ans--,l++,r--;}
            else {ans-=!((r-l+1+q.size())&1);break;}
        }printf("%d\n",ans-(ans==2));
    }return 0;
}

upd: 被叉了。。。

1
9
5 5 5 5 10 10 10 10 10

正确输出应该是 6。

比赛后

刚开始预估的是 270 分，但是种种原因挂了 100 多分。。。

民间数据测出来是 100 分到 120 分上下浮动。。。

心里还是有些不舒服。