@Cyhlnj
2019-04-06T12:33:45.000000Z
字数 119281
阅读 3059
ios :: sync_with_stdio(false);
用了这个后只能 cin,cout
,不然会
AtCoder(Yahoo Programming Contest 2019)
A
每 个选前两个贪心
B
判断是否是一条链
C
如果 或 那么只进行操作一
否则先凑足 个,每次换完钱后再换饼干
D
这场比赛最难的题目?
假设枚举了一个起点和终点
那么 之间的贡献就是其间 为奇数的个数,可以转化为前缀和的形式
考虑 向左或 向右走的贡献
同样的枚举一个边界,贡献就是边界之外的 加上边界内的偶数()的个数,算上 的贡献,这个都可以预处理,都是前(后)缀相减取 的形式
最后枚举 ,也是前(后)缀相减取 的形式,乱搞搞就行了
E
枚举一个行的集合,如果这些行中有 个列的异或和为 , 个列的异或和为
那么列的选择方案就是
只需要统计异或和不为 的行向量集合个数
即总方案 异或和为 的行向量集合个数,线性基即可
F
不难发现序列第 个可以是前 个人手中的球
只需要 前 个的序列,剩下的组合数即可
Codeforces Global Round 1
A
模拟即可
B
总长度减去前 大的间距
C
当 ,那么一定能找到一个数字 使得 ,
否则,,输出 的最大因子
D
记录这每个数字的个数,
表示从小到大的第 个数字,这个数字还有 个,上一个有
理论上 ,一个位置能出的不同顺子最多三种,如果 ,那么一定有一种出了三次,直接拆开每个出三连即可
考场上写到了9
E
这个变换在差分数组上表现为相邻两个数的交换,直接判断即可
F
在线就是维护每个点到所有点的距离,主席树存储,两遍 预处理,空间有点卡
直接离线存储询问一起 就行了
G
官方题解
首先黑点不会获胜,如果黑点获胜,那么白点一定可以在按照黑点获胜的策略在之前获胜
考虑如果没有选过的点的做法,分情况讨论
1. 存在一个度数大于 的点,显然白点
2. 存在一个度数大于 的,且有大于 个非叶子的相邻点的点,还是
3. 剩下的情况就是一些度数为 的点,以及不超过两个的度数为 的点有大于一个叶子的相邻点的点,不难发现这种情况只有当点数为奇数的时候才会
4. 其它情况均为
考虑有选过的点怎么办,题解里面把这样的点变成了四个没有被选过的点
懒得放图片就描述一下中间一个点,然后周围挂三个点,选挂的三个点中任意一个为原来的点连回原图
这样为什么是对的呢,因为在双方绝顶聪明的时候,白的选了原来的点,黑的就一定会选中间的那一个,如果黑的再次选一个点,那么白的可以拿走剩下的点,状态不变
H
首先如果合法的串不多就是一个简单的 自动机 +
考虑到自动机上有很多状态是存在所有转移的,也就是数位 ,第一个满足 或 的地方
把所有这样的前缀加入 自动机,最多 个
设 表示从 点开始,任意再选 个能得到的合法串的个数
这样就把那些没有新建的状态的贡献加上了
Codeforces Round #545 (Div. 1)
T1
对于每行每列分别离散化,求出大于这个位置的数字的个数即可。
T2
每次选择当前串的最长的 接上去即可
T3
拆点,对于一个点 ,拆成 ,在原图中如果有边 则连边 。
可以发现如果 能到 ,那么 也一定能到达 。
所以 要么在同一个强连通分量里,要么不在同一条直链上。
所以直接缩点 即可。
T4
判环法,一个人 一次 步,另一个人 一次 步。
设 走了 步, 走了 步。
不难发现 ,而 是一次 步,所以 一定没有走完一个环,所以只要再次走 步就可以刚好到了终点。
其它的点也是一样。
总步骤 。
T5
不难发现每次加的一些 只要保留第一个就行了。
一操作很好做,直接扔掉前面的信息即可。
考虑二三操作,可以想到用单调队列来维护。
假设 ,那么一次三操作 变得小于 的条件显然是
,所以维护一个 的斜率单调递增的下凸壳即可。
T6
首先可以以最后烧掉的点为根,变成有根树。
考虑一次 操作的影响,设原来的根为 ,那么会使得 这条链的顺序变成 烧到 并且是最后烧的链,其它点相对顺序不变。
现在问题是怎么统计每个点在它之前的点的个数。
可以把 操作看成是一种区间(链)覆盖一个新的最大编号,然后换根。
那么一个点的排名就变成了小于等于它的编号的点个数减去它祖先编号和它相同的点的个数。
这种染色问题可以用 维护, 就直接 ,同一个编号的点一定在一棵 中,直接覆盖即可。
外加一个树状数组维护小于等于它的编号的点个数。
导数
令待测数字为
选取 作为测试底数(一般为素数,可以多选取几个,男神 个)
令
枚举 ,令
令 ,若 且 则返回
二次探测定理:
若
必定存在 两个平凡平方根
如果存在其它的非平凡平方根,则 为合数
最后,,若 不为 ,则返回
注意特判 为测试底数的情况(因为不互质)
递归处理 和
龙舟
质因数分解即可
求 模 意义下的值
令
那么就只要求出模 的值,然后 合并即可
考虑求
# include <bits/stdc++.h>
using namespace std;
typedef long long ll;
namespace IO {
const int maxn((1 << 21) + 1);
char ibuf[maxn], *iS, *iT, c;
int f;
char Getc() {
return (iS == iT ? (iT = (iS = ibuf) + fread(ibuf, 1, maxn, stdin), (iS == iT ? EOF : *iS++)) : *iS++);
}
template <class Int> void In(Int &x) {
for (f = 1, c = Getc(); c < '0' || c > '9'; c = Getc()) f = c == '-' ? -1 : 1;
for (x = 0; c <= '9' && c >= '0'; c = Getc()) x = (x << 3) + (x << 1) + (c ^ 48);
x *= f;
}
}
using IO :: In;
const int maxn(1e6 + 5);
int mod, p[20], a[20], x[20], b[20], num, fac[maxn];
inline int Pow(ll x, ll y, int m) {
ll ret = 1;
for (; y; y >>= 1, x = x * x % m)
if (y & 1) ret = ret * x % m;
return ret;
}
inline void ExGcd(int a, int b, int c, int &xx, int &yy, int m) {
if (!b) {
xx = (c / a + m) % m, yy = 0;
return;
}
ExGcd(b, a % b, c, yy, xx, m);
yy = (yy - 1LL * (a / b) * xx % m + m) % m;
}
inline ll Gcd(ll a, ll b) {
return !b ? a : Gcd(b, a % b);
}
inline ll F(ll xx, int yy) {
return xx < yy ? 0 : xx / yy + F(xx / yy, yy);
}
int ans, cur, xx, yy;
inline int Inv(int a, int m) {
return ExGcd(a, m, Gcd(a, m), xx, yy, m), xx;
}
inline int Fac(ll n, int pi, int xi) {
return n <= pi ? fac[n] : 1LL * Pow(fac[xi], n / xi, xi) * fac[n % xi] % xi * Fac(n / pi, pi, xi) % xi;
}
ll n, m;
inline ll Solve(int pi, int ai, int xi) {
ll nn = F(n, pi) - F(m, pi) - F(n - m, pi);
if (nn >= ai) return 0;
nn = Pow(pi, nn, xi);
int facn = Fac(n, pi, xi), im = Inv(Fac(m, pi, xi), xi), inm = Inv(Fac(n - m, pi, xi), xi);
return 1LL * facn * im % xi * inm % xi * nn % xi;
}
int main() {
In(n), In(m), In(mod), cur = mod, fac[0] = 1;
for (int i = 2; i * i <= cur; ++i)
if (cur % i == 0) {
p[++num] = i, x[num] = 1;
while (cur % i == 0) cur /= i, ++a[num], x[num] *= i;
}
if (cur > 1) p[++num] = cur, ++a[num], x[num] = cur;
for (int i = 1; i <= num; ++i) {
for (int j = 1; j <= x[i]; ++j)
if (j % p[i]) fac[j] = 1LL * fac[j - 1] * j % x[i];
else fac[j] = fac[j - 1];
b[i] = Solve(p[i], a[i], x[i]);
}
for (int i = 2; i <= num; ++i) {
int xx, yy, c = b[i] - b[1], lcm = x[1] * x[i];
ExGcd(x[1], x[i], c, xx, yy, lcm);
b[1] = (1LL * xx * x[1] % lcm + b[1]) % lcm, x[1] = lcm;
}
printf("%d\n", b[1]);
return 0;
}
方程
容斥原理
抛硬币
如果
那么答案就是总方案 相等的然后除
即
若
给定 ,且 最好为质数
可以算出 的解
首先可以算出 的原根
解方程 ,这个直接
设
那么 ,这个直接
无解在 和 的时候判掉,最后快速幂得到答案
求 的一个解 ,其中 为一个奇素数
1. 有二次剩余的条件
这就好了,因为
所以
现在只要证明 不存在 项就好了
假设
那么
所以 或者
如果 且 ,那么
因为 没有二次剩余,而 显然有二次剩余
所以 没有二次剩余,矛盾
得到
总结一下
第一步随机一个 ,使得 不存在二次剩余
第二步直接重载运算求出 即 的二次剩余
形式上类似于欧几里得算法,把 转化成 可能就是是类欧几里得算法的精髓
Earthquake
设
问题转化为求
ALADIN
先套用一个线段树维护离散化之后的区间的每一段的答案
那么只要考虑怎么下面的东西即可
Sum
那么原式变成
考虑计算这样一个东西
令 ,卡塔兰数满足递归式:
(其中 )
表示 个球放进 个无标号的盒子内,要求盒子不为空的方案数
1. ,其中
2. ,其中
3. ,其中
4.
结论
表示 个不同元素,分成 个圆,排列的方案数
那么
显然有
的集合划分数,显然是第二类斯特林数的前缀和
Team Work
求
根据第二类斯特林数的结论
Crash的文明世界
第二类斯特林数+换根
直接用下面的式子展开即可
建筑师
首先 一定会被看到,那么 把序列分成了两部分
设 表示 个元素的排列,有 个能看到的方案数
枚举最小的数字的位置,那么
Bandit Blues
和上一道题目一样,用分治 求
color
显然当 的时候,最左边的和最右边的颜色种类相同,并且中间的颜色集合是两边的交集
那么直接枚举左边的颜色,再枚举子集
Partitions
考虑每个数字的贡献
第二类斯特林数
要么新建一组,
或者加入之前的组,设每个小组 个,就是
即贡献为
那么
置换个数 等价类个数 不动点数
Cards
求不动点个数
color
优化
因为它的置换为每个点向后移动,只有 种,每一种的每一个环的大小一样
设 为向后移动的位置数,那么环长为 那么个数就是
设颜色 种,那么不动点的个数就是
也就是每个环只能染相同的颜色
这个显然可以枚举约数计算
Magic Bracelet
矩阵乘法 优化
有色图
对于一个点的置换
对于两个点
他们对应的边的置换的循环大小为
那么类似这样的点对的边的循环的个数为
对于两个点
设其周期为
如果 为奇数,那么循环个数为
否则,存在还有一种的循环节是(就是两个点刚好相隔半个周期,而边是双向的)
所以就是
总结一下就是
若将一个循环看成一个圆形的排列,现在要把 个人分配到 个长度分别为 的独立不相关圆排列中,并且
方案数为
图的同构
和上面的题目一样,颜色只有
[SDOI2013]项链
求每个珠子的方案数
即有序的求三元组 满足
设 表示 个小于等于 的有序数字,满足 的方案数
容斥得到要求的
定义
两种
1.对于一个数的最小正整数是,那么就称是的原根
2.假设一个数对于来说是原根,那么的结果两两不同,且有 ,那么可以称为是的一个原根
性质
求法
求模原根的方法:对素因子分解
若恒有成立,则就是的原根
设
证明
不能丢!!!
PYXFIB
设
LJJ 学二项式定理
直接考虑 每一个的贡献
复读机
输出
,构造生成函数,就是求
把第一类Stirling数看成无符号的
第一类Stirling数幂与下降幂的关系
第二类Stirling数幂与下降幂的关系
反转公式
证明
另外一个同理
证明
考虑一种第 大值被作为最小值计算的次数
kthmax
求第 大元素
构造容斥系数
使得
最小公倍佩尔数
容易得到
Koishi Loves Number Theory
容易得到
那么直接最值反演
暴力求出所有约数,然后计算答案
小Z的礼物
容斥
设
设 表示第 行,喜欢的物品选取状态为 ,一共有 的概率得到的方案数及容斥系数
转移即可
Positions in Permutations
排列可以看成是 的矩阵上放棋子,要求每行每列只能有一个棋子
那么满足 即放在对角线的上面或者下面
X | X | ||
---|---|---|---|
X | |||
X | |||
X | X |
(数字即为满足要求的, 为对角线)
显然, 为一组, 为一组
两两互不干扰,每一组相当于是不能同时选两个相邻的位置(组中)
然后就可以 出 忽略 个,有 个满足要求的方案
这样再乘上 就可以算出 表示至少有 个位置满足要求的排列方案
要算出恰好 个的,然而答案不是 (虽然看上去很对)
因为 个受了限制,另外 个没有限制的也会有满足要求的情况
这样就导致一种情况被算了多次,并且显然在 个的时候和 的时候被重复算的次数不同
假设 表示恰好有 个位置满足要求的排列方案
那么
因为每一种恰好 个的被算了 次
舞会
求出至少有 组的方案数,然后像上一题一样弄(神 要写高精度)
集合计数
考虑选出元素个数至少 个的方案数
即
表示选出 个,有 个集合,这些集合有 种选法
然后容斥一波
答案就是
即
分特产
反过来想,求至少 个人没有分配的方案数
每种物品独立,求出分成 组(可以为空)的方案数,乘起来
然后直接容斥
isn
求出非降子序列长度为 的个数
令 表示至多 步就停止的方案数
设 恰好 步就停止的方案数
则
答案就是
放棋子
设 表示前 种颜色,有 行, 列被占据了的方案数
染色问题
容斥套容斥,枚举有至少有哪些颜色没有,之后枚举有哪些列没有
即
已经没有什么好害怕的了
同 舞会,解出来恰好要 组
两双手
题目保证了 所以走到任意一个点的两种的步数唯一
首先算出走到每个障碍点的两种各需要多少次,把这个定义为这个点的坐标
那么就很容易算出一个点到另外一个点的方案数
考虑容斥,按坐标排序,设 表示 只经过这一个关键点的到这个点的方案数
那么
四维世界
做法和两双手一样
卡农
好神仙。。。
首先假设是有序的,最后除掉 即可(有序便于计算)
设 表示选了 段,满足所有要求的方案数
考虑用容斥来转移
首先总的方案数为 因为确定了前 个,最后一个就唯一了
减去空集,即
减去相同的情况,枚举和哪一个位置相同 种方案,固定前 个,然后相同的方案数为
即
成绩比较
求出至少 个人被碾压的方案,容斥求出总方案
至少 个人被碾压的方案
染色
考虑容斥,求至少 种颜色出现 次的方案数
即
(意思:枚举颜色,枚举位置,做可重排列,其它的染除了这 种颜色外的任意颜色)
设
直接把上面的式子合起来容斥一下,得到
黑暗前的幻想乡
容斥,枚举至少有多少公司没有修,然后矩阵树定理求行列式即可
序列染色
神仙题, 状态都那么神仙
为当前枚举第 个位置,染 这个颜色, 表示当前的状态数
,序列中不含连续 个
,序列中含连续 个 ,不含连续 个
,序列中含连续 个 ,含连续 个
利用容斥进行转移,注意到每次 都可能有不含转化为包含
每次染 的时候, 的要加上转化为包含的方案数, 的要减去转化为包含的方案数
这个方案数为 ( 表示 的前缀和)
染 同理
有标号的DAG计数I
但是这样会算重复,要减去重复的,变成容斥
有标号的DAG计数III
算出上面的 ,设 表示连通的 个数
枚举钦定的某个点所在的联通块的大小
[Shoi2007]Permutation
容斥 错排 高精度
对于求恰好 个的方案数,并且贡献为 的形式
可以利用二项式定理展开
含义为枚举所有的集合 ,如果 是答案的子集,那么贡献为 ,否则为
所有子集 的贡献之和恰好是
这样可以省去容斥
序列统计
枚举长度 ,把每个数加上下标就变成了递增序列
那么答案就是
累加上就是
这个可以用格路问题证明
queue
首先,如果没有要求,那么答案就是
你发现一些性质,如果最后的一个数字 确定了,那么之前的数字只能这样排列:
必须顺序排列, 必须倒序排列
那么枚举最后的数字,答案就是
考虑现在有一个位置要放数字
那么有两种情况:
第一种, 在 的前面,那么在 后面的只能是 的一个前缀,并且要倒序。
多余的部分放在 的前面,也要倒序,而且 也要在 的前面顺序排列。
第二种, 在 的前面,那么在 后面的只能是 的一个后缀,顺序排列。
同理,多余的部分放在 的前面,也要顺序,然后 在 的前面倒序排列。
假设我们确定了这个人后面应该怎么排列
你发现,丢给前面的是一个形如 的东西
并且他们的顺序是确定的也就是 必须要顺序排列, 必须倒序排列。
那么对于 前面一个被钦定的人 :
他只能在 或 内,否则不合法,
而且他只能满足 或 的其中一个。
如果满足 那么他前面的只能是 的一个后缀的倒序排列和 的顺序排列。
因为 不能被放在 前面倒序。
满足 类似。
所以 这里只有一种方式,而且他丢给前面的还是一个类似 的东西。
那么只要确定了最靠后面一个被钦定的人的后面的方法就可以确定全部
枚举他的两种方法,算出前面的即可。
Atcoder BBQ Hard
可以看成是从点 走到
直接设 表示所有点出发到 的方案数,最后去掉重复的即可
加长棒
容斥+组合数
超能粒子炮·改
设
那么
话旧2
对于第二问,只要求相邻两个都向上的最大值即可
对于第一问,可以发现有解当且仅当相邻两个点的曼哈顿距离为偶数
那么可以转化成切比雪夫距离
问题变成不越过某条直线的格路问题,组合数即可
要用到
Matrix
1. 给定一棵带标号的无根树,找出编号最小的叶子节点,写下与它相邻的节点的编号,然后删掉这个叶子节点。反复执行这个操作直到只剩两个节点为止
2. 注意到,如果一个节点A不是叶子节点,那么它至少有两条边;但在上述过程结束后,整个图只剩下一条边,因此节点A的至少一个相邻节点被去掉过,节点A的编号将会在这棵树对应的Prüfer编码中出现。反过来,在Prüfer编码中出现过的数字显然不可能是这棵树(初始时)的叶子。于是我们看到,没有在Prüfer编码中出现过的数字恰好就是这棵树(初始时)的叶子节点。找出没有出现过的数字中最小的那一个(比如④),它就是与Prüfer编码中第一个数所标识的节点(比如③)相邻的叶子。接下来,我们递归地考虑后面n-3位编码(别忘了编码总长是n-2):找出除④以外不在后n-3位编码中的最小的数(左图的例子中是⑦),将它连接到整个编码的第2个数所对应的节点上(例子中还是③)。再接下来,找出除④和⑦以外后n-4位编码中最小的不被包含的数,做同样的处理……依次把③⑧②⑤⑥与编码中第3、4、5、6、7位所表示的节点相连。最后,我们还有①和⑨没处理过,直接把它们俩连接起来就行了。
为什么不全部删除呢
根据上面的东西,显然前 个点就可以找出最后剩下的两个点了
那么长度为 的最后两个是唯一确定的
所以长度为 或 的序列可能存在有不合法的情况
结论
一些大小为 的连通块生成树方案数为 ( 为连通块数, 为点数)
证明:
的每一位需要从 中枚举,所以方案数是
从块内不同点连出去一样是不同的方案,对于每个被删除时联通块,需要乘以联通块内的点数
最后两个连通块的边的方案数也是
所以就是
算式子
暴力枚举倍数,一个前缀和,一个差分即可
[HAOI2008]圆上的整点
令
那么
又有 互质,所以 都是完全平方数
设
那么
那么
假设 ,那么
所以枚举 然后暴力枚举 算出
检查 都是完全平方数且互质
更新答案即可
因为 ,少算了坐标轴的贡献,同时之算了第一向限的贡献,所以
国王奇遇记加强版
设
递推即可
[Zjoi2011]看电影
这题太神仙了。
首先 则必定无解,直接特判解决。
现在只考虑 的情况。
现在要求解的是概率,即总合法方案数除以总方案数,总方案数很容易算,显然是 。
考虑如何计算合法方案数。不难发现当且仅当一个人的 超过了 时是不合法的。那么我们假装 和 收尾相连就好了,这样子如果一个人的 如果跨越了,就让他回到
不难发现这样子每个人都一定能够坐下
考虑如何计算合法方案数,我们如果在K的后面再加一个椅子,那么就可以知道 ,那么至少会多出一个空位置,那么我们把某个空位置定为 号位置,不难发现如果 号位置是一个空位置,那么意味着必定没有人会跨越 位置(因为如果他要跨越K位置就会坐到 号位置上)
那么,这样子就可以计算合法方案数了。
即
也就是首先这些人随意坐,那么空位置还剩下 个,而因为考虑的是环,所以要除掉 消去环的影响。
地精部落
这样的序列有一些性质:
把每一个元素都变成 ,那么原来的山峰变成山谷,山谷变成山峰,所以方案数相同
设 表示强制开头为山谷的 的数的序列的方案数
那么枚举其中的最大数的位置
那么
最后答案就是
数三角形
枚举矩形的大小 ,一共有 个
考虑每个的三角形的个数,必须要保证这个三角形不被其它的矩形包含
如果只有一个点在顶点上,方案数就是
有两个点的时候,分是否在对角线上考虑,分别为 和
有三个点的时候就是
地形生成
第一问可以考虑按照山的高度从大到小放
但是这样如果遇到高度相同的就不好考虑,那么同时要求数量限制从小到大
这样每次放的时候后面的一定不会影响前面,并且高度相同的时候前面能放的位置后面的也能放
直接乘起来就好了
对于第二问,此时高度相同的会有影响
对于高度相同的一段,强制要求数量限制从小到大,并且后面的位置必须小于前面
设 表示放了 个到 个空位,最后一个放的在最后,的方案数
那么
前缀和优化即可,最后把答案乘起来
[Hnoi2013]数列
差分之后
第一类初等变换(换行换列)使行列式变号
第二类初等变换(某行或某列乘k倍)使行列式变k倍
第三类初等变换(某行(列)乘k倍加到另一行(列))使行列式不变
对于一个 的矩阵 ,选出一个长度为 的排列 ,设其逆序数为
对于 ,矩阵 是 删除 行和 列的结果
代数余子式:
那么
那么有
Matrix Power Series
矩乘快速幂,构造矩阵
分解
显然的矩阵乘法求解系数
「2017 山东一轮集训 Day6」子序列
设 表示结尾在 之前的,以 结尾的方案数
假设这一位为
那么 ,其它
显然可以矩阵优化,并且存在逆
而且矩阵非常特殊,可以玩出来一个 的转移
把矩阵 的右边放一个单位矩阵,然后把左边高斯约当成单位矩阵,此时右边就是
如果不能高斯约当成单位矩阵则无解
设 是数域 上的一个 矩阵,
是 的特征多项式,则
它实际上是这么个鬼玩意儿。。。
其任意一个代数余子式是所有生成树的边权积的和。。。
重建
可以想一个简单的暴力枚举所有树 ,然后
计数
直接的想法就是设 为边权,矩阵树定理一波后取出 的系数即可
也就是求出模 意义下的循环卷积的常数项
考虑插值出最后多项式,所以只要得到 的点值就可以得到最后的多项式了
这道题 所以直接用原根就好了,最后插值一下
upd: 其实最后并不需要插值
根据单位根反演
由于是边权三进制不进位的相加,那么可以考虑每一位的贡献
对于每一位,生成树的边权相当于是做模 意义下的加法
考虑最后每一种边权的生成树个数,这个可以直接用生成函数,在矩阵树求解的时候做一遍这个生成函数的模 意义下的循环卷积求出系数即可
暴力多项式运算不可取
考虑选取 个数字 ,使得
即找出 次单位复数根
这个直接带入三角表示法即可得到
把这些东西带入,矩阵树定理求出点值,最后手动 即可
若 为积性函数
首先
然后考虑线性筛,一个质数
,那么 为 的最小质因子
假设它的指数为 ,那么
那么当 时
否则就只要能快速求出 就好了
直接莫比乌斯反演得到:
签到题
预处理出根号以下的所有质数,用这些数字暴力筛
复杂度
每次对于区间内的数字暴力分解,复杂度 一个数字的质因子只有 个
小清新数学题
用 的质数筛,最后只有 种情况,要么是 ,要么是质数的平方,要么是质数,要么是质数的乘积
用 判断即可
求解积性函数 的前缀和
Sanrd
设 表示 的次大质因子
题目就是要求
Misaka Network 与求和
假设 就是
莫比乌斯反演得到
奇怪的数学题
设 表示 所有约数中第二大的, 表示 的最小质因子
奇怪的式子
拆开变成
DZY Loves Math IV
枚举 ,就是求
其中
设
设 ,
那么
Lcm
题目所给的不合法的条件可以转化为
设
递归常数大,所以搞个非递归
考虑上面不断的分组分治最后会是什么样子
设一共有 个位置,考虑第 次分组,定义二进位顺序为从低到高
分到左边的一定是二进制的第 位为 的
分到右边的一定是二进制的第 位为 的
而左边和右边的位置的编号个个数都是 ,这就使得
左边的位置的编号二进制的第 位为
左边的位置的编号二进制的第 位为
这样看来最后的每个位置 ,它上面的数字的二进制一定是 的二进制表示反转过来的
有了 就可以先换好位置,然后每一层对应的 一定是一段连续的区间
这样就可以快速定位从而方便的实现非递归
在模 意义下 , 为 的原根
若
泰勒展开后
若给出点值
则
Count
与一个数字互质的数会成对出现,那么除了 ,
自然幂数和直接插值
教科书般的亵渎
拉格朗日插值
Stranger Trees
设答案的生成函数为
带入 个 求出点值后插值即可
现在问题变成选定恰好 条边的权值为 ,求总权值
方法详见 数树
已知次多项式和次多项式,
求除以的商及余式
也就是
问题描述
个变量 ,求所有的
给定一个多项式
求出对于每个点 的
考虑分治
设
给出 个点 ,求出这个多项式
根据拉格朗日插值
求一个满足 阶齐次线性递推数列 的第 项
如何求
显然P(x)=C(x)
把 写出来
一道难题
考虑要求的东西的组合意义,问题转化为:
有 种小球,每种的大小为 ,求选出大小总和为 的小球排成一排的排列数
有递推
套常系数线性递推的方法即可,前面 项可以预处理求逆得到
[NOI2017]泳池
一道 好题
设 为一个块合法的概率
套路一恰好为 的概率不好算,算小于等于 的减去小于等于 的
那么设 表示宽为 的合法的泳池面积都小于等于 的概率
设 表示宽为 的合法的泳池面积都小于等于 且最下面一行都合法的概率
那么考虑转移
套路二强制前面的满足一定的性质,后面接一段不满足的
首先 ,然后枚举放一个不合法的块在最下面
那么贡献就是
考虑怎么得到 ,考虑到 表示的一定是下面都合法,上面是一个不合法的轮廓线的状态
那么枚举轮廓线的最下面的点
设 表示宽为 最下面一行都合法,且向上第一个不合法的高度为 的概率
仍然用套路二转移
首先
显然有用的状态只有 ,然后前缀和优化做到
直接这样子写就有 分
观察这个东西
就是个常系数齐次线性递推的形式
套用线性递推即可
对于一种集合运算 ,求 ,。
一个很 的想法就是构造一种变换以及它的逆变换,使得能像 一样弄,这个东西就是 。
构造 :
(即 的子集的 和)
显然
即 (这里指的是按数组相同下标相乘)
现在考虑求 以及它的逆变换 。
考虑分治计算,把 数组按照二进制为分成 到 和 到 两部分,设为 和 。
假设我们算出了 和 。
和 相当于一个的二进制的第 位为 ,一个为 。
那么 就是 (表示数字拼接, 指的是按数组相同下标相加)
缺少的 到 的子集由 得到。
同样考虑分治,假设我们算出了 和 。
显然
多余的 到 的子集由 扣除。
构造 :
(即 的母集的 和)
???
与/或卷积不就是个高维前缀和吗???
好有意思啊。。。
mmp异或打不出
构造 :
表示 二进制下 的个数姑且这么叫着吧
是不是很鬼畜?
如果你想要问我是怎么弄出来的那我就只能orz了
你发现它也是满足 (类似于容斥)
FWT模板
真 模板
Hard Nim
快速幂
技巧:先 ,快速幂后,再
Binary Table
首先可以枚举哪一些行要操作,然后
考虑记录状态为 的列的个数
对于一种取反状态 ,那么列如果不操作,答案就是 , 表示 二进制下的 的个数。
现在有了列的操作,贪心即可,所以 与其 二进制下的 的个数取 即可。
按位或
容斥,求出某个子集最先或出一位的期望
不好求,变成不能或出某个子集,然后 高维前缀和即可
州区划分
设 表示选出了集合为 的答案, 表示选出集合为 的权值
那么
Kanade's convolution
首先可以得到
令
那么
同时要满足
还要算上满足要求的 的对数
就是 为什么?
首先 必定有一段 必须相同,剩下的位置必须不同,也就是把 分成不相交的两个集合的方案
现在有
这是一个不相交的集合卷积 和 不相交,仍然可以用州区划分那一套
然后 即可,把 的去掉
[Snoi2017]遗失的答案
将 唯一分解为
对 G 也分解为 。
称 分别为 这个质因子幂次的上下界。
显然为了满足 为 且 为 ,对于每一个 ,就至少要
有一个数触其上界,有一个数触其下界。
那么就可以拿一个长为 的二进制状态表示每个质因子是否已
触其上界,是否已触其下界。
然后前后缀对于 的约数且是 的倍数的数作一遍
直接 合并成为答案
还有更加优秀的容斥做法
首先问题已经转化为给定一些集合,求出或为全集的方案数
设 表示或为 的方案数
直接求不方便
设 表示或为 的子集的方案数
那么 ( 表示 的子集个数)
那么容斥得到
对于钦定了一定要选集合 ,只需要把 的超集 然后再次做上面的容斥
记得
暴踩duliuGSY
Sum the Fibonacci
和子集卷积模板
Random Elections
看懂题目就会的 模板题。。。
【UTR #3】量子破碎
学过 看到操作 不难可以联想到
考虑一遍 会把 变成什么
考虑这个东西
当 和 同奇偶时才有值
实际上就是 为偶数
而只需要知道互不相关的 个 就可以解出
并且题目又是随机的,那么期望做 遍,询问次数期望
一个小细节, 矩阵为 ,这玩意儿并不满足
但是它满足
所以只要令 就好了
序列计数
用总的序列数减去不含有素数的序列数
每次暴力多项式卷积,暴力快速幂
Partial Sums V2
每个位置 对它后面 位的贡献的系数是一定的,设为
打表发现
理解:把 次的前缀和一行一行排开
第一行为原数列,第二行为第一次前缀和后的,依此类推
那么 对 的贡献就相当于 走到 ,即
然后就任意模数
一个人的高三楼
同上,不用任意模数
乘积之和
分治 模板,用任意模数
哈希统计
倍增 一个傻逼错误调了一个上午。。。
残缺的字符串
假设没有通配符,那么把 翻转
设
如果 为 则 之前的一一匹配
那么可以给每个字符一个权值
重新定义 就可以 了
然后有通配符,设权值为
再定义 然后拆开 就可以了
神仙的游戏
自己还是太 了,上来就构造多项式和通配符直接匹配,然后遇到 相交的时候就 了
神仙的游戏蒟蒻还是玩不来
一个小小的性质:
存在长度为 的 的充要条件是
等价于按照 的剩余系分类,那么每一类都要求不同时含有
考虑两个位置 分别为 会对于哪一些长度的 有影响
显然是满足 的 ,即
设 表示 是否存在 分别为
这个是一个经典套路
只要对于 和 分别构造函数, 一下就好了
Yet Another String Matching Problem
考虑如何计算两个等长串的距离
相当于两个匹配的字符之间连边,同一个连通块内可以互相转化,答案就是并查集合并的次数
本题的字符集大小只有 ,那么考虑枚举两种字符匹配连边
匹配就是一个非常套路的反转 了
Many Easy Problems
考虑每个点的贡献,每个点被一个大小为 的块经过的方案数不好算
考虑计算每个点不被一个大小为 的块经过的方案数
那么就是
Kyoya and Train
表示 到 ,时间为 的最小期望代价
Transforming Sequence
表示前 个,选了 个二进制位
倍增+ 即可
Perpetual Subtraction
首先显然有一个 , 表示前 轮之后为 的概率
那么
不会线性代数,不会矩阵
设生成函数
那么
仙人掌计数
求 个节点无重边、自环,有标号的仙人掌个数
设 为其指数级生成函数
可以考虑把它分成若干个部分,然后 起来
那么可以钦定一个点删掉,也就是弄个根
设 为有根仙人掌个数的生成函数
显然有
考虑删掉根之后的图长成什么样子
对于与根不在一个环上的相邻节点,就会变成以该点为根的仙人掌,生成函数为
对于与根在一个环上的相邻节点,把这个环拆开,变成以环上的点为根的仙人掌,由于还可以翻转,那么生成函数为
把这些东西 起来,即
口袋里的纸飞机
很好的一个题目
求一个数 会被多少数列生成不好处理,考虑求 不会被多少数列生成
逆序对数列
暴力就是
如果 ?
考虑问题的转换,设 表示 小的在它后面的数的个数
,显然任何一个满足要求的 数列都可以从大到小放数字构成一个满足要求的排列
那么就是要求 的方案数
考虑生成函数
食物
简单生成函数
化简后写出来就是
那么答案就是
Triple
生成函数后容斥,因为直接生成函数会选择重复的
即可
付公主的背包
一些形如
(模板)分治 FFT
构造
小朋友和二叉树
设 表示权值为 的二叉树的个数
设 表示是否有 这种权值可以选择
那么
异化多肽
设 表示大小为 的氨基酸的个数, 表示和为 的多肽的方案数
那么
CF891E Lust
设 表示 选择了多少次
把对 的一次操作的贡献看成是
有标号的DAG计数II
设 表示 个点的答案
那么枚举至少 个点的出度为
有标号的DAG计数IV
设 表示不要求连通的 个点 的 的方案数
直接 那样求出来
设 表示 个点的答案
方法一
钦定第一个连通块的一个点
咱们去烧菜吧
运用结论
遗忘的集合
运用结论
Nikita and Order Statistics
前缀和后,相当于要求差是一个定值把其中一个反过来变成和是一个定值,所以构造生成函数, 即可
射命丸文的笔记
首先求所有的竞赛图的哈密顿回路条数
就是
猎人杀
我们杀人后将其打上标记,但还是可以以他为目标重复选,直到选到一个未打标记的人
这和原问题等价,而且这样每轮选中每人的概率都不变,只是游戏变成了无穷轮数
考虑容斥,枚举在 后面被标记的猎人集合 ,设其 的和为 ,总的 的和为
那么
[国家集训队]整数的lqp拆分
构造 数列的母函数
那么答案就是
[TJOI2015]概率论
设 表示 个点的二叉树个数, 表示 个点的二叉树的叶子节点个数的和
那么
抄题解
,随便做一下,设 为相同的边的个数,输出
,给定其中一棵树
设初始答案为 ,首先可以发现,每有一条边和给定的树相同就会使得答案除去
那么可以利用矩阵树定理,已经有的边权值为 ,其它的连成完全图,权值为
求解行列式之后乘上 即可,
第一种正解 即可 不会
第二种正解
一个小trick
对于求恰好 个的方案数,并且贡献为 的形式
可以利用二项式定理展开
含义为枚举所有的集合 ,如果 是答案的子集,那么贡献为 ,否则为
所有子集 的贡献之和恰好是 ,这样可以省去容斥
那么可以直接算 在每一种两棵树都包含的边集 的贡献
下面的 默认为
对于一种边集 ,假设它把图分成了 个连通块,每个连通块大小为
运用 的知识,不难得到其生成树的方案数为
直观上来看这个东西,只能得到一个 的 , 表示 所在连通块,大小为
然后考虑 的组合意义,即从每一个连通块选出一个点的方案数
那么就可以把上面的 改成 表示 所在连通块是否选择了一个点
树形 即可
,同样的利用那一个trick
设 表示钦定 条边相同的方案数
那么
考虑计算 ,还是直接利用 ,容易得到
K Paths
考虑枚举一条路径 ,求出所有边经过它的答案
只需要求出 的子树内选出 个可以重复的点,使得它们到 的路径不相交
不难发现,就是从 的儿子的子树内各自选一个以及可以选多次 自己
设这个方案数为
再设 表示 的子树大小, 表示 的儿子集合
考虑生成函数,设
生成树计数
推导:
根据 序列,答案显然就是
求出模 意义下的循环卷积
考虑插值出最后多项式,类比 的方法
假设我们要求
白兔的刁难
如果大力推单位根反演就可以获得一个 的好方法
性能优化
题目翻译:给定两个 次多项式 和一个整数 ,求 在模 意义下的卷积
显然就是个循环卷积,所以只要代入 进去求出点值,然后插值就好了
??? 不是 的形式,不能直接
怎么办呢?
根据题目性质,可以把 拆成 的形式
这启示我们每次不是每次分成两半而是拆分成 次,然后再合并点值
设
那么
根据单位复数的性质(消去引理和折半引理)那么
石家庄的工人阶级队伍比较坚强
设运算 ,一个表示三进制不进位的加法,一个表示不退位的减法
设 分别表示 转成三进制后 的个数
那么
设
那么可以发现
那么我们要求的就是 与 的第一行的 次卷积的卷积
其中下标运算为
那么我们求出 和 的"点值表达",快速幂之后变换回去即可
下标运算可以看成是每一位的模 的循环卷积,用三次单位根 ,每一层手动做一遍长度为 的
由于题目中 的性质,可以得到 ,所以 有逆元
注意到
把所有数字用 表示,重定义运算即可
线段树维护一次函数,以x为值域,比较交点的上下,每个点存储一个最大/最小的那个线段
递归处理(一些类似标记永久化的东西)
世界树
毒瘤虚树,两遍 处理出每个虚树上的点属于哪一个询问的点
枚举每一条边,如果属于的点一样,加上这条边不在虚树上的点
否则二分出分界点,分给两个点
一个好依然毒瘤的方法:
两个数组,一个维护子树中还有多少点没有分配,一个维护分配到的点
答案就是第二个数组+管辖的点的第一个数组的和
树上游戏
对于每个颜色建立虚树,树上差分分别统计每一种颜色的答案
车站
首先可以用线段树维护链交的两个端点( 分类讨论)
注意到最远点肯定是在以这条链为根的两个端点的子树中各自选择一个,线段树还是可以维护
最后在链上二分(倍增)即可
新年的小黄鸭
设 表示选完了 的子树的答案
枚举 一条重链,转移贡献为
后面的 很好维护,主要是前面的
直接把贡献拆分成 个,分 次加入,用一个 的数组把每个点挂在它的 的祖先上
只需要在一棵线段树修改+查询即可
Wall
打上两个标记每次讨论下放就好了
V
毒瘤 出清华集训的题到
题目是要求区间加减法和区间覆盖,并且最小值小于
询问区间(单点)最大值或区间(单点)历史(出现过的)最大值
神仙操作
把操作视为一个二元组
对 重新定义修改为
那么
即分段函数取
(自己 一下标记和正确性)
维护历史最大值:
维护历史最大的标记,每次先 历史标记,然后再 现在的标记
位运算?位运算!
分开考虑每一位,暴力覆盖 即可
毒瘤
[Hnoi2018]转盘
一个贪心的策略,枚举起点,显然是等到一定的时间后走一圈更优秀,那么就是求一个斜率最大的直线
首先倍长数组,对于起点
答案就是
把所有的 减去
即
那么就是求每个点 的后缀最大值的最小值
从后往前维护一个单调不降的单调栈即可
那么我们可以用线段树来维护这个单调栈
用类似楼房重建的方法维护答案
注意要统计的是每个点 全局的后缀最大值,每次不能取右儿子的答案
void Update(int rt, int o, int l, int r, int mx) {
if (l == r) {
tr[rt].ans = min(tr[rt].ans, max(tr[o].mx, mx) + l);
return;
}
register int mid = (l + r) >> 1;
if (tr[o << 1 | 1].mx >= mx) { //直接更新,递归右边
tr[rt].ans = min(tr[rt].ans, tr[o].ans);
Update(rt, o << 1 | 1, mid + 1, r, mx);
}
else { //右边取端点,递归左边
tr[rt].ans = min(tr[rt].ans, mid + 1 + mx);
Update(rt, o << 1, l, mid, mx);
}
}
Rikka with Data Structures
先只讨论 的情况。
求出 内的最大值 , 若 就在 内找到第一个
大于 的位置 , 答案为 内大于等于 的前缀非严格最大值个数;
若 , 答案为 内大于等于 的前缀非严格最大值个数
线段树维护单调栈即可
New Home
首先二分答案 ,问题变成求区间 在该年份的不同类型个数为
关于年份的限制可以离线下来
现在的问题就是区间数颜色,一个套路就是维护每个颜色的后继,即这个位置颜色的下一个位置
那么,如果有 的某一个值大于 就不合法
这个可以在线段树上二分实现
时间复杂度
[IOI2018]排座位
求出前 个大小为 的连通矩阵
当 等于 的时候,可以维护点数减去两个相邻点都小于等于 的边数,委会区间最小值为 的个数
对于任意的
设 的为黑点, 的为白点
统计这样的点的个数
第二种点最多 个,所以还是维护最小值 的个数
【IOI2018】会议
首先可以设 表示 的答案
设 为区间 的最大值的位置,那么
这样的 结构形成了笛卡尔树
那么考虑在笛卡尔树上维护
对于笛卡尔树上的一个点 它有一个区间 ,考虑维护 和
对于固定左端点的 ( 类似)
1首先可以由 在笛卡尔树的左儿子继承,即
2 那么
3 那么
前两个好办,对于3,可以证明,这个 的函数是存在一个分界点,使得在左边一个更优,而右边另一个最优,并且具有可二分性
证明
只需要证明下面的东西即可
因为
那么可以证明上式取
那么直接二分端点就好了
现在只需要支持区间加,区间对等差数列取 ,单点询问这些操作
可以离线线段树统计答案或者主席树在线回答
[IOI2018试机赛T3]冒泡排序
你有一个长度为 的数组 ,你要对它进行bubble sort
你会进行如下操作若干轮直至数组有序:从前往后遍历每一个 ,若 则交换两数
有 次修改操作,每次修改原数组中的一个数,并求bubble sort的操作轮数
注意这里的修改基于上次修改后的数组而非初始数组。
Sol
答案就是
线段树维护, 存储每个权值的下标,每次区间修改单点更新
「ROI 2017 Day 2」学习轨迹
首先如果只在一个学校上课的话,答案显然就是选择所有的课程。
否则在两个学校上课,不难证明至少有一所学校上课的权值和必定大于其所有权值和的一半 (否则不如在某一个学校上课)。
对于权值做前缀和,假设 的前缀和是 , 的前缀和是 , 不难证明只要超过了一半,必定会选择前缀和第一次 和 的位置。
不妨先随便令一所学校要跨过中位数。比如说 吧。
那么显然答案就是在 的课程中随意选择一段,然后把重复的课程在 的课表中标记出来,然后从中位数开始向两侧拓展,能走就走。
那么设 表示选择了 的 这一段的答案,那么枚举右端点用线段树动态来维护这个东西。
贡献显然是 。
因为是从 位置开始,向左右两侧拓展。
那么我们枚举右端点之后,两侧分别维护一个单调队列。
首先因为枚举了 ,所以 很容易计算,现在问题就在于如何维护 。
在单调队列加入当前位置和弹掉当前位置的时候,会影响一段区间的贡献,在线段树上修改即可。
Play with sequence
定义标记 表示把 变成
因为任意时刻数都不会小于 ,所以变成了求最小值的个数
维护一个最小值 以及个数, 次小值 ,每次修改
如果 ,那么没有修改
如果 ,那么可以直接打上标记
如果 ,那么暴力
定义势函数 为最小值和父亲不相同的点的个数
每次修改最多修改 个, 最多增加
每次 遇到 的就会终止,因为父亲的最小值一定不会大于儿子,每弄到一个 , 就会减
而 最多只会增加到
总复杂度为
最假女选手
同上
元旦老人与数列
考虑用 那一套理论,维护区间最小值 和严格次小值
那么可以直接 维护前三个操作
考虑维护历史最小值,先维护历史最小标记
写了写发现 那个修改不好操作
对于 操作来说,只会在 的时候打上标记
这就相当于区间内等于 的权值都要变成
那么 操作就可以变成对区间最小值的加法操作
而 ,这样就可以非常方便维护历史最小值了
具体来说,维护下面几个标记
即线段树套线段树
注意每个点维护的是矩阵的整体的信息
1. 当前外层树节点是叶节点
修改这个外层树节点所对应的内层树,由于是单点修改,找到内层树叶节点时,直接修改。
2. 当前外层树节点不是叶节点
修改这个外层树节点所对应的内层树,同理找到内层树叶节点,但是不能直接修改,而是要从当前外层树的儿子所对应的内层树的相同的叶节点更新上来
# include <bits/stdc++.h>
using namespace std;
typedef long long ll;
namespace IO {
const int maxn((1 << 21) + 1);
char ibuf[maxn], *iS, *iT, c;
int f;
char Getc() {
return (iS == iT ? (iT = (iS = ibuf) + fread(ibuf, 1, maxn, stdin), (iS == iT ? EOF : *iS++)) : *iS++);
}
template <class Int> void In(Int &x) {
for (f = 1, c = Getc(); c < '0' || c > '9'; c = Getc()) f = c == '-' ? -1 : 1;
for (x = 0; c <= '9' && c >= '0'; c = Getc()) x = (x << 3) + (x << 1) + (c ^ 48);
x *= f;
}
}
using IO :: In;
const int maxn(1e5 + 5);
int ch[2][maxn], fix[maxn], val[maxn], size[maxn], trash[maxn], top, tot, rt;
inline int NewNode(int v) {
int x = top ? trash[top--] : ++tot;
fix[x] = rand(), val[x] = v;
ch[0][x] = ch[1][x] = 0, size[x] = 1;
return x;
}
inline void Update(int x) {
size[x] = size[ch[0][x]] + size[ch[1][x]] + 1;
}
int Merge(int x, int y) {
if (!x || !y) return x + y;
if (fix[x] > fix[y]) {
ch[1][x] = Merge(ch[1][x], y), Update(x);
return x;
}
else{
ch[0][y] = Merge(x, ch[0][y]), Update(y);
return y;
}
}
void Split(int x, int k, int &l, int &r) {
if (!x) l = r = 0;
else {
if (val[x] <= k) l = x, Split(ch[1][x], k, ch[1][l], r), Update(l);
else r = x, Split(ch[0][x], k, l, ch[0][r]), Update(r);
}
}
int x, y, z;
inline void Insert(int v) {
Split(rt, v, x, y), rt = Merge(Merge(x, NewNode(v)), y);
}
inline void Delete(int v) {
Split(rt, v, x, y), Split(x, v - 1, x, z);
rt = Merge(Merge(x, Merge(ch[0][z], ch[1][z])), y);
trash[++top] = z;
}
inline void Rank(int v) {
Split(rt, v - 1, x, y);
printf("%d\n", size[x] + 1);
rt = Merge(x, y);
}
inline int Kth(int o, int v) {
while (true) {
if (size[ch[0][o]] + 1 == v) return val[o];
else if (size[ch[0][o]] >= v) o = ch[0][o];
else v -= size[ch[0][o]] + 1, o = ch[1][o];
}
}
inline void Pos(int rk) {
printf("%d\n", Kth(rt, rk));
}
inline void Pre(int v) {
Split(rt, v - 1, x, y);
printf("%d\n", Kth(x, size[x]));
rt = Merge(x, y);
}
inline void Suf(int v) {
Split(rt, v, x, y);
printf("%d\n", Kth(y, 1));
rt = Merge(x, y);
}
int main() {
srand(time(NULL));
int n, op, v;
for (In(n); n; --n) {
In(op), In(v);
if (op == 1) Insert(v);
else if (op == 2) Delete(v);
else if (op == 3) Rank(v);
else if (op == 4) Pos(v);
else if (op == 5) Pre(v);
else Suf(v);
}
return 0;
}
可持久化就是每次分裂/合并的时候都记录一下节点即可
inline void Copy(int x, int y) {
fix[y] = fix[x], size[y] = size[x], val[y] = val[x];
ch[0][y] = ch[0][x], ch[1][y] = ch[1][x];
}
int Merge(int x, int y) {
if (!x || !y) return x + y;
if (fix[x] > fix[y]) {
int p = ++tot;
Copy(x, p), ch[1][p] = Merge(ch[1][p], y), Update(p);
return p;
}
else{
int p = ++tot;
Copy(y, p), ch[0][p] = Merge(x, ch[0][p]), Update(p);
return p;
}
}
void Split(int x, int k, int &l, int &r) {
if (!x) l = r = 0;
else {
if (val[x] <= k) l = ++tot, Copy(x, l), Split(ch[1][l], k, ch[1][l], r), Update(l);
else r = ++tot, Copy(x, r), Split(ch[0][r], k, l, ch[0][r]), Update(r);
}
}
Version Controlled IDE
可持久化 模板(没事不要乱回收节点。。。)
T-Shirts
对于维护每个人金钱的
枚举 每次 出小于价钱和大于等于的,另一边打一个减法标记
注意到 时候没有大小关系了,不满足顺序
考虑暴力合并
为第 个人的金额, 为他需要支付的钱那么如果这个人需要暴力插入,那么必须满足:
所以
每次操作 至少要减去它的一半,所以最多会被暴力 次
最长上升子序列
简单
KLO
就是求区间中位数,每次移动区间,平衡树维护
小蓝的好友
考虑枚举下边界,计算答案
注意到可以按照列建一棵树,以行为 的 权值(大根堆)
那么可以得到贡献就是每个点的
鏖战表达式
可持久化 模板。。。毒瘤
[IOI2007]Sail
帆的顺序对答案没有影响,如果一个高度有 个,那么对答案的贡献就是
帆的高度没有什么性质不好操作,那么我们考虑把其高度从小到大排序
这样就好贪心了,相当于每次可以使得高度增高,要选出最小的 个高度使得其个数
每次给前 个 只会改变前 个的最大值和 个之外的大小关系
直接弄个平衡树删除再插入就好了, 可能好写得多
可能和 分裂类似
什么鬼。。。不就是可持久化线段树合并。。。
空间
预处理时间
查询
做法,在线段树的每个点 保存一个 和
表示 的信息和和 的信息和
那么每次查询 只要知道 的 即可
即 表示去掉不同的位置
那么查询 即可
没有人的算术
如果能给每个 按照权值编号就好了
假设之前已经有了所有的权值的编号,现在考虑编号新的
如果看过了陈立杰的论文的话,不难得到一个重量平衡树的做法
给树上每个子树一个实数权值区间 ,这个点权值为
左子树 右子树
只需要选择一个树高 的树(treap/替罪羊树)使得满足精度要求即可
紫荆花之恋
暴力思路就是每次点分治计算答案
点分治之后,条件可以变成
每次只要查找 的排名然后插入 ,随便拿个平衡树维护即可
考虑如果带修改,就是动态点分治,每个点维护两个平衡树,一个表示自己的贡献,一个表示上一层重心要减去的在同一棵子树的贡献
每次加入一个点就直接在父亲下面,暴力向上更新每一个重心的两个平衡树,顺便查询答案
求距离什么的直接暴力维护倍增数组就行了
现在的问题就是可能暴力向上更新的时候链长过大
这个时候运用替罪羊树的思想,维护一个 ,不平衡就暴力重构这个点分树子树的所有信息即可
把1e9看成是1e9+7调了一年
即时战略
按照紫荆花之恋的做法,动态维护一下点分树的形态
把点随机打乱
每次从当前的根开始 ,如果已经有了就暴力跳到那个点
否则加入这个点
方伯伯的OJ
分裂,毒瘤。。。
Souvenirs
好题啊
考虑枚举右端点,更新左边端点的答案
先考虑 的情况,另外的情况类似
对于右端点 找到最靠后的 用 更新答案
然后找到最靠后的 做到找不到结束
分析复杂度 ,因为 之前已经更新了
那么 所以是 的
找 可以直接主席树
Shopping
显然是要选择一个连通块,可以枚举一个点做树形依赖背包(每次要么跳过一个子树,要么选,最好是倒过来做)
然后还要分组背包单调队列优化
你发现可以 每次保留重儿子的信息
inline void Merge(int u, int v) {
for (int i = 0; i < c[u]; ++i) {
int l = 0, r = -1;
for (int j = i; j <= m; j += c[u]) {
while (l <= r && (j - q[l]) / c[u] > d[u]) ++l;
if (l <= r) Cmax(f[u][j], f[v][q[l]] + (j - q[l]) / c[u] * w[u]);
while (l <= r && f[v][j] - j / c[u] * w[u] >= f[v][q[r]] - q[r] / c[u] * w[u]) --r;
q[++r] = j;
}
}
}
inline void Max(int u, int v) {
for (int i = 0; i <= m; ++i) Cmax(f[u][i], f[v][i]);
}
void Solve(int u, int ff, int tp) {
for (int e = first[u], v; ~e; e = edge[e].next)
if ((v = edge[e].to) != ff && v != son[u]) Solve(v, u, 0);
if (son[u]) Solve(son[u], u, 1);
for (int i = son[u] ? dfn[son[u]] - 1 : ed[u]; i >= dfn[u]; --i) {
if (i != ed[u]) Merge(id[i], id[i + 1]);
Merge(id[i], 0);
if (i != dfn[u]) Max(id[i], id[ed[id[i]] + 1]);
}
for (int j = 0; j <= m; ++j) Cmax(ans, f[u][j]);
if (!tp) {
for (int i = dfn[u]; i <= ed[u]; ++i)
for (int j = 0; j <= m; ++j) f[id[i]][j] = inf;
}
}
配对树
存在两个点 他们在子树内都没有配对,那么假设他们分别和 配对,显然改为 配对 配对更优,所以每棵子树中未匹配的点至多只有一个。
考虑每一条边,这一条边会被计算贡献当且仅当这条边连接的子树里有奇数个选出的点。
枚举一条树边,把它子树内的点全部在序列上标为 其余标为 ,来把序列转成 串,于是问题变成了统计 串中包含偶数个 的子串数目。
对 串做前缀和得到 ,则一个区间 要被统计当且仅当
由于 ,我们可以对 按照下标奇偶性分别维护,分别计算 中奇数的数目和偶数的数目,那么包含这条树边的区间数目就是两边的奇数的数目和偶数的数目相乘的和。
可以考虑线段树合并维护。
字符串树
每个点维护到根的 即可
REBXOR
前缀最大区间和后缀最大区间, 即可
A simple rmq problem
三维数点,
Hitchhiking in the Baltic States
设 表示长度为 的上升序列的最后一个数字最小为
那么对于一个 ,首先所有的 都可以 转移到
然后对于 都可以 转移,向后移一位
要删掉/取
用平衡树维护即可
[Ioi2005]mou
区间加,维护最大前缀和,线段树上二分找到答案
[Tjoi2017]异或和
考虑每一个二进制位的贡献,前缀和后你发现会有借位的情况
那么实际上只要分类考虑这一位的 而满足要求的实际上就是去除这一位和高位,其它位置要满足小于等于或者大于这个前缀和的后面的位置
树状数组维护即可
「2017 山东一轮集训 Day5」距离
拆分路径为到根的链相减,类似于 或者开店一样,每个点覆盖到根的边,主席树维护
七彩树
考虑维护每个颜色的虚树
按照 顺序维护这些点,在这些点上 ,相邻点的 处 ,这样,无论包含哪一个子树的几个点,子树权值和始终为
可以用 实现
现在变成了二维数点的问题,按照深度依次加入每个点用主席树维护,每个线段树维护 序即可
Huge Discount
当存在一种字符出现次数超过一半时,一定可以把另外两种字符全部删完;当不存在一种字符出现次数超过一半且长度为偶数时,一定可以全部删完。
现在只需要考虑一种情况:长度为奇数,且不存在一种字符出现次数超过一半。这时一定会留下一个字符。
枚举留下的字符是谁,这就要求它前后都可以恰好删完,也就是要求前后都不存在一种字符出现次数超过一半。对每一种字符维护区间和,然后限制大概就长成个三维偏序的样子。
发现每个位置最多违反一个限制(不可能两种字符出现次数同时超过一半),所以直接统计违反限制的个数就可以知道某种字符是否可行了,直接上树状数组
跳伞求生
直接贪心
考虑到 个人的贡献都是 ,另外 个人的贡献都是
首先 的限制不好做,所以将 从小到大排序
枚举 ,每次把小于 的 加入优先队列,只要从中间选一个最大的匹配,之后将 加入优先队列,表示可以反悔
代码真的短
[SCOI2008]斜堆
考虑最后加入的点:
它到根的所有点都是左儿子,因为每次都是往左
它没有右儿子
考虑一个点如果它没有左儿子,那么它没有右儿子,被换到右边的前提是左边必须加入了一个点
那么考虑从后往前确定加入序列
由上面这些性质可以得到
最后加入的点一定是在一条链上,并且是满足 的最浅的点
因为如果它的下面的点是最后加入的,那么它就要交换左右子树,变成没有左儿子的了,与性质 矛盾
特殊情况,如果它有一个没有儿子的左儿子,那么显然儿子也可以成为答案,为了保证字典序,要选择这个儿子
[ZJOI2008]泡泡堂
类似田忌赛马,注意到有平局的出现,那么没有必要用最弱的送死,如果它可以打过对方最弱,那么就打
皇帝的烦恼
设 表示和 最多有多少相同的, 表示最少
那么
二分 即可
Curfew
直接贪心,能放的就放,每次扩大
[Poi2004]SZN
二分答案,然后贪心匹配,在每个点二分留下哪一条链,注意特判根结点的情况
sequence
牛逼的贪心
显然前面的减少的越小后面越可能出现不降序列
考虑大根堆,每次加入一个数 ,如果小于堆顶即小于之前的最大值 ,那么就要调整
对于之前的次大的
如果 那么把 变成
否则把 都变成
阿狸和桃子的游戏
先手选看成是加入与 相连的边权,后手为减去,这样恰好能使不在同一个集合的边的贡献为
那么直接这样贪心选择即可
High Card Low Card
贪心,前面一定选大的,后面一定选小的,预处理后枚举断点即可
[Noi2017]蔬菜
贵的蔬菜肯定是优先买,并且能在后面买就拖到后面,那么贪心策略确定
每次选择最靠后的时间覆盖 次,用并查集路径压缩优化暴力覆盖
[Tjoi2013]拯救小矮人
贪心的把身高 臂长大的放在后面,然后按照顺序 哪些人出去,每次减去它的高度即可
[CTSC2007]挂缀pendant
按照某种顺序排序贪心,能放则放,否则看能不能替换掉 大的
Sparklers
首先答案显然具有可二分性,考虑如何检查当前速度是否合法。
不难发现显然所有人都是朝着萝卜被点燃的人走的,那么意味着最终会聚在一起的人一定是一个连续的区间。
不妨令 表示这段区间内的人是否能够在 时间内全部聚集在一起。
那么显然只需要考虑 l, r 两人能否到达同一个位置。
如果可行则满足 , 同时 中至少有一个是可行的。
这个过程也是一个从 逐渐拓展成 的过程。
继续考虑之前那个式子:
令 。其实就是 。
现在其实就是要沿着一条合法的路径从 走到某个 。
那么我们贪心的考虑这个移动的过程。假设当前的区间是 , 如果存在一个 满足 ,并且 , 那么可以直接贪心的从 走到 更大,更靠左显然更优。右侧的贪心同理。
这样子从 开始走一遍,再从 开始走一遍,看看能不能走到一起就好了。
从两侧走的原因是中间可以动不了了,但是不难证明在有解的情况下两侧总是有一侧能够动的。
Spiders Evil Plan
贪心
以 为根的时候,直接选择 个叶子节点,每次选一个最大的就把路径权值清
然后这样选的第一个一定是直径的端点,所以对直径的两个端点分别做操作求答案取
如果 不被包含,那么一定是它的子树最大深度的叶子替换掉最后一个加入的叶子
减去最小的多余的贡献即可,这个贡献只有两种情况,讨论一下
对于一条边,算经过这条边的路径的答案
点分治不方便的就是同一棵子树的容斥,而边分治不用考虑
直接边分治显然菊花就卡掉了
所以我们要转二叉树
具体来说就是把一个点的儿子建一棵线段树,添加虚拟节点,点权为其父亲的点权,只有线段树的叶子节点有边权
int Build(int val, int l, int r) {
if (l > r) return 0;
if (l == r) return tmp[l];
int mid, ls, rs, cur;
mid = (l + r) >> 1, cur = ++n, w[cur] = val;
ls = Build(w[cur], l, mid), rs = Build(w[cur], mid + 1, r);
if (ls) Add2(cur, ls, ls <= m);
if (rs) Add2(cur, rs, rs <= m);
return cur;
}
void Rebuild(int u, int ff) {
int e, v, mid, ls, rs;
len = 0;
for (e = head[u]; ~e; e = edg[e].next)
if ((v = edg[e].to) != ff) tmp[++len] = v;
mid = (len + 1) >> 1;
ls = Build(w[u], 1, mid), rs = Build(w[u], mid + 1, len);
if (ls) Add2(u, ls, ls <= m);
if (rs) Add2(u, rs, rs <= m);
for (e = head[u]; ~e; e = edg[e].next)
if ((v = edg[e].to) != ff) Rebuild(v, u);
}
通道
就是求两个点 使得 最大
step1对第一棵树边分治
那么变成 最大
并且 属于边分开的不同的集合
step2对第二棵树建虚树
建出 的虚树
变成
枚举 那么变成求一个类似于 的最大值
step3第三棵树
不需要什么,上式类似于一个求最长链的东西
而两棵子树合并之后的最长链的端点一定是原来两棵树的最长链的端点
所以只需要在第三棵树上求距离就好了,然后在第二棵树上 维护
暴力写挂
看到要求两棵树的 深度不太好操作
考虑枚举第二棵树的 ,这样剩下的都是只和第一棵树有关的
而注意到
那么
这样就好多了,可以直接沿用WC2018通道的做法
对于第一棵树进行边分治,把两边的集合合起来在第二棵树上建个虚树
然后在虚树上枚举 , 统计不属于同一个集合的答案
复杂度 可以强行优化到
上述做法不够优美
考虑另外一种做法,仍然是对于第一棵树进行边分治
对于每个点,维护每一次边分治时的集合和到分治中心的距离
那么只需要在第二棵树上枚举 统计每次边分治时不同集合的最大的贡献就好了
这个可以用线段树(二叉树)合并实现,
然后考虑怎么维护每一次边分治时的集合和到分治中心的距离
直接想法是直接暴力插入,
然而边分治每次是分成两个集合,类似一个线段树的结构
所以可以对于每个点维护一个线段树(二叉树),要保证树上每个点和是哪一次边分治对应
只需要将这些点的树的当前点记录下来
每次边分治的第一个集合向左跳,第二个向右跳就可以 建树了
复杂度
Painting Edges
带撤销带权并查集,可以则改,并且把修改丢进线段树,否则不改变,把原来的颜色丢进去
Shortest Path Queries
类似WC的XOR,线性基,每次把环的路径丢进去,然后每次把路径丢进去查询即可
[WC2005]双面棋盘
直接线段树分治 并查集
也可以 维护以时间为关键字的最大生成树
百度地图的实时路况
线段树分治
String Set Queries
自动机 + 二进制分组,答案具有可减性,直接删除标记减 即可
数列
这是个曼哈顿距离,不好做
转化成切比雪夫距离
切比雪夫距离为
曼哈顿距离为
点 变成
求切比雪夫距离就是原来的曼哈顿距离
那么问题就变成了每次在平面内加入一个点,每次询问矩形和
树套树/ +扫描线即可
玄学
考虑对于操作时间建立线段树,二进制分组
那么现在主要的问题就是怎么合并信息
你发现一个性质,就是每个修改只会在整个区间内增加两个端点
那么我们二进制分组可以得到每个区间内最多只有区间长度级别段,每一段的修改都是一样的
那么可以直接一层层归并上来
最后询问就是二分每一个线段树的节点的询问段即可
unknown
这个题目实际上可以建立出树,然后重链剖分维护一条链的凸包
然后离线询问排序斜率做到 ,或者点分治+平衡树也行
但是这个题目卡空间,数组一不小心就爆了卡一卡也能过
考虑其它空间常数小并且又好写的做法
根据一般的二进制分组的方法,每次这个块满了就合并儿子的凸包
这样显然不对,只要又删又加就假了
我们换一种方法,每次这个块满了就合并线段树同一层前一个节点的儿子的凸包
这样每次都要花费 次添加操作才能换来一次 的合并
此时的没有合并节点顶多 个
查询就定位每个节点,在凸包上二分即可
时间 空间
取余最大值/Yura and Developers
最大值分治,然后主席树查询,或者直接把查询的东西存下来,离线查询
Norma
分治,考虑过中点的区间的答案
枚举左边的端点,右边两个端点分别维护 左边最大的最靠后的 ,以及 左边最小的
然后分
,, 且
三种情况讨论贡献
你发现可以用前缀和优化
High Cry
考虑算出或的权值正好等于最大值的区间个数(因为或起来一定 最大值)
考虑枚举每个值,那么要求其它的都是它的子集
每一位考虑然后取交,注意还要对它作为最大值的区间取交
Prime Gift
二分
为了防止分成两边时一边过多,可以考虑把 排序,取奇数下标和偶数下标
Iloczyn
搜出所有的约数,然后剪枝
貌似是一些块用链表维护,核心思想为分裂和合并
先只考虑 1,把询问按照左端点的块排序,相同则右端点从大到小
每次先把左端点放在块的最左边,右端点单调,只需要每次暴力删除左边,得到答案之后再滚(还原)回去即可
如果一个题目你发现直接询问空间小时间大,而暴力预处理空间大时间小。
你可以考虑分块,大于 暴力查询,小于的暴力更新(预处理)
蒲公英
求区间众数,考虑分块
处理出任意的两块之间的众数以及块内的众数,
询问直接借用中间的整块的答案,然后左右不完整的暴力更新
QAQ的序列
分块
对于 ,处理出出现次数大于 的数字,然后暴力枚举
对于 ,处理出两块之间每个数出现的次数以及每种次数出现的个数,然后暴力调整
细节很多
第十四分块(前体)
好题
考虑莫队,每次移动端点,我们都要询问区间内和当前数字异或有 个 的数字个数
询问 可以再次离线,拆成询问 和
考虑莫队要移动 的 到
假设
那么相当于每次询问 和 ,然后 直到
即每次询问 和 , 和
对于前面的部分,它每次都是前缀区间的最后一个数字询问前缀区间,可以预处理
对于后面的部分,它每次都是一个数字询问一个固定的区间,直接在 处打上一个询问 的标记,之后离线暴力询问 ,这一部分复杂度和莫队一样
然后其它移动端点的方法类似
注意细节即可
吉夫特
可以发现, 当且仅当
即 二进制下为 的子集
那么可以直接写一个 的枚举子集
但是还有一个 的做法
把数字分成前 位和后 位
设 表示前 位为 ,后 位为 的超集的答案
那么对于一个数 ,分成 ,转移的时候枚举 的超集,更新的时候枚举 的子集即可
能量采集
第一眼,强上矩阵预处理 的幂之后倍增,发现 太大了
怎么办?
那就预处理 的幂之后倍增
Hello world!
长度小于根号的直接暴力预处理,树状数组统计,修改用并查集压缩
否则暴力
「雅礼集训 2017 Day1」字符串
直接建立
对于 暴力枚举区间计算贡献,用 记录某一个询问有哪些,每次二分即可
否则就在 上跑,记录每个右端点的位置,枚举每个询问然后在 树上倍增即可
套路
一个性质
根号分治,区间长度小于 直接暴力区间
大于 则答案不超过 ,可以枚举区间右端点,维护每种答案的左端点最右能取到的位置
最大独立集和最小点覆盖互为补集
最小点覆盖
先最大匹配
每次从左边找到一个未匹配点增广(假的增广,显然增广不了,因为已经是最大匹配)
然后标记点
最后左边没有标记过的点和右边标记过的点就是最小点覆盖
伪证:因为一条假的增广路一定是左边的点作为开头和结尾的,所以选右边的就能覆盖这个假的增广路
最长反链
最大独立集就是最长反链可能,猜的
去掉这些最小点覆盖就是要找的最长反链
先用 求任意一组最大匹配,然后建一张新图:
匹配边 , 到 连边
非匹配边 , 到 连边
匹配的左点 ,
不匹配的左点 ,
匹配的右点 ,
不匹配的右点,
然后用 求强连通分量
是可行边的条件:
是匹配边或者 在同一个 里。
即残量网络
伪证:
每找到一个环,就说明可以根据环的方向退流+增广得到一组新的匹配。
你发现不在同一个 里的匹配边就是必须边。
在残余网络上跑 求出所有
记 为点 所在 的编号
显然有 (否则 到 有通路,能继续增广)
为点数, 为边数, 为平面区域数
二分图 中,,当且仅当 中任意 个顶点都与 中至少 个点相邻时,该二分图存在完美匹配
一个长度为 的序列 ,是合法的比分序列当且仅当:
且 时这个式子必须取等号。
或者倒过来和下面一样
EarthCup
个人两两之间打一场比赛,共 场,每场比赛赢的人得一分。
现给出每个人的得分,问得分是否合法。
把第 个点拆成 个,相当于是问左右各 个点的二分图是否存在完美匹配。Hall定理。
将 从大到小排序,记 表示前 大的 值之和,需要满足
[POI2009]Lyz
hall定理,贪心显然是把大小一样的一起选,而诶日一定是选一段连续的
那么要求
即
每个点减去 维护最大子段和
将边定向,由度数小的点指向大的,相同则指向编号大的
枚举每条边,将所有 与相连的点打上标记,再枚举与 相连的点,如果有标记则算进答案
每个点的出度都小于等于
证明:对于度数小于 的点显然,度数大于 的点出度一定指向度数大于 的点,而度数大于 的点不超过 个,所以每个点的出度都小于等于
可以保证是个有向无环图。
为什么呢,要想定向存在环,则这个环上的点度数必须相同,由于保证了编号从小到大走
所以是不可能存在环的。
复杂度
用最少的点让每条边都至少和其中一个点关联。
最少点覆盖数 最大匹配数
用尽量少的不相交的简单路径覆盖有向无环图所有顶点
最小路径覆盖数 节点数 二分图的最大匹配
证明:
每有一个匹配,就有两条路径的合并
即所需路径减 ,那么答案就是
选择最多的顶点,使得所选择的点集中任意两点之间没有连边
二分图的最大独立集 = 点数 二分图最大匹配数
证明:
即删掉最少的点使得剩下的点没有边相连,即 最小点覆盖
算法
初始时把所有点放在一个集合
从中任选两个点出来跑原图中的最小割
然后按照 集合与 集合的归属把当前集合划分成两个集合,递归处理
这样一共跑了 次最小割
可以证明图中任意一对点之间的最小割的数值都包含在这 个数值当中
把每次求出的最小割看成是两个点之间的边,可以建出一棵树
定理1
任意三点之间的最小割一定是两个相等的较小值和一个较大值
证明
设任意三点 之间的最小割分别为
设 是这三者中的最小值
那么在做 割时, 一定属于其中的某一个集合,设其与 同属于一个集合
那么就有
又因为 ,所以两者相等
定理2
图中至多只有 种不同的最小割
证明
编了一个构造的证明
首先根据定理 ,可以转化成如下问题:
个点的无向完全图,要给每一条边染色,要求每个三元环上有两条边同色,求最多可以染多少种颜色
考虑归纳法
假设现在已经有一条长度大于 的链 到 上的边的颜色互不相同
考虑染 这条边
如果链长 ,那么 只能选择链上某条边的颜色
如果链长 ,假设两个端点在链上的不是 的边的颜色都是链上某条边的颜色
那么取出其中两条 和 , 只能选择两个中其中一条边的颜色,即链上某条边的颜色
所以可以得到,颜色互不相同的边不能形成环,所以最优的显然是树,即 中颜色
无源汇有上下界可行流
流量平衡
有源汇有上下界最大流
流量平衡 , 的最大流
有源汇有上下界最小流
流量平衡 , 的最大流(退流)
Pollutant Control
损失最小的前提下停止的卡车数最少
可以考虑用进制数来表示代价,损失放在首位,数量在末位
最小割
见上面
[Wc2007]剪刀石头布
竞赛图定向,使得三元环最多
正难则反,求不是三元环的最少
考虑不是三元环,那么其中必定有一个点出度为
那么如果一个点出度为
那么就会贡献 的点对不是三元环
那么
即
只要 最小就好了
运用 费用流拆边权的思想
这个东西的斜率递增,也就是差分后递增,那么可以拆成费用为 这样的形式,流量都为 ,这些数字显然只会选择一个前缀,那么就可以表示出平方数了
A + B problem
主席树优化连边,注意新建的点要向原来的点连边!!!
无限之环
要给每个管道匹配一个后继,这是一个回路模型
强制 流入一些点流量,一些点流出流量到 ,那么黑白染色即可
把每个点拆成 个点分别表示四个方向和自己,四个方向向四个方向对应的点的四个方向连边
对于一个出口的好做,直接连权值为 的边,流量为
两个的比较神仙,每个方向向相对的方向连 边正好,流量为
三个的直接每个方向向没有的方向连边 ,流量为
Masha与老鼠
模拟费用流,关键在于匹配边不会交叉
每次增广都会使一只未匹配的老鼠匹配或者使一只往左跑的老鼠改为往右跑
所以可以得到增广的次数为
具体来说,一个洞每次只丢一个,每用一个再丢一个
[IOI2017]Wiring
模拟费用流
拆点,一个权值为 ,容量为 ,另一个权值为 ,容量为
因为两侧都有了容量为 的点,所以我们要重新分析一下复杂度。
如果是第一类点 匹配了左边某一个点 ,则 不可能反悔。因为 是必须匹配的, 一旦反悔,a 和 将同时连往 右边的点,匹配交叉,矛盾
如果是第二类点 匹配了左边某一个点 ,则 一定是第一类点。因为 是必须匹配的,所以 a 一旦反悔, 和 将同时连往 右边的点,匹配交叉,矛盾
所以,每次匹配完之后,只有一方可能反悔。增广总次数不超过
雪灾与外卖
遇到一只老鼠时,老鼠可能会先匹配之前的堆,然后往老鼠堆中丢一个这只老鼠反悔的操作。
这个过程放到本题,堆操作总次数依然是线性。
当遇到一个洞时,洞可能会匹配一大堆老鼠,即从老鼠堆中取一大堆元素。然后洞和老鼠都有可能反悔,这样要同时往老鼠堆和洞堆中丢元素。
每次一个洞匹配了若干个老鼠之后,往老鼠堆中丢的元素都是等权的。这样我们就只需要在堆中对每个元素记录一下出现的次数,堆的操作总次数就变成了线性。
看代码清晰的多QwQ
if (!hole.empty()) {
ans += (v = -hole.top().first + x[i]);
id = hole.top().second, mouse.push(make_pair(x[i] + v, 0));
hole.pop();
if (id) hole.push(make_pair(y[id], id));
while (!hole.empty() && -hole.top().first + x[i] < 0) {
ans += (v = -hole.top().first + x[i]);
id = hole.top().second, hole.pop();
hole.push(make_pair(x[i], 0));
if (id) hole.push(make_pair(y[id], id));
}
}
else ans += inf, mouse.push(make_pair(x[i] + inf, i));
mouse.push(make_pair(x[i], i));
「ICPC World Finals 2018」征服世界
在 处考虑,模拟费用流,维护两个可并堆即可
inline int Bfs() {
int e, u, v;
memset(dis, 63, sizeof(dis));
memset(vis, 0, sizeof(vis));
dis[T] = 0, vis[T] = 1, Q.push(T);
while (!Q.empty()) {
u = Q.front(), Q.pop();
for (e = first[u]; ~e; e = edge[e].next)
if (edge[e ^ 1].f && dis[u] - edge[e].w < dis[v = edge[e].to]) {
dis[v] = dis[u] - edge[e].w;
if (!vis[v]) vis[v] = 1, Q.push(v);
}
vis[u] = 0;
}
return dis[S] != dis[T + 1];
}
int Dfs(int u, int maxf) {
if (u == T) return maxf;
vis[u] = idx;
int ret = 0, &e = cur[u], v, f;
for (; ~e; e = edge[e].next)
if (dis[v = edge[e].to] + edge[e].w == dis[u] && edge[e].f && (vis[v] ^ idx)) {
f = Dfs(v, min(maxf - ret, edge[e].f));
ret += f, edge[e].f -= f, edge[e ^ 1].f += f;
if (ret == maxf) return ret;
}
if (!ret) dis[u] = dis[T + 1];
return ret;
}
inline int MCMF() {
int ret = 0, f, sum = 0;
while (Bfs()) {
idx = 0;
while (true) {
++idx, memcpy(cur, first, sizeof(cur));
ret += (f = Dfs(S, 1e9)) * dis[S], sum += f;
if (!f) break;
}
}
return sum == flow ? ret : -1;
}
详见国家集训队 by cyb
[SDOI2006]二进制方程
把相等的并查集连起来,高精度即可
Robots
每个点把其边按照边权排序,询问离线,按照 排序
那么满足要求的边可以单调,如果都满足要求了就用并查集把父子连起来即可
RAJ-Rally
先建立汇点和源点向每个点连边,求出每个点 到源点和汇点的最长路径
那么边 的答案就是
考虑删去了某个点 那么就是要求 的最大值,并且不经过
如果 的拓扑序都小于或者大于 ,那么要么 经过 要么 不优
找到那个 连通的拓扑序列最前面的点或 连通的拓扑序列最后面的点就可以证明
那么直接用个堆按照拓扑序列贪心就好了,每次弹出不合法的
[HNOI2014]道路堵塞
删掉边后的最短路一定是原来最短路的一个前缀然后走到一个后缀最后到终点
先把所有的给定的边 掉,然后考虑按照顺序加入边
每次到达最短路径上就把到终点的距离和当前最短路径加入堆中
然后从堆中取出元素,不合法则弹出
复杂度
棋盘上的守卫
行和列连边,显然是要求一个环套树森林
那么记录一下这个连通块是否形成了环即可
狼人
把边权看成是 两遍重构树之后就是一个二维数点问题
失格
暴力枚举倍数,连接最接近的边,然后 可以过
Royal Questions
将每个公主的两个候选人连边,那么使得每个王子的入度不大于1即是一种合法的方案
求一个最大权环套树森林
PA2014Final Krolestwo
对于二分图,从 交替走回到 部的路径长度一定是偶数。
沿用欧拉路做法,建一个点 ,把 与度数为奇的点连边。
然后考虑把点 拆成两个点 ,把原图改造成二分图。
改造后:
原图边 对应 或者 中的一条。
每个点的度数为偶数。
如果能做到上述转化,跑欧拉路即可得解。
因为每个点度数为偶,即不存在脱离的边,所以一定能跑出解。
转化方法?
首先先一顿乱连,把二分图整出来。
显然若保证左侧度数都为偶数,那么右侧一定度数都为偶数。
然后跑原图的一棵生成树,自底向上不断调整即可。
Maximum Matching
每个颜色看成点,那么就是求最大值合法的欧拉路径
枚举断边然后计算即可
Sightseeing tour
先给每条无向边随便定一个方向
然后记录每个点的入度 和出度
对于 不是偶数的图,那么显然不合法
否则就是要让
而出入平衡类似于流量平衡
考虑网络流
如果 那么 向该点连流量为 的边
如果 那么该点向 连流量为 的边
无向边保留在图中,流量为 ,表示只能改变一次方向
那么对于一条增广路
直接把这条路径的所有边反向就可以使得
所以直接最大流,满流则有解
原始生物
连边,求有向图每个连通块中经过每一条边的最短路径,判断欧拉回路,其它的不满足要求的点两两匹配即可
相框
首先所有度数大于 的都要拆,拆成若干度数为 的或者加一个度数为 的
如果只有一个连通块,把为 的匹配即可
否则要把每个连通块都弄出两个 来,串成环,直接并查集即可
太鼓达人
首先答案就是 ,将 位的二进制数看做点, 位的二进制数看成边,边由入点和出点接龙得到,标准的欧拉图
吃货jyy
三进制状压是否选以及选了之后的度数,注意可以选择重的边。。
Tanya and Password
把两个字符看成是点,三个字符是边,跑一遍有向图欧拉回路
Weird journey
把每条边变成两条,问题转化为删去两条边是否存在欧拉路径
如果没有自环,显然就是连接了同一个点的边
否则可以选两个自环或者一个
King Arthur's Knights
任意找两个相邻的节点 和 ,然后左右扩展
Tour Route
枚举终点,然后强制不能直接接在终点后面
Turysta
每个强连通分量分别求 回路即可
先求出一条 路径,然后有一条回路,考虑加入一个点
如果 直接连上环,直接连上
否则,因为是竞赛图且强连通,所以一定有一条路径使得 到环上
写法:可以维护当前的环上的两个点,首先不把它们接上,每次加入一个点再接上即可
void Hamilton() {
int l = que[1], r = l;
for (int i = 2; i <= len; ++i) {
int cur = que[i];
if (lnk[cur][l]) nxt[cur] = l, l = cur;
else if (lnk[r][cur]) nxt[r] = cur, r = cur;
else {
for (int k = 0, j = l; j; k = j, j = nxt[j])
if (lnk[cur][j]) {
nxt[k] = cur, nxt[cur] = j;
break;
}
}
}
r = 0, vis[l] = 1;
for (int i = nxt[l]; i; i = nxt[i])
if (!vis[i]) {
if (r) {
for (int j = i; j; j = nxt[j]) {
int flg = 0;
for (int k = r, lst = l; ; lst = k, k = nxt[k]) {
if (lnk[j][k]) {
if(j != l) nxt[l] = r;
nxt[lst] = i, flg = 1;
l = j, r = k;
break;
}
if (k == l) break;
}
if (flg) {
for (int k = i; ; k = nxt[k]) {
vis[k] = 1;
if (k == j) break;
}
break;
}
}
}
else if (lnk[i][l]) r = l, l = i;
vis[i] = 1;
}
for (int i = 1; i <= len; ++i) vis[que[i]] = 0;
nxt[l] = r, len = 0;
}
[IOI2007]Flood 洪水
按照顺序依取出 最小的点,删掉所在的外围的边,如果删的时候边不成环就是答案
Price List
第一种是 的最短路,然后每两条边替换成
第二中,枚举一个点,类似找三元环,标记它的所有出边的点
然后枚举这些点在新图的出边,如果没有被标记就说明可以走 边,然后把这条单向的边在新图中删除
复杂度同找三元环复杂度
基本问题
有一堆石子,总个数是 ,两名玩家轮流在石子堆中拿石子,每次至少取 个,至多取 个。取走最后一个石子的玩家为胜者。判定先手和后手谁胜。
解决方法
如果 则先手必败,否则先手必胜。
基本问题
有两堆石子,石子数可以不同。两人轮流取石子,每次可以在一堆中取,或者从两堆中取走相同个数的石子,数量不限, 不能不拿,取走最后一个石头的人获胜。判定先手是否必胜。
解决方法
这个东西意义不是很大,打表找规律之后可以发现先手必败的状态一定形如
。其中 , 表示不大于 的最大整数。
基本问题
有三堆石子,两人轮流取,每次可以从一堆中取走任意数量个石子,至少取走一个,取走最后一个石头的人获胜,问先后手谁胜。
一般推广:有 堆石子 ,两人轮流取,每次可以从任意一堆石子中取走至少一个石子,问先后手谁胜。
解决方法
方法很简单,直接求所有
的异或和,如果异或和为 则先手必败,否则先手必胜。
基本问题
一堆石子共 个,两人轮流拿,不能不拿,要求该轮拿走的石子的个数不能超过上一轮的 倍
数,先手首次操作不能把石子都拿走,取走最后一个石头的人获胜
k=1
当石子的个数是 时先手必败,否则先手必胜
k=2
当石子的个数是斐波那契数列中的元素时先手必败,否则先手必胜
基本问题
一共 堆石子,每次每人可以从任意一堆中拿走 个石子,取走最后一个石头的人获胜
解决方法
对每堆石子 后异或和为 则先手必败,否则先手必胜
基本问题
一共 堆石子,每次每人可以从最多 堆中拿走任意多石子,不能不拿,取走最后一个石头的人获胜
解决方法
把每堆石头的数量二进制拆开,对每位分别求和,若每一位上的和都是 的倍数则先手必败,否则先手必胜
基本问题
在 级阶梯上每级有若干个石头,每次操作可以从任意级阶梯把任意多石头移动到下一级阶梯(移动第一级的石头相当于丢掉),不能不移,不能操作者输
解决方法
计算奇数级阶梯的异或和,为 先手必败否则先手必胜
SJ 定理:
对于一个 Anti-SG 游戏,如果我们规定当前局面中所有单一游戏的 SG 为 0,游戏结束。那么先手必胜的条件就是:
1. 游戏的 SG 值不为 0,且存在一个单一游戏的 SG 值大于 1。
2. 游戏的 SG 值为 0,且不存在一个单一游戏的 SG 值大于 1。
AGC005E Sugigma: The Showdown
有一个 个节点的图,有 条红边, 条蓝边,每种颜色的边都构成了一棵树。
现在 (先手) 控制了一个棋子从 出发,(后手中) 控制了一个棋子从 出发
每次可以不动或者走一条红边, 每次可以不动或者走一条蓝边。当棋子相遇时游戏结束,而 因为还要和很多很多人玩各种各样的博弈十合一游戏,所以他希望最小化游戏时间。不希望 能够玩太多的博弈十合一,所以希望最大化游戏时间。求出游戏时间。
Sol
先考虑啥时候游戏永远不会停止。显然就是 不被 抓到。
假设 当前在 位置, 当前在 位置。如果 以及它在红边下所有的相邻点在蓝边下距离 的距离都是 ,那么就可以原地等死了。否则,反过来,如果出现了一条红边 ,满足 ,并且 已经到达了 ,那么 就一辈子都抓不住 了 ( 只需要在这两条边上反复横跳)。
如果游戏不能永远进行下去,意味着 一定会被 给抓住,
显然以 点为根,蓝边构树, 一定走不出子树,只能找到一个深度最大的点等死。
[JSOI2009]游戏Game
这个博弈类似放骨牌,所以就可以黑白染色之后跑二分图最大匹配,其中的不必匹配的点就是答案
这些点是什么呢, 一下发现貌似就是残余网络中与 或 在同一个强连通分量的点?
蒟蒻的理解:
首先要满足每个决策的区间右端点单调
柠檬
选取的区间的开头结尾的东西一样,每种东西维护一个决策栈
如果加入的东西比栈顶优,那么以后也一定比栈顶优( 的单调性)
但是随着 的 坐标后移,可能存在某些前面的决策会变得比后面优
只要对于每两个元素,二分出那个分界点,让每个决策的区间递增即可
Lightning Conductor
为什么窝的决策单调性和大家的都不一样
upd:其实是一样的,貌似我的常数非常大。。。(做了许多无用的操作)
诗人小G
打表发现了决策单调性。。。
Yet Another Minimization Problem
分治解决决策单调性问题:
如果发现信息不好维护时,考虑分治,每次考虑决策区间 对 的 的影响
然后找出 的 的决策点分治下去
一些注意点:
1. 的决策点对 和 都有影响,两边都要分治下去
2.维护信息可以维护一个全局的 表示当前的信息为 内的,每次像莫队一样移动端点
3.移动端点有个小 ,每次让区间的一个端点不变,移动另一个端点,也就是每次让区间重合的部分大一些
upd: 貌似可以直接每次暴力扫,然后暴力清空...(不过不太想写...)
小Q的书架
和上面方法一样
upd:上面的东西可能有点问题。。。代码没判 没有决策的情况
贞鱼
满足决策单调性(矩形的面积),再加上凸优化可以过(还要加上恶心的 。。。)
Ciel and Gondolas/同上
上面的,不加凸优化可以过
数据分块鸡
决策单调性+主席树
Hero meet devil
把 数组压入状态,对于每个 ,把 差分变成了 状态
LCS Again
只关心T的位置 的 , , ,又要满足
而此时只有两种取值, 状态表示即可
神奇游乐园
括号表示法,相邻的括号一定匹配,不然就会相交,三进制状压转移
注意只能选择一条路径,那么当只有一对括号匹配时不转移,直接更新答案
【模板】插头dp
括号表示法,相邻的括号一定匹配,不然就会相交,三进制状压转移
强制不连成回路,只在最后一个可以放的点计算贡献,不能不放
主旋律
考虑容斥
强联通图反过来就是一些缩点后的
一个套路就是对出(入)度为 的点进行容斥
设 分别表示选了奇数个 入度和偶数个的,集合为 的方案数
那么通过钦定一个特殊的点 有
串珠子
容斥
设 表示与 相连的连通块集合为 的方案数
设 表示 点集随便连边的方案数
那么
动态dp
注意矩阵乘法的顺序
全局平衡二叉树
就是相当于静态的
重链剖分之后,对于每一条链建一棵树,为了保证最后的树高为
选取链的重心(带权,权值为除去链的子树大小)作为树的根,然后用轻边与上层相连
每次暴力修改即可
[Sdoi2017]切树游戏
动态 +
设 表示强制选 的子树和 的子树的 的和、
可以得到链上的递推方程,可以矩阵乘法优化
对于轻边的(初始化)转移:
可以看成是轻儿子的
就是轻儿子的
然后就可以码码码了
[IOI2007]training
首先去掉那些路径长度为奇数的非树边
然后考虑剩下的非树边,如果覆盖的区间有交,那么就是两个奇环,去掉交就边成了偶环
所以覆盖的区间不能有交
也就是最大边权的仙人掌
考虑在非树边的 处处理,而度数非常的小
设 表示 号点,忽略儿子集合 的最大答案
转移。。。
小h的树
本质上需要做的是求出原树的一个大小为 的联通块
使得联通块内部的边权之和的两倍减去直径最小
设 表示 的子树中,选了 个点,有 个直径的端点在子树中的答案
不用关心是否会算成不是直径的链,那样显然不优
Riv河流
设 表示 点,有一个 建造站点, 为 的祖先,子树内用了 个的最小代价,转移大力讨论即可
[JSOI2008]魔兽地图
表示 号点,有 个用于父亲合成,花了 元的最大价值
然后转移即可
[NOI2008]道路设计
首先题目给的是一棵树,由轻重链剖分可以得到答案不超过
那么可以枚举答案,考虑计算方案
类似林克卡特树设 表示 号点,答案不超过 , 的度数为 的方案数
设 那一维就可以一遍预处理得到答案
最后枚举答案,看方案数是否为 即可,注意取模后可能为 ,记录一下就好了
[NOI2008]奥运物流
基环树
树上就是直接做,环上,若环长为 ,那么就是乘上
考虑更换后继,贪心的想,肯定直接接在 下面
环的长度肯定不会超过原长度,肯定不优,那么可以先枚举环长,更改环上的一条边,然后变成树
可以设 表示 的子树,改了 个点, 到 的距离为 的最大答案
那一维用于计算答案
那么每次就是决策一个点是否接在 下面
是,可以从 转移而来,即子树要么没有更改,要么接在 下面
否,可以从 转移而来,同理
注意枚举 不能越界,不能到达 ,除了根和其儿子
如果到达了 就说明接在 下面了,要把 加
[CTSC2007]动物园
显然是要状压 位,处理出一个位置的每一种状态是否会开心
然后枚举环的开头进行
[Jsoi2011]序的计数
首先把 个点单独拿出来,并全部连向一个虚拟节点 ,这样强制 为第一个走的点就可以得到所有的 序了。
设 表示当前在 ,经过的点集为 的 序数。
由于 转移的时候,进入一棵子树,如果需要回溯的话一定是从这棵子树里转移出来了,那么提前预处理 表示当前在 ,经过的点集为 ,接下来要经过的点的集合是哪些。转移的时候,进入子树就直接从 得到转移的系数。需要注意的是,当某棵子树内存在连向不在 个点中的边时,不能再向外转移,因为此时l是不能回溯的。
【UNR #2】积劳成疾
很容易得到一个状态 表示笛卡尔树的区间为 ,最大值不超过 的答案
但是实际上我们不关心它的实际是哪一个,只关心它的长度,那么可以设 表示长度为 ,最大值不超过 的答案
[Zjoi2013]话旧
设 表示到第 个已知点,第 个已知点之前的直线斜率是 还是 。讨论 种转移即可。
Rikka with Consistency
设 表示第一个人在 ,第二个人在
由于最多可能有一个人不在整点,再记录 表示这种情况
最短路+大力讨论转移
Immortal...Universe
当两个串存在一对前缀其和为 且下一位都是 那么就可能 。
也就是只需要求出每个串下一位是 的最小前缀是多少,若其和 则可能 。
由于一个串取空后只能到另一个串里取,所以串的末尾应当视作 。此时就需要特判一种情况: 两串的最小前缀都取了整串且不存在其他的最小前缀,和为 ,这种情况应该要被判定为 。
所以对每个串求出 表示最小前缀和为 ,最小前缀和的下一位是某个 还是序列末尾(需要严格小于所有下一位是 的前缀)的方案数,再 合并一下即可。
从后往前倒着 求 可以做到 。
Eternal Average
好神啊
直接考虑一棵 个叶子的 叉树,根结点权值为
对于一个 的序列
如果
那么一定可以构造出一棵 叉树满足要求
(从deep大到小考虑,除去 进位)
那么对于一个答案数 ,它的每一位的数字(可以通过退位)和
退位就是 ,那么也就是
同理 的每一位的数字(可以通过退位)和
设位数为
即
那么可以设 表示小数点后前 位,每一位的数字和为 ,的不同的数字个数
每次判断 且
满足则贡献答案
只需要枚举到 即可
Mausoleum
显然是要从左右往中间 ,然后暴力判断是否合法。。。
小w、小j和小z
二分答案,那么就是求最长的满足原来和现在的位置递增的最长上升序列
MST
好妙的题目,用整数拆分来表示连通块,计入状态
按照边权顺序从小到大加边,非树边不能跨越连通块
树边枚举合并连通块
[Shoi2007]Bookcase
显然是要记录厚度在状态中,第三个的厚度可以用前面两个算出来
那么考虑高度的限制,竟然是 ,那么就考虑排序
你发现只要从大到小排序就好了,第一次放进去的一定是最大的
小 Y 的背包计数问题
对于小于 , 直接每个物品的容量剩余类做一遍
对于大于 , 最多只能选择 个,并且相当于无限制,可以
最后卷起来就好了
Group
显然把 排序后可以设状态 表示前 个,有 个组没有选最大值,总和为 的方案
但是这样 的范围很大
考虑到
那么我们可以把 数组差分计算贡献
注意转移的时候可以一个数字分一组。。。
RGB Sequence
考虑 ,设 表示第 位每个颜色最后一个位置是什么
由于 所以不用记
Leftmost Ball
考虑钦定白球的位置,设 表示 个白球, 种颜色放完了的方案数
那么 然后转移,要么选择一个成为白球(白球选择哪一个都是一样的),要么选择一种颜色向后放完,乘上组合数即可
[HNOI2007]梦幻岛宝珠
首先按照 的 分别 , 表示小于等于 的体积的最大价值
然后不同的 之间转移
表示 组内,容量为 的最大价值
[ZJOI2008]生日聚会
设 表示前 个位置, 个男,男比女多得最多的后缀,多了,女比男一样的
转移即可
[HAOI2008]玩具取名
区间 ,设 表示区间 是否缩成
[SHOI2008]循环的债务
设 表示前 个面值, 有 元, 有 元的最小代价
暴力转移,复杂度???
成绩单
设 表示 取完的最小代价
设 表示 选出连续的 为最大, 为最小的最小代价
直接转移即可
注意一个转移:
[HAOI2007]修筑绿化带
二维单调队列,直接每一列一个单调队列,然后对于队首开一个单调队列即可
背包
每个物品的容量剩余类做一遍单调队列
In(n), In(w);
for (int i = 1, s, nw, v; i <= n; ++i) {
In(s), In(nw), In(v);
for (int j = 0; j < nw; ++j) {
int l = 0, r = -1;
for (int k = j; k <= w; k += nw) {
while (l <= r && (k - q[l]) / nw > s) ++l;
while (l <= r && f[q[r]] - q[r] / nw * v <= f[k] - k / nw * v) --r;
q[++r] = k;
if (l <= r) Cmax(g[k], f[q[l]] + (k - q[l]) / nw * v);
}
}
for (int j = 0; j <= w; ++j) f[j] = g[j];
}
int ans = 0;
for (int i = 0; i <= w; ++i) Cmax(ans, f[i]);
printf("%d\n", ans);
[AHOI2008]逆序对
显然 的位置填递增的数不会更差,那么直接 即可
Inversions
考虑满足要求的所有的排列数怎么算
记 表示 的 个数
那么答案就是
考虑枚举逆序对计算贡献
那么每次枚举一对
当 的时候,答案就是合法排列数除以 ,因为 和 的方案数一样
当 的时候,直接把 变成 算就可以了
当 的时候,直接求 的方案(与上面类似),然后总方案减去即可
而由于 变成了 那么就有在区间 的 都减少了
可以考虑维护 的前缀积
但是这样,如果乘上了 就假了
可以考虑维护每一个 的上一个 的
那么如果区间穿过了这个 答案就是
这样子是 的
考虑到每次只要求一段区间的前缀积的和,所以直接树状数组优化就好了
木棍分割
第一问二分
第二问,设 表示前 个分了 组的方案数
处理出每个棍子前面还能连续放多少个,前缀和优化即可
[HNOI2005]数三角形
处理出每个点六个方向能扩展多少,然后枚举下界的左端点,二维树状数组计数
[AHOI2006]基因匹配
有用的状态就只有 个,记下来就好了,直接树状数组转移即可
[HNOI2012]双十字
比较简单的一道题目
处理出来每个位置向上下左右分别能扩展多远
然后枚举中轴线和下边界,暴力就是再枚举一个上边界计算答案
你发现暴力有 分, 上面过了。。。
考虑优化,观察计算答案的时候的写法
假设下边界的最长半径为 上边界的为
如果 那么贡献就是
还要乘上向上下扩展的长度,上边界的贡献显然可以用一个树状数组维护
如果 那么贡献就是
也要乘上向上下扩展的长度,把与上边界有关的东西提出来,显然可以用三个树状数组维护贡献
Stop. Otherwise...
对于每个 ,可以把 个数字分成 的若干组。
那么就是求每组只能其中选择一个且可以重复的方案数。
预处理 表示从 个组内选 个,每个组必须选的方案数。
注意组有序,而选出来是无序的,所以要强制选择最后一组
那么每个组可以不选的方案数 就是
Counting Sheep in Ami Dongsuo
设 表示 号点,选了 个终点,权值和为 的方案数
建反图跑一边即可预处理
最后对于每一个 , 加起来就是答案
直接做是 的,代入 个点求点值,最后插值即可
复杂度
Normal
根据期望的线性性,答案就是 每个连通块出现次数的期望
而每个连通块次数的期望就是 连通块的根与每个点连通次数的期望
也就是对于一条路径 ,设 为根,那么 必须是这条路径第一个被选择的点,概率为 ,其中 表示 上的点数
那么只要统计不同的 的个数即可
直接点分治+
[THUWC2017]随机二分图
对于只有 的,直接设 表示左边前 个点,匹配了右边的集合 的期望
考虑另外的 方式,设 表示左边集合 匹配右边的集合 的期望,枚举一个不在 中的编号最小的点转移,每次选择边就必须匹配
对于 的,拆贡献,拆成两个 的和一对必须选的边
,拆开的两条边都是 ,一对必选的为
,类似
这样就可以补上贡献的(期望的线性性)
随机游走
容斥
Piglet's Birthday
设 表示第 行,有 个没有尝试的概率
这样 最多只有 直接转移即可
仓鼠找sugar II
假设终点确定,并设为根
设 表示 往 走一步的期望步数
那么
[JLOI2012]时间流逝
的整数拆分数比较小,考虑暴力
如果记录下当前的拆分,那么走法是一个树形结构
设当前状态为 , 表示 到终止状态的期望天数
那么
T-shirt
的考试题:
有 个虫洞, 每个虫洞的特征值观察之前在 内随机
你需要分配 个人进入虫洞,这 个人在观察到虫洞时可
以根据虫洞的特征值自行进入虫洞
求成功进入虫洞最大人数的期望
Sol
设 表示 个虫洞有 个虫洞特征值为 的概率,转移简单
设 表示 个人的特征值为 能成功的人的期望,枚举虫洞转移
期望具有线性性,那么就可以直接背包求解了
但是这样时间复杂度是 的,过不去
重返现世
, 容斥的扩展
根据 有
歌唱王国
方法1
表示给定的串长, 表示随机的范围, 表示 是否是 的一个 , 为 表示是, 为不是。
令 为结束时随机序列长度为 的概率,其概率生成函数为 。
令辅助数列 为随机序列长度达到 且还未结束的概率,其普通生成函数为 。
我们需要求的便是 。
通过分析可以得到如下等式:
OSU!
设 分别表示 结尾的连续的 的长度的期望和平方的期望和 结尾的答案
和 直接二项式定理维护
当前这一位为 的三次方的贡献为
每次如果成功,对答案贡献
失败则贡献
Rainbow Balls
首先可以枚举最后的球都是什么颜色的
设 表示当前有 个钦定的颜色的球,把所有球都变成这种颜色的期望时间
显然 不存在
设 那么
对于 可以得到一个 方程
亚瑟王
考虑期望的线性性
设 轮出每张牌的概率为
那么答案就是
由于是按照顺序考虑的,那么前面没有出的牌是会对后面有影响的
那么可以设 表示 轮前面 张牌只有 张出了的概率
抵制克苏恩
设 表示第 次, 个一的, 个二的, 个三的的期望
暴力转移
小 Y 和恐怖的奴隶主
把上面的转移搬下来,设 表示第 次, 个一的, 个二的, 个三的概率
预处理状态之后跑矩阵快速幂卡常
随机树
第一问
设 表示 个叶子的平均深度的期望
那么
「2017 山东一轮集训 Day7」重排
首先考虑不存在自环的情况
设 表示 到 的最短路径的期望
那么每次到达一个点 ,需要把边权和后继节点的 两两匹配,算出每一种方案的最短路
这样子不好做,考虑计算长度大于等于某个值的概率,然后差分计算期望
从小到达枚举匹配,其它的点 ,这样每次只会修改一个点的决策
如果有自环,就直接迭代到精度为止,每次更新 加入决策重新做一遍
地震后的幻想乡
根据期望的线性性,算出第 小的边作为最小生成树的最大边的概率,设为
那么根据题目的信息,答案就是
考虑计算 ,相当于在加入 这条边的时候,前 条不连通,而 条恰好连通
设 表示点集 中选择 条边连通的方案数
设 表示点集 中的边数, 表示全集
那么
珍珠游戏
珍珠项链长度为 ,贪玩的 突然想把这条项链拆开来
已知每颗珍珠的价值为
每次会在当前未被拆下的珍珠中,随意选择一颗珍珠,然后得到其所在链的珍珠价值和的收益
然后把这颗珍珠拆下,将其所在的链延此分裂成两条链(链可以是空的), 当所有珍珠都被拆下时停止
想知道在所有操作方法下,他能够得到收益和的期望,你能帮他解决这个问题吗?
答案对 取模。
Sol
很好的一道题目
首先第一个想法就是设 表示 贡献的期望次数
那么
怎么求
这个题目就妙在这里,把包含 的块拆成前面和后面(美妙的期望的线性性)
设 表示一个长度为 的块,它的首部贡献的期望次数
那么 ,多算了所以要
很好算,,即每个位置在前所有位置之前取走的概率
斯坦纳树是这样一类问题:带边权无向图上有几个点是关键点,要求选择一些边使这些点在同一个联通块内,同时要求所选的边的边权和最小。
为什么不能直接求解最小生成树,因为会有边相交的情况
游览计划
求解斯坦纳树
设 表示与 是否相连关键点的状态
转移有两种
修路
和上面一样,最后记一个 表示前面 个是否连通,状态为
枚举子集转移
管道连接
上面的加强版,变成要连通的有多个,一样的做就好了
机器人
斯坦纳树,预处理出每个点四个方向到达的点
设 表示合并了 当前根为 的最小代价
边权都是 ,所以我们用 来扩展
我们把原有的节点按照 值排序
然后维护一个栈来存储原有的节点,用一个队列存储扩展的节点
容易发现这两个里面都是单调的,每次比较头即可
[BJWC2018]词韵
反过来建立 树,然后 求一条包括儿子的链即可
Biology
公共的就是 上的 的
补退选
每个节点维护一个所有值的 ,因为最大值一定连续,然后暴力查询即可
id = 1, mx = 0;
for(RG int i = 2; i <= n; ++i){
if(i <= mx) lcp[i] = min(lcp[lcp[id] - mx + i], mx - i + 1);
while(i + lcp[i] <= n && s[lcp[i] + 1] == s[lcp[i] + i]) ++lcp[i];
if(lcp[i] + i - 1 > mx) id = i, mx = lcp[i] + i - 1;
}
for(RG int i = 1; i <= n; ++i) s[i] = s[n + i];
RG int m = n << 1, i = 1, j = 2;
while(i <= n && j <= n){
RG int len = 0;
while(s[i + len] == s[j + len] && i + len <= m && j + len <= m) ++len;
if(s[i + len] > s[j + len]) i += len + 1;
else j += len + 1;
if(i == j) ++j;
}
RG int m = 30;
for(RG int i = 1; i <= n; ++i) ++t[rk[i] = s[i] - 'a' + 1];
for(RG int i = 1; i <= m; ++i) t[i] += t[i - 1];
for(RG int i = n; i; --i) sa[t[rk[i]]--] = i;
for(RG int k = 1; k <= n; k <<= 1){
RG int l = 0;
for(RG int i = n - k + 1; i <= n; ++i) tmp[++l] = i;
for(RG int i = 1; i <= n; ++i) if(sa[i] > k) tmp[++l] = sa[i] - k;
for(RG int i = 0; i <= m; ++i) t[i] = 0;
for(RG int i = 1; i <= n; ++i) ++t[rk[tmp[i]]];
for(RG int i = 1; i <= m; ++i) t[i] += t[i - 1];
for(RG int i = n; i; --i) sa[t[rk[tmp[i]]]--] = tmp[i];
swap(rk, tmp), rk[sa[1]] = l = 1;
for(RG int i = 2; i <= n; ++i) rk[sa[i]] = Cmp(sa[i - 1], sa[i], k) ? l : ++l;
if(l >= n) break;
m = l;
}
for(RG int i = 1, h = 0; i <= n; ++i){
if(h) --h;
while(s[i + h] == s[sa[rk[i] - 1] + h]) ++h;
st[0][rk[i]] = h;
}
for(RG int i = 2; i <= n; ++i) lg[i] = lg[i >> 1] + 1;
for(RG int j = 1; j <= lg[n]; ++j)
for(RG int i = 1; i + (1 << j) - 1 <= n; ++i)
st[j][i] = min(st[j - 1][i], st[j - 1][i + (1 << (j - 1))]);
IL void Extend(RG int c){
RG int np = ++tot, p = last; last = np;
len[np] = len[p] + 1;
while(p && !trans[c][p]) trans[c][p] = np, p = fa[p];
if(!p) fa[np] = 1;
else{
RG int q = trans[c][p];
if(len[p] + 1 == len[q]) fa[np] = q;
else{
RG int nq = ++tot;
len[nq] = len[p] + 1, fa[nq] = fa[q];
for(RG int i = 0; i < 26; ++i) trans[i][nq] = trans[i][q];
fa[q] = fa[np] = nq;
while(p && trans[c][p] == q) trans[c][p] = nq, p = fa[p];
}
}
}
后端插入
IL void Extend(RG int pos, RG int c){
RG int p = last;
while(s[pos - len[p] - 1] != s[pos]) p = fa[p];
if(!son[c][p]){
RG int np = ++tot, q = fa[p];
while(s[pos - len[q] - 1] != s[pos]) q = fa[q];
len[np] = len[p] + 2, fa[np] = son[c][q];
son[c][p] = np;
}
last = son[c][p], ++size[last];
}
前后插入
int n, tot, prel, sufl, son[26][maxn], len[maxn], deep[maxn], fa[maxn], l, r;
ll ans;
char s[maxn << 1];
IL void Init(){
for(RG int i = l; i <= r; ++i) s[i] = 'z' + 1;
for(RG int i = 0; i <= tot; ++i){
len[i] = deep[i] = fa[i] = 0;
for(RG int j = 0; j < 26; ++j) son[j][i] = 0;
}
prel = sufl = 0, tot = 1, fa[1] = fa[0] = 1, len[1] = -1;
}
IL void Extend(RG int pos, RG int c, RG int &last, RG int op){
RG int p = last;
while(s[pos - op * (len[p] + 1)] != s[pos]) p = fa[p];
if(!son[c][p]){
RG int np = ++tot, q = fa[p];
while(s[pos - op * (len[q] + 1)] != s[pos]) q = fa[q];
len[np] = len[p] + 2, fa[np] = son[c][q];
son[c][p] = np;
}
last = son[c][p], deep[last] = deep[fa[last]] + 1, ans += deep[last];
if(len[last] == r - l + 1) prel = sufl = last;
}
int main(){
while(scanf("%d", &n) != EOF){
Init(), l = 1e5, r = l - 1, ans = 0;
for(RG int i = 1; i <= n; ++i){
RG int op = Input();
if(op <= 2){
RG char c; scanf(" %c", &c);
if(op == 1) s[--l] = c, Extend(l, c - 'a', prel, -1);
else s[++r] = c, Extend(r, c - 'a', sufl, 1);
}
else printf("%lld\n", op == 3 ? tot - 1 : ans);
}
}
return 0;
}
Palindrome Partition
首先 为奇数肯定无解
当 为偶数时
老套路,把串 变成 ,设为
那么满足条件的 的划分相当于 中的划分,使得每一段为长度为偶数的回文串
下面就只考虑 的划分
设 表示前 个字符合法划分的方案数,用 可以做到 树高
这样子远远不够
考虑 的一条 链,分析其性质
设 为位置 在树上对应的点
设 表示 与其中父亲的长度之差
由回文串的性质可以发现,向上会有一段的 相同
设 表示 上面第一个 与 不同的祖先
容易得到 的长度至多为 长度的一半
那么每次跳 统计 到 的贡献就可以做到
现在考虑计算 到 的贡献
我们把父亲的串都关于儿子对称,发现恰好是以 结尾的
在树上就是 的父亲,当然父亲必须在 到 的链上
那么
设 表示在 到 的贡献和
增量构造 的同时计算 ,修改
因为要分偶数,所以奇数的 就直接去掉即可
有趣的字符串题
同样的是 的等差数列的性质,注意到每个等差数列中间一定不会缺少一种回文串
枚举右端点,那么同一段的贡献相当于是给一个区间的左端点答案加上
在线直接用主席树即可
火星人prefix
平衡树动态维护区间 值
「2017 山东一轮集训 Day3」第二题
二分答案 ,考虑如何 使得做起来方便
把每个点挂在 级祖先上,考虑在祖先上删除
这道题巧妙在于其可以对于 序/括号序列
这样在 级祖先上暴力删除就好了
用平衡树维护每一个后缀的排名
关键在于查询两个后缀的大小
可以用二分加hash,复杂度 插入
或者:
每次前面插入一个字符,先比较两个后缀第一个字符的大小
而后面的大小我们已经在平衡树上维护好了
像这样分配权值
给树上每个子树一个实数权值区间 ,这个点 权值 为
左子树 右子树
注意删除的时候,左子树 右子树 ,不能是 ,不然会重复甚至颠倒
那么可以做到 比较
只需要选择一个树高 的树(treap/替罪羊树)使得满足精度要求即可
Phorni
后缀平衡树模板题,线段树维护一下每个幻影的最小的后缀
wxh loves substring
每次暴力匹配即可
用 和 找到排名
convex
求凸四边形的个数
转化成总数减去凹四边形的个数
凹四边形一定是一个三角形中间包含的另外一个点
那么枚举被包含的点,其它的对于这个点极角排序
被包含不好算,算总数减去不被包含的
枚举三角形的一个顶点,那么另外一个顶点和这个顶点关于枚举的被包含的点的角度不超过
那么直接 统计即可
信号覆盖
对于凸四边形,必有一组对角大于 ,此时这组对角所对应的顶点必然在另外三个点组成的圆中,所以每个凸四边形对于总的答案贡献两个点
对于凹四边形,设 在三角形 内,那么只有 在 组成的圆中, 都不在另外三个点的圆中,所以凹四边形对总的答案贡献一个点。
由于总的四边形个数一定,我们只需要求出凹四边形的个数。
算法见
为点积。。。
几何解释就是一个向量在另一个向量上的投影的长度
1. 可以判断一个向量 是否在 的逆时针方向
则 在 的逆时针方向(内侧)
2. 面积
其围成的三角形的面积
极角排序后单调栈求 ()
Circling Round Treasures
判断一个点是否在多边形的方法是任意引出一条射线判断交点的奇偶性
状压这个奇偶性即可
围豆豆
同上
枚举一条边,找到斜率最靠近它的边,
[JSOI2007]合金
只有当合金在材料组成的多边形内部时候才会有答案,那么就是求一个包含所有合金的最少的点的凸包,枚举每一个向量,只要所有的合金在其内侧就连一条边,最后求一个最小的环, 即可
[SCOI2007]最大土地面积
枚举对角线,那么要求两边的三角形面积最大,旋转卡壳即可
[SCOI2007]折纸
算出来孔所有可能折回去的位置去重即可
注意如果孔不在线段的逆时针方向则这个孔不合法
[HNOI2007]最小矩形覆盖
其中一条边一定在多边形上,枚举这条边,旋转卡壳求出另外三个卡住的点,分别用点积和叉积即可
随机增量, 一下
枚举一个点为圆心,看其它的点是否被包含,否则以这两个点为圆的直径,看其它的点是否被包含,选取最大的三角形外切圆
求所有向量的内侧的平面
按照斜率排序,相同的就保留最内侧的(叉积)
然后双端队列插入向量
为什么是双端?因为要围成封闭图形,可能使头部弹出
入队条件:尾部的两个向量的交点在该向量的内侧(叉积)
最后记的把首尾相接,继续弹出不合法的
要先弹尾再弹头,不然就GG了!!!
q[++tl] = l[1], q[++tl] = l[2];
for (int i = 3; i <= m; ++i) {
while (hd < tl && Jud(q[tl - 1], q[tl], l[i])) --tl;
while (hd < tl && Jud(q[hd + 1], q[hd], l[i])) ++hd;
q[++tl] = l[i];
}
while (hd < tl && Jud(q[tl - 1], q[tl], q[hd])) --tl;
while (hd < tl && Jud(q[hd + 1], q[hd], q[tl])) ++hd;
q[tl + 1] = q[hd]
[CQOI2006]凸多边形
所有边拿出来半平面交。
射箭
考虑一个抛物线
能射中要满足
即
(https://blog.csdn.net/wu_tongtong/article/details/79346196)
首先对其微小扰动,避免出现四点共面的情况
对于一个已知凸包,新增一个点
将 视作一个点光源,向凸包做射线
可以知道,光线的可见面和不可见面一定是由若干条棱隔开的 将光的可见面删去,并新增由其分割棱与 构成的平面
重复此过程即可
扰动之后各个平面一定是一个三角形,逆时针方向记录三个顶点表示一个面
有点类似右手螺旋定则,右手定则确定的方向指向多边形的外部
其模长仍然表示以这两个三维向量作为邻边的平行四边形面积
方向符合右手定则,穿过掌心向手内
struct Point3D {
double x, y, z;
inline Point3D(double _x = 0, double _y = 0, double _z = 0) {
x = _x, y = _y, z = _z;
}
inline Point3D operator +(Point3D ad) const {
return Point3D(x + ad.x, y + ad.y, z + ad.z);
}
inline Point3D operator -(Point3D ad) const {
return Point3D(x - ad.x, y - ad.y, z - ad.z);
}
inline double operator ^(Point3D ad) const { //dot
return x * ad.x + y * ad.y + z * ad.z;
}
inline Point3D operator *(Point3D ad) const { //cross
return Point3D(y * ad.z - z * ad.y, z * ad.x - x * ad.z, x * ad.y - y * ad.x);
}
inline Point3D operator *(double ad) const {
return Point3D(x * ad, y * ad, z * ad);
}
inline double Len() {
return sqrt(x * x + y * y + z * z);
}
};
inline double Rand() {
return rand() / (1.0 * RAND_MAX);
}
inline double Disturb(Point3D &a) {
a.x += (Rand() - 0.5) * eps, a.y += (Rand() - 0.5) * eps, a.z += (Rand() - 0.5) * eps;
}
Point3D a[maxn];
struct Surface3D {
int v[3];
inline Point3D Normal() {
return (a[v[1]] - a[v[0]]) * (a[v[2]] - a[v[0]]);
}
inline double Area() {
return Normal().Len() * 0.5;
}
};
Surface3D f[maxn], tmp[maxn];
int n, tot, vis[maxn][maxn];
double area;
inline int Cansee(Point3D x, Surface3D y) {
return ((x - a[y.v[0]]) ^ y.Normal()) > 0;
}
inline void Convex3D() { //Polygon3D
int i, j, k, cnt, v, x, y;
f[++tot] = (Surface3D){1, 2, 3};
f[++tot] = (Surface3D){3, 2, 1};
for (i = 4; i <= n; ++i) {
cnt = 0;
for (j = 1; j <= tot; ++j) {
if (!(v = Cansee(a[i], f[j]))) tmp[++cnt] = f[j];
for (k = 0; k < 3; ++k) vis[f[j].v[k]][f[j].v[(k + 1) % 3]] = v;
}
for (j = 1; j <= tot; ++j)
for (k = 0; k < 3; ++k) {
x = f[j].v[k], y = f[j].v[(k + 1) % 3];
if (vis[x][y] && !vis[y][x]) tmp[++cnt] = (Surface3D){x, y, i};
}
for (j = 1; j <= cnt; ++j) f[j] = tmp[j];
tot = cnt;
}
}
int main() {
int i;
srand(time(NULL)), scanf("%d", &n);
for (i = 1; i <= n; ++i) scanf("%lf%lf%lf", &a[i].x, &a[i].y, &a[i].z), Disturb(a[i]);
Convex3D();
for (i = 1; i <= tot; ++i) area += f[i].Area();
printf("%.3lf\n", area);
return 0;
}
官方定义:两个图形 的闵可夫斯基和
通俗一点:从原点向图形 内部的每一个点做向量,将图形 沿每个向量移动,所有的最终位置的并便是闵可夫斯基和(具有交换律)
利用瞪眼法得,闵可夫斯基和的边是由两凸包构成的
也就是说把两凸包的边极角排序后直接顺次连起来就是闵可夫斯基和
由于凸包的优美性质,直接归并排序就好了
但是需要注意的是可能会有三点共线的情况,于是再扔过去重新求一次凸包就好了
反演中心为 ,反演半径为 ,若经过 的直线经过 ,且 ,则称 关于 互为反演
定点都是整点的多边形,内部整点数为 ,边界整点数
把每个整点近似地看成一个圆,那么多边形内部的整点所代表的圆全部被算入
多边形边界上的圆被算了一半,顶点上被算了 半角 外角
外角和 度,于是
首先函数必须收敛
inline double Simpson(double l, double r) {
return (r - l) * (F(l) + F(r) + 4.0 * F((l + r) * 0.5)) / 6.0;
}
inline double Calc(double l, double r, double neps, double ans) {
double mid = (l + r) * 0.5, lans = Simpson(l, mid), rans = Simpson(mid, r);
double dx = lans + rans - ans;
if (fabs(dx) < 15.0 * neps) return lans + rans + dx / 15.0;
return Calc(l, mid, neps * 0.5, lans) + Calc(mid, r, neps * 0.5, rans);
}
算法
它可以用来求常系数线性递推的系数,并且可以求出最短的
求出来有什么用呢?
你可以闷声Cayley-Hamilton定理优化递推矩阵快速幂
算法简介:
首先设一个数列 ,我们想要试出其中满足
的最小的 以及对应的系数
考虑增量法构造
1. 首先因为要求 ,所以 且 都为 显然是满足条件的,所以初始可以就是全
2. 假设有一个长度为 的 在 都满足条件,并且 不满足了
设
我们只要构造出一个长度为 最短的
使得 然后 按位相加就好了
怎么找到呢,实际上我们之前已经存在有一些不满足条件的情况
假设有个
把 向后移动 位,前面补 个 ,第 位搞个
这样得到的长度为 的 再搞个 乘起来就好了
搞出来的 显然就是我们要求的,但是可能不是最短的
万物皆可持久化把之前所有求过的 全部记录下来
然后又搞个 表示第 个 挂了的位置
最后弄个变量记录一下最短的就好了
随机映射多随机几百次...
维护两个方向 的矩阵,查询变成四个相交的矩阵
这个东西可以用来优化最大流连边
DZY Loves Chinese
线性基 随机化神仙题
随便构出一棵树,给非树边随机一个边权,树边边权就是覆盖它的非树边的边权的异或和
那么询问就是有没有一个树边和一些非树边的边权异或和为
线性基计算
「2017 山东一轮集训 Day1 / SDWC2018 Day1」Set
建立线性基后贪心,注意直接高位贪心是错的
考虑如果总的 的某一位为 显然是尽量都选 ,否则尽量让 选
那么可以给线性基插入定一个顺序,先插入总的 为 的,最后贪心选取 即可
Atcoder:AGC004F Namori
先考虑树,树是一个二分图。
看到是二分图并且每次是对两边的同色的点反色可以想到转化:让奇数层的点为黑,偶数为白,变成每次可以交换两个点的颜色。
把黑看成 ,白看成 ,那么求一个子树和,考虑每一条边的贡献可以得到
如果根的 不为 ,那么肯定是无解的。
对于基环树,先考虑奇环。
断开奇环的一条边 ,变成树, 肯定是同一边的点。
操作一次 相当于可以两边可以同时新增加白点/黑点,也就是可以把根的 用这两个点来变成 ,( 必须为偶数)平均分配之后用树的做法即可。
考虑偶环。
断开偶环的一条边 ,变成树, 肯定不是同一边的点。
操作一次 相当于是让左右的点走了一次捷径。
设用的次数为 。
如果一个点同时包含或不包含 两个点,那么 一定不变。
否则加上或者减去 。
相当是是要求
经典问题,排序之后取中位数即可。
[IOI2018]机械娃娃
建出一棵线段树,只需要强行在序列最后加入一个 即可
注意要把空节点放在前缀,保证都走完
[IOI2018]高速公路收费
首先可以直接二分边找到最短路必经的边
分成两边分别在 序上二分
[CTSC2016]单调上升路径
把一个点放在中间,其它排成多边形,中间的点向另一个点连边
以这条边为对称轴两边的对称点连边
然后边权递增连,旋转后继续连
Anton and Tree
同色相邻点的距离为 ,否则为
显然答案就是每个点距离它最远的点的距离的最小值
组合动作
比较有意思
首先可以 次试出来第一个字符
那么我们现在想要 次试出接下来的字符
考虑分情况,第一个字符不会出现大于 次
那么 就可以了
最后一个字符要特殊处理, 次
Anticube
把每个数字质因数分解,求出每个质因子的幂 ,等于 的不用考虑,因为和它互补的也是
那么可以求出互补的数字,显然只有一个
考虑质因数分解:
因为是立方,所以质因数 ,最多只有两个
所以小于时直接分解,大于的时候判断两个是否是一样的
最后贪心选择即可
Password
异或差分后,最多有 个
奇数个 无解,那么就是这些 两两匹配的最小代价
把所有边连进去,然后暴力匹配即可
Love Triangles
同一个连通块内的边一定可以确定
不同连通块之间确定了任何一条边,其他的也可以确定
那么答案就是
注意判断无解
[POI2011]IMP-Party
每次枚举两个点,如果没有边就删掉这两个,那么最后 个就是答案
因为每次最多只会误判 个点,至少判断对 个点
[POI2011]LIZ-Lollipop
如果有前缀和等于 就直接输出
否则一定有 或者 这样的前缀和
因为前缀和之间最多相差
那么找到 的区间,向后移动即可
要么左端点删掉一个
或者左右端点加入一个
Atcoder Colorful Balls
两种颜色能交换就连边,那么同一个连通块可以随便换
对于每一种颜色,算出来有用的一部分,即满足在颜色内交换或者通过外界最小值交换可以和颜色内最小值连边的,这一定是一个前缀
然后把每个颜色取出最小值排列成一排,算出满足可以和最小值连边的前缀
最后用可重排列算一下即可
[Beijing wc2012]最多的方案
每个数字都可以拆成若干个不同的 数的和
手玩一下就可以归纳
县把 拆成最大的几个,考虑替换
可以发现,每次只能替换最小的一个,显然可以归纳证明
由于一段中端点被替换了会影响到另一个端点
那么就可以
设 表示 是否替换即可
天天爱跑步
对于向上能够到达的和向下的分开处理
对于两个都能到达的减去即可
对于向上的,只要满足 就会有贡献
那么就是要查询 的子树中满足 的且 为 的祖先或 的起点的个数
可以线段树合并直接维护,也可以用差分的思想
差分
维护一个全局的桶
进去的时候,减去子树外的满足 的点,向桶中加入以这个点为起点的点
回溯回来的时候减去满足 的点,删掉以这个点为 的点
对于向下的,只要满足 就会有贡献
同样的,就是要查询 的子树中满足条件的且 为 的祖先或 的终点的个数
一样的也可以差分
一个 解决所有问题
[HNOI/AHOI2018]寻宝游戏
考虑对于某一位来说, 和 不会对答案造成影响
于是只考虑 和
若最后一位结果为 , 那么最后一个 要在 之后
把每一位看成二进制数,然后把符号也看成二进制数
看成 , 看成 , 后面为高位
可以发现当且仅当符号 这个数时,结果为 ,否则为 ;
于是我们就可以找到结果为 的最小值以及结果为 的最大值,做减法就是方案数。
WC2019I君的商店
首先最大值一定为 ,直接扫一遍两两比较 求出最大值
设最大值位置为 ,对于任意两个没有确定的位置
询问 ,如果 那么 的最大值为 ,否则 最小值为
再询问 即可
复杂度
考虑 ,首先花费 的代价找到端点的
假设序列为 ,只需要找到最靠前的位置 ,使得 ,二分即可
然后 的位置都是 , 的位置都是 ,利用奇偶性判断 是否为
再考虑 ,猜想复杂度为 左右
任取三个没有确定的位置 ,询问 ,再花费 的代价确定 或者
假设
如果 ,那么
否则 ,把 当成新的 继续做
最后可以得到一个不确定的位置 和一条递增的链 ,其它的都是
一定为 ,那么可以直接用 的方法二分
最后利用常数的代价 奇偶性求出 和二分中不确定的位置
[IOI2018试机赛T2]风琴
有一个 排列,保证 在 的左边
你每次可以询问交互库一个区间,交互库会告诉你这个区间内的最大值减去最小值的结果
你需要在不超过 次询问内还原出这个排列
Sol
先询问出间隔为 的,通过间隔为三的确定符号方向,再通过 是否在 左边确定答案
Next or Nextnext
考虑转化成图论问题, 向 连边,那么合法方案一定是形成了若干个简单环或自环
考虑一个环内的情况:
令 和 连边的图为原图,和 的为新图
现在已知 和 的边,求原图的方案数
考虑一个环上的一条链,它还原成原图的环的方法只能是沿着环的逆时针方向插空还原
因为新图的两个相邻点之间只能插入一个点
那么有显而易见的几种无解的情况:
1. 对于一个不属于环上的点,如果有两个及以上的点同时指向它,那么肯定不能还原成原图的环
2. 对于一个属于环上的点,如果有两个及以上的点同时指向它,那么肯定也不能还原成原图的环
3. 如果环上一条链 和环的沿逆时针方向的另一条链的距离小于 的长度,那么无解
考虑计算答案:
1. 对于新图的单个的环,把长度相同的一起 ,每次可以合并两个,或者奇数长度的同构等
2. 对于基环内向树,如果环上一条链 和环的沿逆时针方向的另一条链的距离等于 的长度,那么只有一种方案,否则如果大于,就有两种,因为此时 的靠近环的点可以选择连上逆时针方向的一个点
把这些东西互不影响,乘法原理即可
Japan2018 Airline Route Map
通信题
实现两个程序。
第一个程序会得到一个 个点 条边的无向图。你需要返回一个 点的无向图。
第二个程序会得到这个 个点的无向图,但是标号会被随机打乱。你需要还原出原图。
不能有重边和自环
Sol
相当于要用 个点识别 个点
由于 ,那么可以用 个点标记二进制位
第 个点用来连接这 个点
剩下的第 个点与所有的除了 的点连边,这样就能找到 和
但是不能确定前 个点
可以先把这 个点从小到大一一连接起来
现在的问题是怎么确定 个点中的 号,只需要将 再连接除了 外所有 到 的点即可
新年的Dog划分
先构出一棵生成树,判断是否是二分图只要在这个生成树中看一下有没有同奇偶性深度的边(奇环)即可
怎么构造一棵生成树?
考虑从一个点开始每次找出一条与它相连的边
一个比较好的方法就是 ,把已经在生成树里面的不在队列中的点到任意点的非树边全部去掉
当没有加入的点有若干个只与当前点连通时扩展,这样的点的存在性可以判断,找到这样的点可以二分
「JOISC 2017 Day 3」自然公园
对于一条链而言:
假设我们已经知道了一段链 , 我们现在要把 给加入链, 那么先把 删掉或者 删掉,就可以判断离 较近的那个点是 还是 。
这里不妨设为 。
那么通过一次二分可以得到 链上的编号最小的点 ,那么递归 , 处理即可。
找边可以在 序上二分
询问次数
剩下的就是正解:
假设我们已知一个联通的点集 S,每次都要把点 和这个点集连接在一起,显然也可以通过二分找到路径上的一个点,然后递归处理。
把这个点加入到点集 前,考虑它到所有已知点集的出边,对于每个点集,每次可以通过二分找到其中一条出边,这样子反复做多次就可以求出所有出边。这样子总的询问次数是 。
Cultivation
显然向上下与向左右的先后顺序对于答案是没有影响的,意味着如果我们确定了上下的限制的话,对于每一行就只有一个左右的限制。
向上或者向下一共只有 种情况。
不妨令向上移动的次数为 , 向下的次数为 。
那么可以理解为向下 次, 再把整个网格向下移动 次。
那么这样子我们只需要枚举 的和,方案数只有 种。
设 表示最靠左的到边界的距离, 表示相邻之间最远的距离, 表示最右侧的到边界的距离。
那么贡献就是
提前 预处理出每一段的 。
枚举所有的 计算答案。
首先因为看成了向下整体移动 ,所以每个点能够影响的范围是一段区间。
而本质不同的行只有 个,可以利用预处理的结果把他们所影响的段的 全部算出来。
对于 维护三个单调队列,考虑每个行数为 的矩形,计算出这段区间内最大的 ,这样子就可以更新答案了。
总的时间复杂度就是
【UER #8】打雪仗
通信题
对于 直接 返回所有,
对于 可以分成两部分,询问多一半直接 返回,少的 询问,
对于 可以分成三部分,询问多的 直接 返回,少的 询问,
New Year and Finding Roots
首先如果一开始就找到了一个叶子,那么暴力去递归找它的父亲,每次随机一个方向(除了已知的儿子)走深度次,如果走到了一个叶子就不是这个方向
(设根的深度为 )这样子最后到达深度为 的点需要花费 次
注意到此时只有与该点距离不超过 的点可能是根,这样的没有询问过的点不超过 个
所以只要询问 次,一共 次
如果一开始不是叶子,那么尝试 到一个叶子,最后再套用上面的做法
注意每次随机一个方向的时候要判断之前是否已经有一条长度为深度的链(也可以优先选择询问过的点)
Compressed Spanning Subtrees(H)
首先可以 找出所有的叶子
为了保证得到祖先关系,选择某个叶子为根
这样可以求出每个叶子的所有祖先
将它的祖先按照 排好序,一个个接上去就可以得到这棵树了(因为不存在度数为 的点)
询问次数
Guess the Tree(I)
思路:每次找出直径
Train Service Planning
无解:,若不是这种情况则一定可以构造解
把 到 的看成是从 到 走,时间倒流
设 , 分别为每种列车在 等待的时间
因为是每 个时间一辆,所以都是在模 意义下的
那么就是求满足
在模 意义下,就是
问题转化
有 个区间,你可以选定一个数,每次可以选择给它 ,要求第 次在区间内,求最小代价。
有起点就直接走就好了,每次从左端点走到下一个
没有起点可以从后往前预处理出以每一个点为起点的答案,可以用线段树找到不包含一个左端点的下一个区间
[SCOI2007]组队
神仙单调性
考虑外层枚举 ,内层枚举
那么 可以单调处理
但是 不好处理
你发现 且 时
就能满足要求了,此时就把满足要求的一个个加进去
当 增大时,就要把满足要求的 删掉,此时只要满足 就要删除,它一定之前加入了
这样就能保证不重不漏
签到题IV
你发现枚举右端点 后左端点 会被分成 段,每一段 的 的值相等
那么就有 个端点,只要一个一个的跳就好了
考虑到 往后移动之前分好的端点还可以继续用,只要稍做调整就是现在的情况了,所以可以接着上次的做,把相同的合并即可
Talent Show
分数规划 背包
圈地游戏
分数规划
建图:格点纵向连边,横向连纵向格子前缀和/前缀和相反数的,你发现这样子建图就是直接求解正环了。
[Lydsy1711月赛]分割序列
对 求一遍前缀 设为
显然是要求
你发现可以按位贪心, 当前为 ,那么 的这一位置为 才行
否则 当前为 ,那么 的这一位置为什么都不行
所以可以高维前缀和维护最靠前面的位置
Compatible Numbers
高维前缀和傻题。。。
Jzzhu and Numbers
容斥 高维前缀和
Time Limit Exceeded
高维前缀和