【考试总结】2022-07-06
智力游戏
直接 \(\rm bfs\) 即可
放到普及模拟赛可能能当防 AK 题，因为不知道一个竖向木块是不是能横着扫
Code Display
const int N=15;
int a[7][7],vis[N];
int n,dir[N],len[N],c[N];
struct State{
int a[N];
bool operator <(const State &b)const{
for(int i=1;i<=n;++i) if(a[i]^b.a[i]) return a[i] >mp;
// current state,last move(id,delta)
int main(){
freopen("game.in","r",stdin);
freopen("game.out","w",stdout);
rep(i,1,6) rep(j,1,6) a[i][j]=read();
State init;
rep(i,1,6) rep(j,1,6) if(a[i][j]){
if(vis[a[i][j]]) continue;
vis[a[i][j]]=1;
ckmax(n,a[i][j]);
if(a[i][j+1]==a[i][j]){
init.a[a[i][j]]=j; c[a[i][j]]=i;
dir[a[i][j]]=1;
int tmp=j;
while(tmp<=6&&a[i][tmp]==a[i][j]) ++len[a[i][j]],++tmp;
}else{
init.a[a[i][j]]=i; c[a[i][j]]=j;
dir[a[i][j]]=2;
int tmp=i;
while(tmp<=6&&a[tmp][j]==a[i][j]) ++len[a[i][j]],++tmp;
}
}
queue >q;
q.push({init,0});
while(q.size()){
State now=q.front().fir;
int stp=q.front().sec;
q.pop();
if(now.a[1]==5){
print(stp);
vector >ans;
while(stp){
pair opt=mp[now];
char dire=' ';
if(dir[opt.fir]==1){
if(opt.sec<0) dire='L';
else dire='R';
}else{
if(opt.sec<0) dire='U';
else dire='D';
}
ans.emplace_back(opt.fir,dire,abs(opt.sec));
stp--;
now.a[opt.fir]-=opt.sec;
}
reverse(ans.begin(),ans.end());
for(auto t:ans){
printf("%d %c %d\n",get<0>(t),get<1>(t),get<2>(t));
}
return 0;
}
rep(i,1,6) rep(j,1,6) a[i][j]=0;
rep(i,1,n) if(dir[i]){
if(dir[i]==1){
for(int j=now.a[i];j<=now.a[i]+len[i]-1;++j) a[c[i]][j]=i;
}else{
for(int j=now.a[i];j<=now.a[i]+len[i]-1;++j) a[j][c[i]]=i;
}
}
for(int i=1;i<=n;++i) if(dir[i]){
int rec=now.a[i];
if(dir[i]==1){
for(int p=now.a[i]-1;p>=1;--p){
if(a[c[i]][p]) break;
now.a[i]=p;
if(mp.find(now)!=mp.end()) continue;
mp[now]={i,now.a[i]-rec};
q.push({now,stp+1});
}
now.a[i]=rec;
for(int p=now.a[i]+1;p+len[i]-1<=6;++p){
if(a[c[i]][p+len[i]-1]) break;
now.a[i]=p;
if(mp.find(now)!=mp.end()) continue;
mp[now]={i,now.a[i]-rec};
q.push({now,stp+1});
}
now.a[i]=rec;
}else{
for(int p=now.a[i]-1;p>=1;--p){
if(a[p][c[i]]) break;;
now.a[i]=p;
if(mp.find(now)!=mp.end()) continue;
mp[now]={i,now.a[i]-rec};
q.push({now,stp+1});
}
now.a[i]=rec;
for(int p=now.a[i]+1;p+len[i]-1<=6;++p){
if(a[p+len[i]-1][c[i]]) break;
now.a[i]=p;
if(mp.find(now)!=mp.end()) continue;
mp[now]={i,now.a[i]-rec};
q.push({now,stp+1});
}
now.a[i]=rec;
}
}
}
return 0;
}
区域划分
如果有两个相邻城市同颜色或者某个颜色的城市从未出现过，那么无解
否则使用 \(0\) 将环划分成若干段，两个 \(0\) 之间是 \(12121212\)
对于只有 \(1\) 个 \(0\) 的情况，可以将和 \(0\) 相邻的 \(12\) 中较远者和 \(0\) 相连，再删去中间元素变成子问题
如果某个 \(0\) 两侧不同，将其连边并删去这个 \(0\)。如果相同设为 \(1012\) 型，连两条边可以将中间 \(01\) 删去
不过还有 \(01010\) 的情况，找到后面第一个 \(2\) 再删相邻的 \(01\) 即可
删元素用链表实现
Code Display
const int N=1e5+10;
int nxt[N],pre[N],a[N],n;
inline void remove(int x){
pre[nxt[x]]=pre[x];
nxt[pre[x]]=nxt[x];
}
inline void link(int x,int y){
print(x); print(y); putchar('\n');
}
int main(){
freopen("divide.in","r",stdin);
freopen("divide.out","w",stdout);
n=read();
bool exi[3]={};
for(int i=1;i<=n;++i) exi[a[i]=read()]=1;
if(!exi[0]||!exi[1]||!exi[2]) puts("No"),exit(0);
for(int i=1;i<=n;++i) if(a[i]==a[i%n+1]) puts("No"),exit(0);
puts("Yes");
int zero=0;
for(int i=1;i<=n;++i){
nxt[i]=i%n+1;
if(i==1) pre[i]=n;
else pre[i]=i-1;
zero+=a[i]==0;
}
for(int i=1;i<=n;++i){
if(!a[i]){
if(zero==1){
while(pre[pre[pre[i]]]!=i){
link(i,pre[pre[i]]);
remove(pre[i]);
}
break;
}else{
if(a[pre[i]]!=a[nxt[i]]){
link(pre[i],nxt[i]);
remove(i);
}else{
if(a[pre[pre[i]]]+a[nxt[i]]==3){
link(pre[pre[i]],i);
link(pre[pre[i]],nxt[i]);
remove(pre[i]);
remove(i);
}
}
--zero;
}
}
}
return 0;
}
基因识别
做法很麻烦，但是复杂度保证不了，图一乐
可以一个 \(\log\) 求出来某个 \(s_i\) 在某个时刻的权值
对所有询问串 \(t\) 建立广义 \(\rm SAM\) ，让 \(n\) 个 \(s_i\) 在上面走出边，跳 \(\rm Fail\) ，保证每个串只经过每个广义 \(\rm SAM\) 上节点一次。
这部分经过的点数是 \(\Theta(\sum |s_i|\sqrt{|s_i|})\)
跳到的某个广义 \(\rm SAM\) 节点，对于在该节点结束的询问，判断 当前匹配长度是否大于询问串长度，如果是则一个 \(\log\) 计算贡献
不难发现不同的前缀在广义 \(\rm SAM\) 的匹配长度不同，所以要找每个点子树内最长匹配长度。也就是每个前缀走出边的过程是进行连边，每个前缀结束节点打标记，最后 \(\rm dfs\) 所有遍历过的节点得到每个点最长匹配长度
显然的冗余就是某个节点有大量询问串结束时每次二分很浪费。不过可以发现每个时刻的 \(s_i\) 的增加会给一个后缀内长度小于定值的询问造成贡献，也就是二维偏序。
所以询问数量大于某个阀值就将所有修改操作存下来，最后用树状数组统一处理即可
阀值设 \(500\)，过了。一开始用 “询问数量大于修改数量” 当做阀值，树状数组操作有 \(10^7\) 次
那么有没有水博客的 dalao 证明/证伪复杂度啊？
Code Display
const int N=6e5+10;
int son[N][26],len[N],fa[N],tot=1,las=1;
inline int extend(int x){
if(son[las][x]){
int q=son[las][x];
if(len[q]==len[las]+1) return q;
int clone=++tot; len[clone]=len[las]+1;
for(int i=0;i<26;++i) son[clone][i]=son[q][i];
fa[clone]=fa[q]; fa[q]=clone;
while(son[las][x]==q) son[las][x]=clone,las=fa[las];
return clone;
}
int tmp=las,np=las=++tot; len[np]=len[tmp]+1;
while(tmp&&!son[tmp][x]) son[tmp][x]=np,tmp=fa[tmp];
if(!tmp){
fa[np]=1;
return np;
}
int q=son[tmp][x];
if(len[q]==len[tmp]+1){
fa[np]=q;
return np;
}
int clone=++tot; len[clone]=len[tmp]+1;
fa[clone]=fa[q]; fa[q]=fa[np]=clone;
for(int i=0;i<26;++i) son[clone][i]=son[q][i];
while(son[tmp][x]==q) son[tmp][x]=clone,tmp=fa[tmp];
return np;
}
vector val[N];
vector tim[N];
int n,Q,opt[N];
string s[N],qs[N];
char tmps[N];
vector id[N],lim[N];
ll ans[N];
int mark[N],Time;
vector > matr[N];
int U;
struct BIT{
ll c[N];
inline void ins(int x,int v){
for(;x;x-=x&(-x)) c[x]+=v;
return ;
}
inline ll query(int x){
ll res=0;
for(;x<=U;x+=x&(-x)) res+=c[x];
return res;
}
}T;
int Mx[N];
vector virt[N],Mn[N];
signed main(){
freopen("dna.in","r",stdin);
freopen("dna.out","w",stdout);
n=read(); Q=read();
for(int i=1;i<=n;++i){
tim[i].emplace_back(0);
val[i].emplace_back(read());
scanf("%s",tmps+1);
int slen=strlen(tmps+1);
for(int j=1;j<=slen;++j) s[i]+=tmps[j];
ckmax(U,slen);
}
for(int i=1;i<=Q;++i){
opt[i]=read();
if(opt[i]==1){
scanf("%s",tmps+1);
int slen=strlen(tmps+1);
ckmax(U,slen);
las=1;
for(int j=1;j<=slen;++j) las=extend(tmps[j]-'a');
id[las].emplace_back(i);
lim[las].emplace_back(slen);
}else{
int x=read(),delt=read();
tim[x].emplace_back(i);
val[x].emplace_back(val[x].back()+delt);
}
}
for(int i=1;i<=tot;++i){
int siz=id[i].size();
Mn[i].resize(siz);
for(int j=siz-1;j>=0;--j){
Mn[i][j]=lim[i][j];
if(j+1dfs=[&](int x){
for(auto t:virt[x]) dfs(t),ckmax(Mx[x],Mx[t]),Mx[t]=0;
if(id[x].size()>500/*val[i].size()*/){
int siz=val[i].size();
ll lst=0;
for(int e=0;e=id[x].size()) break;
if(Mx[x]>=Mn[x][pos]) matr[x].emplace_back(pos,Mx[x],val[i][e]-lst);
lst=val[i][e];
}
}else{
int siz=id[x].size();
for(int e=0;eMx[x]) continue;
int pos=upper_bound(tim[i].begin(),tim[i].end(),id[x][e])-tim[i].begin()-1;
ans[id[x][e]]+=val[i][pos];
}
}
virt[x].clear();
};
dfs(1);
Mx[1]=0;
}
for(int node=1;node<=tot;++node){
U=0;
for(auto t:matr[node]) ckmax(U,get<1>(t));
for(auto t:lim[node]) ckmax(U,t);
cnt+=matr[node].size();
sort(matr[node].begin(),matr[node].end());
int siz=id[node].size(),ind=0;
for(int i=0;i(matr[node][ind])==i){
T.ins(get<1>(matr[node][ind]),get<2>(matr[node][ind]));
ind++;
}
ans[id[node][i]]+=T.query(lim[node][i]);
}
for(auto t:matr[node]) T.ins(get<1>(t),-get<2>(t));
}
for(int i=1;i<=Q;++i) if(opt[i]==1) print(ans[i]);
return 0;
}