考试前
呃呃也没怎么太复习,考完普及匆匆吃了个饭就去考提高了。。。
考试时
进了考场,当然是先看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
1
挂了 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 分上下浮动。。。
心里还是有些不舒服。