文化课补完了，但是考试考炸了，所以来补题。
D1T1 火车站 station
实际上只需要判断从 \(x\) 能否一直向一个方向移动且每个位置能不能作为这个方向的终点站。
区间覆盖差分一下即可。
点击查看代码
int n,m,x;
int st[maxn][2],cov[maxn];
bool vis[maxn];
int main(){
freopen("station.in","r",stdin);
freopen("station.out","w",stdout);
n=read(),m=read(),x=read();
for(int i=1;i<=m;++i){
int l=read(),r=read();
st[l][0]=1,st[r][1]=1;
++cov[l],--cov[r];
}
for(int i=1;i<n;++i) cov[i]+=cov[i-1];
for(int i=x-1;i>=1;--i){
if(!cov[i]) break;
if(st[i][0]) vis[i]=1;
}
for(int i=x+1;i<=n;++i){
if(!cov[i-1]) break;
if(st[i][1]) vis[i]=1;
}
for(int i=1;i<=n;++i){
if(vis[i]) printf("%d ",i);
}
printf("\n");
return 0;
}
D2T1 过河卒 zu
不是博弈论，是博弈论暴搜。
图很小，可以压成 \(10^6\) 的状态记录三个棋子的位置，合法转移直接连边。
不好解决的问题是可能出现平局——成环，这样不能从起始状态开始搜。改成从每个结束状态开始搜，由于根据步数的奇偶性可以判断出当前是谁的回合，我们只需要拓扑转移即可。
如果一个状态当前被转移到的都是必败状态，那么一直取步数的 \(\max\)，一旦出现必胜决策可以直接入队，由于 BFS，此时步数一定最小，且在当前位置决策者一定会选这种必胜决策。也就是魔改了一下拓扑排序。
在答案处要注意的是，如果是必败状态且初始状态处于一个环中，那么会选择走环来达到不败的情况，要特判一下。（在转移过程中由于没有被完全剥出的节点不会入队，实际上也是存在不败一定选不败）
点击查看代码
int t,n,m;
char s[15][15];
pii B,R1,R2;
struct state{
pii bp,rp1,rp2;
//0->B 1->R
state()=default;
state(pii bp_,pii rp1_,pii rp2_):bp(bp_),rp1(rp1_),rp2(rp2_){}
}S[maxn];
bool opt[maxn];
int winchk[maxn];
int mp[11][11][11][11][11][11];
int tot,mark;
int dx[4]={-1,0,0,1},dy[4]={0,-1,1,0};
struct edge{
int to,nxt;
}e[maxn<<3];
int head[maxn],cnt;
int deg[maxn];
inline void add_edge(int u,int v){
e[++cnt].to=v,e[cnt].nxt=head[u],head[u]=cnt;
++deg[v];
}
queue<int> q;
int dp[maxn];
int main(){
freopen("zu.in","r",stdin);
freopen("zu.out","w",stdout);
read(),t=read();
while(t--){
n=read(),m=read();
for(int i=1;i<=n;++i) scanf("%s",s[i]+1);
B=R1=R2=make_pair(0,0);
for(int i=1;i<=n;++i){
for(int j=1;j<=m;++j){
if(s[i][j]=='X') B=make_pair(i,j);
if(s[i][j]=='O'){
if(!R1.x) R1=make_pair(i,j);
else R2=make_pair(i,j);
}
}
}
tot=0;
memset(mp,0,sizeof(mp));
for(int bx=1;bx<=n;++bx){
for(int by=1;by<=m;++by){
for(int rx1=1;rx1<=n;++rx1){
for(int ry1=1;ry1<=m;++ry1){
for(int rx2=1;rx2<=n;++rx2){
for(int ry2=1;ry2<=m;++ry2){
pii bnow=make_pair(bx,by),rnow1=make_pair(rx1,ry1),rnow2=make_pair(rx2,ry2);
if(bx>B.x) continue;
if(s[bnow.x][bnow.y]=='#'||s[rnow1.x][rnow1.y]=='#'||s[rnow2.x][rnow2.y]=='#') continue;
if(rnow1==rnow2) continue;
int sumstep=abs(B.x-bx)+abs(B.y-by)+abs(R1.x-rx1)+abs(R1.y-ry1)+abs(R2.x-rx2)+abs(R2.y-ry2);
S[++tot]=state(bnow,rnow1,rnow2),opt[tot]=sumstep&1^1,winchk[tot]=-1;
if(bnow.x==1) winchk[tot]=0;
else if(bnow==rnow1||bnow==rnow2) winchk[tot]=opt[tot]^1;
else{
if(!opt[tot]){
bool chk=1;
for(int i=0;i<3;++i){
int xx=bnow.x+dx[i],yy=bnow.y+dy[i];
if(xx<1||xx>n||yy<1||yy>m) continue;
if(s[xx][yy]!='#') chk=0;
}
if(chk) winchk[tot]=1;
}
else{
bool chk=1;
for(int i=0;i<4;++i){
int xx=rnow1.x+dx[i],yy=rnow1.y+dy[i];
if(xx<1||xx>n||yy<1||yy>m) continue;
if(s[xx][yy]!='#'&&make_pair(xx,yy)!=rnow2) chk=0;
}
for(int i=0;i<4;++i){
int xx=rnow2.x+dx[i],yy=rnow2.y+dy[i];
if(xx<1||xx>n||yy<1||yy>m) continue;
if(s[xx][yy]!='#'&&make_pair(xx,yy)!=rnow1) chk=0;
}
if(chk) winchk[tot]=0;
}
}
mp[bx][by][rx1][ry1][rx2][ry2]=tot;
// printf("%d (%d %d) (%d %d) (%d %d)\n",tot,S[tot].bp.x,S[tot].bp.y,S[tot].rp1.x,S[tot].rp1.y,S[tot].rp2.x,S[tot].rp2.y);
if(bnow==B&&rnow1==R1&&rnow2==R2) mark=tot;
}
}
}
}
}
}
// printf("%d\n",mark);
for(int i=1;i<=tot;++i) head[i]=0,deg[i]=0;
cnt=0;
for(int i=1;i<=tot;++i){
if(winchk[i]!=-1) q.push(i);
pii bnow=S[i].bp,rnow1=S[i].rp1,rnow2=S[i].rp2;
if(!opt[i]){
//move R
for(int j=0;j<4;++j){
int xx=rnow1.x+dx[j],yy=rnow1.y+dy[j];
if(xx<1||xx>n||yy<1||yy>m) continue;
if(mp[bnow.x][bnow.y][xx][yy][rnow2.x][rnow2.y]){
int nxt=mp[bnow.x][bnow.y][xx][yy][rnow2.x][rnow2.y];
if(winchk[nxt]!=-1) continue;
add_edge(i,nxt);
}
}
for(int j=0;j<4;++j){
int xx=rnow2.x+dx[j],yy=rnow2.y+dy[j];
if(xx<1||xx>n||yy<1||yy>m) continue;
if(mp[bnow.x][bnow.y][rnow1.x][rnow1.y][xx][yy]){
int nxt=mp[bnow.x][bnow.y][rnow1.x][rnow1.y][xx][yy];
if(winchk[nxt]!=-1) continue;
add_edge(i,nxt);
}
}
}
else{
//move B
for(int j=1;j<4;++j){
int xx=bnow.x+dx[j],yy=bnow.y+dy[j];
if(xx<1||xx>n||yy<1||yy>m) continue;
if(mp[xx][yy][rnow1.x][rnow1.y][rnow2.x][rnow2.y]){
int nxt=mp[xx][yy][rnow1.x][rnow1.y][rnow2.x][rnow2.y];
if(winchk[nxt]!=-1) continue;
add_edge(i,nxt);
}
}
}
}
for(int i=1;i<=tot;++i) dp[i]=0;
while(!q.empty()){
int u=q.front();
q.pop();
// printf("%d (%d %d) (%d %d) (%d %d) opt:%d winchk:%d dp:%d\n",u,S[u].bp.x,S[u].bp.y,S[u].rp1.x,S[u].rp1.y,S[u].rp2.x,S[u].rp2.y,opt[u],winchk[u],dp[u]);
for(int i=head[u];i;i=e[i].nxt){
int v=e[i].to;
if(winchk[u]==opt[u]){
//必败策略
if(winchk[v]==opt[v]) continue;
winchk[v]=opt[v]^1,dp[v]=max(dp[v],dp[u]+1);
--deg[v];
if(!deg[v]) q.push(v);
}
else{
//必胜策略
if(winchk[v]==opt[v]) continue;
winchk[v]=opt[v],dp[v]=dp[u]+1;
deg[v]=0;
q.push(v);
}
}
}
if(winchk[mark]==-1) printf("Tie\n");
else if(winchk[mark]==opt[mark]) printf("Red %d\n",dp[mark]);
else if(!deg[mark]) printf("Black %d\n",dp[mark]);
else printf("Tie\n");
}
return 0;
}
没有做出的问题在于如何处理平局以及压成状态建图搜索的简单转换。