做题笔记

几个杂题

P2150 寿司晚宴 [dp] [状压dp] [ntt]

大于 $\sqrt n$ 的质因数最多只有一个, 最多出现一次, 相同大质因数一起处理, 背包合并

P2048 超级钢琴 [greedy]

要求所有区间的前k大, 考虑处理 $k$ 次取最大, 开一个堆记录 $(l, rl, rr, t)$ 表示左端点为 $l$ , 右端点在 $rl$ 到 $rr$ 间时最优位置为 $t$ 的答案, 每次从堆中取出最优解, 把区间分裂成 $(l, rl, t-1)$ 和 $(l, t+1, r)$ 两个区间放回堆中

P3783 天才黑客 [ds] [virtual-tree] [最短路] [前缀和优化建图]

点边互换, 考虑对于一个点怎么把这些边连到一起.

考虑边之间的贡献是lcp, 那么可以转字典树上lca, 然后转字典树欧拉序最小值.

那么在这个序列上一个最小值会贡献前面一段后面一段, 用前后缀优化建图. 并且因为要对每个点单独跑一遍所以要用虚树.

最后可能会连出多余的边, 但是最短路保证了只会走最小值(重边自动取min), 所以是正确的.

P1763 埃及分数 [ida] [搜索]

居然是第一次写迭代加深

首先迭代加深主要是用在dfs搜索情况太多必然会挂, bfs每层情况太多存不下, 此时若能确定一个状态的后继状态的一个较小的范围那么就可以用.

如果我们决定每层分母从小到大, 也就是分数递减, 那么重点就是看每层的上下界, 设减去前面搜了的还剩 $\frac {a}{b}$ 要填, 当前分母为x, 后面还有 $rest$ 层:

当分母大到一定程度, 即使后面的都等于自己也到不了1时显然是不行的, 所以 $rest*\frac {1} {x} \ge \frac {a} {b}$

当分母小到一定程度, 即使后面都是0也超了更是不行的, 所以 $\frac {1} {x} \le {a} {b}$

最后, 这题似乎并没有靠谱做法, 至少在要求最大分母少于 $10^7$ 时讨论区里这组数据还杀遍程序无敌手:

1
2
3
4
Input:
570 877
Output:
2 7 144 15786 18417 42096

P8350 [SDOI/SXOI2022] 进制转换

给定$n,x,y,z$求$\sum_{i=1}^n x^iy^{f(i)}z^{g(i)}$.
$f(i),g(i)$表示$i$在二进制,三进制下表示的数位和.
$n\le 10^13$

数据范围让你想到根号,于是考虑折半.

因为看起来二进制结构更好,所以考虑折三进制,可以设数$w=i+j\cdot 3^C_1$,

那么看起来$x$和$z$的贡献就是把项$x^iz^{g(i)}$卷起来.

考虑二进制,在依据刚才的$C_1$划分后,再按照二进制划分为$C_2$使得$2^{C_2}\ge 3^{C_1}$,此时发现合并时低$C_2$位是直接加,问题是可能出一个进位,于是只需卷两遍即可.

P8330 [ZJOI2022] 众数

给定$a_n$,求区间$[l,r]$使得区间内的众数出现次数和区间外的数的众数出现次数的和最大.

$n\le 5\times 10^5$,3s

出现次数相关,根号分治.

大的部分,枚举一个多于$\sqrt n$的数,处理出出现次数的前缀和,再枚举另一个数作为内区间,显然区间内这个数的出现次数要多于刚才的大数,所以用SDOI2022 d1t1 trick让复杂度关于小数即可.大数作为内区间同理.

小的部分,考虑对于一个出现次数$c$的颜色本质不同区间有$c^2$个,于是一共有$n\sqrt n$个本质不同区间,那么只要$O(1)$算区间众数,这显然不太可做,性质是众数出现次数数根号级.考虑扫描线,对每个$l$维护$[l,r]$的答案,那么当$r$移动一个的时候,遍历位置$r$之前所有的出现位置$x_1\ldots x_m$,对每个$x_j$,从$x_j$开始更新$x_j,x_j-1\ldots $的答案,如果不能更新直接结束,这样因为更新总次数(也就是维护的答案总和)是$n\sqrt n$量级,所以复杂度是对的.

总复杂度$n\sqrt n$.

codeforces 2200左右的trees题

CF76A Gift [lct] [mst]

一张图, 每条边有两个属性 $(g_i, s_i)$ . 给定 $G, S$ , 求一棵图的生成树 $T$ , 使得 $G \times \max(g_i) + S \times \max (s_i)$ 最小. ( $i\in T$ )

注意: 图可能包含重边和自环.

$N\le 200, M\le 50000$

考虑把所有 $G$ 和 $S$ 直接乘上去, 就不用管了. 问题变成 $\min \max(g_i)+\max(s_i)$

那么枚举一个最大的 $g$ , 能选的边是一个前缀, LCT! .

题解区里没有LCT? 要不我去写一个? 考虑一个阳间做法, 这题 $N$ 只有200. ///kx

CF77C Beavermuncher-0xFF [dp]

给定一棵树, 点 $i$ 的权值为 $k_i$ 求一条从根出发到根结束的路径使得每个点经过次数不大于其权值. 最大化路径长度.
$n, k_i\le 10^5$

$f_i$ 表示进入 $i$ 的子树走一圈回到 $i$ 的最大数量, 那么求 $f_u$ 肯定是走了孩子中 $f$ 递增排休后的一个前缀. 结束了.

CF575B Bribes [ds]

给一棵树, 一些边无方向边权为0, 有向边逆向经过一次边权翻倍. 求按照给定顺序经过 $k$ 个点的边权和. 答案膜.

$n\le 10^5, k\le 10^6$

首先一个显然的 $2log$ 做法, 就是树剖区间乘区间和.

那么正解可以对每一条边单独考虑, 按某方向经过它的代价当然是有若干次子树内与子树外这个切换.

考虑切换是上一次在一个子树区间内, 下一次在子树区间外的个数, 那么把相邻两个数看作一个点, 就转化为二维数点了, 1log.

看题解, 愚蠢了. 直接树上差分做.

CF893F Subtree Minimum Query [线段树合并]

给你一颗有根树, 点有权值, $m$ 次询问, 每次问你某个点的子树中距离其不超过 $k$ 的点的权值的最小值. (边权均为 $1$ , 点权有可能重复, $k$ 值每次询问有可能不同)
强制在线

$n\le 10^5, m\le 10^6, a_i\le 10^9$

线段树合并一眼题.

看题解, 原来题目深意在于难为主席树///kx. 不过可以直接考虑就是深度, dfs序两维的数点要强制在线. 那显然就是时间轴建哪的问题, 发现如果时间轴建在dfs序上会寄因为要考虑这个值在区间中出现次数(值有重复). 但只要两维反一下就直接做.

另外给相同点权强行钦定大小整成多个也能做啊.

CF1174F Ehab and the Big Finale [交互] [点分治] [树剖]

给一棵 $n$ 点树, 有一个不知道的点 $x$ , 每次你可以询问 $x$ 到一个点的距离, 或者询问 $x$ 的祖先的哪一个儿子是 $x$ 的祖先. 找出 $x$ .

你可以进行36次操作. $n\le 2\times 10^5$

首先显然是一个 $\log$ 的复杂度. 在树上进行 $\log$ 的常见分治有点/边分治, 树剖.

我们没法添加虚边, 排除边分治.

发现点分治很直接, 我们找到重心, 如果是点的祖先就进入对应子树再找重心, 否则距离可以用来判断当前点是不是祖先. 就做完了. 次数可能多一次随便剪一剪.

CF652E Pursuit For Artifacts [边双] [连通性]

给定一张 $n$ 点 $m$ 边简单无向连通图, 边权是 $0, 1$ . 每条边只能走一次, 求是否存在 $a\to b$ 的路径边权不为0.

$n, m\le 3\times 10^5$

圆方树的重要结论是两个点间简单路径的并集是圆方树上到两个圆点路径距离为1的点. 边双结论相同. 所以缩点之后树上做即可. 所以这题完全可以 $10^5$ 询问吧!

Codeforces 好题 Div. 1-1

看了上面那几个, 又从后面随机了几个, 没意思就换了个题单. 是编号2213 Codeforces 好题 Div. 1-1

尽量秒///fendou

CF5E Bindian Signalizing [单调栈] [环转序列]

圆环上有 $n$ 个点, 每个点有权值 $a_i$ , 求点对 $(i, j)$ 数量使得对于圆环上的两个区间 $[i, j]$ 中有至少一个满足 $\max_{k\in [i, j]} a_k\le \min{(a_i, a_j)}$

$n\le 10^6$

考虑一个点能与哪些点形成点对.

如果这个点是全局最大值, 那么能与所有形成点对. 否则不会有一个点同时可以与这个点在两个方向的区间上形成点对.

考虑序列上一个点与前面的点形成点对, 显然维护缀max这件事只需要一个单调栈.

环上需要考虑跨过最后的贡献, 很难写. 最好的办法是把最大值转到最前面按序列做.

CF8E Beads [数位dp] [dp]

求所有长 $n$ 的01串 $s$ 中同时满足字典序不大于其逆序串, 取反串和逆序取反串的串中按字典序排序的第 $m$ 个.

$n\le 50, m\le 10^16$

字典序不大于取反串, $s_1=0$ .

根据最后一位是0或1决定是小于逆序串还是逆序取反串. 分别处理. 假设现在最后一位是0, 处理不大于逆序串.

可以同时两边向中间dp. $f_{i, 0/1}$ 表示前 $i$ 个和后 $i$ 个已经确定, 且填到现在是小于逆序串还是等于逆序串的方案数.

我们会计数了, 但如何求 $kth$ 呢?

假设我们会钦定若干个字符后的方案数–我们确实会, 那么可以直接逐位确定.

看题解: 可以直接折半搜? ! 看来以后看到 $n\le 50$ 要想到这基本上是折半的上界.

CF10E Greedy Change

给定 $n$ 种货币, 求最小的 $w$ 使得贪心求解兑换方式不对(贪心方式就是每次找到不大于它的最大的减去), 或说明不存在.

$n\le 400$

论文题///fn, 汪娟题///se

todo

CF11D A Simple Task [dp] [状压dp]

求简单无向图的环数.

$n\le 19$

降智了, 这不是图论题///fn这是状压dp///fn看到19该想到的.

那就对每个点跑一遍, $f_{i, S}$ 表示从点 $u$ 出发走到点 $i$ , 走过的点集合为 $S$ , 但很遗憾会把一个环算好多次.

不对每个点跑一次了, 钦定 $S$ 中走过的点最小的为出发节点(所以扩展时只能扩展比这个大的).

最后这样会把一条边算成一个环, 还会把一个环算两次, 所以去掉即可.

CF13E Holes [lct] [分块] [ds]

就是弹飞绵羊

CF15D Map [二维前缀和]

小P要在某个 $n\times m$ 规模的矩阵上建大小为 $a\times b$ 的房子, 已知这个矩阵每一点上的数值 $h_{i, j}$ 代表开始时地面的高度.
若建造 $a\times b$ 房子的地面不一致, 则要把选取的 $a\times b$ 大的矩阵中所有地面都挖低使得和其中一块最低的地面高度一样, 花费是挖的高度和. 小P会重复如下的步骤直至无法再建造更多的房子:

  1. 找到 $n\times m$ 矩阵中建造房子花费最少的 $a\times b$ 矩阵, 优先选择左上角的矩阵. \
  2. 输出左上角的位置, 并输出在这里建房子的花费\
  3. 已经建过房子的地面不能再建房子.
    $a, b\le 1000, h_{i, j}\le 10^9$

直接每个点预处理以这个点为左上角的代价排序. 代价处理需要二维前缀和求和, 和一个东西求最小值.

最小值要想求的简单, 感觉一个不错的办法是先竖着求竖着 $b$ 个的最小值再横着合并 $a$ .

然后解决选的不能和已有的覆盖, 这个怎么做呢? 每次选定一个点就把受这个影响的地方暴力覆盖, 复杂度是对的因为一共 $nm$ 个点.

CF19E Fairy [dfs树] [graph]

给一张无向图, 求删一条边变成二分图的方案数.

$n, m\le 10^4$

碰到不知道咋做的图论想dfs树.

dfs树上只有树边和返祖边, 定义一个返祖边对应的只有一条返祖边的环为本源环, 其中本源环为奇环的是坏边, 偶环的是好边, 注意到边能被删当且仅当在所有坏边的本源环上且不在好边的本源环上, 于是树上差分实现判断每条树边被多少坏边的本源环包含即可. 而返祖边只有当奇环总数是 $1$ 的时候删掉那条坏边可行.

这个充要条件是最巧妙的一步, 必须包含所有本源环显然, 不能删掉偶本源环内的是因为去掉之后偶环剩下的部分和奇环剩下的部分组成奇环.

[think] 这个做法的本质是dfs树把无向图排布成一个优秀的结构让返祖边表示本源环.

CF25E Test [greedy] [string]

给出 $s_1, s_2, s_3$ , 求最短的 $t$ 使得其包含给出的三个串作为子串.

$n\le 10^4$

暴力枚举三个子串出现的先后顺序, 最后答案只能是它们接起来. 算接起来的重叠部分可以直接kmp或hash二分.

CF39C Moon Craters [dp]

给出在一个直线上的 $n$ 个圆(位置和半径为 $p_i, r_i$ ), 如果两个圆不相交则可以放在一起(可以包含), 求最多有多少个圆一起.

$n\le 2000$

$f_{i, j}$ 表示区间 $i, j$ 的个数做就行了. 注意直接转移 $n^3$ , 但划分区间的时候可以钦定左半边是一整个圆, 这样只要划分那些有一个左端点是 $i$ 的区间的右端点即可.

CF55D Beautiful numbers [dp] [状态设计]

求 $[l, r]$ 中美丽的数的个数, $x$ 美丽当且仅当 $x$ 可以被每一个非零位整除( $15$ 是美丽的因为可被 $1, 5$ 整除)

$1\le l\le r\le 9\times 10^18$

看着很数位dp. 但要想判断是否能被整除需要知道数值是无法忍受的. 考虑 $1-9$ 的 $lcm$ 只有 $2520$ , $2520$ 的因数(对应当前 $0-9$ 的不同选择情况)只有48个, 于是就 $f_{i, j, k, 0/1}$ 表示前 $i$ 位, 膜 $2520$ 为 $j$ , 当前选择的数要求它被 $2520$ 的第 $k$ 个因数整除, 是否顶到头的方案数.

CF73D FreeDiv [graph] [greedy]

给出一个 $n$ 点 $m$ 边的图和常数 $k$ , 你可以现在图中任意连边, 然后在得到的图中继续连边, 但此时一个点只能连出一条, 同一个连通块只能连 $k$ 条, 求为了得到一个连通图第一步需要连多少边.

$n, k, m\le 10^6$

一开始以为需要点分类讨论的, 但这个题可以通过贪心避免讨论.

首先考虑判断继续加边前什么样子时图可以连通. 实际上只要能连的边总数大于需要边数因为我们可以保证不连环.

那么边数总和是 $\dfrac{\sum \min siz_i, k}{2}$ , 需求量是连通块个数-1, 所以 $siz$ 越大越好(取 $\min$ ), 所以每次取两个最小的连通块合并直到满足式子即可.

CF85D Sum of Medians [ds]

维护一个集合, 支持添加一个数, 删除一个数, 或者查询对于将集合内的数从小到大排好序后形成有 $k$ 个数的序列 $a$ , 求

$$\sum_{i}^{(i\le k)\land (i\bmod 5=3)}a_i$$

$n\le 10^5, x\le 10^9$

权值线段树, 维护每个点膜5余0, 1, 2, 3, 4的和即可.

CF86D Powerful array [ds]

莫队板子.

CF93C Azembler [ds]

爆搜idfs板子

CF95E Lucky Country [dp] [自然根号]

如果一个数中不包含除 $4$ 和 $7$ 之外的数字则是幸运数. 有 $n$ 个岛屿, 通过双向道路连接. 这些岛屿被分为几个地区. 每个岛属于恰好一个区域, 同一区域中的任何两个岛之间存在道路, 不同区域的任何两个岛之间没有路径. 如果一个地区的岛屿数量是一个幸运数字, 则这个地区是幸运的. 问最少增加几条道路能创建一个幸运地区.

$n, m\le 10^5$

处理连通块+背包, 但01背包这个过不去.

考虑所有连通块大小之和为 $n$ , 那么经典套路不同的大小有 $\sqrt n$ 种, 所以可以作成 $\sqrt n$ 个物品的完全背包, 结束.

CF103E Buying Sets

放到了网络流选做里.

CF115E Linear Kindom Races [线段树] [dp]

给定序列 $a_n$ 和 $m$ 个区间, 每个区间有价值 $w_i$ , 若要得到区间 $[l, r]$ 的 $w$ 需要支付 $\sum_{l\le i\le r} a_i$ . 求最大收益(收入-支出)

$n, m\le 2\times 10^5$

这是dp题.

很自然的想法是 $f_i$ 表示前 $i$ 个的最大收益, $i$ 如果不修复直接从上一个整过来, 否则 $f_i$ 可能一直修复一个区间到 $f_j$ , 我们钦定没有跨过区间 $[j, i]$ 的端点, 然后贡献就是完整包含在 $[j, i]$ 的区间的 $\sum w_k$ 减去 $\sum a_l$ , 考虑优化.

用线段树维护它, 线段树上每个位置放的就是完整包含在这一段的贡献, 那么就每个下标 $i$ 维护这个决策的值就行了.

CF132E Bits of merry old England

放到网络流选做里.

CF164C Machine Programming

放到网络流选做里

CF176E Archaeology [ds]

就是 异象石.

CF200A Cinema

给出 $n\times m$ 的01矩阵 $A$ , 每个元素初值为 $0$ , $k$ 次操作, 每次给出 $x, y$ , 求离其曼哈顿距离最近的 $0$ 并将其设置为1.

$n, m\le 2000, k\le \min(nm, 10^5)$

KDT? ///kx

最无脑的一定是拆开曼哈顿距离, 四个方向各放一个树套树了吧, 可以直接冲.

代码阳间的是, 考虑因为只有 $k$ 个 $1$ , 所以一个 $0$ 距离最近的 $1$ 不超过 $\sqrt k$ , 于是维护每个点离它最近的距离, 然后查的时候暴力枚举等于这个距离的一圈有没有即可. 因为你询问的 $q$ 个点的最近距离的总和是 $\sqrt k$ 的. 就做完了啊.

CF204D Little Elephant and Retro Strings [count]

给定字符串 $s$ , 字符为 $\texttt{01? }$ , $\texttt{? }$ 表示任意. 求多少种方案满足存在两个不相交子串(严格), 且左边的全 $\texttt{1}$ , 右边的全 $\texttt{0}$ .

$k\le \vert s\vert \le 10^6$

统计问题, 设 $f_i, g_i, h_i$ 分别表示前 $i$ 个的最后 $k$ 个全 $\texttt{0}$ , 后 $i$ 个前 $k$ 个全 $\texttt{0}$ , 后 $i$ 个出现过 $\texttt{0}$ 段, 然后方案数就是 $\sum f_ih_{i+1}$

就是要这种可以在多个地方贡献的问题钦定在第一处/最后一处等特殊位置.

CF235C Cyclical Quest

收录在字符串选做上

CF254D Rats [bfs]

一个 $nm$ 的网格图中, 有一些格子是墙, 用 $X$ 表示, 其余格子中, 有一些格子中有*老鼠, 用 $R$ 表示, 其余空格子用 $.$ 表示

现在需要放置两颗手榴弹, 每颗手榴弹初始在格子 $(r_i, c_i)$ 上, 在 $1-d$ 秒内, 每过 $1$ 秒其伤害范围会从现有的每个伤害范围的格子向外扩展一格, 即若 $(a, b)$ 为伤害范围, 则下一秒 $(a+1, b), (a-1, b), (a, b+1), (a, b-1)$ 中不为墙的格子都会变为伤害范围, 当一个有老鼠的格子成为伤害范围, 那个格子的老鼠就会死掉

你需要给出能够杀死所有老鼠的两个手榴弹的放置坐标 $(r_1, c_1)和(r_2, c_2)$ , 如果无解, 则输出 $-1$
$n, m, d$ 为常数, $n, m\le 1000, d\le 8$

疯狂bfs, 先随便找一只老鼠bfs能炸到它的地方, 在这个区域枚举第一个炸弹的位置, 找到一只第一个炸弹炸不到的老鼠, 在这里枚举第二个炸弹的位置, 复杂度 $d^8$

CF263E Rhombus

$n\times m$ 的矩阵 $a$

函数 $f(x, y)=\sum_{i=1}^n\sum_{j=1}^m a_{i, j} \times max(0, k-\vert i-x\vert -\vert j-y\vert )$ , 求 $(a, b)$ 最大化 $f(a, b)$ , 其中 $a\in [k, n-k+1], b\in [k, m-k+1]$
$n, m\le 1000$

todo

qyc推荐

[2022SDFZ省选模拟赛6]词典 [闵可夫斯基和] [决策单调性] [dp]

一个 $01$ 串 $s$ 是单词当且仅当 $s$ 中不含两个连续的 $0$ .

一个包含 $n$ 个单词的词典是 $n$ 个单词的集合, 且满足其中任意一个单词都不是任意其他单词的前缀.

给定一个词典 $D$ , 定义 $01$ 串 $s$ 的代价 $C(s)=\displaystyle \sum^{k}_{j=1}\lfloor 1+\log_2 j\rfloor$ , 其中 $k$ 是 $D$ 中满足 $s$ 是 $t$ 的前缀的单词 $t$ 的数量. 该词典 $D$ 的代价即为所有 $01$ 串的代价之和.

例如, 考虑一个包含 4 个单词的词典 ${0, 10, 110, 111}$ . 这个词典的代价为 $C(\epsilon)+C(0)+C(1)+C(10)+C(11)+C(110)+C(111)=8+1+5+1+3+1+1=20$ . 这里 $\epsilon$ 表示空串.

求包含 $n$ 个单词的词典的代价的最小值.

多组询问, $n\le 10^{15}, t\le 50000$

神仙题.

考虑把字典插入到一个trie里, 那么因为没有互为前缀所以所有单词叶子, 因为没有两个连续 $0$ 所以左儿子没有左儿子, 树的结构就是

! picture 2

于是考虑dp, 设 $f_{i}$ 表示 $i$ 个叶子的最小代价, 设题面里的代价函数为 $g(k)$ 则有 $f_{i}=g(i)+g(j)+f_j+f_{i-j}$ . 这里 $j$ 是枚举 $b$ 的子树大小, 那么发现 $v$ 的代价是 $g(j)$ , $u$ 的代价是 $g(i)$ . 如果你不明白为什么是 $g(i)$ 你就再想想.

然后猜测 $g$ 和 $f$ 都是上凸的, 用闵和优化(闵和带来的决策单调性, 两个函数归并每次向后延一段)可以做到 $O(n)$ . 再考虑发现因为 $g$ 的差分只有 $\log$ 段, $f$ 的差分只有 $\log^2$ 段, 所以每次向后延伸一段差分相同的部分, 复杂度就成了 $\log^2$ 的了.

然后最后实际上它是差一点上凸的, 仅在 $n=5$ 的时候会算错, 需要特判.

UOJ182. [UR #12]a^-1 + b problem [poly]

区间加, 区间和, 区间取逆元

$n\le 10^5, m\le 6\times 10^4$ , 膜998244353

每个数可以写成 $\dfrac{ax+b}{cx+d}$ , 把 $c$ 化成1, 写成 $a+(b-ad)\dfrac{1}{x+d}$ , 前面的提出来是常量, 所以最后多点求值.

P8371 [POI2001]绿色游戏 [game] [graph] [调整]

绿色游戏是一种两人游戏, 双方分别称 $\text{Ann}$ 和 $\text{Billy}$ . 游戏的内容主要是轮流在棋盘上移动一颗棋子.

棋盘上的点一部分是绿色的, 其余是白色的. 它们全部从 $1$ 至 $a+b$ 编号. 编号 $1$ 至 $a$ 的点属于 $\text{Ann}$ , 编号 $a+1$ 至 $a+b$ 的点属于 $\text{Billy}$ . 每个点都有一些后继点, 均可一步到达. 属于 $\text{Ann}$ 的点的后继点一定属于 $\text{Billy}$ , 反之亦然. 所有的点都至少有一个后继点, 这样总可以往下走一步.

游戏开始时把棋子放在任意的一点 $P$ 上, 然后双方轮流移动棋子至当前所在点(属于移动方)的一个后继点上(属于对手). 游戏由点 $P$ 的拥有者开始, 结束时棋子第二次到达了某一点, 称点 $Q$ . 如果在从点 $Q$ 至点 $Q$ 的一连串移动中, 棋子至少一次被放到绿色点上, 则 $\text{Ann}$ 赢. 若从点 $P$ 开始, 不管 $\text{Billy}$ 如何移动, $\text{Ann}$ 总能保证赢得这次游戏, 则称 $\text{Ann}$ 对起始点 $P$ 有必胜的策略.

请你编写一个程序:

  1. 读入对棋盘的描述.

  2. 算出 $\text{Ann}$ 有必胜策略的起始点.

$a, b\le 3000$ , 边数 $30000$ , 绿点个数 $green\le 100$

qyc推荐的题.

考虑路径上所有经过的点中, 只让走了两次的那个绿点贡献(必然存在的), 那么如果一个绿点出发有必到达自己策略它是必胜的, 否则就不用管. 而只要从必胜绿点走出去dp就行了. 于是把所有绿点都当必胜的去dp, 每次dp出一个会输的绿点就把它从必胜绿点踢出去接着做, 复杂度是 $green\times m$ .

这么做最后被踢出去的当然真的不能胜利, 而胜利的确实可以走到环上, 所以正确.

[think] POI最爱的钦点-调整法.

from dwt blog

AGC052B Tree Edges XOR [adhoc]

给定 $Tree(n)$ , 保证 $n$ 是奇数, 边有边权 $w_{i, 1}$ , 现在你可以任意次把与一个边相连的其他边的权值异或上这条边的权值, 求是否可以让每条边的边权变为 $w_{i, 2}$ .

$n\le 10^5, w\le 2^30$

最困难的一步在第一步吧. 考虑这个操作本质上在干什么, 发现让边权等于连到它上的两个点权的异或, 则这是在交换相邻两点的点权.

[think] 重新赋值出性质.
[think] 考虑操作本质.

于是现在要给初始状态和结束状态分配点权使得权值集合相同. 考虑点权其实只要确定一个点, 剩下的点权都是确定的这个点异或上一个定值, 于是分别确定1号点权值, 然后解异或方程即可.

ARC126D Pure Straight [dp] [状压dp]

给定 $a_n$ , $a_i\in [1, k]$ , 每次可以交换相邻两个, 求最少次数使得 $a$ 包含子区间值恰为 $1, 2, 3, \ldots, k$ (排好序).

$n\le 200, k\le 16$

$k$ 很小, 说明很状压.

于是想到设 $f_{i, S}$ 表示前 $i$ 个, 最后 $\vert S \vert$ 个已经是排好序的 $S$ 的最小代价.

对于一个元素, 它如果在最终集合里就移动到 $S$ 对应位置, 否则应该整个移动过 $S$ 前面.

发现是错误的–这个元素除了往前移动到 $S$ 前, 还可以向后移动出 $S$ . 于是取个min即可.

CF选糊

看看他们都VP了哪些场.

CF1083 Codeforces Round #526 (Div. 1)

A. The Fair Nut and the Best Path [dp] [树形dp]

给定 $Tree(n)$ , 点有点权 $w_i$ , 边有边权 $c_i$ , 一开始你的分数是0, 走过一个点加 $w_i$ , 走过一个边减 $c_i$ , 任意时刻要求分数 $\ge 0$ , 求走一条链最大化最大分数.

$n\le 3\times 10^5$

直接dp, $f_{i, 0/1}$ 表示当前点作为端点/作为中间点的最大收益即可, 转移显然.

B. The Fair Nut and Strings [greedy]

有 $k$ 个长度为 $n$ 的只含 $a$ 或 $b$ 字符串, 并不知道它们具体是多少, 只知道它们的字典序不小于字符串 $A$ , 同时不大于字符串 $B$ . 定义一个字符串是合法的当且仅当它是这 $k$ 个字符串之一的前缀(如果它是多个串的前缀那么只计算一次). 求最多一共会有多少个合法的字符串.

$n\le 5\times 10^5, k\le 10^9$

就是最大化这 $k$ 个字符的trie点数.

直接贪心, 尽可能多的分配, 和 $k$ 取个min.

C. Max Mex [ds] [线段树] [可合并信息]

给定一棵有 $n$ 个点的树, 每个节点有点权. 所有的点权构成了一个 $0 \sim n - 1$ 的排列. 有 $q$ 次操作, 每次操作 $1$ 为交换两个点的点权, 操作 $2$ 为查询 $Mex(l)$ 值最大的 $Mex(l)$ 值, 其中 $l$ 是树上的一条路径. 定义一条路径 $l$ 的 $Mex$ 值 $Mex(l)$ 为这条路径上最小的没有出现过的自然数.

考虑这个东西是可合并信息: 两条链能不能合并是简单的, 那你就开一个线段树维护走了值在这个区间的点的链, 操作 $1$ 就是单点修改, 操作 $2$ 直接线段树上二分.

实现重点应该是链的合并, 写法包括:

  • 枚举新的链的两个端点判断剩下两个是否在上面. 6个lca.
  • 枚举新的链的两个端点判断长度是否等于虚数边权和. 4个lca.
  • 枚举新的链不是端点的两个点, 分类讨论.

前两个要树剖lca(倍增直接T飞), 第三个不用lca(就是为了和dwt证明不写树剖///kx)

1
2
3
4
5
6
7
8
9
10
11
12
13
bool check(int a,int b,int c,int d){
    if(intree(b,a))swap(a,b);
    if(intree(a,b)){
        if(intree(b,c)&&(!(intree(a,d)&&intree(findchild(a,c),d)))||intree(b,d)&&(!(intree(a,c)&&intree(findchild(a,d),c))))return true;
        else return false;
    }
    if(intree(a,c)&&intree(b,d)||intree(a,d)&&intree(b,c))return true;
    else return false;
}
/*
bool intree(a,b): return if a is the ancestor of b
int findchild(a,b): return the child of a which is the ancestor of b
*/

D. The Fair Nut’s getting crazy [ds] [扫描线] [拆式子] [线段树]

给定一个长度为 $n$ 的序列 ${a_i}$ . 你需要从该序列中选出两个非空的子段, 这两个子段满足:

  • 两个子段非包含关系.
  • 两个子段存在交.
  • 位于两个子段交中的元素在每个子段中只能出现一次.
    求共有多少种不同的子段选择方案. 输出总方案数对 $10^9 + 7$ 取模后的结果.
    需要注意的是, 选择子段 $[a, b]$ 、 $[c, d]$ 与选择子段 $[c, d]$ 、 $[a, b]$ 被视为是相同的两种方案.
    $1 \leq n \leq 10^5, -10^9 \leq a_i \leq 10^9$ .

第一眼看成选任意多个子段, 转变成某些不可做题.

假设每个值分别考虑, 那么相当于划分若干段, 限制了四个端点的范围. 问题似乎变成了四维超长方体并体积. 这做个锤子.

假设一个确定的交, 要查第一个满足 $pre$ 在交这个区间的位置. 三维偏序是2log. 发现不可扩展. 不对这不是智障行为吗? 查在这个区间中最大的 $nxt, pre$ 可是简单的很, 也就是如果确定了 $[l, r]$ 作为交, 左右端点范围是 $\min_{i\in [l, r]} nxt_i -1$ 和 $\max_{i\in[l, r]} pre_i +1$

不如考虑画画式子, 为了方便设那个 $\min, \max$ 分别为 $f(l, r), g(l, r)$ 我们要求

$$
\sum_l \sum_r [l<r] (f(l, r)-r)*(l-g(l, r))
$$

可能还有点不重要的常数项(好像没有? ). 拆开, $r\cdot g(l, r)$ 这种东西似乎可以扫 $r$ 解决, 就是区间取max(单调! 变成区间赋值)和区间和.

现在问题是 $f(l, r)\cdot g(l, r)$ , 考虑扫描 $r$ , 问题是区间赋值, 求序列点积. 发现维护区间 $a, b$ 和答案就是线性变换.

就这也配3500

E. The Fair Nut and Rectangles [dp] [斜率优化]

给定 $n$ 个矩形, 左下角为 $(0, 0)$ , 右上角为 $(x_i, y_i)$ , 每个矩形有权值 $a_i$ , 矩形互不包含, 求选择若干矩形使得并的面积减权值和最大.

$n\le 10^6, x_i, y_i\le 10^9$

考虑你画一画, 发现如果我们从左往右选, 因为 $y_i$ 递减, 每个矩形的贡献就是上一个矩形到它的距离乘 $y_i$ , 于是就直接dp, $f_i$ 表示前 $i$ 个矩形选的最大值, 然后斜率优化转移.

F. The Fair Nut and Amusing Xor [ds] [greedy] [分块]

给定 $a_n, b_n$ 和常数 $k$ , 每次可以选择长 $k$ 的子段全异或上一个值, 求把 $a$ 变成 $b$ 的最小次数或说明无解. 有 $q$ 次单点修改, 每次修改结束输出结果.

$n, q\le 2\times 10^5$

设 $c_i=a_i\operatorname{xor} b_i$ , 就成了从全 $0$ 变成 $c$ 的次数.

然后因为区间异或想到差分数组设为 $d$ , 每次修改 $d$ 的两个位置.

然后考虑每个 $\bmod k$ 等价类是独立的, 那么此时一个等价类的次数就是大小减前缀异或和等于自己的数的个数.

那这个就好做了, 相当于区间异或, 查询0的个数. 每个整块存出现次数和异或标记散块暴力即可.

CF1687 Codeforces Round #796 (Div. 1)

A. The Enchanted Forest [greedy]

魔法森林可以被抽象成一条有着 $n$ 个节点, 从 $1$ 到 $n$ 标号的数轴. 在魔理沙出发之前, 她的好友帕秋莉运用魔法去侦测了每个节点上的蘑菇数量, 分别为 $a_1, a_2, \dots, a_n$ .
在第 $0$ 分钟的时候, 魔理沙可以从任意一个节点出发. 在每一分钟的时候, 她将会做以下事情:

  • 她将从节点 $x$ 移动到节点 $y$ ( $\vert x-y\vert \leq 1$ , 即 $y$ 可能等于 $x$ )
  • 她将会收集节点 $y$ 上的所有蘑菇.
  • 魔法森林中每个节点会再生长出一个蘑菇.
    注意, 她不能在第 $0$ 分钟的时候收集蘑菇.
    现在魔理沙希望知道她在前 $k$ 分钟的时候, 最多能收集到多少个蘑菇. 请你帮帮她.

考虑如果她 $k\ge n$ , 是不是直接答案一样模拟.

如果 $k<n$ , 那么一定不会回头, 新长出来的部分是固定的, 于是求最大的长 $k$ 的和.

B. Railway System

收录在图论选做里.

C. Sanae and Giant Robot [greedy]

给定 $a_n, b_n$ 和 $m$ 个区间 $[l_i, r_i]$ , 每次可以把一个区间的 $a_i$ 赋值为对应位置的 $b_i$ 当且仅当这么做 $\sum a_i$ 不变. 求是否可以把 $a$ 变成 $b$ .

$n, m\le 2\times 10^5$

考虑每个位置先减去 $b_i$ , 那么相当于每次选一个和为 $0$ 的区间赋值成0, 问最后能不能全变成0.

相当于前缀和, 每次选择相同的两个数把中间变得也相同. 感觉这个模型比较好.

考虑如果某一次赋值的时候不是赋成0, 那么一定不优–你必然需要一个更大的把它搞成0, 或者你必然不会用中间的部分和区间外组成匹配对.

那就简单了, 每次找个0的对暴力操作, 想怎么做怎么做.

D. Cute number [math] [复杂度]

给定 $a_n$ , 找到最小的 $k\ge 0$ 使得 $\forall i, a_i+k$ 是可爱的. 定义一个数 $x$ 是可爱的当且仅当 $x-g(x)<f(x)-x$ , 其中 $f(x), g(x)$ 分别是第一个大于, 小于等于它的数.

$n\le 10^6, a_i\le 2\times 10^6$ , $a$ 不降.

相当于值域被划分成若干段, 每个段的前一半是合法的. 或者说每个数处在一个 $[x^2, x(x+1)]$ 中.

考虑 $a_1$ 对应的 $x$ 是 $v$ 一定合法, 所以只有 $v$ 段.

那么枚举一个 $x_1$ ( $a_1+k$ 所对应的 $x$ ), 合法的 $a_1+k$ 是一个区间, 对接下来的每个 $a_i$ , 这个区间能到的 $x$ 段必然只有一个(它们的 $x$ 只会更大, 长度只会更长, 并且一个 $x$ 两边一段都是不合法的). 于是求个交就能得到答案.

考虑优化, 当枚举到 $x$ 时, 两个差在 $x$ 之内的数必然在同一块, 把它们缩起来, 分析复杂度的话考虑差分数组 $c_n$ , $c_i$ 在 $x<c_i$ 的时候没有被缩起来, 所以总代价是 $\sum c_i=v$ . 复杂度 $O(v)$ .

E. F. todo

CF1152 Codeforces Round #554 (Div. 2)

A. Neko Finds Grapes

智障题.

B. Neko Performs Cat Furrier Transform

模拟

C. Neko does Maths

给定两个正整数 $a, b$ , 找到非负整数 $k$ 使 $a+k$ 与 $b+k$ 的最小公倍数最小, 如有多解输出最小的 $k$ .
$a, b\le 10^9$

降大智了.

考虑最小公倍数很离谱, 但最大公约数比较好: 两者差始终为定值, 最大公约数是差的约数.

于是直接枚举最大公约数, 算出最小的 $k$ 然后更新最小公倍数即可.

D. Neko and Aki’s Prank

求所有长度为 $2n$ 的合法括号序列组成的trie的最大匹配. 合法括号串是仅有 $\texttt{()}$ 组成且匹配的. 膜 $998244353$ .
$n\le 1000$ .

考虑一个子树可以由 $(d, v)$ 表示为高度为 $d$ , 并且括号和是 $-v$ .

可以转化为求最大独立集.

$f_{d, v, 0/1}$ 表示这样的子树, 有没有选根即可. $n^2$ .

看到题解区里由点离谱的构造: 直接选所有深度为偶数的边和其父节点的连边(冲突保留一条), 然后用卡特兰数.

E. Neko and Flashback

对于序列 $a_n$ 和 $p_{n-1}$ , 构造 $b_i=\min(a_i, a_{i+1}), c_i=\max(a_i, a_{i+1}), b’i=b{p_i}, c’i=c{p_i}$ . 给定 $b’, c’$ 求 $a$ 或判断无解.
$n\le 10^5, v\le 10^9$

看错题了, $b$ 和 $c$ 的重排方式是相同的.

考虑那么任意一个 $b_i, c_i$ 相当于告诉你 $a_i, a_{i+1}$ 两个数连着, 是充要的, 于是每个值建图跑欧拉回路即可.

F. Neko Rules the Catniverse

给定参数 $n, k, m$ , 你需要求有多少个大小为 $k$ 的序列 $a$ 满足如下三个条件:

  1. 任意两个元素其权值不同.
  2. 对于任意 $i$ 满足 $1\le i\le k$ 有 $1\le a_i\le n$ .
  3. 对于任意 $i$ 满足 $2\le i\le k$ 有 $a_i\le a_{i-1}+m$ .
    答案对 $10^9+7$ 取模.

$1\le k\le \min(n, 12)$ , $1\le m\le 4$ .

F1 (Small Version)

$1\le n\le 10^5$

显然你应该扫值域插入着dp, 插入的要求是这个位置的前一个位置在不小于 $i-m$, 发现插入更大的元素无法缩小两个数的间距, 所以要求一开始插入的时候就让前一位置不小于 $i-m$. 于是显然你至少要记录 $f_{i, j}$ 表示前 $i$ 个数选了 $j$ 个, 此时你能插入的位置取决于在 $[i-m, i-1]$ 中的元素选了几个, 因为这个要转移所以你要记录选了谁(不然向上一位不知道掉出去的是谁), 所以 $f_{i, j, S}$ 表示最小的 $i$ 个数, 选了 $j$ 个, $[i-m, i-1]$ 中选了集合 $S$. 复杂度 $nk2^m$

F2 (Big Version)

考虑两层之间转移固定, 直接矩阵快速幂就是 $(k2^m)^3\log n$.