AtCoder Beginner Contest 263

Original link:



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).

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

Leave a Comment