今天是 ABC 427 的 DEF。
D
博弈，套路的设状态，令 \(dp_{i,k_1,k_2,op}\) 表示棋子在点 \(i\)，Alice 还剩 \(k_1\) 步可以走，Bob 还剩 \(k_2\) 步可以走，现在拿棋子的是 \(op\)，\(0\) 是 Alice，\(1\) 是 Bob。此时 Alice 一定赢吗。
好像其实不用再开 \(op\) 一维的。
然后对于所有的 \(dp_{i,0,0,0}\)，根据自己的字母附上值。
然后从 \((i,0,1,1),(i,1,1,0),(i,1,2,1)\) 这种顺序枚举每个点及其邻接边转移即可，时间复杂度是 \(O(KN)\) 的。足够了。
赛时被神秘 RE 卡了一会。
code
Show me the code
#define psb push_back
#define mkp make_pair
#define ls p<<1
#define rs (p<<1)+1
#define rep(i,a,b) for( int i=(a); i<=(b); ++i)
#define per(i,a,b) for( int i=(a); i>=(b); --i)
#define rd read()
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll read(){ll x=0,f=1;char c=getchar();while(c>'9'||c<'0'){if(c=='-') f=-1;c=getchar();}while(c>='0'&&c<='9'){x=(x<<3)+(x<<1)+(c^48);c=getchar();}return x*f;
}
const int N=3e5+45;
bitset<N> dp[16][16][3];
vector<int> e[N];
int n,m,k;
string s;
void init(){for(int i=1;i<=n;i++)e[i].clear();return ;
}
void solve(){cin>>n>>m>>k;cin>>s;s=' '+s;for(int i=1;i<=m;i++){int u,v;cin>>u>>v;e[u].push_back(v);}for(int i=1;i<=n;i++){if(s[i]=='A')dp[i][0][0][0]=1;else dp[i][0][0][0]=0;}for(int b=1;b<=k;b++){for(int pp=0;pp<=1;pp++){int al=b-1+pp,bb=b; int op=!(al==bb);if(op==1){for(int i=1;i<=n;i++){bool kill=1;for(int v:e[i]){if(dp[v][al][bb-1][op^1]==0){kill=0;break;}}dp[i][al][bb][op]=kill;}}if(op==0){for(int i=1;i<=n;i++){bool kill=0;for(int v:e[i]){if(dp[v][al-1][bb][op^1]==1){kill=1;break;}}dp[i][al][bb][op]=kill;}}}}if(dp[1][k][k][0]==0){cout<<"Bob"<<'\n';}else cout<<"Alice"<<'\n';return ;
}
int main(){int T;cin>>T;while(T--){init();solve();}return 0;
}
E
读完题就想到可以把推垃圾的过程想象成自己在移动，于是每次移动检测下自己相对坐标下周围 \(H\times W\) 里面还有没有垃圾，由于 \(H,W\) 很小所以怎么做都行，BFS 找最小路径即可。
注意不能移动到垃圾上，还有要找到最小的包括全部垃圾的矩形范围进行操作。
code
Show me the code
F
这种数据范围除了去想搜素和神秘 DP 之外还有一个重要的东西就是折半查找。
tbd。