qbxt2021国庆

· · 个人记录

Day 1

T1 送分

T2

在长度为 n 的全0序列上进行 m 次操作，每次操作形如 (l,r,x,c) 表示 对区间 (l,r) 异或上 y,0\le y<2^{x+1} 现在我们可以花费 C 的代价使用 c_i\le C 的所有操作，求所有可以生成的所有序列的代价和。n\le 10^5,m\le 10^5, 0\le x\le 30

考虑用 C 的代价能生成哪些数组，这样就可以直接 \sum_C C\times (tot_C-tot_{C-1})

首先每一位是独立的。

即每个操作形如反转一个操作，询问有多少个数组可以被得到。

线性基！！（其实没必要）

你发现这个东西是经典题（假衡好像讲过？

把序列进行差分，区间异或相当于l和r+1异或。

对于一个大小为n-1的连通块，其代价为 2^{n-1}

（其实就是把没贡献的边干掉

orz hxs!!!

T3

求树上 (i,j),s.t. i<j,|i-j|<dist(i,j) 的点对数

启发式合并/点分治/dsu on tree

复杂度 O(nlog^2n) 感觉很水。

T4 自闭了

构造一个有标号有向图，满足这个有向图的内向生成树的数量为 C\le 10^{18},limN=80,limM=220

首先 C=2^k 很好做。

于是我们充分发扬人类智慧。

考虑1\rightarrow2\rightarrow3\rightarrow4\rightarrow...\rightarrow n\rightarrow rt

考虑加入一个点 x，1\sim n 向它连边。

如果 x 连向点 i，则后面的点都是连过去到根，前面的点正好是 2^{i-1}。所以我们实现了一个加法器，把 C 拆一拆就做完了。

如果是无向图呢？

bzoj4293

草的单调性不会改变，所以线段树上二分。

loj 6029

势能线段树，考虑nlogn个节点的极差发生改变，当且仅当/d、

CF576E

线段树分治！

并查集启发式合并。

但是并不知道这个操作会不会被执行....

所以在线地判断一下。

具体细节不太懂

bzoj2383

r_i=\min_{j}\{\frac{(x_i-x_j)^2}{4r_j},R_i\}

发现 x 上升且 r 上升则一定很优，所以我们维护一个 r 下降的单调栈。

然后我们发现我们其实可以不停地pop栈顶，直到要加进栈之前把栈顶当成答案。

典中典

给一个排列，如果 a_l\sim a_r 排序后是连续的一段数我们称 a_l\sim a_r 是连续的。 现在每次询问一个区间 [l,r]，你需要输出 k \geq r 最小的 [l,k] 满足是一 个连续段或者输出不存在。

这种连续段的性质： r-l+1=max-min

即计算 max-min-r=-l+1 的个数。

扫描线倒着扫 l，把后缀的max,min,max-min用单调栈和线段树维护出来。

最后线段树上二分统计答案。

loj3153

考虑如果 a\sim b 中出现一个大于 x_a 或 x_b 的，那么它一定不由。

所以 x_a,x_b 一定是 a\sim b 中的最大和次大。

对于一个b，优秀的a一定在单调栈上

由于我们pop一次就会增加一个优秀的区间，所以区间个数是 O(n) 的

喵嗷！

然后对于 c 做一个扫描线就搞定了。

好像这种奇怪的一堆元的题都可以找性质然后发现某某两个实际上是线性的

bzoj 4127

树剖。

直接维护负数绝对值最小值，暴力做。、

apio2019 桥梁

考虑每B个分一块，这样我们对于块之前的所有修改以及没有改过的边直接改了放过来，然后如果有要改的边就暴力加入然后算答案然后可撤销并查集撤销掉。

这样由于每次改的边是B个，那就是qB的回答，然后如果

CF896E

offline

数三元环

无向图一共几个三元环

gym 102331F

offline

Day 2

T1 T2 T3 简单题

windows下换行符 \r\n

Linux就 \n

T4

大意就是树上查单点，或者子树内对于所有到达 u 的路径上的边权大于等于 y 的点加一个 x， n,m 都是 10^5。

这个题我大力做了半天。

然后发现想麻烦了。

直接上一个kruskal重构树。

考虑每个修改操作对应了两个dfn中间那一圈东西。

也就是矩形加单点查。

然后就是一个经典cdq分治。

滚啦我要树状数组套分块套树状数组！！

不能做。。。还是老老实实cdq罢

P0

给出 a_i 求数对 a_i+a_j=a_k

n\le 50000, a_i\le 10^5

序列分块

同块暴力做

否则枚举 j，然后 a_j=a_k-a_i

我们把每个数加上一个 100000，然后前缀后缀搞出来一个桶，把这两个桶FFT出来然后对于每个块内的 j 查系数。

hxs：什么阳间东西不学，学这个阴间东西。

hxs'：什么阳间东西，不学学这个阴间东西？

P5758

先枚举加，乘，等于，确定每一个数的位数然后判断可不可能。

注意 0，这里需要特判一位数。

退火！！

你有 n 个变量：

x_1,x_2,x_3,...,x_n x_i\in \{b_1,b_2,b_3,...\}

求 P(x_i,..) 的最优解

爬山：你先随机出来一个P，然后我们微调某一个 x，如果优就改。

模拟退火：和爬山一样，但是我们设定一个温度 T表示当前的活跃度。

如果 P(x_i)<P(x'_i) 那么我们直接走，和爬山一样。

否则我们有 p 的概率走劣。

其中 p 与 T 正相关，与 \Delta=P(x_i)-P(x'_i) 负相关。

每次 T'=T\times 0.98，然后继续找x'_i

这样我们一开始会跳很多，到最后就跳得比较少了。

退火好题

你有一堆 01 变量，我有一堆 3-SAT C_i，使得 \sum C_iw_i 尽可能大。

n\le 5\times 10^4

Day 3

T1 可持久化数组（不用回退历史版本）

直接上vector+二分

T2

你有一个树，树上有 k 个点，定义一个集合的权值是从根开始走到所有节点，经过的边权和（只算一次），求所有子集的异或和 k\le 24

你把每个点按照 dfs 序排个序，然后发现加入一个 dfn 最大的节点贡献的权值就是 w(u)-w(lca(u,u-1))

所以 O(2^k) 枚举就做完了

T3

CSP2019 D1T2

T4

不记了，构造题，我随手cnm

ABC159F

首先我们考虑一个选法，它会贡献 l * (n-r+1)

所以我们稍微搞一搞dp状态

$$f(i,j)=\sum_k f(k,j-a(i)), f(i,a(i))=i$$ 关于 $i$ 求个前缀和然后随便转移/se ## CF815C 由于值域 1e9，你直接自闭。 但你其实可以把维护的东西和状态swap 然后直接爆做。 $f(i,j,0/1)$ 表示前 $i$ 的子树中买 $j$ 个物品，$i$ 有没有使用优惠券。 转移就树形背包。 ## CF1093F 考虑暴力dp $f(i,j)$ 表示前 $i$ 个数并且第 $i$ 个数填了 $j$ 的方案数。 $f(i,j)=\sum_k f(i-1,k)

然后我们可以进行一个容斥

f(i,j)=\sum_k f(i-1,k) -\sum_{x\neq j}f(i-len,x)

CF613E

冷静考虑一条路径分成哪些

形如左边一个U，中间上下走，右边一个U

然后大力转移、哈希，吐了。

CF303E

首先如果每个人区间相等，那么每个人获奖的概率是 \frac {1} {n}

然后我们发现我们其实对于每个区间可以dp，求出来每个人他有没有落在区间 i，如果落了 x 个，那么就意味着概率为 \frac 1 x

所以就可以乱做了。

具体地，f(j,k,l) 表示考虑前 j 个人，有 k 个人落在 i 前面， l 个人落在 i 里面的概率。

现在我们可以算一个人落在某个区间里的概率，然后发现获得某一个排名的概率是相等分布的，于是就算出来了。

直接转移复杂度是 O(n^5) 的。

为啥？？？

PKUSC2019D1T2

这种题也是考虑每一个同学，剩下的同学就变成0/1了

于是就变成一个 3^n 的状态。

暴力枚举每个0/1桌的胜负状态，然后就可以大力转移。

复杂度 O(4^n\times n^2\times m)

轮廓线dp可以优化到 O(3^n\times n^2\times m)

CF599E

经典题

转移大概就是 $f(rt,msk)=\sum_{msk'} f(rt,msk-msk')\times f(rt_{msk'},msk')

然后强制连边就是指定小 msk' 的根。

LCA就是两个点不能在同一个子树里，不然gg。

然后你就 O(3^npoly(n,m,q)) 了

JOISC2020 D3T1

建出来笛卡尔树，问题变成求链不交的最大权值和

Day 4

T1

求 x\le 10^9 能被多少个组合数表示。

把n\le 10^3 的组合数预处理出来，剩下一个 C(n,2) 和 C(n,1)，直接大力判断。

T2

你有一个无向图，第 i 条边的权值是 2^i，求两两点对的最短路之和。n,m\le 10^5

你发现这个玩意本质上等价于两个点之间最大编号最小的路径就是最短路。

直接MST上算贡献即可

T3

有 n 个人，编号排成一排，我们每次把编号最小的杀掉，然后随便杀 k 个，问你每个人存活概率。

n, k\le 2000

概率的本质是操控概率。

考虑 k=1，n 是奇数。

考虑我们钦定 i 活下来了。

有 i>\frac n 2

那么他前面 i-1 只，后面 n-i 只。

后面那些死掉的方案是 (n-i)!，左边的有 C_{i-1}^{n-i} 这些与右边配对，剩下的 2i-n-1 种两两配对，令他为 m。

C_{m}^2C_{m-2}^2...=\frac {m!} {2^{\frac m 2}}

做完了。

这是推式子，钟神告诉我们 100% 也可以推式子，但是我不会。

所以dp！

初始化 $$ f(0,0)=1 $$ 自然干掉编号最小的 $$ f(i,j)\rightarrow f(i+1,j+k), $$ 随机干掉编号最小的 $$ f(i,j)\times C_{j}^1 \rightarrow f(i+1,j-1) $$ 算答案，$g(i)$ 代表 $i$ 活着，并且 $i$ 是存活的人当中编号最小的方案。 $$ g(i)=\sum_j f(i-1,j)\times A(n-i,j) $$ 但是我还得算一个东西,$h(i)$ 代表 $i$ 活着，并且 $i$ 编号最小，后面某个人的存活的方案数。（每个人相等） $$ h(i)=\sum_j f(i-1,j)\times A(n-i-1,j) $$ 然后就可以算答案了 $$ ans(i)=g(i)+\sum_{j<i} h(j) $$ 但是我直接垃圾做法： $f(i,j)$ 表示还剩 $i$ 个人，第 $j$ 个人活到最后的概率。 然后死 $k+1$ 个人，等价于先死一个，再死一个，再死一个，再死一个，一直死到 $k+1$ 个。 于是这个dp的边界就是 $f(n\mod (k+1), j)=1

然后你就大力讨论，每次是删编号最小，还是删那k个中的某一个，这个显然可以讨论。

于是...

T4

杀死一只皮克敏需要 N 道工序，由 N 个人来完成，第 i 个人负责第 i 道工序。现在有 M 只皮克敏需要杀死，第 i 个人完成杀死第 j 只皮克敏的第 i 道工序需要 T_{i,j} 的时间（注意，由于 N 和 M 太大了，T 数组以 T_{i,j}=a_i\times b_j的形式给出）。为了让皮克敏有更优质的体验，杀死皮克敏的过程是流水线的。第一个人会先对第一只皮克敏执行第一道工序，完成之后将第一只皮克敏交给第二个人进行第二道工序以此类推。问把所有皮克敏杀光需要的时间。注意：在流水线工作中，每个人同时只能杀死一只皮克敏，并且开始杀死一只皮克敏的过程中不能够停止。所以如果第i个人完成了杀死当前皮克敏的工作，但第i+1个人还没有完成杀死上一只皮克敏的工作，这就会导致没有办法连续地杀死当前这只皮克敏，这是不合法的。所以你实际上是要决定每只皮克敏开始被杀死的时间，使得杀死一只皮克敏的过程中不会有中断的时间。

考场上直接放弃了。

题目等价于每两只皮克敏他们有多少的时间差才能不冲突

考虑 1,2

T(i,1)=a_i\times b_1,T(i, 2)=a_i\times b_2

那么就是

\max_i\{s_ib_1-s_{i-1}b_2\}

输出这个玩意就是40。

现在的核心问题是快速计算这个最大值。

f(x,y)=\max_{1\le i\le n}\{s_ix-s_{i-1}y\}

我们开始变形了！

\frac {f(x,y)} x=\max_{1\le i\le n}\{-\frac y xs_{i-1}+s_{i}\}

你发现我进行了 减元，所以现在直接变成一个一元的柿子。

然后你就可以开始搞事。

b=\frac {f(x,y)} x,k=\frac y x,x_i=s_{i-1},y_i=s_i

我们直接维护上凸壳进行一个二分

dij复杂度

STL堆： O((n+m)log(n+m))

斐波那契堆 O(nlogn+m)

手写堆 O((n+m)logn

差分约束

若干个变量，有限制 x_i-x_j\le y_k

求 x_k-x_1 最大是多少。

不妨令 x_1=0，问你 x_n 最大多少。

考虑最短路中 (i,j,d)，有 dis(j)\le dis(i)+d

所以令 (j,i,y_k)，跑最短路即可。

为啥是最短路？

高中数学——恒成立问题——参数分离

Problem3

$n\le 100

你要找到两个数列 b_i,c_j，满足 l\le a_{i,j}b_ic_j\le r

乘法变加法？

\log l\le \log a + \log b_i + \log c_j \le \log r

你再变！

\log l\le \log a + \log b_i - \log c_j \le \log r

直接把乘c变成除c

存在性？

判负环！！！！！！

入队 n+1次即负环。

很牛逼这个题我觉得

MST

最大值最小/最小值最大

Problem 1

n个点m条边，每条边是黑色白色。

问是否存在一棵生成树使白边数量是斐波那契数列中的某一项。

n,m\le 10^5

zhx：生成树题，一般来说都是先求出来一棵生成树再说。

你先拎出来所有黑边，然后加白边。

然后得到一个生成树，白边记为 a。

反着搞一次，所有白边，然后加入黑边。

得到一个生成树，白边记为 b。

然后你发现不用手动调整，直接考虑是否存在 i，a\le f_i\le b 即可。

因为你必定能调整过去。

Problem 2

你先随便求一棵最小生成树。 然后考虑调整。 我们引入一个套路 **惩罚值**。 如果度数大于 $k$，考虑把每个与 $1$ 连边的权值给加上一个大于 $0$ 的权值。 然后二分这个惩罚值，做完了。 然后你就得小数一下，不然他不连续。 直接归并，然后 $O(nlogw)

刚才那个题也能那么做。

二分图匹配

常见技巧：黑白染色

二分图最大独立集： n+m-k，其中k为最大匹配。

二分图补图的最大团=二分图的最大独立集。

Problem ?

平面上 N 个点，选 M 个点使得他们的最大距离最小。

M\le N\le 200

首先显然二分答案。

问题变成是否存在大小为 M 的团。

求最大团显然NP。

挑战NPC

被骗了

别二分，

换一种方法，

你发现答案最多就 n^2 种。

我们 n^2 的去枚举是哪两个点的距离。

你发现剩下的点恰好是圆的交集。

然后你发现！！

交集上半部分和下半部分形成了一个二分图！！！

然后！！！

补图的最大匹配！！！

！！！！

我草！！！

树上三角形

强联通分量

tarjan

缩点

DAG上DP/瞎搞

2-SAT

Problem ?

你有 N 个点，求 1\sim N 的最短路，我有 m 组边，其中每一组边从 P 出发连向一个 [l,r]

N,M\le 10^5

线段树优化建图

Day 5

T1

求序列中每个区间的平均数之和。

考虑包含 i 的区间个数是一个上升，不变，下降的东西。

你可以直接预处理。

T1.5

定义 f_0,f_1,f(i)=f(i-1)+f(i-2)。

定义 g(x) 表示 x 的二进制有几个零。

求 g(f(0)|f(1)|f(2)|f(3)|...|f(n))

f_0,f_1\le 10^6,n\le 10^9

部分分 n\le 10,n\le 1000,f_0=0,f_1=1

做法：

把 n 和 60取min然后做暴力。

原因：我们每次加一下， 他就一定是刚好进了一位。

所以直接就做完了。

T2

已经印在DNA里了

注意到 1001+1001=2002

T3

令 f(i) 表示长度为 i 路径中最小边权最大是多少，求 \sum f(i)\times i

把点权排序后按顺序加入。

LCT动态维护树的直径

其实没必要，因为你没有删除操作，所以直接并查集维护直径的端点。

T4

给你一个无向图，求所有其导出子图的边数的g(x)和。

g(x)=ax^3+bx^2+cx+d n\le 10^5

前两个项都好做。

怎么算部分分？

考虑 x 代表的是子图当中有多少边。

也就是我从整张图里选两条边，看有多少个子图包含这两条边。（首先加上第一个点） 1. 两条边有一个公共端点 $\sum d(v)(d(v)-1)2^{n-3}
  1. 两条边没有公共端点 [m^2-m-\sum d(v)(d(v)-1)]2^{n-4}

然后你再考虑三次项

  1. 链 枚举中间这个边

  2. 长度为2的链 枚举2链的点，然后再随便选一条

  3. 三个单链 减一减

  4. 三元环 数三元环根号分治

  5. 菊花 枚举中间点

数学

直接略了

计数

n\le 10^9,m\le1000,p\in N^{+}

爆算两两之间gcd，约成1.

n\le 10^9,p\le 100 质数

Lucas定理

C(n,m)=C(\frac n k,\frac m k)\times C(n\mod k,m\mod k)

n对夫妻问题

n对夫妻坐成一圈

如果两个方案循环同构算一种。

任意一对夫妻不能相邻

求方案数

首先圆排列 (n-1)!

然后就总方案 (2n-1)!

减去让某一对夫妻强制相邻 -C_n^12^1(2n-2)!

然后容斥

\sum_{i=0}^nC_n^02^{i}(2n-i-1)!

就是你把比较强的方案给容斥掉。

经典问题

你从 (0,0) 走到 (n,m)，我要从(x,y) 走到 (x+d_x,y+d_y) 要求满足 0\le d_x\le T_x,0\le d_y\le T_y,d_x+d_y\neq 0

我现在给你 r，代表你需要走 r 步从 (0,0) 且到 (n,m)，有 k 种方法不能走，我告诉你 (d_x,d_y)\neq (10z_i,10z_i)

n,m,t_x,t_y\le 800,r\le 1600,k\le 50

暴力 f(i,x,y) 代表走了 i 步，走到 (x,y) 这个点的方案数。

我直接枚举

f(i,x,y)=\sum_{d_x,d_y}f(i-1,x-d_x,y-d_y)

二维前缀和优化 O(rkn^2)

现在有一个部分分 k=0

直接x,y分开dp然后乘起来。

终于，我们可以开始容斥了。

$$ ans=\sum_{i=0}^r\sum_{z=0}^{\min\{\frac n {10},\frac m {10}\}}h(i,z)\times f(r-i,n-10z)\times g(r-i,m-10z)\times C_r^i\times (-1)^i $$ # Day 6 糖椰叶！ # T2 你有长度为 $n$ 的序列，有 $m$ 位置被染色，你可以重复把一个没有颜色的染成相邻颜色。染完之后将 $($颜色数量，颜色编号$)$ 排序，输出排序后字典序最大的排序后点对列。 $n\le 10^9,m\le 10^5

可删堆，维护每个颜色现在选能造成多大的贡献，选最大的那个直接输出。

然后枚举这个颜色所有点的两边，把这些颜色删掉再加回来。

然后你发现没必要用可删堆，每次弹出来的时候看一下他和当前的一不一样就好了。

T1

对于排列的每个位置求所有的子区间满足他是第 k 大。

n\le 3\times 10^5,k\le 100 $nklogn$ 直接前面找找后面找找。 $nk$ 就小trick，对于每个 $p_i$ 把大于等于它的记为 $1$ 小于它的记为 $0$， 问题变成区间中恰好 $k$ 个 $1$。 枚举左右 $k$ 个 $1$ 然后算贡献。 从小到大枚举然后把 $1$ 删掉，直接链表维护。 # T3 树上有权值 $a_i

对于每个 c 把 (a_i+c)\mod n，求 mex 最大的链。

n\le 10^5

考虑在 S\rightarrow T 新加一个点，我们希望求出来新加的点到 S\rightarrow T 的交点。

有一种牛逼做法是 lca(x,y)\ \text{xor}\ lca(y,z)\ \text{xor}\ lca(x,z)

于是我们可以完全做出 c=0

我们插入 c=n-1，然后我们直接类似于 two pointers 的操作扩展。

不过我们现在要删点。

开一个 set，维护到 s 的距离。

然后我们就可以直接删，顺带打个tag。

然后发现这题有 O(n) 做法？？

双栈模拟队列。

如果弹空了，令 mid=r，重构一个栈，这玩意还是线性的。

T4

求 \sum_i |p_i-i|=k 的所有错排数量

n\le1000,m\le2000

考虑 m\le 10+n

依然状压。

我们画个图。

我们肯定不能让 p_i 和 i 离得太远，所以 |p_i-i|\le 10

我们记忆化搜索一个。

看一下 m-n\ge 多少

然后就可以了。

接下来考虑多项式做法。

逐渐记不懂。

线头dp？？？？

膜你

我直接略了

P2949

CF1333F

脑筋急转弯。

你考虑 x 的最大因数 c_i。

如果 c_i 没被选那么我们显然可以选 c_i，如过选了 c_i 那么答案一定比 c_i 更多。

所以我们直接把 c_i 排序就做完了。

Day 7

Gym 102984A

先特判一大堆情况，得到 k<log,sum\$\ge 2

我们找到第 a_i 个字符的确切位置

逐层二分。

CF1500F

令 \Delta_i=|h_i-h_{i+1}|

然后大力讨论，发现只要有 \Delta_i 那么一定有解

我们直接设计dp转移。

CF 960H

把每种颜色的糖果拎出来然后树剖。

O(qlog^2n)

SGU 514