T1 语言
水题不多说，很容易发现 NP 需要满足的只是最后一个单词为 N，前面是 A 或 N 都可以随意放。
所以用两个数组，\(v1_i\) 记录以 \(i\) 结尾的前缀是否可以构成 NP，\(v2_i\) 记录以 \(i\) 为开头的后缀是否可以构成 NP。
最后 for 循环扫一遍是否有同时满足 \(v1_{i-1}=true\) 和 \(v2_{i+1}=true\) 的就可以了。
时间复杂度 \(O(n)\)，代码如下(100pts)：
#include<bits/stdc++.h>
using namespace std;
char ch[100005];
int t,len,flag,w[26],v1[100005],v2[100005];
int main(){
scanf("%d",&t);
while(t--){
for(int i=0;i<26;i++) scanf("%d",w+i);
memset(v1,0,sizeof v1);
memset(v2,0,sizeof v2),flag=0;
scanf("%s",ch+1),len=strlen(ch+1);
for(int i=1;i<=len;i++){
if(!(w[ch[i]-'a']&1)&&!(w[ch[i]-'a']&2)) break;
if(w[ch[i]-'a']&2) v1[i]=1;
}
if(w[ch[len]-'a']&2){
for(int i=len;i>0;i--){
if(!(w[ch[i]-'a']&1)&&!(w[ch[i]-'a']&2)) break;
v2[i]=1;
}
}
for(int i=2;i<len;i++) flag|=(v1[i-1]&&v2[i+1]&&(w[ch[i]-'a']&4));
printf("%s\n",flag?"Yes":"No");
}
}
T2 色球
很明显的双向链表的题目，但这道题一定不能去想哪边是 \(pre\) 哪边是 \(next\)，不然就会把自己给绕进去。
对于链表的每一块，维护 \(col\) 和 \(val\) 两个信息，而对于每个桶，维护里面链表的表头和表尾就行了。
对于操作 1，我们把当前找的这个链表的表头，那边没有值就把那边赋值成现在加进去的这一块。
对于操作 2，如果现在的这个表头的 \(val\) 已经大于等于 \(x\) 了，就直接 break，然后输出表头的 \(col\) 就行了。
否则，因为表头一定只有一边有值，我们直接往那一边跳就行了。
而对于现在跳到的这一个点，哪边是刚才的表头，就直接赋值成 \(0\) 就行了，另外一边就是它下面的数。
对于操作 3，直接把两个表头连起来，然后把 \(v\) 的表头赋值成 \(u\) 的表尾就行了。
代码如下(100pts)：
#include<bits/stdc++.h>
using namespace std;
#define N 200005
char op[10];
int n,m,cnt,hed[N],tal[N],col[N],val[N],ch1[N],ch2[N];
int main(){
scanf("%d%d",&n,&m);
for(int i=1,x,y,z;i<=m;i++){
scanf("%s%d%d",op,&x,&y);
if(op[2]=='s'){
scanf("%d",&z),cnt++;
if(!tal[z]) tal[z]=cnt;
col[cnt]=y,val[cnt]=x,ch1[cnt]=hed[z];
(ch1[hed[z]]?ch2[hed[z]]=cnt:ch1[hed[z]]=cnt),hed[z]=cnt;
}
if(op[2]=='p'){
while(val[hed[y]]<x){
x-=val[hed[y]];
int to=(ch1[hed[y]]?ch1[hed[y]]:ch2[hed[y]]);
(ch1[to]==hed[y]?ch1[to]=0:ch2[to]=0),hed[y]=to;
}
val[hed[y]]-=x,printf("%d\n",col[hed[y]]);
}
if(op[2]=='t'){
if(!hed[x]) continue;
if(!hed[y]) hed[y]=tal[x],tal[y]=hed[x];
else{
ch1[hed[y]]?ch2[hed[y]]=hed[x]:ch1[hed[y]]=hed[x];
ch1[hed[x]]?ch2[hed[x]]=hed[y]:ch1[hed[x]]=hed[y];
hed[y]=tal[x];
}
tal[x]=hed[x]=0;
}
}
}
T3 斐波
完全不会，写的 10pts 暴力...
T4 偶数
先写一下 40pts 的做法吧，100pts 的等我过了再来写。
首先，我们把 \(u\) 设成 \(vv\) 的形式，那么扩展后就一定是 \(vwvw\) 的形式.
其中，\(w\) 是 \(v\) 的一个前缀，且是 \(v\) 的周期，这个性质可以手模得出。
而显然的一点，\(w\) 肯定为 \(v\) 的周期中最短的前缀。
那我们就可以通过对 \(v\) 做 kmp 来求出 \(w\)，再把 \(vw\) 作为新的 \(v\) 求 \(w\)，知道 \(u\) 的长度大于 \(n\)。
最后的询问就可以通过类似字符串 Hash 求解区间 Hash 值的方法，用前缀和来解决了。
时间复杂度 \(O(n+q)\)，代码如下(40pts)：
#include<bits/stdc++.h>
using namespace std;
#define LL long long
#define N 200005
char ch[N];
const LL mod=998244353;
LL t,n,q,po[N],sum[N],Next[N];
int main(){
scanf("%lld",&t);
while(t--){
Next[0]=Next[1]=0,po[0]=1;
scanf("%s%lld%lld",ch,&n,&q);
int len=strlen(ch)/2,i=1;
while(len<n){
for(;i<len;i++){
int j=Next[i];
while(ch[i]!=ch[j]&&j) j=Next[j];
Next[i+1]=(j+1)*(ch[i]==ch[j]);
}
int tlen=len-Next[len];
for(int j=0,k=len;j<tlen;j++,k++) ch[k]=ch[j];
len+=tlen;
}
for(int i=1;i<=n;i++)
po[i]=po[i-1]*10%mod,sum[i]=(sum[i-1]*10+ch[i-1]-'0')%mod;
for(int i=1,l,r;i<=q;i++){
scanf("%d%d",&l,&r);
printf("%lld\n",(sum[r]-sum[l-1]*po[r-l+1]%mod+mod)%mod);
}
}
}