Original link: https://www.shuizilong.com/house/archives/educational-codeforces-round-138/
- https://codeforces.com/contest/1728
- https://zhuanlan.zhihu.com/p/575699975
- https://zhuanlan.zhihu.com/p/575702697
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
adjustment method. Consider the decision problem first, use extended Euclidean to find the special solution of Diophantine equation ax + by = n, and then judge whether there is a set of solutions such that ax is in the range of [0, n].
Considering the optimization problem, according to the input, the non-strict convex function f can be preprocessed about ax, whose definition domain is an integer between [0, n]. The so-called non-strict is that there may be some equality in the middle, such as the maximum may be an interval,
But as you’ll see later, it’s not that big of a problem. .
The domain of the objective function of each query is a subset of the f function, centered on the particular solution, and each step is lcm(a, b), which is also a non-strictly convex function, because we have preprocessed it. The derivative of , so the extremum can be calculated by bisection on the derivative.
But we can do better, just check the functional values f(xl), f(xr) of the two points near the maximum value, specifically, assuming that we keep the right end point of the maximum value in the preprocessing stage x0,
then check xl < x0 <= xr, if it is the left endpoint,
Just check that xl <= x0 < xr. . .
#include <lastweapon/io> using namespace lastweapon; const int N = int(3e5) + 9; int a[N], b[N], x0; LL f[N]; int n; LL exgcd(LL a, LL b, LL &x, LL &y){ if (!b){ x = 1, y = 0; return a; } LL d = exgcd(b, a % b, y, x); y -= a / b * x; return d; } LL query() { LL a, b, x, y; RD(a, b); LL d = exgcd(a, b, x, y); if (n % d) return -1; x *= n/d*a; d = a/d*b; x -= ceil(max(0ll, x-x0), d) * d; x += max(0ll, x0-x) / d * d; LL z = -1; if (x >= 0) checkMax(z, f[x]); x += d; if (x <= n) checkMax(z, f[x]); return z; } void init() { RD(n); LL s = 0; REP(i, n) RD(a[i], b[i]), s += b[i]; REP(i, n) a[i] -= b[i]; sort(a, a+n, greater<int>()); f[0] = s; REP(i, n) f[i+1] = f[i] + a[i]; x0 = upper_bound(a, a+n, 0, greater<int>()) - a - 1; } int main() { #ifndef ONLINE_JUDGE freopen("in.txt", "r", stdin); //freopen("out.txt", "w", stdout); #endif init(); Rush OT(query()); }
Problem E. Cactus Wall
floor plan minimum cut
Equivalent to Dual Graph Shortest Path
The edge weight is only 01, so you can open two queues bfs() .
This article is reprinted from: https://www.shuizilong.com/house/archives/educational-codeforces-round-138/
This site is for inclusion only, and the copyright belongs to the original author.