T1
博弈+dp，设f[i][j]表示第f个人报j是否有必胜策略。
分i+1是不是同类讨论即可。
#include <iostream>
#include <queue>
#include <cstdio>
#include <cstring>
using namespace std;
const int N=5005;
int n,m,k;
bool f[N<<1][N];
int sum[N][N<<1];
int a[N<<1];
int rd() {int x;__builtin_scanf("%d",&x);return x;}
int main() {
freopen("vode.in","r",stdin);
freopen("vode.out","w",stdout);
scanf("%d%d%d",&n,&m,&k);
for(int i=1;i<=n;i++)f[i][m-1]=0,a[i]=rd();
for(int j=m-2;j>=0;j--) {
for(int i=1;i<=n;i++) {
int l=i+1;
if(l>n) l=1;
if(a[l]==a[i]){
if(sum[l][j+1]-sum[l][min(j+k,m-1)+1]>0) {
f[i][j]=1;
}
}
else {
if(sum[l][j+1]-sum[l][min(j+k,m-1)+1]<min(j+k,m-1)-(j+1)+1) f[i][j]=1;
}
sum[i][j]=sum[i][j+1]+f[i][j];
}
}
for(int i=1;i<=n;i++) {
if(f[i][0]==1) printf("%d ",a[i]);
else printf("%d ",a[i]^1);
}
}
T2
给每个点和其上下左右各连一条边，再给其上下左右的各第一堵墙连一条长度为到最近墙的距离的边，跑dij
#include <iostream>
#include <queue>
#include <cstdio>
#include <cstring>
using namespace std;
const int N=505,M=505*505*10;
struct Edge{int to,nxt,val;}e[M];
int head[N*N],ecnt,n,m,dis[N*N],leaf,ans[N*N],t[N*N<<2];
int id(int x,int y) {return (x-1)*m+y;}
void add(int bg,int ed,int val) {e[++ecnt].nxt=head[bg];e[ecnt].to=ed;e[ecnt].val=val;head[bg]=ecnt;}
bool g[N][N];
struct Node{int x,y;}S,T,dir;
int ck(int x,int y) {
return dis[x]<dis[y]?x:y;
}
void build(){memset(dis,0x3f,sizeof dis);for(leaf=1;leaf<=n*m;leaf<<=1);leaf--;for(int i=1;i<=n*m;i++) t[leaf+i]=i;}
void modify(int x,int y){dis[x]=y;x+=leaf;x>>=1;while(x)t[x]=ck(t[x<<1],t[x<<1|1]),x>>=1;}
void dij() {
build();
dis[id(S.x,S.y)]=0;
int u=id(S.x,S.y);
for(int i=1;i<=n;i++) {
for(int j=1;j<=m;j++) {
ans[u]=dis[u];
int disu=dis[u];
modify(u,0x7fffffff);
for(int k=head[u];k;k=e[k].nxt) {
int v=e[k].to;
if(dis[v]<0x7fffffff&&dis[v]>disu+e[k].val) {
modify(v,disu+e[k].val);
}
}
u=t[1];
}
}
}
int main() {
freopen("portal.in","r",stdin);
freopen("portal.out","w",stdout);
scanf("%d%d",&n,&m);
static char s[605];
for(int i=1;i<=n;i++) {
scanf("%s",s);
for(int j=1;j<=m;j++) {
if(s[j-1]=='#') g[i][j]=1;
else if(s[j-1]=='C') S.x=i,S.y=j;
else if(s[j-1]=='F') T.x=i,T.y=j;
}
}
for(int i=2;i<n;i++) {
for(int j=2;j<m;j++) {
if(g[i][j]) continue;
if(!g[i+1][j]) add(id(i,j),id(i+1,j),1);
if(!g[i][j+1]) add(id(i,j),id(i,j+1),1);
if(!g[i-1][j]) add(id(i,j),id(i-1,j),1);
if(!g[i][j-1]) add(id(i,j),id(i,j-1),1);
int tp1=i+1,tp2=i-1,tp3=j+1,tp4=j-1,minn=0x7fffffff;
while(!g[tp1][j]) tp1++;if(tp1-i<minn) minn=tp1-i,dir={tp1-1,j};
while(!g[tp2][j]) tp2--;if(i-tp2<minn) minn=i-tp2,dir={tp2+1,j};
while(!g[i][tp3]) tp3++;if(tp3-j<minn) minn=tp3-j,dir={i,tp3-1};
while(!g[i][tp4]) tp4--;if(j-tp4<minn) minn=j-tp4,dir={i,tp4+1};
add(id(i,j),id(tp1-1,j),minn);
add(id(i,j),id(tp2+1,j),minn);
add(id(i,j),id(i,tp3-1),minn);
add(id(i,j),id(i,tp4+1),minn);
}
}
dij();
if(dis[id(T.x,T.y)]!=0x3f3f3f3f)
cout<<ans[id(T.x,T.y)];
else puts("nemoguce");
}
T3
按秩合并并查集，维护一个时间即可。比可持久化并查集少log^2 n。。。
#include <bits/stdc++.h>
using namespace std;
int n,m,q;
const int N=100005;
set<int>s;
int fa[N],dep[N],t[N];
int find(int x) {return x==fa[x]?x:find(fa[x]);}
void merge(int tim,int x,int y) {
int fx=find(x),fy=find(y);x=fx,y=fy;
if(fx!=fy) {
if(dep[fx]<dep[fy])
fa[x]=y,dep[y]=max(dep[y],dep[x]+1),t[x]=tim;
else fa[y]=x,dep[x]=max(dep[x],dep[y]+1),t[y]=tim;
}
}
bool vis[N];
int main() {
for(int i=0;i<N;i++) fa[i]=i,dep[i]=0,t[i]=0x3f3f3f3f;
scanf("%d%d%d",&n,&m,&q);
for(int i=1;i<=m;i++) {
for(int j=(m-i+1)<<1;j<=n;j+=(m-i+1))
merge(i,j,j-(m-i+1));
}
int x,y;
while(q--) {
scanf("%d%d",&x,&y);
s.clear();
int tx=x,ans=0,res,flag=1;
while(x!=fa[x]) s.insert(x),x=fa[x];
while(y!=fa[y]&& s.count(y)==0){ans=max(ans,t[y]);y=fa[y];}
while(tx!=y){ans=max(ans,t[tx]),tx=fa[tx];}
printf("%d
",ans);
}
}