WORIA

https://codeforces.com/gym/102028 A. Xu Xiake in Henan Province   纯签到 12345678910111213141516171819202122232425262728293031#include<bits/stdc++.h>using namespace std;typedef pair<int, int> pii;int t;int main(){ ios::sync_with_stdio(false); cin.tie(0); cin >> t; while (t--) { int cnt = 0; for (int i = 0; i < 4; i++) { int u; cin >> u; if (u != 0)cnt++; } switch (cnt) { case 0:cout << "Typically Otaku" << endl; ...

https://codeforces.com/gym/102114 H. Hills And Valleys   题意：给定一个长为 1≤n≤1051\le n\le 10^51≤n≤105 的数组 AAA，0≤Ai≤90\le A_i\le 90≤Ai​≤9，要求翻转一个区间，使得新数组的最长不下降子序列最长。输出长度与翻转的区间。 dp 先假设不翻转。 设有数组 B[10]={0,1,2,3,4,5,6,7,8,9}B[10]=\{0,1,2,3,4,5,6,7,8,9\}B[10]={0,1,2,3,4,5,6,7,8,9}，则数组 AAA 的最长不下降子序列可以视为与 BBB 的特殊的最长公共子序列，特殊之处在于 AAA 的子序列中连续的相同数字可以视为一个数字。 转移方程也与普通最长公共子序列类似：原来是 dp[i][j]=dp[i−1][j−1]+1dp[i][j]=dp[i-1][j-1]+1dp[i][j]=dp[i−1][j−1]+1，现在是 dp[i][j]=dp[i−1][j]+1dp[i][j]=dp[i-1][j]+1dp[i][j]=dp[i−1][j]+1 ...

[E. The Kouga Ninja Scrolls][http://codeforces.com/gym/101955/problem/E] The story centres around nnn rival ninja clans labelled from 111 to nnn, and nn ninjas also labelled from 111 to nnn. For each ninja, the family decides his/her initial belief and affiliation of a clan. But some conflicts occur in the story, such as two young souls, facing the rivalry between their ninjas but falling in love, can change their mind and some ninjas may desert to other opposite clans. These ninjas are living i ...

https://codeforces.com/gym/102012 G. Rikka with Intersections of Paths   题意：给定一棵树，m 条路径，要选出 k 个有公共点的路径，问有几种选法。 树上差分 如果两条路径相交，那么两条路径的LCA中更深的那个一定是交点之一，也是所有交点中深度最小的。 枚举每个点 u，作为这 k 条路径的交点，那么这 k 条路径的LCA中深度最深的那个（也是深度最小的交点）一定就是这个点 u。 这样枚举每个点，仅当这点是深度最小的交点（即上述LCA）时更新答案，就不会有重复了。 必须要保证选择的 k 条路径至少有一条的LCA是点 u。 经过点 u 的路径数用树上差分得到。 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879808182838485868788899091929394959 ...

http://codeforces.com/gym/102040 F - Path Intersection   题意：给定一棵树，多次询问，每次给定 k 条路径，问有几个点被所有这 k 条路径覆盖。 树链刨分 把路径转化成 O(log⁡n)O(\log n)O(logn) 个区间，暴力做 k 次区间集合并，最终区间长度就是答案。 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116#include <bits/stdc++.h>#define rep(i, l, r) for (int i = l, i##end = r; i <= i##end ...

http://codeforces.com/gym/101991 A. Awesome Shawarma   题意：给定一棵树，问有几种添加一条边的方式，使得新图上的桥的数量在 [L,R][L,R][L,R]。新图不能有自环，可以有重边。 树上点分治 容易发现问题其实是求距离在 [n−1−L,n−1−R][n-1-L,n-1-R][n−1−L,n−1−R] 的点对个数。 这是经典的树上点分治问题。 找到重心，分割成若干棵子树，同一子树中的点对继续递归，枚举这棵树被分割前的所有点，找到不在同一子树的点对。由于每次分割后点数都变少了，所以总的点数为 O(nlog⁡(n))O(n\log(n))O(nlog(n))，由于找点对个数时还要排序，所以最终为 O(nlog⁡2(n))O(n\log^2(n))O(nlog2(n))。 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717 ...

https://codeforces.com/gym/102253 L. Limited Permutation   题意：给定 nnn，长为 nnn 的数组 l,rl,rl,r，问有几种 nnn 的排列 ppp 满足：对于每一个 iii 都有：对于任意 L,RL,RL,R，p[L...R]p[L...R]p[L...R] 的最小值为 p[i]p[i]p[i] 当且仅当 l[i]≤L≤i≤R≤r[i]l[i]\le L\le i\le R\le r[i]l[i]≤L≤i≤R≤r[i]。 题目简单来说就是：对于每一个 iii，pip_ipi​ 是 p[li...ri]p[l_i...r_i]p[li​...ri​] 的最小值，且 p[li−1]>pip[l_i-1]>p_ip[li​−1]>pi​ 且 p[ri+1]>pip[r_i+1]>p_ip[ri​+1]>pi​，问满足条件的排列数。 树上dp 首先要发现如果题目有解，那么给出的 [li,ri][l_i,r_i][li​,ri​] 一定不会交叉，只会包含。 对于每个区间，找到最小的包含它的区间， ...

https://vjudge.net/contest/436481 A - XOR   题意：给定一个数组和 K，多次询问，每次询问给定L，R，求区间 [L,R][L,R][L,R] 的子序列，满足子序列的异或和与 K 的按位或最大。输出这个最大值。 线段树+线性基 由于要与 K 按位或，所以可以不考虑 K 中为 1 的位，所以先全都去掉。问题变为求子序列的异或和最大。 要求的是最大异或和，考虑线性基。询问的是多个不同的区间，显然不能每次重新建线性基。但是也没法一边插入一边删除，所以考虑不删除，而是用几个区间拼成需要的区间。 线段树维护区间的线性基，当合并两个节点时合并这两个区间的线性基，即把其中一个的所有基插入另一个中。 询问时先用线段树拼出区间 [L,R][L,R][L,R] 的线性基，再用这个线性基求出最大异或和。 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717 ...

https://vjudge.net/contest/436638 C - Empty Convex Polygons   题意：最大空凸包模板题。 参考 https://blog.csdn.net/cdsszjj/article/details/79366813 dp 先把所有点按照极角从小到大排序，设 OOO 是最大空凸包上最下最左的点，dp[i][j]dp[i][j]dp[i][j] 表示 OijOijOij 是凸包上最后一个三角形。 枚举 OOO，枚举 i,j,ki,j,ki,j,k，则有 dp[i][j]=max⁡k(dp[j][k]+SΔOij)dp[i][j]=\max\limits_{k}(dp[j][k]+S_{\Delta Oij})dp[i][j]=kmax​(dp[j][k]+SΔOij​)，其中 OijkOijkOijk 是凸的。那么如果能够维护一个序列，使得对于已知的 O,i,jO,i,jO,i,j，序列上任意点 kkk 都满足 OijkOijkOijk 是凸的且围成的凸包中不含其它点，就可以通过在计算dp的同时记录dp的最大值，而不需要枚举 kkk，这样复 ...

https://vjudge.net/contest/439155 C - Pocky   题意：给定一个长为 LLL 的棍子，当棍子长度小于等于 ddd 时停止操作，每次操作随机选择一个位置切开，扔掉左部分，在右部分上继续操作。问期望操作次数。 积分方程 设长度为 xxx 时的期望操作次数为 f(x)f(x)f(x). 则有 f(x)=∫dxf(t) dtx+1  ⟹  f′(x)=xf(x)−∫dxf(t) dtx2  ⟹  ∫dxf(t) dt=xf(x)−x2f′(x)\begin{align} &f(x)=\frac{\int_d^x {f(t)} \,{\rm d}t}{x}+1\\ \implies &f'(x)=\frac{xf(x)-\int_d^x {f(t)} \,{\rm d}t}{x^2}\\ \implies&\int_d^x {f(t)} \,{\rm d}t=xf(x)-x^2f'(x)\\ \end{align} ⟹⟹​f(x)=x∫dx​f(t)dt​+1f′(x)=x2xf(x)−∫dx​f(t)dt​∫ ...