Original link: https://www.shuizilong.com/house/archives/educational-codeforces-round-135/
Problem D. Letter Picking
Interval game dp, state f[][], but simpler than general game dp, transition trivial.
First of all, we can bind the two rounds of operations together to transfer, as long as the state with an even length is considered, and there is no need to record what character was selected in the previous round.
It is not difficult to further conclude that the result is only likely to be a first mover win or a draw, which further simplifies the state and transition.
#include <lastweapon/io> using namespace lastweapon; const int N = int(2e3) + 9; char s[N]; bool f[N][N]; int n; int main() { #ifndef ONLINE_JUDGE freopen("in.txt", "r", stdin); //freopen("out.txt", "w", stdout); #endif Rush { n = strlen(RS(s)); REP(i, n+1) f[i][i] = 0; for(int l=2;l<=n;l+=2) { REP(i, n-l+1) { int j = i+l; bool ll = f[i+2][j] || (s[i] > s[i+1]); bool lr = f[i+1][j-1] || (s[i] > s[j-1]); bool rl = f[i+1][j-1] || (s[j-1] > s[i]); bool rr = f[i][j-2] || (s[j-1] > s[j-2]); f[i][j] = (ll && lr) || (rl && rr); } } puts(f[0][n] ? "Alice" : "Draw"); } }
Problem E. Red-Black Pepper
Problem F. Fishermen
Expense flow?
This article is reprinted from: https://www.shuizilong.com/house/archives/educational-codeforces-round-135/
This site is for inclusion only, and the copyright belongs to the original author.