CF504E Misha and LCP on Tree
题：给出一棵 n n n结点的树，每个结点上有一个字符， ( x , y ) (x,y) (x,y)表现从点 x x x到点 y y y路径上字符组成的字符串。有 q q q个查询，每个查询给出 a , b , c , d a,b,c,d a,b,c,d，求 ( a , b ) (a,b) (a,b)和 ( c , d ) (c,d) (c,d)的最长公共前缀。( n , q ≤ 300000 n,q\le300000 n,q≤300000)。
解：界说串 s s s的哈希函数为 h s ( s ) = ∑ i = 1 n ( s i − ′ 0 ′ + 1 ) ∗ b a s e i hs(s)=\sum\limits_{i=1}^n(s_i-'0'+1)*base^i hs(s)=i=1∑n(si−′0′+1)∗basei
界说 f ( x , y ) f(x,y) f(x,y)为 ( x , y ) (x,y) (x,y)的哈希值。对于每一个结点 u u u，纪录 f ( 1 , u ) f(1,u) f(1,u)和 f ( u , 1 ) f(u,1) f(u,1)。设点 s s s为 t t t的祖先，则 f ( s , t ) = ( f ( 1 , t ) − f ( 1 , f a s ) ) ∗ i n v ( b a s e d e p s − 1 ) f(s,t)=(f(1,t)-f(1,fa_s))*inv(base^{dep_s-1}) f(s,t)=(f(1,t)−f(1,fas))∗inv(basedeps−1) f ( t , s ) = f ( t , 1 ) − b a s e d e p t − d e p s ∗ f ( s , 1 ) f(t,s)=f(t,1)-base^{dep_t-dep_s}*f(s,1) f(t,s)=f(t,1)−basedept−deps∗f(s,1)同时，若 s s s和 t t t互不为祖先，求出其 l c a lca lca拆分出两条路径并采取，仍然可用上述方法 O ( 1 ) O(1) O(1)求出哈希值。
从而，对于每个查询，求出 l c a ( a , b ) lca(a,b) lca(a,b)和 l c a ( c , d ) lca(c,d) lca(c,d)，二分 ( a , b ) (a,b) (a,b)和 ( c , d ) (c,d) (c,d)最长公共前缀的长度，长链剖分求 b b b和 d d d的 k k k级祖先，判定哈希值是否相等即可，时间复杂度 O ( n l o g n ) O(nlogn) O(nlogn)。
CF505E Mr. Kitayuta vs. Bamboos
有 n n n朵花，第 i i i朵花最初高度为 h i h_i hi，天天晚上长高 a i a_i ai。天天白天可以使用 k k k次邪术，邪术选择一朵花 i i i，将其高度变为 m a x ( 0 , h i − p ) max(0,h_i-p) max(0,hi−p)。 m m m天后所有花中的最大高度最小是多少？
n ≤ 100000 ; m ≤ 5000 ; k ≤ 10 ; p , a i , h i ≤ 1 e 9 n\le100000;m\le5000;k\le10;p,a_i,h_i\le1e9 n≤100000;m≤5000;k≤10;p,ai,hi≤1e9
二分 m m m天后花的最大高度 H H H，判定 m m m天后花的高度是否都 ≤ H \le H ≤H。由 h i = m a x ( 0 , h i − p ) h_i=max(0,h_i-p) hi=max(0,hi−p)的限制，在 h i ≤ p h_i\le p hi≤p时，会浪费 p − h i p-h_i p−hi的长度，因此需要思量尽大概少的浪费长度。
问题转换：有 n n n朵花，第 i i i朵花最初高度为 H H H，天天白天长矮 a i a_i ai。天天晚上可以使用 k k k次邪术，邪术选择一朵花 i i i，将其高度增加 p p p。 m m m天后花的高度是否大于 h i h_i hi？过程中花的高度要 ≥ 0 \ge0 ≥0。每次贪心选择最快会长矮为负数的花使用邪术长高即可。
− 过 程 中 花 的 高 度 ≥ 0 的 条 件 仍 然 充 满 疑 问 中 − -过程中花的高度\ge0的条件仍然布满疑问中- −过程中花的高度≥0的条件仍然充满疑问中−
arc110F
给定 0 , 1 , . . . , n − 1 0,1,...,n-1 0,1,...,n−1的分列 P 0 P 1 . . . P n − 1 P_0P_1...P_{n-1} P0P1...Pn−1。执行交换 p i p_i pi和 p ( i + p i ) m o d n p_{(i+p_i)\bmod n} p(i+pi)modn最多 200000 200000 200000次，使得分列升序。
解：先不绝执行 p i = 1 p_i=1 pi=1将 0 0 0交换到位置 n − 1 n-1 n−1，然后把 1 , 2 , . . . , n − 1 1,2,...,n-1 1,2,...,n−1逐个交换到位置 n − 2 , n − 3 , . . . , 0 n-2,n-3,...,0 n−2,n−3,...,0（重复交换一个位置，总是得到差别的数，但由于 0 , 1 , 2 , . . . , x 0,1,2,...,x 0,1,2,...,x被排在交换位置的 1 x + 1 1~x+1 1 x+1步中，故当 a n − x − i = x a_{n-x-i}=x an−x−i=x之前不会打乱顺序）。最后，将得到一个 n − 1 , n − 2 , . . . , 2 , 1 , 0 n-1,n-2,...,2,1,0 n−1,n−2,...,2,1,0的降序分列，此时，因为 1 1 1可以自由移动，因此对于 2 , 3 , 4 , . . . , n − 1 2,3,4,...,n-1 2,3,4,...,n−1先把 1 1 1移动到对应要交换的位置，然后再举行交换。
arc109D
首先，把一个格子分成四块，每一块格子可以唯一表现一个 L L L形。
其次，观察 L L L形的移动，一个重心可以向其周围 7 7 7个位置移动（除了重心格子角的那边）。
于是可以将问题转换为重心的移动，将 L L L形转换为新棋盘中重心的坐标。观察上述移动计谋可以发现，若重心坐标为 x , y x,y x,y且 x ≠ y x\neq y x=y，则答案为 m a x ( ∣ x ∣ , ∣ y ∣ ) max(|x|,|y|) max(∣x∣,∣y∣)，否则为 ∣ x ∣ + 1 |x|+1 ∣x∣+1。
[code]#includeusing namespace std;struct node{ int x,y; bool operator=1,a=a*a%mod) if(n&1) ans=ans*a%mod; return ans;}int main(){ scanf("%d",&n); if(n==1) printf("%d\n",qpow(2,mod-2)); else { ll sum=qpow(2,n),isum=qpow(sum,mod-2); for(int i=1;i |
