T1 语言
比较简单的题，然后就瞎写了，所以考场上就我一个写了线段树的，所以我的常数。。。。
所以就枚举动词的位置，找前面后面有没有出现$4$即可
1 #include<bits/stdc++.h>
2 using namespace std;
3 inline int read(){
4 int x=0,f=1;char ch=getchar();
5 while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
6 while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
7 return x*f;
8 }
9 const int NN=100005;
10 int T,w[27],n,a[NN];
11 char s[NN];
12 struct SNOWtree{
13 #define lid (id<<1)
14 #define rid (id<<1|1)
15 int ll[NN<<2],rr[NN<<2],sm[NN<<2][8];
16 inline void pushup(int id){
17 if(ll[id]==rr[id]) return;
18 for(int i=1;i<=7;++i) sm[id][i]=sm[lid][i]+sm[rid][i];
19 }
20 inline void build(int id,int l,int r){
21 ll[id]=l; rr[id]=r;
22 if(l==r){
23 ++sm[id][a[l]];return;
24 }int mid=l+r>>1;
25 build(lid,l,mid); build(rid,mid+1,r);
26 pushup(id);
27 }
28 inline int query(int id,int l,int r,int opt){
29 if(l<=ll[id]&&rr[id]<=r)return sm[id][opt];
30 int mid=ll[id]+rr[id]>>1,ans=0;
31 if(l<=mid) ans+=query(lid,l,r,opt);
32 if(r>mid) ans+=query(rid,l,r,opt);
33 return ans;
34 }
35 }tr;
36 inline bool check(int i,int x){
37 if(i-1==0||i==n) return 0;
38 if(x==1||x==2||x==3) return 0;
39 if(a[i-1]==1||a[i-1]==4||a[i-1]==5) return 0;
40 if(tr.query(1,1,i-2,4)!=0||tr.query(1,i+1,n-1,4)!=0) return 0;
41 return 1;
42 }
43 namespace WSN{
44 inline short main(){
45 // freopen("in.in","r",stdin);
46 freopen("language.in","r",stdin);
47 freopen("language.out","w",stdout);
48 T=read();
49 while(T--){
50 memset(a,0,sizeof(a));
51 for(int i=1;i<=26;i++)w[i]=read();
52 scanf("%s",s+1);n=strlen(s+1);
53 for(int i=1;i<=n;i++){
54 int ch=s[i]-'a'+1;
55 a[i]=w[ch];
56 }
57 if(a[n]!=2&&a[n]!=3&&a[n]!=6&&a[n]!=7){puts("No");continue;}
58 memset(tr.ll,0,sizeof(tr.ll));
59 memset(tr.rr,0,sizeof(tr.rr));
60 memset(tr.sm,0,sizeof(tr.sm));
61 tr.build(1,1,n); bool flag=0;
62 for(int i=1;i<=n;i++)
63 if(check(i,a[i])){flag=1;break;}
64 puts(flag?"Yes":"No");
65 }
66 return 0;
67 }
68 }
69 signed main(){return WSN::main();}
View Code
T2 色球
珂朵莉树写错一句话，就惨挂$30pts$，非常悲伤
于是先贴一个珂朵莉树的暴力
1 #include<bits/stdc++.h>
2 #define int long long
3 using namespace std;
4 inline int read(){
5 int x=0,f=1;char ch=getchar();
6 while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
7 while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
8 return x*f;
9 }
10 const int NN=200005;
11 int n,m,top[NN],tp;
12 char ch[5];
13 namespace Chtholly{
14 #define sit set<node>::iterator
15 struct node{
16 int l,r; mutable int v;
17 node(int l,int r=0,int v=0):l(l),r(r),v(v){}
18 bool operator<(const node&a)const{return l<a.l;}
19 };
20 set<node> s[NN];
21 inline sit split(int i,int pos){
22 sit it=s[i].lower_bound(pos);
23 if(it!=s[i].end()&&it->l==pos) return it;
24 --it; if(it->r<pos) return s[i].end();
25 int L=it->l,R=it->r,V=it->v;
26 s[i].erase(it);
27 s[i].insert(node(L,pos-1,V));
28 return s[i].insert(node(pos,R,V)).first;
29 }
30 inline void assign(int i,int l,int r,int v){
31 sit itr=split(i,r+1),itl=split(i,l);
32 s[i].erase(itl,itr);
33 s[i].insert(node(l,r,v));
34 }
35 }using namespace Chtholly;
36 namespace WSN{
37 inline short main(){
38 freopen("color.in","r",stdin);
39 freopen("color.out","w",stdout);
40 n=read(); m=read();
41 for(int i=1;i<=n;i++) s[i].insert(node(0,1e18,0));
42 while(m--){
43 scanf("%s",ch);
44 if(ch[2]=='s'){
45 int x=read(),y=read(),z=read();
46 assign(z,top[z]+1,top[z]+x,y);
47 top[z]+=x;
48 }
49 if(ch[2]=='p'){
50 int x=read(),z=read(),l=top[z]-x+1,r=top[z];
51 sit itr=split(z,r+1),itl=split(z,l);
52 printf("%lld\n",itl->v);
53 assign(z,l,r,0); top[z]-=x;
54 }
55 if(ch[2]=='t'){
56 int u=read(),v=read();
57 sit it=s[u].end();
58 if(it!=s[u].begin()) --it;
59 while(it!=s[u].begin()){
60 if(it->v==0) {--it;continue;}
61 assign(v,top[v]+1,top[v]+it->r-it->l+1,it->v);
62 top[v]+=it->r-it->l+1; --it;
63 }
64 if(it->v!=0){
65 assign(v,top[v]+1,top[v]+it->r-it->l+1,it->v);
66 top[v]+=it->r-it->l+1;
67 }
68 top[u]=0;s[u].clear();s[u].insert(node(0,1e18,0));
69 }
70 }
71 return 0;
72 }
73 }
74 signed main(){return WSN::main();}
View Code
然后考虑双端队列的暴力，因为他可以优化成正解，
在直接双端队列的基础上使用启发式合并就行啦
1 #include<bits/stdc++.h>
2 #define int long long
3 using namespace std;
4 inline int read(){
5 int x=0;char ch=getchar();
6 while(ch<'0'||ch>'9'){ch=getchar();}
7 while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
8 return x;
9 }
10 const int NN=200005;
11 int n,m,top[NN];
12 bool rev[NN];
13 char ch[10];
14 struct node{
15 int num,col;
16 };deque<node> q[NN];
17 namespace WSN{
18 inline short main(){
19 freopen("color.in","r",stdin);
20 freopen("color.out","w",stdout);
21 n=read(); m=read();
22 for(int i=1;i<=n;i++)top[i]=i;
23 int u,v,x,y,z;
24 while(m--){
25 cin>>ch;
26 if(ch[2]=='s'){
27 x=read(),y=read(),z=read();
28 if(!rev[z]) q[top[z]].push_back(node{x,y});
29 else q[top[z]].push_front(node{x,y});
30 }
31 if(ch[2]=='p'){
32 x=read(),z=read(); node now;
33 if(!rev[z]){
34 z=top[z];
35 while(x&&!q[z].empty()){
36 now=q[z].back(); q[z].pop_back();
37 if(now.num>x){
38 now.num-=x; q[z].push_back(node{now.num,now.col});
39 printf("%lld\n",now.col);
40 break;
41 }
42 x-=now.num; if(!x) printf("%lld\n",now.col);
43 }
44 }
45 else{
46 z=top[z];
47 while(x&&!q[z].empty()){
48 now=q[z].front(); q[z].pop_front();
49 if(now.num>x){
50 now.num-=x; q[z].push_front(node{now.num,now.col});
51 printf("%lld\n",now.col);
52 break;
53 }
54 x-=now.num; if(!x) printf("%lld\n",now.col);
55 }
56 }
57 }
58 if(ch[2]=='t'){
59 u=read(),v=read(); bool flag=false;
60 if(q[top[u]].size()>q[top[v]].size())
61 swap(top[u],top[v]),swap(rev[u],rev[v]),flag=true;
62 if(!rev[u]&&!rev[v]) while(q[top[u]].size()) q[top[v]].push_back (q[top[u]].back()), q[top[u]].pop_back();
63 else if(rev[u]&&!rev[v]) while(q[top[u]].size()) q[top[v]].push_back (q[top[u]].front()),q[top[u]].pop_front();
64 else if(!rev[u]&&rev[v]) while(q[top[u]].size()) q[top[v]].push_front(q[top[u]].back()), q[top[u]].pop_back();
65 else while(q[top[u]].size()) q[top[v]].push_front(q[top[u]].front()),q[top[u]].pop_front();
66 if(flag) rev[v]^=1;
67 }
68 }
69 return 0;
70 }
71 }
72 signed main(){return WSN::main();}
View Code
T3 斐波
考场上推出来了个$f_i^2+f_{i+1}^2=f_{2i+1}$，但不知道怎么用，然后题解里的那个也没推出来，就死掉了
就咕咕咕
T4 偶数
咕咕咕