Noip模拟81 2021.10.20

T1 语言

比较简单的题,然后就瞎写了,所以考场上就我一个写了线段树的,所以我的常数。。。。

Noip模拟81 2021.10.20

 

 所以就枚举动词的位置,找前面后面有没有出现$4$即可

Noip模拟81 2021.10.20
 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$,非常悲伤

于是先贴一个珂朵莉树的暴力

Noip模拟81 2021.10.20
 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

然后考虑双端队列的暴力,因为他可以优化成正解,

在直接双端队列的基础上使用启发式合并就行啦

Noip模拟81 2021.10.20
 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 偶数

咕咕咕

上一篇:Mac网站优化分析:Link-Assistant WebSite Auditor Enterprise


下一篇:noip模拟81(待补)