ZJOI2015 & SDOI2015 & TJOI2015 题解

TJOI2015 Day1

线性代数

【题目大意】
最大化
【题目解析】
经过推导变形,最后我们要最大化这个玩意儿
这是一个比较显然的最小割模型,当且仅当才计入贡献,一种通用的建边方法是认定即属于S集合,将代价扩大一倍,对于的情况,我们分别建立(S->i: D), (S->j: D), (i->j: D), (j->i: D),其中的系数。可以发现所有不能造成贡献的情况最后都会被减掉。对于的系数,我们可以把它和一同处理。

组合数学

【题目大意】
给出一个网格图,其中某些格子有财宝,每次从左上角出发,只能向下或右走。问至少走多少次才能将财宝捡完。此对此问题变形,假设每个格子中有好多财宝,而每一次经过一个格子至多只能捡走一块财宝,至少走多少次才能把财宝全部捡完。
【题目解析】
Dilworth定理,最小链覆盖=最长反链。
我们发现题目实质是带权的最小DAG链覆盖,反过来就是求它的最长反链。
状态转移方程

弦论

【题目大意】
求本质相/不同的第K小子串
【题目解析】
对于不同的第K小子串,实质就是在SAM构建出的DAG上路径计数;如果一个串可以算多次,相当于每个节点带的权重统计即可。

ZJOI2015 Day1

幻想乡战略游戏

【TAG】点分治树维护树的带权重心
【题解】
好厉害的题目,点分治树做树上关于链的动态修改问题大家都会,也很好想。而这却是关于整棵树的问题,有2种做法。
[我的想法]
每次动态在重心树上寻找重心,转移的时候就将当前被抛弃的部分接到转移过去的子树上,最后撤销即可。转移条件是儿子的军队和大于总军队数量的两倍。修改操作就是直接暴力将一个节点在重心树上的祖先修改对应信息。
[PoPoQQQ大爷的方法]
每次转移的时候暴力计算带权距离和,转移相似。
[点分治树的构建技巧]
相邻层之间的重心连边,对于每个重心记录祖先集合,父亲到该节点的距离,以及父亲连向该节点对应子树的入点。这些信息都可以在点剖的过程中建立。

地震后的幻想乡

【TAG】概率多项式+状压DP
【题解】
分布函数是概率密度函数的积分。由于一条边权值在[0, 1]随机分布,这个条件下求MST上的最大边的期望,我们把问题转化为,设答案大于x的为P(x),可以看作一条边的出现概率为x,整个图无法连通的概率。
如何计算这个概率呢,这是一个典型的DP,设F[state]表示当前处理的状态为state下整个图连通的概率。
最后就是这个玩意儿求积分
【相似题目】
CLJ在WC上有一道mst,只不过那题是求mst大小的期望,做法大同小异,只是积分的式子变为

诸神眷顾的幻想乡

【TAG】多串后缀自动机
【题解】
注意到只有20个叶子,我们就从每一个叶子节点出发遍历全树,建立一棵大的trie树,接着就是统计这个大trie树的子串个数了。直接上多串SAM即可,与单串自动机不同的在每次append时新节点np的len是L+1,其中L为trie中该节点的深度。最后在SAM的Parent树上统计答案,将计入答案。

SDOI2015 Round1

排序

【题目大意】
给定一个长度为的序列。通过一些操作使其升序。求操作方案数。每类操作只能执行一次,第i类是将序列分成连续块,然后交换其中两块。
【题目解析】
首先可以分析得到,操作顺序与最终结果无关。于是我们按块长从小到大的顺序考虑操作,每次将相邻2的块一一配对,如果存在一块内部不满足连续上升,记为非法块。如果有3块及以上的非法块,则当前方案必不可行。如果有1块非法块,交换后判定是否合法,如果有2块非法块,枚举所有的交换方式,检验即可。最后将操作步数的阶乘计入答案。

寻宝游戏

【题目大意】
每次动态翻转树上一个点的状态,之后询问当前活跃点组成的树的总长。
【题目解析】
考虑静态的情况,就是一棵虚树,相邻dfn的两个点的距离之和即为答案。现在每次添加一个节点,删除一个节点,可以用set维护当前活跃点集合的dfn解决。
坑点:set的end()依旧有值,该特判时还是要特判

序列统计

【题目大意】
求有多少个长度为的数列,数列中的每个数属于集合,且最后乘积模恰好为,将其结果模输出。
【题目解析】
因为题目中的是质数,所以存在原根,对于中的每个数,我们求出其在g下的指标。问题继而转化为指标的卷积了。重新定义多项式乘法,每次乘法后将相同同余类的数合并。跑快速幂即可。
坑点:对于两个模数对应2个原根,一个是算指标的小原根,一个是NTT对应的原根

星际战争

【题目大意】
将M个武器的攻击力分配给N个机器人使得总耗时最短。
【题目解析】
直接二分时间,建图SAP就好。精度开高点。
(一般题目名称和本题类似都是水题)

约数个数和

【题目大意】
简单粗暴,求
【题目解析】
回顾一维的情况,我们可以直接算每个因子被计算多少次。
还是沿用一维的思想,这里有一个巧妙的转换,显然,不同的质数肯定可以分开考虑。我们只需要考虑,它们相乘会产生个因子,而这恰好是它们的互质因子对的数量,所以我们枚举互素因子对,然后计算有多少个包含它们的对。Mobius反演后用根号优化加速。

道路修建

【题目大意】
给定的点阵,每次询问[L, R]内所有点构成的MST,或者修改相邻点边权
【题目解析】
题目类似SHOI2008 堵塞的交通。利用环切性质,每次必定切掉一条边,分类讨论用线段树维护。总共需要维护最左/右竖边权值,最左/右横边最大值,竖边条数,MST,区间边界这些信息。