Summary-Problems

Table of Contents

BZOJ [36/62]

DONE 3160 万径人踪灭   FFT manacher

题目大意

求出字符和位置都对称且不连续的序列的个数.

分析

考虑先求出字符和位置都对称的序列的个数,再用 manacher 减去连续的序列(其实就是回文串). 记 \(cnt_x = \sum_{i=0}^{x}[s_i = s_{x - i}]\), 易知普通序列的个数为: \(\sum_{i=0}^{2n}2^{cnt_x}-1\) 求 cnt 可以用 FFT 求卷积后去重.然后减去回文串的个数即可.

DONE 2086 [POI2010] Blocks   单调性

题目大意

给出N个正整数a[1..N],再给出一个正整数k,现在可以进行如下操作: 每次选择一个大于k的正整数a[i],将a[i]减去1,选择a[i-1]或a[i+1]中的一个加上1. 经过一定次数的操作后,问最大能够选出多长的一个区间,使得这个区间的每个数都不小于k. 总共给出M次询问,每次询问给出的k不同,你需要分别回答. 要求 O(nm) 完成.

分析

首先有一个结论: 如果区间 [L, R] 的平均值 大于等于 k ,那么我们可以在这个区间内进行题目所给的操作,使得每一个数都大于等于 k. 可以自己脑补.

既然是平均值,我们考虑把每一个数都减去 k ,然后求前缀和: 记 \(pre(x) = \sum_{i=1}^{x}a_i\). 那么一个区间 [L, R] 的平均值若要大于等于 k, 则要满足: \(pre(R) - pre(L - 1) \leq 0\). 我们要求满足该条件的前提下, 最大的 R - L + 1. 所以,假设 R = n, 此时最优的 L = j, 那么当 R = n - 1 时, L 必须小于 j 才能再次更新答案. 也就是说, 如果从右往左枚举 R , 那么 L 也必须 单调递减, 否则不会比之前算出的答案优. 利用该单调性即可.

DONE 1293 [SCOI2009] 生日礼物   TwoPointers 离散化

题目大意

有一些多种颜色的彩珠分布在一维空间上,要求你选出一段一维空间上的线段,使得所有的颜色都在这段线段中出现. 彩珠个数: 1000000, 颜色种数: 60.

分析

首先我们将位置离散化,然后直接 TwoPointers 即可. 具体地,首先右端点一直向右,直到包括了所有颜色;然后右端点每右移1次,就右移左端点,直到再左移就不能包含所有颜色为止. 由于要离散化,复杂度 O(nlogn).

DONE 1098 [POI2007] 办公楼biu   补图 bfs 链表

题目大意

给你一个图,要求你把它的结点分成多个集合,使得任意两个不在同一集合的结点都有连边.

分析

考虑在补图上操作.如果补图上有两个点有连边,那么原图上他们就必须在同一集合,因为原图上他们没有连边. 进一步可以得到: 原图的集合对应着补图中的联通块. 考虑 bfs .从一个点出发,找到和自己不直接相连的点,然后将它们入队,重复该操作,直至队空.这样就能把与这个点相连的所有点拓展出来. 但这样复杂度会萎.因为一个点可能会被在同一联通块内的多次访问. 我们可以建链表.如果确定链表上的某个点和当前点在同一联通块,则将它入队,同时在链表中删去该点即可.

DONE 1083 [HNOI2009] 梦幻布丁   链表

题目大意

这里有很多种颜色的布丁排成一行,要你实现两种操作: 1.把1种颜色的布丁全部改为另一种颜色; 2.询问有多少段颜色; 布丁数量为 n (\(n <= 10 ^ 5\)), 颜色种数为 Color (\(Color <= 10 ^ 5\))

分析

容易发现的是,颜色个数会越来越少. 进一步分析,如果我们认为同一颜色的布丁为一个集合,改颜色的实质便是合并两个集合. 用启发式合并即可.至于询问,在修改颜色的同时检查一下有没有和前后的颜色合并即可.

DONE 1150 [CTSC2007] 数据备份   链表 贪心

题目大意

一维空间上有 n 个点,要取 k 对点,满足没有点被多次取且每对点之间没有其余的点. 对于第 i 对点, 记 dis(i) 为这两个点坐标差的绝对值, 要求最小化 \(\sum_{i=1}^{k} dis(i)\).

分析

我们可以考虑贪心. 假如我们删掉一对点 u, v (u < v), u 的前一个点为 last, v 的后一个点为 next, 并且把代价累加进了答案. 有一种可能会使解变劣: last 与 u 配对, v 与 next 配对出现在了最优解中.显然这是有可能的. 所以我们还要支持撤销到这种情况. 记 点 i, j 配对的代价为 dis(i, j), 则我们认为 last 可以和 next 配对, 且代价 dis(last, next) 为 dis(last, u) + dis(v, next) - dis(u, v). (之所以要减去 dis(u, v), 是因为我们已将 dis(u, v) 累加进了答案.) 正确性在于: 此时, dis(last, next) >= dis(u, v). 我们可以将点 1..n 连成一条链, 然后用堆实现寻找 dis(u, v) 最小的点对 (u, v). 找到后, 将 dis(u, v) 累加进答案, 在链表中删去 (u, v) (这意味着 last, next 相连), 堆中删去点对 (last, u), (v, next), 加入点对 (last, next), 代价如上述. 取 k 次即可. 由于 堆 要删除,建议用 set 实现.

DONE 2151 种树   链表 贪心

题目大意

给你一个长度为 n 的数列,该数列首尾相接形成环形,要你选出 m 个不相邻的数,最大化这 m 个数的元素和. 要求 O(mlogn) 的时间复杂度.

分析

和 BZOJ1150 类似的做法.也是要堆 + 贪心然后支持撤销.我们用堆选出最大的元素. 如果我们选出了 a(u), 那么 a(u-1) 和 a(u+1) 将不可选.由于堆贪心的性质,当同时选 a(u-1), a(u+1) 出现在解中时,贪心的解会变劣. (如果只选 a(u+1) 或 a(u-1), 那就不会比只选 a(u) 更优,所以不必考虑这种情况) 所以,我们删除序列中的 a(u-1), a(u+1) (在堆中也要删除), 将 a(u) 的权值改为 a(u-1) + a(u+1) - a(u), 表示选 a(u-1) 和 a(u+1), 放弃之前的 a(u). 删除可以用链表实现.堆可以用 set 代替,便于删除.

DONE 3750 [POI2015] Pieczęć   链表

水题不解释

DONE 4385 [POI2015] Wilcze doły   TwoPointers

题目大意

给定一个长度为 n 的序列 \(a_{1..n}\), 你有一次机会选中一段连续的长度不超过 d 的区间,将里面所有数字全部修改为 0 . 请找到最长的一段连续区间,使得该区间内所有数字之和不超过 p .

分析

可以使用 TwoPointers 解决.显而易见的是,如果区间 [L, R] 是当右端点为 R 时最长的区间,那么当 R 递增时, L 不递减. 问题在于我们选定要删除的区间是哪一段.记 \(pre(x) = \sum_{i=1}^{x} a_i\), 则我们要删除 \(pre(i) - pre(max\{i-d, 0\})\) 取到最大值时的 i. (\(i \in [L, R]\)) 由于 i 的取值范围限制, 我们用单调队列即可.

DONE 3772 精神污染   点分治

题目大意

给定一棵 n 个结点的树和树上的 m 条路径,求这m条路径中任选两条不同的路径时其中一条包含另一条的概率是多少. n, m <= 1e5.

分析

多路径问题,考虑点分治. 在点分治结构中,我们只考虑 经过根结点 的路径包含了多少条路径. 显而易见的是, 所有被包含的路径都会出现在当前的点分治结构中,所以不会漏算. 我们把被包含的路径分为两类:

  1. 经过根结点的路径
  2. 不经过根结点的路径

注意到,对于不经过根结点的路径,只有当它被一条来自根的链完全包含时才会累加贡献,因为所有经过根的路径都能拆成两条来自根的链.这个遍历1次点分治结构就行了. 对于经过根的路径,假设是路径 u -> v, 只要路径的两个端点分别在以 u, v 为根的子树中, 路径 u -> v 就会被包含. 考虑 Dfs. 由于遍历到某个结点后, 在回溯到该结点之前,该结点子树中的每一个结点都会被遍历一次. 这可以解决其中的一个端点.如果说这个结点是路径 u -> v 中的结点 u, 那么回溯之前, u 的子树都会被访问. 只要子树中存在路径的另一端点在 v 的子树中,就应该累加贡献. 容易想到用线段树维护子树信息.处理一下 DFS 序就可以用 区间加,单点查询 来累加贡献.回溯到结点 u 时去除贡献即可. 由于只需要单点查询,可以将线段树改为树状数组,用差分完成区间加减.

DONE 2521 最小生成树   最小割

题目大意

Secsa 想知道对于某一条无向图中的边 (a, b), 至少需要多少次操作可以保证 (a, b) 边在这个无向图的最小生成树中. 一次操作指: 先选择一条图中的边 (u, v), 再把图中除了这条边以外的边, 每一条的权值都减少 1.

分析

首先所有其他边权值减小 1 就相当于自己的权值增加 1. 而我们要求所有 a 到 b 的路径上的最大边大于 (a, b) 的权值. (可以对应一下 kruskal 的过程) 不妨给每条边一个新边权 \(w_i = max\{w(a, b) + 1 − w_i, 0\}\) 然后做一遍最小割就完了. 我们可以认为当某条边边权小于 w(a, b) 时, 这条边可以走, 那么我们的目的就是使得 a, b 不联通. 不联通并保证最优 就对应着 最小割. 割边就是在最优方案中把权值增加到了 w(a, b) + 1 的边.

DONE 3732 Network   LCT

题目大意

给出一个带权的无向图,k个询问,每次询问两点之间的所有路径上的最大边的最小值. n,m,k <= 30000.

分析

构出最小生成树,可知最大边的最小值一定是在最小生成树上的(最小生成树一定是最小瓶颈生成树).直接查询路径上的最大边权即可. 可用 LCT 实现.

DONE 2303 [APIO2011] 方格染色   DSU

题目大意

有一个n * m的网格,每个格子里可以放入0或1,要求每个2 * 2的格子里0和1的个数都为奇数. 有k个格子中的数字是已经确定的. 现在要求满足要求的染色方案数. n, m, k <= 1000000.

分析

我们自己随手画几个,发现一个性质: 对于相邻的行, 要么是奇数列的互不相同而偶数列相同,要么是偶数列的互不相同奇数列相同. 我们利用这个性质,来限制第一行的颜色. 注意到对于两个奇偶不同的列,它们从第1行到最后1行的颜色的异或值是交替的. 而对于奇偶相同的列,它们在同行的异或值是恒定的. 所以,如果在已给定的格子中如果有同行的,那么我们就可以利用它们颜色的异或值和行号来确定第1行这两列的颜色的异或值. 这样我们就把所有的限制转到了第1行.在第1行,我们每确定某一列的颜色,所有与它已经确定了颜色的异或值的列都会确定颜色.不妨认为此时这两列有连边. 那么,填第1行的方案数就是 pow(2, {联通块个数}). 但是, 如果第1行的某些位置已经确定,则要消掉这些行的贡献. 还有,答案是什么? 注意到有些行是空行, 将数量记为 x (不包括第1行), 则答案还要乘上 pow(2, x).

DONE 3626 LCA   LCA 路径交

题目大意

给出一个n个节点的有根树,q次询问,询问编号在[l, r]间的节点与z的LCA的深度和. n,q <= 50000.

分析

考虑LCA深度的实质.对于结点 u, v, 其 LCA 的深度就是 u 到根的路径 与 v 到根的路径 的交 的长度. 我们发现, 对于同一个询问, 结点 z 到根的路径是固定的. 所以可以将每一个结点到根的路径上的所有结点的权值+1, 每次询问 z 到根的点权和. 这可以用链剖实现. 编号的限制怎么解决? 我们将结点按编号先后算贡献, 然后将询问分为 [1, l), [1, r], 在处理到 l - 1 和 r 时算一下即可.

DONE 3694 最短路   LCT

题目大意

题目给出一个n个点m条边的无向图,n个点的编号从1~n,定义源点为1. 定义最短路树如下:从源点1经过边集T到任意一点i有且仅有一条路径,且这条路径是整个图 1 到 i 的最短路径,边集 T 构成最短路树. 给出最短路树,求对于除了源点1外的每个点i,求最短路,要求不经过给出的最短路树上的1到i的路径的最后一条边.无法到达则输出 -1.

分析

既然不能经过给出的最短路树上的某一条边,对于某一结点 u, 它能怎么到达源点?

  1. 从 u 经过一条非树边到达结点 v(结点 v 不在 u 为根的子树中), 从 v 沿着树边到达源点;
  2. 从 u 经过树边到达 u 为根的子树中的结点 v, v 经过一条非树边到达结点 w(结点 w 不在以 u 为根的子树中), 从 w 沿着树边到达源点.

不妨枚举两种情况中的非树边, 发现对于每一条非树边 (u, v) , 能够经过它的点是 u->v的树上路径上的所有点,但不包括 LCA. 这可以拆成两条链. 这样我们维护数据结构给链上结点取最小值即可.

DONE 2127 happiness   最小割

题目大意

高一一班的座位表是个n*m的矩阵,经过一个学期的相处,每个同学和前后左右相邻的同学互相成为了好朋友. 这学期要分文理科了,每个同学对于选择文科与理科有着自己的喜悦值,而一对好朋友如果能同时选文科或者理科,那么他们又将收获一些喜悦值. 作为计算机竞赛教练的scp大老板,想知道如何分配可以使得全班的喜悦值总和最大.

分析

其实就是让我们把点分为两类: 一类选文科, 一类选理科. 不妨考虑最小割: 与 S 相连的选文科, 与 T 相连的选理科. 首先把所有的喜悦值加起来, 然后用 Dinic 找出最小割, 使得 S 到 T 不联通. 考虑当某一个人选文科时, 喜悦值会减少多少. 显然是 选理科时的喜悦值. 对源点连一条容量为 选理科时的喜悦值 即可. 理科同理. 但是, 怎么处理两个人同时选某一科的情况? 记两个人在网络流中的结点编号为 u, v, 同时选理科的喜悦值为 x, 同选文科为 y, 如果两个人都选文科, 那么就会损失 x 的喜悦值, 不妨将 S 到 u, v 的流量分别加 x / 2. 同选理科同理. 那如果 u 选文科, v 选理科怎么办? 不妨连一条 u 到 v 的边, 边权设为 x / 2 + y / 2, 表示如果 v 不选文科, 而 u 选, 就必须割掉这条边, 否则 S 可以到达 u 然后通过这条边 到达 v. u 选理科, v 选文科同理.

DONE 2957 楼房重建   分块

题目大意

有 n 栋楼房在一个二维平面上. 第 i 栋楼房可以用线段 (i,0)-(i,Hi) 表示. 最开始楼房的高度全为 0, m 次操作,每次把第 xi 栋楼房的高度修改为 yi, 并询问在 (0,0) 处可见楼房数量. 1 <= xi, n, m <= 100000 , 1 <= yi <= 109

分析

不妨把高度和位置相除得到斜率, 转化为有多少个元素满足大于在它前面的所有元素. 考虑分块. 对于每一个块, 如果能知道块左端点以前的最大元素的值, 并在事先预处理出哪些元素满足大于在它前面的块内元素, 然后在这些元素中二分即可得到对答案的贡献. 然后再用块内元素更新最大元素的值, 帮助下一个块计算贡献. 从左到右计算每一个块的贡献即可. 注意边界. 高度为 0 的楼房其实是不算的.

DONE 1452 [JSOI2009] Count   树状数组

二维树状数组水题, 不解释.

DONE 3339 Rmq Problem   线段树

题目大意

给你一个长度为 n 的数列 A, 要求处理 q 个询问, 每个询问用 (l, r) 表示, 意为询问 \(mex(\{A_l, A_{l + 1}, A_{l + 2}, ... , A_{r}\})\). 其中, mex(S) 表示满足 "不属于 S 集合" 的最小自然数. n, q <= 2 * 10 ^ 6

分析

不妨考虑 mex 值的变化. 对于区间 [l, r] 和 [l + 1, r], 我们可以发现, 如果下一个和 A(l) 相等的元素是 A(p), 当满足 r < p 时, [l + 1, r] 的答案为 min{ mex[l, r], A(l) }, 否则就为 mex[l, r]. 因此, 我们可以将所有询问按 l 排序, 然后维护一个指针, 按照上述约束对区间取 min, 用线段树完成; 但是我们要预处理 mex[1, 1], mex[1, 2], … , mex[1, n]. 从后往前扫一遍即可.

DONE 2324 [ZJOI2011] 营救皮卡丘   费用流

题目大意

给你一个无向图, 边有权. 一开始一共有 K 个人在 0 号点. 每个人可以独立地在边上移动. 任何人若想要到达 i, 必须有人到达过 i − 1. 要求到达 N 号点, 并且花费代价最小.

分析

注意到对于任何一个人, 如果在它的行走路径上, 结点 \(u_1, u_2, u_3, ... , u_{cnt}\) 都是第一次被访问的, 那么对于其中的任意两个结点 \(u_i, u_j\), 若满足 \(u_i < u_j\), 那么访问 \(u_i\) 的时间必须早于 \(u_j\). 而且, 只要每一个人都满足上述条件且所有的结点都被访问, 那么就一定能构造出一组解. 预处理出 dis(u, v), 表示只经过结点编号小于 v 的结点, 从 u 到 v 的最短路. 对于每一个人的路径, 我们只保留第一次被访问结点, 删除其他结点. 利用这个路径模型建模即可. 不妨拆点, 一个表示第一次被访问, 一个表示从这里出发. S 连所有表示 "从这里出发" 的结点, 其中费用为 0, 结点0的流量为 k, 其余为 1 (流量表示结点在整个路径模型中总共出现了多少次) T 连除结点 0 以外的所有表示 "第一次被访问" 的结点, 费用0, 流量 k, 表示结点在必然被访问; (最大流的性质)

"从这里出发" 的结点 u 向所有编号大于自己的 "第一次被访问" 的结点 v 连边, 费用为 dis(u, v), 流量为 inf. 这是因为这个人可以等待所有结点编号大于 u 小于 v 的结点都被访问后再出发, 所以费用应为 dis(u, v). 而如果最优解中那些等待被访问结点有被这个人访问的, 此处的流量就不会从 u 流向 v. (最小费用的性质)

DONE 1937 [SHOI2004] MST 最小生成树   KM

题目大意

给你一个图和这个图的一棵生成树,你有两种操作:

  1. 将一条边的边权加1
  2. 将一条边的边权减1

要使得这棵生成树成为原图的最小生成树之一. 输出至少需要多少次操作.

分析

如果把在生成树上的边认为是树边, 其余的认为是非树边, 那么树边的边权肯定是减小, 非树边的边权肯定是增加. 由于非树边的存在, 非树边会和树边形成环. 若要保证这棵树是最小生成树, 那么非树边必须是环上最大的边(之一). 对于环上任一一条树边, 假设其边权为 w1, 边权减少量为 d1, 环上非树边的边权为 w2, 边权增加量为 d2, 则要满足: w1 - d1 <= w2 + d2, 即 d1 + d2 >= w1 - w2. 其中 d1, d2 非负. 注意到最后得到的式子, 就是 KM 算法中松弛量的条件: \(Lx_i + Ly_j >= w_{ij}\). 所以将每条边拆成两个点, 分属 KM 算法中二分图的两侧, 然后将限制作为连边即可. 由于要非负, w1 - w2 < 0 时不连边.

DONE 2734 [HNOI2012] 集合选数   状压DP

题目大意

输入 n, 要你求出集合 {1, 2, 3, … , n} 的所有子集中, 有多少个满足以下条件: 如果元素 x 在该集合中, 那么 2 * x, 3 * x 不在该集合中.

分析

考虑将限制连边: x 向 2x, 3x 连边, 则有: 1 2 3 4 6 9 8 12 18 27 ……….. 其中每个元素向它 下面 和 下面的右边 的元素连边. 我们注意到, 极限情况下, 每一层的元素个数 和 这一层的层数 相等. 由于最左端的元素以指数级增长, 对于 n = 100000, 层数也不会超过 log2(100000) ~= 17. 状压即可. 限制的话, 用位运算处理一下即可.

DONE 2732 [HNOI2012] 射箭   二分

题目大意

平面直角坐标系上的射箭游戏. 我们 射出的箭 的路径是 经过原点的抛物线. 所有的靶子都是 平行于 y 轴的线段, 以 (x, yl, yr) 的形式给出, 表示靶子是连结 (x, yl), (x, yr) 的线段. 每一个靶子都有一个编号. 如果能一箭射中所有编号小于等于 x 的靶子, 就认为过了第 x 关. 求最多能过多少关. 靶子数 <= 100000.

分析

能过多少关是可以二分的. 我们现在要判断的就是给你很多靶子, 能否一箭射中. 我们的任一一个限制条件都可以写为: yl <= ax2 + bx <= yr, 即 yl / x <= ax + b <= yr / x. 这就变成一次函数的问题了. 这个也可以二分. 复杂度 O(nlog2(n)). 事实上, 这些不等式可以用半平面交来表示, 我们只要看半平面交是否为空即可. 复杂度 O(nlogn).

DONE 2756 [SCOI2012] 奇怪的游戏   二分图 dinic

题目大意 给你一个 n*m 的矩阵, 你可以给矩阵中相邻两个位置上的数同时 +1. 求出使所有位置上的数都相等至少需要多少次操作.

分析

考虑网络流. 如果说我们知道把数字变为多少, 其实是很好做的. 假设把数字变为 D. 利用网格图的二分图性质, 将矩阵二分染色后, 相邻的位置颜色必然不同, 连边即可, 表示这两个元素可以同时 +1. 增加数值的上限用连向源和汇的流量限制住即可.

但是我们不知道 D 是多少. 如果 n * m 是偶数, 显然可以二分. 如果 n * m 是奇数, 那么染色后一种颜色肯定会比另一种多一个元素, 而且所有数字都相等时也是一样: 此时, 元素的值就是两种颜色的元素和 之 差. 而我们的操作不改变两种颜色的 元素和 之 差, 所以可以求出唯一可能的 D.

连向源点和汇点的弧都满流时有解.

DONE 1189 [HNOI2007] 紧急疏散   拆点 dinic

题目大意

发生了火警,所有人员需要紧急疏散!假设每个房间是一个N*M的矩形区域.每个格子如果是'.',那么表示这是一块空地;如果是'X',那么表示这是一面墙,如果是'D',那么表示这是一扇门,人们可以 从这儿撤出房间.已知门一定在房间的边界上,并且边界上不会有空地.最初,每块空地上都有一个人,在疏散的时候,每一秒钟每个人都可以向上下左右四个方向移动一格,当然他也可以站着不动.疏 散开始后,每块空地上就没有人数限制了(也就是说每块空地可以同时站无数个人).但是,由于门很窄,每一秒钟只能有一个人移动到门的位置,一旦移动到门的位置,就表示他已经安全撤离了.现在 的问题是:如果希望所有的人安全撤离,最短需要多少时间?或者告知根本不可能.

分析 '每一秒钟只能有一个人移动到门的位置' 暗示着拆点. 将所有的点按时间拆成多个点, 此时人移动时不仅是位置上的移动, 同时也是时间的移动. 按照这个思路建模即可, 容量也很显然.

DONE 1061

DONE 1563 [NOI2009] 诗人小G   决策单调性

题目大意

给你常数 L, P 和 n 个元素 \(w_i\) , 要你将它分为连续的几组, 每一组都有一个不协调度, 如果从元素 l 到元素 r 都被分为了一组, 则该组的不协调度为 \(\left| -L + r - l + \sum_{i=l}^{r} w_i \right| ^ P\). 要求最小化总的不协调度并输出. 如果该值大于 1e18, 按无解的格式输出. n <= 1e5.

分析

我们设 dp(i) 表示 对 元素1 到 元素i 分组时最小的总不协调度. 则有 dp 方程: \(dp(i) = \min_j\{dp(j - 1) + \left|-L+i-j+\sum_{k=j}^{i}w_k\right|^P\}\) 方程中的 求和 可以用前缀和预处理. 朴素 DP 显然是 O(n2) 的. 如果我们记 g(i) 为 使得 dp(i) 取到最小值时的 j, 打表可以发现 g(i) 是递增的. 这样我们就可以用决策单调性优化了. 具体地, 我们用一个队列来记录到目前为止, 从小到大的每一个元素更新哪一段是最优的. 由于 g(i) 是递增的, 所以这些段也都是连续的. 当我们要更新 元素i 时, 我们不停地弹队头, 直至 元素i 被队头所能更新的最优区间包含. 更新完后, 我们要将 元素i 更新的最优区间入队. 我们检查队尾元素. 如果该元素更新的最优区间中, 最靠前的那一个元素也不如 元素i 优, 由于 g(i) 递增, 所以队尾元素将不存在更新的最优区间. 出队. 否则, 我们通过二分找出分界点 k, k 以前的用队尾元素更新, k 以后的用 i 更新. 这个把队尾的更新区间改一改就行了. 有可能我们的出队操作会导致队列为空, 此时直接将 k 设为 i + 1 即可. 然后 [k, n] 作为元素 i 更新的最优区间入队. 由于要二分, 复杂度 O(nlogn).

另外, 由于最终的答案可能爆 long long, 不妨用 long double 完成所有运算.

DONE 4173

题目大意

记 S(n, m) 为满足 \(m \mod k + n \mod k \geq k\) 的所有整数 k 组成的集合. 输入 n, m, 请输出 \(\varphi(n) \times \varphi(m) \times \sum_{k \in S(n, m)} \varphi(k)\). 答案对 998244353 取模.

分析

易知 \(\sum_{k \in S(n, m)} \varphi(k) = n \times m\). 所以输出 \(\varphi(n) \times \varphi(m) \times nm\) 即可. \(\varphi(n)\) 什么的按定义暴力求即可.

DONE 2669

题目大意

有一个 n*m 的整数矩阵, 其中的元素为 1 到 n*m 的排列. 如果一个格子比所有相邻的格子都小 (八联通), 那么称这个格子为局部极小值. 给出所有局部极小值的位置,你的任务是判断有多少个可能的矩阵. 1 <= n <= 4. 1 <= m <= 7.

分析

由于 n,m 的限制, 局部极小值最多只有 8 个. 我们考虑 从小到大往矩阵中加入元素, 由于最多只有 8 个极小值, 我们可以状压DP. 但是这样会不可避免地将 产生了新的局部极小值的方案 也计算进去. 这个我们暴力枚举产生的新的局部极小值, 容斥一下即可.

DONE 2330

差分约束系统裸题.

TODO 4237

TODO 2001

TODO 1095

TODO 4556

DONE 4558 方   正方形统计

题目大意

上帝把我们派到了一个有N行M列的方格图上, 图上一共有 (N+1)*(M+1) 个格点, 我们需要做的就是找出这些格点形成了多少个正方形(换句话说, 正方形的四个顶点都是格点). 但是这个问题对于我们来说太难了, 因为点数太多了, 所以上帝删掉了这 (N+1)*(M+1) 中的K个点. 既然点变少了, 问题也就变简单了, 那么这个时候这些格点组成了多少个正方形呢?

\(N, M \leq 10^6, K \leq 2 \times 10^3\), 答案取模.

分析

我们不妨补集转换, 计算有多少个正方形的顶点包括了被删掉的点. 但是, 这些正方形的顶点可能被多个被删掉. 所有的可能是 1, 2, 3, 4. 不妨考虑容斥, 因为计算恰好有多少个顶点被删掉的正方形并不方便.

首先计算至少一个顶点被删掉的正方形的个数. 多个顶点被删掉的正方形会被重复计算. 由于正方形可以是倾斜的, 我们要考虑怎样有效计算正方形的个数.

对于每一个方格中的正方形, 无论它是否倾斜, 都有且只有一个不倾斜的外接正方形.
而对于一个正方形, 如果其边长为 x, 那么它有 x 个内接正方形. 从 0 到 x-1 可以对应这个正方形的每一个内接正方形, 同样也可以对应到这个内接正方形的四个顶点. 由于是内接, 所以内接正方形的四个顶点都在这个正方形的边上.
我们利用这个特点, 枚举某个被删掉的点所影响的正方形的不倾斜的外接正方形的个数, 显然和影响的正方形的个数是相等的. 由于影响的条件是在这个外接正方形的边上, 所以实际上相当好算.
不妨枚举在正方形上,下,左,右的哪条边上, 然后再枚举一下边长, 然后计算一下有多少个这样的不倾斜的外接正方形即可. 枚举边长那里可以用等差数列优化.

至少两个, 三个, 四个顶点被删掉的正方形个数相当好算, 对每两个被删掉的点判一下就好了. 可能要离散化一下.

至于总的正方形个数是多少, 可以参照 "计算至少一个顶点被删掉的正方形的个数" 里的做法.

TODO 3932 任务查询系统   可持久化

TODO 3053 The Closest M Points   KD树

TODO 2391 Cirno的忧郁

DONE 3456 城市规划   分治FFT 生成函数 多项式求逆

题目大意

输出 n 个有标号的点的无向联通图的个数.

分析

我们记 g(n) 为 n 个有标号的点的无向图个数, f(n) 为 n 个有标号的点的无向联通图的个数, 则有: \[g(n) = \sum_{i=1}^{n} f(i) g(n-i) \binom{n-1}{i-1}\] 上式可以理解为是在图不一定联通时枚举节点1 所在的联通块的大小. 转换得: \[\frac{g(n)}{(n-1)!} = \sum_{i=1}^{n} \frac{f(i)}{(i-1)!} \times \frac{g(n-i)}{(n-i)!}\] 发现很像卷积的形式. 分别记 \(\frac{g(n)}{(n-1)!}\), \(\frac{f(i)}{(i-1)!}\), \(\frac{g(n-i)}{(n-i)!}\) 的生成函数为 H(x), F(x) G(x), 则有: \[H(x) = F(x)G(x)\] 所以: \[F(x) = H(x)G^{-1}(x)\] 这个多项式求逆即可.

DONE 4011 [HNOI2015] 落忆枫音   DAG DP

题目大意

给你一个 n 个节点的 DAG, 要你输出在给这个 DAG 加一条指定的从 x 到 y 边后, 以节点1 为根的树形图有多少个. 保证加边之前入度为 0 的点只有节点1. 加边可能形成重边或自环.

n <= 100000. 对 1e9+7 取模.

分析

假如加边以后仍是 DAG, 记 \(d(x)\) 为节点 x 的入度, 方案数显然是 \[\prod_{u=2}^{n} d(u)\] 如果不是 DAG, 那么显然有多的方案算进去了. 我们记 S(u, v) 为所有从 u 到 v 的路径所组成的集合, 则我们只需减去 \[\sum_{S \in S(x, y)} \prod_{u \neq 1, u \notin S} d(u)\] 这个可以用 DP 求.

DP初值 \(dp(y) = \prod_{u \neq 1, u \neq y} d(u)\).
我们记 \(dp(v) = \sum_{S \in S(v, y)} \prod_{u \neq 1, u \notin S} d(u)\), 然后转移得到 dp(x), 减去即可.

注意 y=1 时要特判. 因为 y 不需要入边, 这条边是废的.

TODO 4012 [HNOI2015] 开店

3720 Gty的妹子树

DONE 2124 等差子序列   bitset

题目大意

给你一个长度为 n 的排列 \(A_{1..n}\), 要你判断是否存在 \(1 \leq p_1 < p_2 < p_3 \leq n\), 使得 \(A_{p_1}, A_{p_2}, A_{p_3}\) 顺次组成了一个等差数列 (公差可以为负). 多组数据, \(n \leq 10000\), 数据组数 \(T \leq 7\).

分析

我们不妨枚举 \(p_2\), 然后就是判断是否存在 \(p_1, p_2\), 使得 \(A_{p_1} - A_{p_2} = A_{p_2} - A_{p_3}\). 不妨枚举 \(A_{p_1}\), 则只要判断是否存在 \(A_{p_3} = A_{p_1} - A_{p_2} \times 2\). 如果我们开一个桶记录 \(1..p_2-1\) 中哪些数字出现过, 在开一个桶记录 $p2+1..n$中哪些数字出现过, 那么我们对于每一个 \(p_2\) 就可以 \(O(n)\) 枚举. 不过这个枚举显然可以用 bitset 优化, 所以总复杂度就是 \(O(\frac{n^2T}{32})\). 不过听说可以用 BIT + HASH 做到 \(O(n \log n)\).

TODO 4009 接水果

TODO 3551 [ONTAK2010] Peaks加强版

DONE 4010 [HNOI2015] 菜肴制作

题目大意

给你一个图, 要你对其拓扑排序, 使得编号小的节点在拓扑序中的位置尽可能靠前. 不能拓扑排序输出无解.

分析

太弱了 2333… 如果有解一定是拓扑图.

考虑拓扑序中的最后一个元素. 它一定是所有没有出度的节点中编号最大的. 我们把这个点放到拓扑序的最后一个, 从图中去掉这个点, 然后递归考虑. 然后发现这就是对反图做字典序最大的拓扑排序… 这个用堆搞一搞就行了.

DONE 4013 [HNOI2015] 实验比较

题目大意

给你 \(n\) 个变量, 这些变量的值有可能相等. 给定一些变量之间的大小关系或相等关系, 形如 \(A < B\) 或 \(A = B\) 的形式保证对于一个变量, 它一共只会在等式右边出现 1 次. 让你求有多少种不同的大小关系.

\(n \leq 100\).

分析

其实可以把问题化简: 现在有两组互不相同的变量, 已知组内变量的大小和相等关系 (即已知有多少种不同的取值), 但是不知道组和组之间的大小关系. 让你求出两组变量共有 1, 2, 3, .. , n 种不同取值时, 大小关系可能有多少种. 这个组合数搞一搞.

由题目条件可知, 假设我们把相等的变量当作一个变量, 那么当存在合法方案时, 限制必然成树形结构. 由于信息合并时枚举子树大小的总复杂度是 \(O(n^2)\) 级别的, 加上还要枚举两组变量共有多少不同取值, 总复杂度为 \(O(n^3)\).

TODO 1564 [NOI2009] 二叉查找树

TODO 2436 [NOI2011] NOI嘉年华

TODO 2055 80人环游世界

TODO 2502 清理雪道

TODO 3698 XWW的难题

TODO 3876 [Ahoi2014] 支线剧情

TODO 3529 [Sdoi2014] 数表

TODO 2728 [HNOI2012] 与非

TODO 4775 网管

TODO 1023 [SHOI2008] cactus仙人掌图

TODO 4768 wxh loves substring

TODO 2298 [HAOI2011] problem a

4771 七彩树

TODO 2733 [HNOI2012] 永无乡

TODO 3571 [HNOI2014] 画框

TODO 3572 [HNOI2014] 世界树

TODO 2006 [NOI2010] 超级钢琴

HDU [5/11]

DONE 3466 Proud Merchants   sort 背包

题目大意

每个物品有三个属性: \(p,q,v\), 分别表示:价格,购买该物品时钱数的下限(不同于价格),得到的价值. 现在给你这些物品和你当前的钱数,要求最大化得到的价值.

分析

其实稍微分析一下的话,我们会发现,选物品的顺序如果不同,能选进来的物品可能也不同. 举个例子:对于两个物品 \(\{p_1, q_1\}, \{p_2, q_2\}\), 先选物品1再选物品2的最小初始钱数: \(max\{q_1, p_1+q_2\}\) 先选物品2再选物品1的最小初始钱数: \(max\{q_2, p_2+q_1\}\) 显然在很多情况下都会不相等嘛…

圣人告诉我们:先选 \(q_i - p_i\) 较大的物品. 至于理由? … 假设我们确定选一些物品,看看在什么情况下需要的初始钱数最少. 不显然的是,把 \(q_i - p_i\) 先放最少; 显然的是, 把 \(q_i - p_i\) 后放最多;

其实讲不太清.详情见:http://debug18.com/solution-to-hdu3466/

DONE 5181 numbers   DP 

题目大意

给你一个序列和一些限制,要你求满足限制的前提下,把元素依次入栈,所有可能的出栈序列. 每个限制用 <A,B> 表示, 意为 A 必须早于 B 出栈. 序列长度为 n (\(n \leq 300\)), 限制个数为 m (\(m \leq 90000\)).

分析

先不考虑限制,设 dp(l,r) 表示将第 l 个到第 r 个元素依次入栈,所有可能的出栈序列. 考虑枚举最后一个出栈的元素 i ,这样就不会有算重的问题. 显然,如果元素 i 要最后出栈,那么元素 [l, i - 1] 会全部早于元素 i 出栈. 这是一个独立的子问题. 同时,在元素 i 入栈后,直到元素 [i + 1, R] 全部完成出栈后,元素 i 才会出栈. 这又是一个独立的子问题. 所以,我们有 DP 方程: \[dp(l,r) = \sum_{i=l}^{r} dp(l, i - 1) * dp (i + 1, r)\] 我们假定对于 l > r, dp(l, r) = 1.

如果有限制? 我们可以把限制用矩阵表示,我们只要保证 不存在 以下三种限制即可:

  1. 元素 [i + 1, R] 中有元素要求早于元素 [L, i - 1] 中的某一元素出栈;
  2. 元素 i 要求早于 [i + 1, R] 中的某一元素出栈
  3. 元素 i 要求早于元素 i 出栈 (这也算限制…)

出现上述任意一种情况,就不转移了. 注意第三种情况如果出现, dp(i, i) = 0.

DONE 5435 A serious math problem   数位DP

题目大意

记 f(x) 为 x 各数位的异或和,如 f(1234) = 1 ^ 2 ^ 3 ^ 4. 给你两个数A,B,要你求 \(\sum_{i = A} ^ {B} f(i)\). \(A,B \leq 10^{100000}\).

分析

A,B 这么大, f(x) 的定义又是数位的异或和,那用数位DP应该比较合适. 我们记 dp(i, j) 为: 从0到 $10i - 1$的这些数中,有多少数的异或和在二进制的第 i 位为 1. 我们考虑的就是:枚举最高位 i. 相当于忽略最高位后,所有的数的异或和又异或上了 i. 如果 i 的二进制上的某一位为 1, 那么原来这一位为 0 的会变为 1 , 1 会变为 0. 否则, 该位不会发生变化. 按照上述思路求出所有的 dp(i, j) 并协助计算答案即可.用数位 DP 统计答案时也是用这个思路.

DONE 4661 Message Passing   树形DP 拓扑序

题目大意

有N(N<=1000000)人,他们的信息流通呈树形结构,每个人都有一个独一无二的信息,现在他们想知道所有人的信息,然后他们的信息就开始流通了. 每一个时刻,有且仅有一个人将自己所知道的信息全部都告诉另外一个人.现在希望流通次数尽量少,使所有人都知道所有人的信息. 当然这不是你的任务,你的任务而是求出流通次数尽量少的情况下,有多少种方案满足条件.

分析

可以观察到一个贪心的性质: 最优的方案一定是先选出一个点,然后所有的信息向这个点汇集,汇集完后再向四周扩散. 考虑枚举这个点,那么我们就以这个点为根,求出树的 拓扑序 的个数. (这里的拓扑序是指: 对于序列中的任意结点,其父亲结点都在自己前面) 如果当前子树的根为 x, 记以 o 为根的子树的拓扑序个数为 f(o), 子树大小为 size(o), 则有: \[f[x] = \prod_{i} f(i) \times \frac{(size(x) - 1)!}{\prod_{i} size(i)!}\] 其中 i 为 x 的子结点.

至于避免枚举根, 我们以任意结点为根, 先 DFS 一遍求出以每个结点为根的子树的方案数及其他信息, 再 DFS 一遍, 对于每个结点,把所有不在自己子树中的结点视为以父亲结点为根的一棵子树,把父亲结点也当作自己的子结点, 从父亲结点将这棵 "子树" 的信息传过来.

TODO 5780

TODO 4985 Peach Blossom Spring

TODO 3124 Moonmist

TODO 5909 Tree Cutting

DONE 4333 Revolving Digits   ExKMP

题目大意

给你一个数字 N, 你每次可以在十进制下将 N 的最后一位移到第一位, 然后就可以得到一个新的数字. 要你分别输出有多少种以这种方式生成的数比 N 小, 和 N 相等, 比 N 大.

\(N \leq 10^100000\).

分析

其实是个字符串问题…

不妨把 3 个要求的值记为 \(ans_1, ans_2, ans_3\).

考虑将字符串倍长后枚举每个位置暴力匹配, 当出现不相同时判断一下是大还是小. 但显然该位置与原串的最长公共前缀比较长的时候复杂度会爆炸. 不妨计算出每个位置与原串的最长公共前缀, 这样就可以直接判断第一个不一样的位置了.

可以用 EXKMP 来解决.

值得注意的是, 题目问的是多少种数字, 所以我们要去重. 考虑重复的时候会发生什么. 显然当且仅当原串是以一个串重复多次得到的时候会重复. 如果s是重复了 X 次得到的, 那么 \(ans_1, ans_2, ans_3\) 就会是正确答案的 X 倍. 由于和 N 相等的数字种数显然只有 1 种, 所以用上面的方法做出来的 \(ans_2\) 必然等于 X. 所以直接 \(ans_1, ans_2, ans_3\) 都除以 \(ans_2\) 就可以得到正确答案了.

TODO 5293 Tree chain problem

TODO 5079 Square

YALIOJ [0/1]

TODO 45718 数据结构

CFGym [1/1]

DONE 100548G The Problem to Slow Down you   回文树

题目大意

对于 2 个串 A,B, 定义 \(f(u, v, p, q) = [A_{u..v} = B_{p..q}][A_{u..v} = A_{v..u}]\), 求 \(\sum_{u} \sum_{v} \sum_{p} \sum_{q} f(u, v, p, q)[u \leq v][p \leq q]\).

备注 \(A_{u..v}=A_{v..u}\) 表示该串为回文串。

分析

其实就是:对于在两个串中都出现了的回文串,统计在 \(A\) 串和 \(B\) 串中的出现次数,两者相乘即是对答案的贡献。 考虑使用回文树。先插入 \(A\) 串,把所有回文树中的结点的出现次数算出来并保存到一个数组中,然后插入一个在两个串中都没有出现的字符,再插入 \(B\) 串。 对于每一个结点,原来出现的次数就是 \(A\) 串中的出现次数;出现次数之差就是 \(B\) 串中的出现次数。相乘后累加到答案中即可。注意会爆 int.

POJ [2/6]

DONE 3740 Easy Finding   DLX

DONE 3162 Walking Race   TwoPointers

题目大意

给你一个长度为 n 的序列和一个常数 m ,要你找出满足最大值和最小值之差小于等于 m 的最长的区间.要求 O(n) 完成.

分析

考虑单调性.假如我们枚举右端点 R ,对每一时刻求出满足要求的前提下最长的区间 [L, R].注意到,当 R 递增时, L 不递减. 对于某一个 L, R, 我们只要知道 [L, R] 的极大极小值,就可以判断是否合法. 更妙的是,如果我们从左往右枚举右端点,那么左端点如果因不合法而要移动,也只能往右移! 那么,区间的极值可以用单调队列维护,因为 L, R 的移动方向只能往右.

TODO 1637   Dinic

题目大意

混合图的欧拉路径判定.

分析

欧拉路径的条件是:

  1. 图联通.
  2. 所有点的入度,出度都相等 或 有一个点入度比出度大1, 有一个点出度比入度大1, 其他的入度等于出度.

首先给所有无向边任意定向. 然后将点分为两类: 入度大于出度的; 出度大于入度的. 这是一个不错的二分图模型. 我们保留原图中的无向边, 考虑将一条增广路认为是这条路上所有的无向边的方向取反, 则起点处的入度-1, 出度+1, 终点处入度+1, 出度-1. 按这个思路建模即可. 不过这道题其实只要求判欧拉回路… 如果是欧拉路径, 如果没有欧拉回路, 我们找到任意两个入度出度之差为奇数的节点, 在他们之间添加一条无向边(当然也要先任意定向), 然后再做一遍网络流. 如果依然无解, 那就的确无解.

TODO 1811

TODO 1282 庆典的日期

题目大意

给你 p 个大小为 n 的置换 G(0), G(1), G(2), … , G(n-1), 要你求出最小的 x 使得 G(0 \pmod p) * G(1 \ pmod p) * G(2 \pmod p) * … * G((x-1) \pmod p) 为 置换 (1)(2)(3)(4)…(n-1)(n). n, p <= 200.

分析

TODO 3525 Most Distant Point from the Sea

内心求成旁心了…

CodeVS [1/1]

DONE 3269 混合背包   多重背包

题目大意

多重背包, \(N\) 为所给物品种数, \(M\) 为初始容量, \(S_i, W_i, V_i\) 分别表示第 i 种物品的数量, 价值, 体积. 要求 \(O(NM)\) 求解.

分析

二进制拆分可以做到 \(O(NM\log{M})\). …… T飞了! 考虑无限背包的实现过程.为什么无限背包可以那样玩? 无限背包的实质是:对于一个状态 \(dp_i\) ,如果物品的体积是 \(V\), 价值为 \(w\), 那么对于 \(kV + i\) ( \(k\) 为整数),其刷表更新方程是: \[dp_{kV + i} = \max\{dp_{kV + i}, dp_i + kw\}\] 反过来,填表更新的方程则是: \[dp_i = \max\{dp_{i},dp_{i-kV}+kw\}\] 我们来比较一下 \(i-V\) 的 DP 转移方程: \[dp_{i-V} = \max\{dp_{i-V},dp_{i-V-kV} + kw\}\] 我们发现,任意两个决策的价值差没有改变! 而差可以判断决策的优劣了!直接取最优的? 等等…还有一个限制:如果物品数量为 \(S\), 要满足 \(k \leq S\)… QAQ…这样的话就只能维护单调队列来做了… 我们按 \(\mod V\) 的结果分类维护即可.

CF [3/13]

DONE 700C Break Up

题目大意

给你一个无向图, 边有权值. 要你删去最多两条边, 使得 S 到 T 不连通, 且删去的边的边权和最小. 点数为 N, 边数为 M, 边权为 \(w_i\). \(N \leq 10^3 , M \leq 3 \times 10^4 , 1 \leq w_i \leq 10^9\)

注意 图可能不联通; 有重边.

分析

不妨先以 S 为根, 把生成树弄出来. 首先考虑删去一条边的情况, 此时删去的那条边一定是 T 走到 S 的那些树边, 并且一定是桥. 然后对于删去两条边的情况, 其中一条也一定是上面所说的树边. 不妨枚举这条边, 然后再对新图做 “删去一条边” 的判断即可. "删去一条边"的判断: 求出所有的桥,判断 S, T 是否分属桥所连的两个联通块. 时间复杂度 O(NM).

TODO 364E Empty Rectangles

TODO 30E

出了点边界问题, 因此花了较长的时间处理.

DONE 739E Gosha is hunting

题目大意

这里有一些猎物, 对每一只猎物, 你可以用箭射, 也可以用刀砍, 但规定同种武器不能对同一猎物多次使用. 现在告知你猎物的数量, 箭的数量, 刀的数量, 每一只猎物被箭射死的概率和被刀砍死的概率, 我们将策略定义为事先确定每一个武器对谁使用, 然后发动捕猎. 请输出最优策略下期望能杀死多少猎物. 猎物个数 <= 2000.

分析

显然可以DP. DP(i, j, k) 表示对于前 i 个猎物, 使用 j 把箭, k 把刀, 最优策略下期望能杀死多少猎物. 似乎是 \(O(2000^3)\) 的, 但有效状态只有约 \(6*10^8\) 种. 只要不枚举无效状态, O2下是可以接受的. 2s 左右.

TODO 736C Ostap and Tree

TODO 286E Ladies’ Shop

TODO 300D Painting Square

TODO 438E The Child and Binary Tree

TODO 504E Misha and LCP on Tree

DONE 739D Recover a functional graph

题目大意

当一个有向图的所有的点的出度都为1时, 从一个点出发沿着唯一的出边往前走是一定会走到一个环上去的 (可能是自环). 我们记 \(precircle_i\) 为节点 i 到达某个在环上的节点最少需要走多少条边, 记 \(circle_i\) 为节点 i 能走到的那个环的点数.
特殊地, \(precircle_i\) 为 0 时, 节点 i 在环上.
允许自环, 即 \(circle_i = 1\).

现在, 给你所有点的 \(precircle_i\) 和 \(circle_i\) 的值. 但是, 有些值可以是任意的, 用 -1 表示. 请你构造出一个满足所给条件的图.
如果有多个解, 输出任意一个即可.

分析

乍一看似乎很简单. 事实上, 真正的难点在于那些 -1. 如果输入没有 -1, 显然可以直接构造.

如果有 -1 的话, 虽然问题变复杂了, 但是仍可以解决.

首先, 找出哪些长度的环是一定存在的并算出它们至少会有几个这样长度的环. 构成这些环是需要节点的.
我们将所有的必有需求用节点表示出来. 比如, 如果需要一个长度为 x 的环, 那么我们新建 x 个节点, 表示这些位置需要有节点 "任职"; 如果需要一个到长度为 x 的环的距离为 y 的节点, 我们新建 1 个节点, 表示必须存在一个 \(precircle_i = x, circle_i = y\) 的节点.
这个可以用二分图匹配实现. 将这些表示需求的点同满足要求的点连边即可.

问题在于, 有些点是 "不确定的". 由于只有 "必有的需求" 是有节点表示的, 因此这些 "需求不确定" 的节点可能没有被匹配. 但是, 虽然值可以任意, 如果没有被匹配, 它们仍然不一定找得到一个合法的位置.

对于 \(precircle_i=-1, circle_i \neq -1\) 的节点是比较容易的, 因为上一步一定会保证存在大小为 \(circle_i\) 的节点, 所以可以将 \(precircle_i\) 设为 1, 前继设为环上任意一个节点即可.

对于 \(precircle_i \neq -1, circle_i = -1\) 的节点, 如果 \(precircle_i\) 为所有 \(precircle\) 的最大值, 那么情况就会很尴尬, 因为前面的做法可能不能满足这个点的 "需求". 可是环的大小又不确定, 所以最好枚举一下 \(precircle_i\) 最大的那个节点的 \(circle_i\) 应该确定为多少. 这会新增一些 "需求", 把它们加入到二分图中即可. 只要\(precircle_i\) 最大的那个节点能满足要求, 那么容易证明这一类点一定存在一种方案使其满足要求.

对于 \(precircle_i = -1, circle_i = -1\) 的, 让它形成一个自环就好了.

输出方案应该就不是问题了.

TODO 741D Arpa’s letter-marked tree and Mehrdad’s Dokhtar-kosh paths

题目大意

给你一棵树, 每条树边上都有一个字母, 要你对于每一个节点求出在它的子树中最长的一条路径, 满足将这条路径上的字母按某种顺序排列后可以组成一个回文串.

节点个数 n <= 500000.

分析

我们考虑用数据结构维护每个节点的子树内的所有路径.

TODO 354D Transferring Pyramid

TODO 55D Beautiful numbers

UOJ [1/1]

DONE 33 树上GCD   暴力 DP 启发式合并

题目大意

给你一棵 n 个结点的树, 我们定义 d(u,v) 为结点 u, v 的树上距离, 定义 lca(u,v) 为 结点 u, v 的最近公共祖先, 定义 f(u,v) 为 gcd(d(u, lca(u,v), d(v, lca(u,v))), 对于 1…n-1 中的每一个数i, 求出有多少点对 (u,v) (u<v) 满足 f(u,v) = i 并依次输出. u <= 200000

分析

我们注意到, 我们可以通过容斥计算答案以消除 gcd 的干扰. 具体地: \[ans(i) = \sum_{u,v, u \textless v} [i|d(u, lca(u,v))][i|d(v, lca(u,v))] - \sum_{i|j, j \textgreater i} ans(j)\] 现在考虑如何统计 上式中的被减数. 如果考虑暴力做法, 有两种显然的思路:

  1. 记录 dp(u,d) 为以 u 为根的子树中, 到 u 的距离为 d 的倍数的结点的个数. 然后就可以在DFS时 通过子树合并来更新 ans(d) 了.
  2. 记录 dp(u,d) 为以 u 为根的子树中, 到 u 的距离为 d 的结点的个数. 然后在子树合并时对于每一个 d 枚举 d 的倍数 来更新 ans(d).

两种做法的复杂度不一样. 不妨以 \(\sqrt{n}\) 为界, 较小的 d 用方法1 计算, 较大的 d 用方法2 计算, 且方法二在求 dp(u,d) 时使用启发式合并. 复杂度 \(O(n\sqrt{n} + n\sqrt{n}log n)\). 然而事实上方法2 的时间远远达不到上界, 速度上反而更快. 所以可以将分界点调至 50, 效果不错.

SPOJ [3/3]

DONE QTREE7   LCT

题目大意

给你一棵树, 树上每个节点有一个颜色和权值. 颜色只有黑或白. 请你维护3种操作:

  1. 翻转某一节点u的颜色
  2. 查询与某一节点u相联通的点中权值最大的. 我们定义点u 和点v 联通, 当且仅当点u 到点v 的唯一路径上的所有节点的颜色相同.
  3. 将某一节点u的权值改为某一整数x.

节点数 <= 100000, 操作数 <= 100000.

分析

可以考虑用LCT维护子树信息. 因此, 虚边信息必须维护. 注意, 每一条虚边都会影响到沿边往上所有节点的信息, 所以应该和实边用类似的方法处理. 所以, PUSHUP时要处理一下虚边信息, 虚父子关系发生改变时也要想办法处理 (如强行access成实边) 出于写法的原因, splay之前要先删掉根对应的虚边信息, splay完了之后再补上; access 之前先沿路删虚边信息, 然后再自底向上一边虚边信息并PUSHUP. 询问时为了方便, 将询问点 makeroot 并 splay 后再查询, 这样就不用考虑父亲方向的信息了.

DONE DIVCNT3   洲阁筛

题目大意

给定 \(n\), 求 \(\sum_{i=1}^{n} \sigma_0(i^3)\).

\(n \leq 10^11\).

分析

显然有 \(G(p) = 4\), \(T(p^a) = 3a + 1\).

可以用洲阁筛.

DONE DIVCNT2

题目大意

给定 \(n\), 求 \(\sum_{i=1}^{n} \sigma_0(i^2)\).

\(n \leq 10^12\).

分析

记 \(w(x)\) 为 \(x\) 含有的不同质因子的个数, 则有:

\[\sum_{i=1}^{n} \sigma_0(i) = \sum_{i=1}^{n} \sum_{d|i} 2^{w(d)} = \sum_{i=1}^{n} 2^{w(i)} \lfloor \frac{n}{i} \rfloor\]

而:

\[\sum_{i=1}^{n} 2^{w(i)} = \sum_{i=1}^{n} \sum_{d|i} \mu^2(d) = \sum_{i=1}^{n} \mu^2(i) \lfloor \frac{n}{i} \rfloor\]

又有:

\[\sum_{i=1}^{n} \mu^2(i) = \sum_{i=1}^{n} \mu(i) \lfloor \frac{n}{i^2} \rfloor = \sum_{i=1}^{\lfloor \sqrt{n} \rfloor} \mu(i) \lfloor \frac{n}{i^2} \rfloor\]

\(\sigma_0(i), 2^{w(i)}, \mu^2(i)\) 都是积性函数, 不妨预处理出前 \(n^{\frac{2}{3}}\) 个值, 其他的都暴力求. \(\mu(i)\) 也只需预处理出前 \(\sqrt{n}\) 个值.

证明复杂度? 可以参考 杜教筛 的复杂度证明. 可以得出复杂度是 \(O(n^{\frac{2}{3}})\) 的.

UVA [0/1]

TODO 12538 Version Controlled IDE

TSINSEN [1/2]

DONE A1486 树   树分治 点分治 边分治

题目大意

给出一棵N个点的树, 每个点有各自的权值, 小A想选出一条简单路径, 使得这条路径上的点的权值的异或和最大. 另外, 小A有一些喜欢的点, 他希望在这条路径上经过至少K个自己喜欢的点.

\(N, K \leq 10^5\).

分析

最优路径问题, 考虑树分治. 树分治之后, 在 DFS 时存一下经过了多少个小A喜欢的点, 我们的问题变为已知许多个分成若干组的二元组 \((x,y)\), 我们要从不同的组中选出两个二元组 \((x_1, y_1)\), \((x_2, y_2)\), 使得在满足 \(x_1 + x_2 \geq K\) 的前提下, 最大化 \(y_1 \ \text{xor} \ y_2\).
其中, 如果使用点分治, "若干组" 到底是多少组取决于重心的度数, 如果是边分治则恒为2.

感觉边分治方便些. 先不考虑辅助点, 而是考虑怎么解决上述问题. 由于只有两组, \(x_1 + x_2 \geq K\) 的条件可以对其中一组维护数据结构, 另一组直接扫过去即可.

考虑怎么维护数据结构来解决最大化异或值.
假设现在我们有一个数 \(A\) 和一些数 \(B_{1..n}\), 我们要选出和 \(A\) 异或值最大的数 \(B_p\). 显然我们可以按位贪心. 从高位枚举起, 逐位确定最优的异或值是多少. 这个显然可以用 trie 来实现.

然后原问题也能很好的解决了. 复杂度 \(O(n \log n \log w)\), 其中 \(w\) 为点权.

其实点分治也能做, 只是要在 trie 树上记录一些信息, 避免用同一棵子树内的两条路径更新答案.

TODO A1339 JZPLCM

TC [1/4]

DONE SRM518 Nim

TC 真坑… 做题花的时间远没有 "钻研" 怎么交题花的时间多…

题目大意

这里有 2 个玩家和 m 堆石子. 游戏规则是每次可以从任意多堆的石子中拿走某一数量的石子. 给定 \(l\), 请求出 m 堆石子的个数均为 \([1, l]\) 之间的素数且后手存在不败策略的方案数.

\(m \leq 10^9, l \leq 5 \times 10^4\).

分析

显然, 后手不败意味着 \(m\) 堆石子的异或和为 0.

考虑用集合幂级数的相关知识.

定义集合幂级数的乘法为集合对称差卷积.

要求的即为 \(f(x) = \left(\sum_{i=1}^{\infty} [i\textrm{ is a prime}][i \leq l] x^{\textrm{set}(i)}\right)^m\) 的第 0 项, 其中 \(\textrm{set}(i)\) 表示 \(i\) 的二进制对应的集合.

FWT 就好. 沃尔什变换后将每个系数变为它的 \(m\) 次幂, 然后再做逆变换即可. 由于 \(l\) 不是很大, 所以只要保留一部分的系数.

复杂度 \(O(l \log l + l \log m)\).

TODO SRM575 TheTilesDivOne

TODO SRM570 CurvyonRails

TODO SRM641 BitToggler

CC [0/1]

TODO STREETTA

Vijos [0/2]

TODO 1005 超长数字串

TODO 1872 酗酒者

Others [0/1]

TODO IOI2016 Aliens

PE [0/1]

TODO 530 GCD OF DIVISORS

HOME