Luogu P4781 problem solving formula inline int FastPow(int x, int y) { if (y == 1) return x; if (!y) return 1; int tmp = FastPow(x, y >> 1) % mod; return tmp * tmp % mod * (y & 1 ? x : 1) % mod; } inline void Lagrange() { go(i, 1, n, 1) { up = down = 1; go(j, 1,
作者: 1016142506
Luogu P3834 tutorial video #pragma once #include #include #include #include #include #include #include #include #include #include&
The property of the portal in the question: For all subtrees obtained after deleting the center of gravity, the number of nodes does not exceed 1/2 of the original tree. A tree has at most two centers of gravity; 2. The sum of the distances from all nodes in the tree to the center of gravity is the smallest. If there are two centers of gravity, then the sum of their distances is equal; two trees are merged through an edge, and the new center of gravity is on the path of the two centers of gravity of the original tree; when a leaf node is deleted or added to a tree, the center of gravity can only move by one edge at most; a tree can have at most Two centers of gravity, adjacent to each other. The idea is that if you find that there is only one center of gravity, then just delete the directly connected edge of one center of gravity and add it back. If two centers of gravity are found, then if you find a direct connection point on one of the centers of gravity and not the other center of gravity, just delete the other one. How to find the center of gravity of a tree? Choose one first
原理 https://blog.csdn.net/alexfaker/article/details/90199074 模板 https://www.cnblogs.com/iloveori/p/12526461.html#%E8%A7%82%E5%89%8D%E6%8F%90%E7%A4%BA%EF%BC%9A%E8%AF%B7%E4%B8%8D%E8%A6%81%E5%9C%A8%E8%B4%9F%E6%9D%83%E5%9B%BE%E4%B8%AD%E7%86%9F%E7%BB%83%E7
Original question link https://codeforces.com/contest/1406/problem/D In the example of the idea, a=2,-1,7,3; the difference is -3,8,-4; Suppose (b[1]= x)+(c[1]=y)=a[1]; ∵b[1]=c[2]>=…>=c[n] x+(y-3)=(x-1)+( y-2)=(x+1)+(y-4)=…=a[2] ∴b[2]=xc[2]=y-3 is the optimal solution. Other solutions will lead to b[n] Or c[1] becomes larger so that the final answer is not the smallest, that is: when the difference > 0, change the difference