Original link: https://www.shuizilong.com/house/archives/atcoder-beginner-contest-264/
portal
Problem E. Blackout 2
The practice of flashback and collection after offline is obvious.
Not sure if it’s online. . .
– https://twitter.com/kyopro_friends/status/1558460630847594496
Problem F. Monochromatic Path
During the game, the state was designed to be dp[2][n][m] and then the transfer write burst. . A lot of time wasted. .
Sure enough, the state needs to be dp[2][2][n][m]. . .
Problem G. String Fair
The brute force automaton dp estimates an upper bound on the length of a string, which is considered infinite if the answer is always updated.
Problem Ex. Perfect Binary Tree
Kind of like dynamic dp. . . (But this question only adds leaves without modification. For example, we all have a simple algorithm for adding leaves to find the diameter…)
Then we only need to add a leaf each time to update all the upward paths, and maintain the delta in the middle. . The depth of each upward update will not exceed log(n). . Leaves with a depth greater than this number can be skipped directly.
#include <lastweapon/number> using namespace lastweapon; const int N = int(3e5) + 9, LOGN = 20; VI adj[N]; Int f[N][LOGN], s[N][LOGN]; int p[N], d[N]; int n; void upd(int x) { int y = p[x]; d[x] = d[y] + 1; if (d[x] >= LOGN) return; Int d = f[x][0] = 1; for (int i=0;x;++i) { s[y][i] += d; d *= (s[y][i] - f[x][i]); f[y][i+1] += d; x = y; y = p[x]; } } int main(){ #ifndef ONLINE_JUDGE freopen("in.txt", "r", stdin); #endif MOD = 998244353; RD(n); cout << (f[0][0] = 1) << endl; FOR(i, 1, n) { adj[--RD(p[i])].PB(i); upd(i); Int z = 0; REP(i, LOGN) z += f[0][i]; cout << z << endl; } }
This article is reprinted from: https://www.shuizilong.com/house/archives/atcoder-beginner-contest-264/
This site is for inclusion only, and the copyright belongs to the original author.