opentrains 1498训练记录
Petrozavodsk Winter-2017. Asia-Tsukuba 2016
2019.4.19打，2019.4.21补：
自补，由于网上貌似没人写过题解，我就写一个
A.Rearranging a sequence
一开始你有一个从$1-n$的数列，然后又$m$次操作，每次将$a_i$放到数列最前面，输出最后的数列
$n\leq 2·10^5\ m\leq10^5$
简单题，相当于求最后每个数字的位置，相当于一开始是空序列，先将$n-1$依此插入队首，然后进行那$m$次操作，那么对于每个数字$i$，考虑最后一次提拔他是在第$b_i$次，那么$[a_{b_i+1},a_{n+m}]$中有多少种不同的数字，在最终数列中就有多少个数字在$i$前面
$O(n+m)$
B.Quality of Check Digits
题意很狗
枚举题意做题。
垃圾模拟题，然而猜题意读题意很麻烦
不讲了，这题可能来源于某种工程算法
C.Distribution Center
有$n$条运载线和仓库，第$i$个仓库就是第$i$个运载线的终点，每条运载线的$x$坐标是$[0,10^5]$，有$m$个机器人，第$i$个机器人有两个属性$x_i,y_i$,表示这个机器人$x$坐标是$x_i$，你可以用它在这个$x$坐标上将$y_i$运载线上的货物换到$y_i+1$运载线的同坐标或者从$y_i+1$换到$y_i$。保证机器人$x$坐标两两不同，运载是将货物从$x=0$送到$x=10^5$的，求每个仓库可能收到多少个运载线送来的货物
$n\leq 2·10^5\ m\leq10^5,x_i\leq10^5,y_i\leq n$
$solution$:每个运载线的货物能运到的仓库是一段区间
按照机器人$x$坐标从大到小$dp$,$dp[0/1][i]$表示货物在$x_i$上的运载线$y_i$处，能到达的仓库编号区间的左端点右端点，$dp$时动态维护每个$y$上$x$坐标最小的机器人编号即可转移。把每个运载线货物能到达的一段区间的答案$+1$，普通的前缀和过程
$O(n+m)$
D.Hidden Anagrams
给定两个长度小于$4000$的字符串，求最长的公共同构子串的长度
公共同构子串：两个子串$A,B$如果能将$A$重排列变成$B$,那么称$A、B$同构
用一个$26$元组描述一个串，表示这个串中每个字母的数量，称为串的特征值，那么同构当且仅当特征值相同。
枚举长度，枚举$A、B$中的串，将特征值哈希然后在哈希表里找同构串即可，用前缀和优化便可$O(26)$计算任意长度子串的特征值的哈希
$O(26nm)$
E.Infallibly Crack Perplexing Cryptarithm
剪枝搜索，不是我喜欢的类型，不补了
F.Three Kingdoms of Bourdelot
$U=[1,sum]$,有一个定义在$U\times U$上的关系$\leq$，满足传递性和反对称性
给出$n$个文件，每个文件含有$m_i$个二元组${x_{ij},y_{ij}}$
这表示，对这个文件里的每个二元组，要么同时有$x_{ij}\leq y_{ij}$,要么同时有$x_{ij}\nleq y_{ij}$
给出$p,q\in U$,求有没有一个关系，满足所有文件的需求以及满足$p\leq q$
$sum\leq 300,n\leq1000,\sum m_i\leq10^5$
空的关系一定是合法的
但是他不能是空的，因为我们强制要求$(p,q)\in F$,下文我们设关系的集合是$F$
$F$中有$sum^2$中可能的元素，我们从$(p,q)$进行$bfs$,就表示$F$中必须有的元素，有这么几种转移：
设当前在$F$中的元素为$(a,b)$
$1.$若有$(a,b)、(c,d)$属于某个同一文件，则$(c,d)$一定属于$F$
$2.$若有$(b,c)$属于$F$，则$(a,c)$属于$F$
$3.$若有$(c,a)$属于$F$,则$(c,b)$属于$F$
$bfs$完成后，检查是否满足反对称性是否满足即可
证明：
1.对于传递性，$bfs$中有转移
2.对于文件的捆绑也有转移
$O(\sum m_i+sum^3)$
G.Placing Medals on Binary Tree
有一颗无穷满二叉树（每个点都有两个儿子），现在有一个长度为$n$操作序列，
每次找一个深度为$x_i$的点，将这个点涂黑，要求任意时刻任何黑点到根的路径上不能包含其他黑点。如果没有符合要求的点就不考虑这个操作，否则一定要做这个操作，那么最后会形成一个长度为$n$的$0/1$串，$0$表示这次操作做了，$1$表示没有做，求一个可能的字典序最小的$0/1$串
$n\leq 5·10^5,x_i\leq10^9$
设$a_i=2^{-x_i}$,那么对于一些操作，如果这些操作的$a_i$的和小于等于$1$,则这些操作可以一个不漏地操作，因此由于字典序，我们只需维护当前已选择的$a_i$的和，如果这个和加上新的$a_i$小于等于$1$则把$a_i$选上，否则不选
证明：考虑将这些$a_i$从大到小涂色，将这个树看成实数域$[0,1]$的线段树，染色时贪心地尽量走左儿子直到找到符合条件的点，易看出以上条件成立
因此：
算法1：将目前的$a_i$和写成二进制小数的形式，用平衡树维护和的每个为$1$的位置，当插入一个数时，暴力进位，由势能分析可得复杂度$O(nlogA)$
很遗憾，这个算法被卡常了，普通$set\ tle\ on\ 6$,用$unordered_\ set$在第七个点超时
算法2：还是将和写成二进制小数，这次，用平衡树维护每个连续的$1$的段，插入时考虑清楚段的分割、消除、合并。能合并一定要合并，否则复杂度不对
写了一年，WA两发，有几种坑
1.要注意$lower\ bound$到$end$指针时，也得考虑前驱元素是否需要修改
2.要注意尽量不要$erase$一个指针，因为可能出现得到指针->修改平衡树->删除原指针，但这时平衡树的结构已经变化，指针指向的元素已经不对了，正确的姿势是：得到指针->保存指针元素->$erase$这个元素
3.分类讨论签完不要漏
过了，也算是锻炼了$STL$平衡树的技巧
H.Animal Companion in Maze
给一张混合图（掺杂有向边和无向边），求最长路。同一条边不能连续经过两次
若有环输出$infinite$
$n,m\leq10^5$
先考虑所有的无向边，那么，将无向边加完后，一定是一个森林（否则有环，直接$infinite$）
这一步需要用到并查集
然后将森林中的每颗树缩成一个点，然后把有向边加进去，注意我们已经缩点，有向边的端点指缩点后的点
将这张有向图拓扑排序，如果没有拓扑序，说明有环，直接$infinite$
这一步需要拓扑排序
然后我们就按照拓扑序$dp$,就是个$DAGdp$,但是注意，我们是按照缩点拓扑序，也就是按照无向联通块的拓扑序，但我们需要求出真正从每个点出发的最长路，因此我们需要对每个联通块做树$dp$
我们得做两遍树$dp$
第一遍，考虑第一步往子树走或者走有向边出去
第二遍，考虑第一步往父亲走
记录每个点在树中的深度，无向边的路径长度可以写成树上差分的形式，而其他有向边的路径长度直接加在这颗树的点上，有一点点繁琐，就可以大力$dp$了
这一步需要树$dp$
板子已留
$O(n+m)$
I.Skinny Polygon
构造一个多边形，要求：
1.是三角形或四边形
2.点的坐标为整数
3.面积不超过$25000$
4.最小的能框住它的矩形长为$x$,宽为$y$
每个测试点$n$组数据
$n\leq10^5,x,y\leq10^9$
构造题，分类讨论：
若$gcd(x,y)\leq50000$,则找到一个点$A=(u,v)$
使得$2S_{\Delta ABC}=gcd(x,y)$即可,其中$B=(0,0),C=(x,y)$
$2S_{\Delta ABC}=xy-uv-(u+x)(y-v)=xv-uy$
简单数论可得$xv-uy=gcd(x,y)$一定存在$v\in[0,y-1],u\in[0,x-1]$的解
这个三角形即位所求
若$gcd(x,y)>50000$
设$x’=x/gcd,y’=y/gcd$，则设$A(0,0),B(x’,y’),C(x-1,y),D(x,y-1)$
$S_{四边形ACBD}=xy-\frac{1}{2}[(x-1)y+(y-1)x+x-x’+y-y’]=\frac{1}{2}(x’+y’)$
$x’,y’\leq10^9/gcd\leq20000$
这个凹四边形即位所求
J.Cover the Polygon with Your Disk
给一个凸包，和一个半径，求一个圆使得它拥有给定半径且和凸包的面积交最大
凸包点数$\leq10$,值域$\leq100$
一看这个题，数据范围好水
决策肯定可以模拟退火啊
甚至是个凸包，三分套三分肯定可以啊
三分套三分肯定更好啊，毕竟是复杂度确定正确性也确定的算法
求一个圆和凸包的面积交
1.求出所有圆和凸包的交点
2.逆时针扫，看每段弧在凸包外还是凸包内，算面积，在凸包的这段折线上随便选一个点看看在圆内还是圆外即可，因为同一段折线一定同时在圆内/外
3.特判一波两个图形完全覆盖的情况
想到这三个case
ddd说很难写就是了
复杂度$O(nlog^2A)$
K.Black and White Boxes
有$n$堆石子，第$i$堆有$a_i$个，石头是从上到下摞起来的。每个石头是黑色或白色，黑人白人玩游戏，轮流进行，黑人每次选一个黑石头，将这个石头以及所有它上面的石头拿走，白人每次选一个白石头，将这个石头以及所有它上面的石头拿走，谁不能拿了谁输。现在这$n$堆石头是候选石头堆，你要选出一些堆然后让黑人白人用这些堆玩游戏，称这样一个选择是公平的，当且仅当：
黑人先手必输，白人先手也必输
或者黑人先手必赢，白人先手也必赢
求石头数量最多的公平选择有多少个石头，注意这里是石头数量最多不是石头堆数最多
$n\leq40,a_i\leq40$，每堆候选石头用$0/1$串表示，从左到右表示从下到上的石头序列
一看就是找到$SG$函数的规律，然后折半搜索。
$SG$函数是什么呢QWQ
设：一个$0/1$串的价值$f(x)$,以$000101011$为例
1.将这个$0/1$串中的$0$变成$-1$ ->$-1·-1·-1·1·-1·1·-1·1·1$
2.找到第一个与首元素不同的元素，将它乘$2^{39}$，它的下一个元素乘$2^{38}$，下下一个乘$2^{37}$依此类推，而这个元素前面的所有元素都乘$2^{40}$，在这个数列中，首元素为$-1$，找到的第一个$1$是在第$4$位
$-2^{40}·-2^{40}·-2^{40}·2^{39}·-2^{38}·2^{37}·-2^{36}·2^{35}·2^{34}$
3.$f(x)$即为将这些数字加起来
$f(000101011)=-2^{40}-2^{40}-2^{40}+2^{39}-2^{38}+2^{37}-2^{36}+2^{35}+2^{34}$
一个局面的$SG$函数就是每堆石头的$f(x)$加起来
很奇怪吧？为什么是加不是异或？
先放结论：
对于黑方来说：若$SG$为正数，那么必赢，否则必输
对于白方来说：若$SG$为负数，那么必赢，否则必输
可知，公平选择的$SG$函数必然为$0$
证明：
我们使用数学归纳法，显然，考虑所有出度为$0$的局面，要么是空局面要么只剩一种颜色的石头，易知上述结论成立
这是个$DAG$游戏，因此按拓扑序归纳即可
由于黑白对偶，这里证明对于黑方的情况即可：
1.若现在$SG$不为正数，那么黑方必输，那么黑方一定无法将$SG$函数变为非负数(也就是白方必输的局面)
发现我们对一堆石头计算的$f(x)$是二进制价值，黑方要拿黑石头，一个黑石头上面的所有白石头产生的负贡献的和，一定不能抵消这块黑石头的正贡献，因此拿走这些石头相当于拿走了正的贡献，非正数减正数必为负数
2..若现在$SG$为正数，那么黑方必赢，那么必存在一种选择使得黑方可以将$SG$函数保持非负(也就是白方必输的局面)
这个证明比上面的难一些：
我们考虑所有的石头堆，我们找出每堆中从下到上第一个和底部石头颜色不同的石头，把这块石头下面的石头全部扔掉
剩下的每堆石头，我们看最高的那一堆石头，设这堆石头有$i$个石头
1.如果这堆石头顶部的石头是黑色，那么将这颗石头扔掉会损失$2^{40-i}$的贡献
2.如果这堆石头顶部的石头是白色，那么找到这颗石头下面第一颗黑色的石头，把它连着它上面的所有石头扔掉，也会损失$2^{40-i}$的概念
由于这堆石头是所有经过处理的石头堆中最高的，因此，所有的石头产生的贡献一定是$2^{40-i}$的倍数，因此当前$SG$为正且是$2^{40-i}$的倍数，用上面的策略扔石头，一定可以保证$SG$函数不会变成负数。
什么？你觉得为什么不能让从下到上乘$2^{40}、2^{39}······$
而非要让最下面颜色相同的一串均为$2^{40}$?
看起来用这种定义方法也可行，也能通过上面的证明的样子？
我一开始就是这么想的，然后愉快的WA4
hack：如果按照刚刚提到的这种方法，有一种情况是上面的证明没有考虑的：
最高的石头堆全是白色
这时这堆石头黑方是不能动的。。。。因此刚刚这种函数是不行的
然而，我们最开始提到的的函数就能避免这种情况，因为：
我们是将从下到上相同的一段石头扔掉后再比高度，因此，如果最高的石头全是白色，说明最高的石头高度为$0$，说明所有石头堆都是每堆只有一种颜色，否则就会出现高度$>0$的堆，当每堆只有一种颜色时，结论显然正确。
这题好有趣啊。
快乐的折半搜索即可，甚至合并的时候相加就行。
$O(n2^{n/2})$