AT450 A-E

link

A,B

简单按题意模拟

C

将与边缘相邻的白色连通块染黑后做bfs

D

首先先将原数列 \(A\) 对 \(K\) 取模,然后发现答案必定在离散化的数组的相邻两项之差之中，只需注意首尾即可

E

非常简单的一道题,对于 \(10^{18},fib_{87}≈1.7 \times 10^{18}\),直接处理对于这一坨每个字符的出现个数，然后分治解决awa

说我没冯的你记住了，我有的是码

#include<bits/stdc++.h>
using namespace std;
#define int long long
int pa[26][11451],pb[26][11451];//表示在前k位对应字符出现次数
int len[1145];//对应的fib值
int cnt[1145][26];//在第k项中对应字符出现次数
string a,b;
int get(int i,int k,int c){if(i==1){int aa=a.size();//兼容性的锅return pa[c][min(k,aa)];}else if(i==2){int bb=b.size();return pb[c][min(k,bb];}else{if(k<=len[i-1]){return get(i-1,k,c);}else{return cnt[i-1][c]+get(i-2,k-len[i-1],c);}}
}
int solve(int k,int c){if(k==0){return 0;}int i=1;while(len[i]<k)++i;if(i==1){i=2;}return get(i,k,c);
}
signed main(){cin>>a>>b;for(int i=0;i<26;i++){pa[i][0]=0;}for(int i=1;i<=a.size();i++){for(int c=0;c<26;c++){pa[c][i]=pa[c][i-1];}pa[a[i-1]-'a'][i]++;}for(int i=0;i<26;i++){pb[i][0]=0;}for(int i=1;i<=b.size();i++){for(int c=0;c<26;c++)pb[c][i]=pb[c][i-1];pb[b[i-1]-'a'][i]++;}len[1]=a.size();len[2]=b.size();for(int c=0;c<26;c++){cnt[1][c]=pa[c][a.size()];cnt[2][c]=pb[c][b.size()];}int cntt=2;while(len[cntt]<2e18){cntt++;len[cntt]=len[cntt-1]+len[cntt-2];for(int c=0;c<26;c++){cnt[cntt][c]=cnt[cntt-1][c]+cnt[cntt-2][c];}}int q;cin>>q;while(q--){int l,r;char ch;cin>>l>>r>>ch;int c=ch-'a';int ans=solve(r,c)-solve(l-1,c);cout<<ans<<endl;}
}

F,G明天写qwq