https://codeforces.com/contest/1864 F. Exotic Queries 题意 给定一个长度为 nnn 的数组 aaa，共有 qqq 次询问，每次询问一个区间 [l,r][l,r][l,r]：每次操作可以选定一个区间，将区间内所有数减去任意一个数。要求最终所有的数组中大小在 [l,r][l,r][l,r] 内的数都恰好变为 000，且所有选择的区间要么不交，要么包

https://atcoder.jp/contests/abc317 F - Nim 题意 给定整数 n,a1,a2,a3n,a_1,a_2,a_3n,a1​,a2​,a3​。求解符合以下条件的 (x1,x2,x3)(x_1,x_2,x_3)(x1​,x2​,x3​) 的个数： 1≤xi≤n1\leq x_i\leq n1≤xi​≤n xix_ixi​ 是 aia_iai​ 的倍数 x1⊕x2⊕

https://ac.nowcoder.com/acm/contest/63804 E Kevin的抽奖黑幕 题意 有 nnn 个人，共 mmm 轮抽奖。每轮抽奖抽 kkk 个人发奖品，若有人连续 ddd 轮没有获得奖品，那么他也能获得一个奖品。求最后所有人获得奖品的总和的期望。结果对 998244355399824435539982443553 取模。 数据范围：1≤n,m≤2000,1≤k≤

F World Fragments II 题意 有 qqq 次询问。每次询问给定两个数 x,yx,yx,y，每次可以对 xxx 进行操作：选定 xxx 的一个数码，令 x←x+bx\leftarrow x+bx←x+b 或 x←x−bx\leftarrow x-bx←x−b。求 xxx 变成 yyy 的最小操作次数。强制在线。 数据范围：1≤q≤3×105,0≤x,y≤3×1051\leq q\l

Kruskal重构树 考虑这样一个问题：给定一个 nnn 个点 mmm 条边的带权无向图。多次询问 uuu 到 vvv 的路径中，边权的最小值最大的路径。 我们仿照Kruskal算法，将边权从大到小排序，依次加入。如果两端点已经连通，那么这条边没有意义（因为它的权值更小）。最终，至多只有 n−1n-1n−1 条边有意义，得到了一棵生成树或生成森林。 Kruskal重构树利用点权信息表示边权信息。具

A Link with Checksum 题意 定义一种 CRC−LINKCRC-LINKCRC−LINK 校验方式。给定 headerheaderheader 长度为 n1n_1n1​ 个字节，footerfooterfooter 长度为 n2n_2n2​ 个字节，要求构造一个长度为 444 个字节的 checksumchecksumchecksum，使得 header,checksum,f

Manacher 算法 简介 Manacher 算法可以 O(n)O(n)O(n) 求解字符串每个位置的回文半径。 回文半径指的是从回文中心到回文串一端的字符个数。比如 abcba 的回文半径为 333，abba 的回文半径为 222。上面两个例子对应了奇回文和偶回文的情况（即回文中心落在某个字符上和回文中心落在两个字符之间）。 过程 下面介绍处理奇回文的过程，偶回文基本类似，字符串下标从 000

A Almost Correct 题意 给定一个 010101 串 sss，长度为 nnn。要求构造一个长度不超过 120120120 的排序网络，使得该网络恰好能排序除给定串以外的所有长度为 nnn 的 010101 串。保证 sss 是未排序的。 其中，排序网络指的是数组 {(x1,y1),(x2,y2),⋯ ,(xm,ym)}\{(x_1,y_1),(x_2,y_2),\cdots,(x_

https://atcoder.jp/contests/abc315 F - Shortcuts 题意 有一场比赛，nnn 个点标。参赛者需要按序通过这些点标，但可以选择跳过这些点标。点标 111 和点标 nnn 不能被跳过，此外，若跳过了 ccc 个点标，则需要增加 2c−12^{c-1}2c−1 罚时（c>0c>0c>0）。参赛者的比赛用时为行走路径距离加上罚时，求最小用时。

https://codeforces.com/contest/1860 D. Balanced String 题意 给定一个 010101 串 sss。每次操作可以交换两个元素，求最小操作次数，使得 sss 中 010101 子序列个数和 101010 子序列个数相等。保证可以通过操作使得 sss 合法。 数据范围：3≤∣s∣≤1003\leq |s|\leq 1003≤∣s∣≤100。 题解 一