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,区间边界这些信息。

UR#6题解

【智商锁】
【懒癌】
神题一道。
题意简化版是有一个N户人家的村庄,每户人家养有一只doge,现在每个人都已知有至少1条狗患病。他们每天早上都会出去查看其它人家的狗是否患病,且如果推断出自己家狗患病会在当天下午6点枪毙了它。人们一旦听到枪声就不再戮杀可爱的doge。请问有多少只狗死了以及开枪在哪一天。人与人之间最基本的信任呢?村民间相互是否能看见其他狗患病构成一张有向图,并且所有人都知道这一张有向图。

对于完全图,如果有K只狗患病,那么将在第K天下午这K只狗一同丧命归西。

对于任意有向图,我们令为患病集合为i时最早响枪时间。那么枚举i中的每位患病狗主人,他肯定会对自己无法看见的狗且自己狗不生病的的所有情况进行枚举,从中取得最大值,实质是最长链。即是

时间复杂度.

显然这是不能通过全部测试点的。我们寻找更加有效的多项式算法。

我们将原图的补图进行处理,将所有点数大于1的强连通分量及其出、入边删掉,这样剩下一个DAG。
对于这个DAG来说,有一些点被染上黑色,其余点是白色。每次可以将一个黑色节点洗白,且可以将与其相连的节点染黑。这个模型与原问题等价。每一次操作实质是DP中转移的一条边,而最终状态是全为0,每次操作可以染白一个黑点,操作次数最大即取得最大值,也是染黑节点数最大。

所以问题转化为一个点集在DAG中最多能够到达的点数。

第一问。算单点贡献,所有子集中只有包含能到达i的点就能计入贡献,所以i的贡献为
第二问。死狗数量等价于开枪的主人数量,如果有能到达某点i的患病狗主人在熄灭i点后才进行操作,那么先熄灭i点一定没取min,所以我们选择一个患病状态集合中,没有其他患病点能够到达的点作为起始点进行操作,对应着一个开枪的狗主人。所以最后答案为

最后用bitset压位DP可以AC。

NOI模拟17解题报告

链型网络

「問題要約」
给定一个无自环、无重边的无向图,每次加一条边或者询问有多少个点可以满足删去之后剩下的每一个连通块都是链。
「問題分析」
显然有2个度大于等于4的点无解。
那么如果所有点的度数都小于等于2,我们只需要判断每个连通块是否无环。
用并查集即可。
具体实现是当有一个点的度数大于等于3时,我们建立四个新图出来,分别去掉当前点与其邻接点。
之后判断即可。

物流

「問題要約」
给你一棵树,你可以在树上选出一些点建立Power station,建立发电站有代价K,每个不建立发电站的点的代价是一个关于到距离最近的发电站的距离的函数,且费用单增,求最小总费用。
「問題分析」
表示距离i点最近的发电站是j,i的子树中的总代价之和的最小值。

时间复杂度

花园

「問題要約」
给你一棵树,每次修改一个点的颜色或者询问路径上指定颜色的点的个数。
「問題分析」
因为树的结构不变,所以对树进行树链剖分。对于每个颜色动态开一棵线段树,在树上查询路径和即可。主席树套树状数组也可以做。
时间复杂度

天津省队互测解题报告

发生

【题意】给定一棵带权树,现有若干个有序对,每个有序对代表树上的一条路径。。求以K为起点的单源最短路。
【题解】
考虑有序对数量很少的情况。
我们将两条路径上的点划分成2个集合,再将对应边连上,就构成一个完全有向的二分图。
这样边数量是O(N^2)级别的。我们不妨虚加入一个点M,将集合的点分别连一条费用的边到M,同理将M与的每个点连一条费用的边。这样边数是O(N)的。

如果是一条链该怎么做呢?这就是本题最精彩的地方所在。
借助刚刚的思想,我们可以将一段连续的区间在线段树中拆分成log(N)个区间,再让这两个区间集相应连边即可。实现共用最低层,一棵顺着建,另一棵倒着建。最后跑SPFA就可以了。
树的做法与链大同小异,剖分一下即可。

适者

【题意】你在玩一个回合制的游戏,现有若干敌机,每个敌机均有血量和攻击输出值。每个回合你先出手,可以对敌方造成固定的伤害,当前回合所有血量大于0的家伙可以向你输出对应的伤害。请你安排最优的攻击顺序使得你收到的伤害总量最低。
【题解】
这题的贪心就是NOIP水平的。先不考虑删点的操作,不妨设,由调整法可知按照从小到大的顺序打伤害总和最小。
现在回到原问题。
如果我们每次枚举删除的两个单位,除掉他们会减少的伤害值为

这样的时间复杂度显然是不优的。
我们不妨枚举第一个被删除的对象,这个点后面所有的点都可以变为该点的决策。发现实质是维护一个凸包,并且从无穷远处有一根斜率为的直线打下来,询问最优解。用栈维护一个凸包,在上面二分最优决策值就好了。
这样非常符合CDQ分治DP的模型,直接上模板即可。

采样

【题意】
给出若干字符串,定义采样为一个字符串的最小表示,对于每个采样求有多少个其他的采样是当前采样的前缀。
【题解】
考察了对长相和谐(丑陋)函数的求导能力。
直接最小表示法后建立Trie树即可。

一些捉不起的题集锦

以后的学弟学妹可以省去找题解的烦恼。

第K大乘积

给出一个长度为N的整数序列,求在从中选取M个数的所有方案中,第K大的乘积是多少?

显然可以分选0个负数、2个负数、……、2k个负数来讨论吧。
要找一个好的方式可以使每一个方案被唯一扩展出,思考一下,我们可以平移一段连续的后缀。可以证明,这是很优秀的扩展方案。

之后就写个堆乱搞一下就行了。

最大凸包

平面上有N个点,求面积最大的一个内部不含其他点的凸包。

四方DP可以过的。
枚举底端顶点,目的是防止第一条边和最后一条边凹进去。然后F[i,j]表示 < i ,j > 是凸包最后一条边的最大面积,暴力转移即可。

激光强度调节装置

给定一无向带权图,求两两点对间不同的最大流流量。

裸的Gusfield直接上。

五彩斑斓

给定一个N * M的棋盘,现在有一个对其中每个格子的染色方案,你需要求出最少的染色次数使得能够染出给定样式的棋盘。

这题有几个性质需要注意。

第一点:至多染色N+M-1次。
第二点:将未染色的那一列作为初始条件,如果条件不满足一定没有合法方案。

证明脑补一下。这里就说一下怎么判断有无可行解,假设当前假设第x行未染色,那么第i列的染色就与Col[x,i]相同,对每个非x行的各自进行枚举,如果颜色与当前列不一样且当前行未染色,则将当前行染成该色。若当前行染色也与该色不同则无解。若当前格子无色但行或列有色无解。最后将N+M个行列建成N+M个点,当一个点所在行列染色不同时,颜色为行的颜色就加一条列到行的边,vice versa.

彩色圆环

给定一个长度为N的环,用M种颜色染色,每种颜色在每个位置均等概率出现,对于每种方案的贡献是各段长度之积。求期望贡献。

简单DP。F[i,j]表示前i个最后一段连续j个且最后一段颜色与第一段相同的期望, G[i,j]表示前i个最后一段连续j个且与第一段不同的期望。答案就是。转移就很显然了。为什么不用考虑段首段尾颜色相同的例子?我们总是可以把它平移到一种不同的方案,使得个数唯一确定。

O(N)的优化也比较可想,可以发现第二维状态可以优化。然后就没有然后了。

矩阵

给定集合,你需要分配权值,求

最小割经典模型,这题巧妙在对第一个和式的转化,两元素在相同集合有贡献比较好做,将贡献事先累加,在算割时减去即可。但是这题是当且仅当在S集合才有贡献。这该怎么搞呢?实际上把费用U double一下,S到i连U的流量,S到j连U的流量,i到j和j到i连U的流量,这样的建模显然是满足条件的。

小A的树

给定一个带点权的树,询问任意两点路径的期望and、or、xor值。

这题比较傻逼,直接按位treedp记录当前and(xor,or)值为0或1的点的个数,乱搞一下。

小B的涂色方案

你得到了一个长度为N的环,每个点你可以染上M种颜色,要求相邻2个珠子颜色不同,且M种颜色都得用上,求本质不同的方案个数。

这题比较有意思。全面考察了对Polya和容斥的运用。

首先我们发现要求M种颜色全用上这个限制很难搞,不妨放宽限制。想想要求两个相邻珠子不同。对在旋转置换下的项链,颜色肯定是一段一段重复出现的,我们只需要对这一段处理即可。因为是环,所以可以设F[i,0..1]分别表示是否与第一颗珠子同色,这个可以矩阵快速转移。思路就很清晰了,容斥颜色数。现在子问题变为有K种颜色去染长度为N的环,在各个旋转变换下不变的置换总数。可以发现旋L格循环节个数为gcd(L,N),但是枚举N铁定TLE。咋整呢?枚举N的约数D,小于等于N的与一个数gcd为D的数的个数为phi(N/D),对于循环节个数为X的染色方案数为F(X,K)。

时间复杂度

小C的填数游戏

题意较长就不简述了。

方法是维护一棵线段树,线段树节点维护的信息是一个4 * 4的状态,分别表示当前区间前段选择情况为s1,后段选择情况为s2的最优值。合并的时候分类讨论下长度为1的就行了。

疯狂赛车

给定一个折线赛道,赛道之外的地方是沙地,赛道不自交,在赛道上行驶速度为,在沙地行驶速度为,求从起点到终点的最短时间。

求导后可知一点到另一条线段的最优点,将折点间的边、点到对应边的最优点的边、一条直线上相邻点的边连接起来Dijkstra+堆即可。

剪刀石头布

给定一个竞赛图,其中有些边未定向,你需要寻找一个定向方案使得图中的三元环数量最多。

补集转化。
与其求三元环,不如求非三元环。
那么什么是非三元环呢?

因为是竞赛图,非三元只能是在任意一个(A,B,C)中,有且仅有一个点在子图中入度为2。
所以答案就是

接下来我们的任务就是使得最大就是了。给每条边定向搞一个费用流就可以了。注意到费用是凸的,直接拆边即可。