Educational Codeforces Round 135

Original link:


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:
This site is for inclusion only, and the copyright belongs to the original author.