看题戳这里
总结
时间分配：30min自习，30min t1，然后在t2,t3,t4中间反复横跳，最后一小时狂冲t3没出来，悲伤。
后来听巨佬说t3很离谱，也不知道是不是真的。
最终分数：0+50+0+0
为什么第一题挂了？为什么第一题挂了？为什么第一题挂了？为什么第一题挂了？
哦，原来是玩原神freopen注释了导致的。
解析
A. 语言
难度：橙
注意到动词只有一个，在这上面搞一搞就可以了。
本人代码能力极差，轻喷。
#include<bits/stdc++.h>
using namespace std;
int bet[30],vcnt,vpos,pd,T;
string s;
void solve(){
vcnt=vpos=0;
for(int i=1;i<=26;i++){
int opt;
cin>>opt;
bet[i]=opt;
}
vector<int> vv;
cin>>s;
for(int i=0;i<s.length();i++){
if(bet[s[i]-'a'+1]==4)vcnt++,vpos=i;
int aa=bet[s[i]-'a'+1];
if(aa==4||aa==5||aa==6||aa==7)vv.push_back(i);
if(vcnt>1){
cout<<"No\n";
return;
}
}
int e=bet[s[s.length()-1]-'a'+1];
if(e!=2&&e!=3&&e!=7&&e!=6){cout<<"No\n";return;}
if(vcnt==1)
vv.clear(),vv.push_back(vpos);
for(int i=0;i<vv.size();i++){
vpos=vv[i];
if(!vpos||vpos==s.length()-1)continue;
int d=bet[s[vpos-1]-'a'+1];
if(d==2||d==3||d==7||d==6){
cout<<"Yes\n";
return;
}
}
cout<<"No\n";
}
int main(){
// freopen("language.in","r",stdin);
// freopen("language.out","w",stdout);
ios::sync_with_stdio(0);
cin.tie(0),cout.tie(0);
cin>>T;
while(T--)
solve();
return 0;
}
B. 色球
难度：绿
链表的巧妙运用。
若无操作 3 用栈就可以解决。但这里操作 3 要求反转，所以可以用双向链表来实现。
#include<bits/stdc++.h>
#define mxn 301010
using namespace std;
struct node{
int col,num,pre,nxt;
}_list[mxn];
int n,m,head[mxn],tail[mxn],cnt;
char opt[6];
int main(){
// freopen("ball.in","r",stdin);
// freopen("ball.out","w",stdout);
ios::sync_with_stdio(0);
cin.tie(0),cout.tie(0);
cin>>n>>m;
while(m--){
int x,y,z;
cin>>opt;
if(opt[2]=='s'){
cin>>x>>y>>z;
_list[++cnt]=node{y,x,head[z],0};
if(head[z]){
if(_list[head[z]].pre)
_list[head[z]].nxt=cnt;
else _list[head[z]].pre=cnt;
}
else tail[z]=cnt;
head[z]=cnt;
}
else if(opt[2]=='p'){
cin>>x>>z;
while(_list[head[z]].num<x){
x-=_list[head[z]].num;
int lasthead=_list[head[z]].pre|_list[head[z]].nxt;
if(lasthead){
if(_list[lasthead].pre==head[z])
_list[lasthead].pre=0;
else _list[lasthead].nxt=0;
}
head[z]=lasthead;
}
_list[head[z]].num-=x;
cout<<_list[head[z]].col<<'\n';
}
else{
int u,v;
cin>>u>>v;
if(!head[u])continue;
if(head[v]){
if(_list[head[v]].pre)
_list[head[v]].nxt=head[u];
else _list[head[v]].pre=head[u];
if(_list[head[u]].pre)
_list[head[u]].nxt=head[v];
else _list[head[u]].pre=head[v];
}
else tail[v]=head[u];
head[v]=tail[u];
head[u]=tail[u]=0;
}
}
return 0;
}
C. 斐波
难度：紫-黑
首先，斐波那契数列的递推式是 \(f(n)=f(n-1)+f(n-2)\)。
设 \(g(n)=f^2(n)\)，则 \(g(n)=(f(n-1)+f(n-2))^2=g(n-1)+g(n-2)+2f(n-1)f(n-2)\)。
又有 \(2f(n-1)f(n-2)\\
=2(f^2(n-2)+f(n-2)f(n-3))\\
=(f(n-2)+f(n-3))^2+f^2(n-2)-f^2(n-3)\\
=g(n-1)+g(n-2)-g(n-3)\)
所以推出 \(g(n)\) 的递推式：
\(g(n)=2g(n-1)+2g(n-2)-g(n-3)\)
转换成矩阵：
\[\left( \begin{gathered} g(n) \\ g(n-1) \\ g(n-2) \end{gathered} \right) = \left( \begin{gathered} 2 & 2 & -1\\ 1 & 0 & 0\\ 0 & 1 & 0 \end{gathered} \right) \left( \begin{gathered} g(n-1) \\ g(n-2) \\ g(n-3) \end{gathered} \right) \]用向量表示即为：\(\overrightarrow{g_n}=A^n\overrightarrow{g_0}\)。
而对于题目中的 \(f(S) = \sum\limits_{T \subseteq S} \left[\operatorname{fib}\left(\sum\limits_{s \in T}s\right)\right]^2\)，我们也用向量表示：
\(\overrightarrow{f(S)}=\sum_{T\subseteq S}g\overrightarrow{\sum(T)} \\\)
$ f(S)$ 即为向量的第一项。
给 \(S\) 再加一个数 \(a\)，可得：
\(
\overrightarrow{f(S\cap\{a\})}=\\
\overrightarrow{f(S)}+\sum_{T\subseteq S}A^ag\overrightarrow{\sum(T)}=\\
\overrightarrow{f(S)}+\overrightarrow{f(S)}A^a=\\
\overrightarrow{f(S)}(I+A^a)
\)
归纳一下，若 \(S=\{a_1,a_2,...,a_n\}\)，则有：
\(\overrightarrow{f(S)}=\overrightarrow{g_0}\prod\limits_{i=1}^n(I+A^{a_i})\)
用该式进行暴力，期望复杂度 \(O(n^3)\)。
用线段树维护 \(\sum\limits_{i=l}^r\sum\limits_{j=i}^r\prod\limits_{k=i}^jI+A^{a_i}\)，期望复杂度 \(O(3^3q\log n)\)。
#include<bits/stdc++.h>
#define ll long long
#define mxn 100010
#define mod 998244353
using namespace std;
struct mat{
ll a[3][3]={0};
mat operator+(mat x){
for(int i=0;i<3;i++)
for(int j=0;j<3;j++)
x.a[i][j]=(x.a[i][j]+a[i][j])%mod;
return x;
}
mat operator*(mat x){
mat ret;
for(int k=0;k<3;k++)
for(int i=0;i<3;i++)
for(int j=0;j<3;j++)
ret.a[i][j]=(ret.a[i][j]+a[i][k]*x.a[k][j]%mod)%mod;
return ret;
}
};
mat quickpow(mat x,int p){
mat ret,base;
ret.a[0][0]=ret.a[1][1]=ret.a[2][2]=1;
base=x;
while(p){
if(p&1)ret=ret*base;
base=base*base;
p>>=1;
}
return ret;
}
mat I,O,A,num[mxn];
int n,q;
struct seg_tree{
mat sum,lsum,rsum,msum;
}tre[mxn<<2];
seg_tree add(seg_tree a,seg_tree b){
seg_tree ret;
ret.sum=a.sum+b.sum+b.lsum*a.rsum;
ret.lsum=a.lsum+a.msum*b.lsum;
ret.rsum=b.rsum+b.msum*a.rsum;
ret.msum=a.msum*b.msum;
return ret;
}
void push_up(int rot){
tre[rot]=add(tre[rot<<1],tre[rot<<1|1]);
}
void change(int rot,int l,int r,int k){
if(l==r){
tre[rot].sum=num[k];
tre[rot].lsum=tre[rot].rsum=tre[rot].msum=num[k];
return;
}
int mid=(l+r)>>1;
if(mid>=k)change(rot<<1,l,mid,k);
else change(rot<<1|1,mid+1,r,k);
push_up(rot);
}
seg_tree query(int rot,int l,int r,int x,int y){
if(l>=x&&r<=y)return tre[rot];
int mid=(l+r)>>1;
if(mid>=y)return query(rot<<1,l,mid,x,y);
else if(mid<x)return query(rot<<1|1,mid+1,r,x,y);
else return add(query(rot<<1,l,mid,x,y),query(rot<<1|1,mid+1,r,x,y));
}
void init(){
I.a[0][0]=I.a[1][1]=I.a[2][2]=1;
O.a[1][0]=O.a[2][0]=1;
A.a[0][0]=A.a[0][1]=2;
A.a[0][2]=mod-1;
A.a[1][0]=A.a[2][1]=1;
}
int main(){
// freopen("fipo.in","r",stdin);
// freopen("fipo.out","w",stdout);
ios::sync_with_stdio(0);
cin.tie(0),cout.tie(0);
init();
cin>>n>>q;
for(int i=1;i<=n;i++){
int a;cin>>a;
num[i]=quickpow(A,a)+I;
change(1,1,n,i);
}
for(int i=1;i<=q;i++){
int opt;cin>>opt;
if(opt==1){
int p,v;cin>>p>>v;
num[p]=quickpow(A,v)+I;
change(1,1,n,p);
}
else{
int l,r;
cin>>l>>r;
mat ans=query(1,1,n,l,r).sum*O;
cout<<(ans.a[0][0]+mod)%mod<<'\n';
}
}
return 0;
}
D. 偶数
难度：紫
有趣的字符串思维题。
首先设一个偶数字符串 \(u\) 为 \(vv\)，其新的偶数字符串必为 \(vwvw\) 的形式，其中 \(w\) 为 \(v\) 的前缀且为 \(v\) 的周期，容易证明 \(w\) 必为 \(v\) 的最小周期。
举个例子，假设 \(u=121121\)，则 \(v=121\)，且 \(w=12\)，则新的偶数字符串为 \(1211212112\)。
所以每次用 KMP 暴力求最小周期，复杂度 \(O(n+q)\)。
继续优化。我们分两种情况：
若 \(len(w)\) 为 \(len(v)\) 的因子，则字符串会变成 \(vww...w\)。
关键在于 \(len(w)\nmid len(v)\) 的情况。手推会发现 \(vw\) 的最小周期必为 \(v\)。
证明（本来想说显然的，还是写出来了）：
假设有 \(x\) 为 \(vw\) 最小周期且满足 \(len(w)\nmid len(v),len(v)>len(x)\)。
则若 \(len(w)\mid len(v)-len(x)\)，有 \(gcd(len(w),len(x))<len(x)\) 为 \(vw\) 最小周期，矛盾。
若 \(len(w)\nmid len(v)-len(x)\)，有 \(gcd(len(w),(len(v)-len(x))\ mod\ len(w))<len(x)\) 为最小周期，矛盾。
所以，若 \(s_1=v,s_2=vw\)，则 \(s_i=s_{i-1}s_{i-2}\)（看上去像不像斐波那契数列？）。
发现 \(len(v_i)\geq 2*len(v_{i-1})\)，所以每次计算 \(\log n\) 次就行了。
期望复杂度 \(O(len(u)+q\log n)\)。
#include<bits/stdc++.h>
#define ll long long
#define mxn 100010
#define mod 998244353
using namespace std;
ll T,n,q,len,fiblen[mxn];
ll f[mxn],fib[mxn],nxt[mxn];
ll bit[mxn];
ll maxn;
char s[mxn];
ll quickpow(ll a,ll x){
ll ret=1,base=a;
while(x){
if(x&1)ret=base*ret%mod;
base=base*base%mod;
x>>=1;
}
return ret;
}
void init(){
cin>>s+1>>n;
len=strlen(s+1);
for(int i=1;i<=len/2;i++)
f[i]=(f[i-1]*10+(s[i]-'0'))%mod;
for(int i=2,j=0;i<=len/2;i++){
while(j&&s[i]!=s[j+1])j=nxt[j];
if(s[j+1]==s[i])j++;
nxt[i]=j;
}
fiblen[0]=len/2-nxt[len/2],fiblen[1]=len/2;
fib[0]=f[fiblen[0]],fib[1]=f[fiblen[1]];
maxn=0;
for(int i=2;;i++){
fiblen[i]=fiblen[i-1]+fiblen[i-2];
fib[i]=(fib[i-1]*quickpow(10,fiblen[i-2])+fib[i-2])%mod;
if(fiblen[i]>=n){
maxn=i;break;
}
}
for(int i=0;i<=maxn;i++)
bit[i]=quickpow(10,fiblen[i]);
}
ll get(ll x){
ll cnt=0,ret=0;
for(int i=maxn;i>=0;i--){
if(cnt+fiblen[i]<=x){
ret=(ret*bit[i]%mod+fib[i])%mod;
cnt+=fiblen[i];
}
}
ret=(ret*quickpow(10,x-cnt)%mod+f[x-cnt])%mod;
return ret;
}
int main(){
// freopen("even.in","r",stdin);
// freopen("even.out","w",stdout);
ios::sync_with_stdio(0);
cin.tie(0),cout.tie(0);
cin>>T;
while(T--){
init();
cin>>q;
for(int i=1;i<=q;i++){
ll l,r;
cin>>l>>r;
cout<<((get(r)-get(l-1)*quickpow(10,r-l+1)%mod)+mod)%mod<<'\n';
}
}
return 0;
}