ARC120 - partial solution
打的不是十分满意。所以写一个全场总结。
题意：给出串 \(S\)，定义 \({S}_i={S}[0,i-1]+{S}[i+1,n]\) 让你求出 \({S}_i={S}_j\) 的 \((i,j)\) 个数。
挺显然的在比较 \(i,j\) 时，lcp,lcs 可以直接忽略掉。
就考虑中间一段，发现这个是长度为 \(n-1\) 的 border，显然 period 是 \(1\)，也就全相等。
问题转化为有多少对 \((i,j)\) \(S(i)～S(j)\) 全相等，简单计数。
我竟然没看出来 period = 1,写的二分哈希，我是SB。
题意：每次给一行/一列染色成 C，最后问每一种颜色出现几次。
其实挺显然的，如果先染 \(x\) 列为 c，接下来在把 \(x\) 列染成别的，这样相当于没有给他染成 c，所以这么算出来每一行/列，最后一次被染色的时间，颜色。
遮掩显然了，染一列肯定能给一行带来 -1 的贡献，不管什么颜色。
简单算即可。
写麻烦了。。。。。。。
挺无聊的题目。。。。
大概就是让你将两个数位上不含 \(0\) 的正整数重新排列数位，使得 \(A+B\) 的数位的数字和最小。
显然让进位尽可能多，显然我们让进位的那些连起来不劣于不连起来，显然只要不是进位最低位，我破门只需要让 \(a_i+b_i\ge 9\) 即可。
贪心选数对 \(\ge 9\)，大概就是让 \(a_i+b_i\ge 9\) 同时最小化 \(b_i\)。这样可以说明如果只能用更小的 \(a_i\) 那么不会更优，因为当前的 \(a_i\) 被浪费了。
然后枚举 \(\ge 10\) 的最低位。。。。。完了。
我也不知道自己赛时写的有什么问题。。。。。
挺无聊的。。。。。。。。。。。。。。。。。
这个题还好。
题意：给定一棵树，让你给设定一个排列，\(p_i\) 就是点 \(i\) 的权值，使得对于任意两对点 \((x,y),(x,z)\) 满足 \(p_x<p_y \text{ and } p_x<p_z\) 或者 \(p_x>p_y\text{ and } p_x>p_z\)。
在 C 没调完时看了这个题。却卡在了最后一步组合合并上，真是个傻瓜。
一般人最先想的应该就是树dp，而不是什么容斥奇奇怪怪的，我也不知道能不能做的东西。
朴素的情感，排列很难计数，原因，并不知道那些出现过，如没有特殊性质，应该只有bitmask能较好处理。
可以大抵发现，这个题一个子树内部的状态只有最上的点有关条件。
可以看作自树独立，那么我们只不过在给子树 \(x\) 的 \(p:[1,sz_x]\) 重新在 \(P:[1,sz_{fa}]\) 中选择排列，显然相对大小不变。
根据 \(3000\) 的数据范围，谁都能猜到 \(f_{x}(i)\) 表示的是 \(x\) 子树，且 \(x\) 是第 \(i\) 大的。
想一想，树dp用子树排列理解定然是较难的，我们还是应该那合并子树理解。
现在大概就算要考虑以下 \(f_x(i),f_y(j)\) 合并会产生什么贡献。
有两种情况 \(p_x>p_y\),\(p_x<p_y\)，对称只管一边。
\([1,2,\cdots,i,i+1,\cdots sz_x]\)，与 \([1,2,\cdots j,\cdots sz_y]\) 归并。
在枚举 \(i\) 前面有几个 \(y\) 集合的。
设其为 \(k\),那么对于 \(F(k+i)\) 贡献即为 \(\binom{k+i-1}{i-1}\times\binom{sz_x+sz_y-(k+i)}{sz_x-i}\)。
前缀和优化即可。
复杂度很经典的 \(\mathcal{O(n^2)}\) 注意以下合并时候的边界。
E 现在毫无思路咕咕咕。
这个题我竟然能想到？？虽然是赛后想了好半天。。
首先，对于一个上凸的区间来说，加入我们都不取整，那么应该比较自然的能看出来那一段应该是一段直线。（一股琴生味？）
考虑四个点，如果 \(x,y,z,w\) 在一个上凸壳上。
一直操作 \(y,z\) 两个点，那会让这个凸壳越来越不凸，最终变成一条直线。
如图所示。
这里说的上凸指斜率单调减，下凸反之，斜率单调增。
到此我们我们能使一段上凸的区间变成直线，考虑对于任意一个不下凸的函数，那么一定可以找到一段上凸的。
那么考虑，我们每次将一个上凸的变成直线，这似乎就是在求下凸壳。
既然不取整的是凸壳，那么考虑下取整会让这个直线变成什么。
不难发现，就算下取整也不能让斜率不单调。
如图，如果中间那个是不取整的直线，我们不可能让他变成上面的黑色折线，而应该变成下面的紫色的折线。
所以就算是取整，一段本应该是直线的区间，也最多被分成两段折线。
显然两段斜率分别为 \(\lceil k\rceil\)，\(\lfloor k\rfloor\) 。
所以本质上我们希望两段原先的直线，现在的折线能接上必然要求 \(\lfloor k_1\rfloor\) 严格小于 \(\lfloor k_2\rfloor\)。
所以按照凸包那么下取整斜率求一求，就好了。
那么显然我们有也能知道两端斜率分别有几个点，所以暴力求一求就好了。
感觉挺有意思的，难度不知道是不是有点虚高，都虚高到了 Cu 题了。