Original link: https://www.shuizilong.com/house/archives/atcoder-beginner-contest-263/
portal
Problem E. Sugoroku 3
Problem solution: Write the transfer equation first, find that the self-loop situation can be eliminated, and then it is very straight forward.
(I didn’t understand the official solution …)
#include <lastweapon/number> #include <lastweapon/fenwicktree> using namespace lastweapon; const int N = int(2e5) + 9; Int f[N]; int a[N]; int n; int main(){ #ifndef ONLINE_JUDGE freopen("in.txt", "r", stdin); //freopen("/Users/minakokojima/Documents/GitHub/ACM-Training/Workspace/out.txt", "w", stdout); #endif RD(n); REP(i, n-1) RD(a[i]); fenwick_tree<Int> T(n); DWN(i, n-1, 0) f[i] = (T.sum(i+1, i+a[i]+1) + (a[i]+1)) / a[i]; cout << f[0] << endl; }
Problem F. Tournament
dp[u][i] represents the current node u, and the winning player is the maximum score of i. Then the winning streak of i in the current round can be calculated from the height of u.
And the score of player i has nothing to do with the opponent, so i can actually not be recorded in the state, and the complexity is O(n2^n).
https://ift.tt/IVqKzu9
Problem G. Erasing Prime Pairs
Can a flowered tree handle edge weights, I’m not sure = =
So first of all, without considering the case of 1, it is a bipartite graph matching, so we can enumerate the matching multiplicity between 1, and then do it as a bipartite graph matching, this function is obviously convex, then the answer can be divided into two.
On the other hand, this convex function is very special, delta is a pattern such as {1,1,1,1,0,0,0,0,-1,-1,-1,-1}, so the optimal point can be found directly .
Problem Ex. Intersection 2
This article is reproduced from: https://www.shuizilong.com/house/archives/atcoder-beginner-contest-263/
This site is for inclusion only, and the copyright belongs to the original author.