「作业」

目录

目前：50/150。

在做了在做了。

2020/10/19：五十道。感觉写了一大车模拟题。

（有 * 标记的并非独立思考出来的，即参考了题解或与国集大佬讨论过后得到的思路）

A(2014 ACM-ICPC World Finals)

K - Surveillance：将环变成两倍长度序列，去掉被包含的区间（为了方便，显式地去掉更好）。则选定一个区间，最优的下一个区间是固定的，于是可以倍增求以每个区间为第一个区间的最小覆盖代价。

B(2015 ACM-ICPC World Finals)

H - Qanat：可以发现两个井相邻之间存在分段点，左边走左井，右边走右井。差分距离 (d_i = x_{i+1}-x_i)，则有 (sum d = w)，且代价是关于 ({d_i}) 的二次函数。考虑拉格朗日算子法，变成线性方程组，发现有点规律，于是就过了。感觉应该有更高妙的做法（找规律找得我快吐了）。

J - Tile Cutting：(f_k = sum_{a+b=k} sigma(a) imes sigma(b))，直接 ntt 可过。

L - Weather Report：哈夫曼树，把初始权值相同的放在一起。

C(2016 ACM-ICPC World Finals)

A - Balanced Diet：可以发现约束是线性规划形式（变量 (x_{i,j}) 表示第 (i) 天是否吃第 (j) 颗糖），因此转化成最大流，贪心模拟增广。如果从左往右进行了 (sum a_i) 次增广仍然有解，则之后也一定有解（注意原序列长度 (>sum a_i) 仍然可能无解）。

B - Branch Assignment：先最短路。可以贪心地让同一个组里的值域连续（一定不劣），所以变成排序后区间划分。之后就决策单调性（类似于 CF321E/bzoj5311）。好像不用带权二分直接 (O(bslog b)) 的决策单调性也可以过。

D - Clock Breaking：对着题意模拟。

K* - String Theory：首先正确理解题意 发现 “k引用” 里面恰好包含 1 个 “(k-1)引用” 最优，枚举模拟即可。注意特判 “1引用”。

D(2017 ACM-ICPC World Finals)

D - Money for Nothing：决策单调性，注意决策区间有范围，用单调栈二分要好写点（之前做过）。

G - Replicate Replicate Rfplicbte：如果没有 bug，则上一个状态的左右上下边界一定是当前状态的边界往内缩 1 单位，那么总可以从左上到右下推回上一个状态，且是唯一的。如果有 bug，只需要分别找到第一个不合法的行、列，将对应的元素修改，然后再 check 一遍即可。

E(2018 ACM-ICPC World Finals)

D* - Gem Island：简单算算可知所有情况可能性相等（目前不知道组合意义是啥）。那么可设 (f_{i,j}) 表示把 (j) 颗宝石分给 (i) 个人，前 (min(r,i)) 大之和的期望。转移类似于整数拆分，枚举多少人有宝石，因为可能性相等所以概率用组合数算（目前也不知道 double 的精度为啥能过）。

G(2017-2018 ACM-ICPC Northern Eurasia (Northeastern European Regional) Contest (NEERC 17))

G - The Great Wall：二分 + 平衡树/离散化后树状数组。

J* - Journey from Petersburg to Moscow：考虑让不合法的路径变得不优。边数 (<k) 的路径直接跑最短路。对于边数 (geq k) 的路径，考虑枚举下界 (p)，只对权值 (geq p) 的边计算费用。此时可以将 (geq p) 的边权减去 (p)，求出最短路后加上 (k imes p)。

H(2016-2017 ACM-ICPC Northeastern European Regional Contest (NEERC 16))

B - Binary Code：trie 优化 2-sat 建图（之前写过，不过不知道为啥在某 oj 上过不了）。

K - Kids Designing Kids：去掉周围的空格。如果矩形 1 第 1 列没有和矩形 2 的第 1 列重合相消，那么矩形 1 第 1 列一定等于矩阵 3 的第 1 列。同理可得共 4 种情况，还有 1 种情况即矩阵 1, 2 的第 1 列第 1 行重合。模拟即可（我自己写的模拟方法是存所有 * 的坐标，好像比别人的长一倍，不知道另有什么高妙的方法），注意矩形 3 可以全空。

L - List of Primes：不难猜到当字符数量 (leq 10^{18}) 时素数之和并不大，打表可以验证素数之和最大是 2100 ~ 2200。先找到 ([l, r]) 之中的第一个方案，然后不断地寻找下一个方案。背包预处理 (f_{i,j}) 表示使用 (geq i) 的素数凑出和为 (j) 的方案数，然后逐位贪心即可。

I(2015-2016 ACM-ICPC Northeastern European Regional Contest (NEERC 15))

K - King's Inspection：如果出边唯一，则哈密顿回路必然包含这条出边。暴力枚举出边不唯一的，用并查集判是否形成哈密顿回路。

J(2014-2015 ACM-ICPC Northeastern European Regional Contest (NEERC 14))

E - Epic Win!：如果已知对手的当前状态，则可以构造一个 (O(n)) 的 ( ho) 形图，使得之后一直赢。如果对于两个点构造出的 ( ho) 形图同构，则认为这两个点等价。尝试用有限步区分所有等价点，如果当前对手可能的状态集合存在某些状态输出不一样，则自己的自动机随便输出即可区分；否则，输出能够赢对手的（即 ( ho) 的第一步）。如果连续 (n) 次都无法区分，则它们等价。

K(2013-2014 ACM-ICPC Northeastern European Regional Contest (NEERC 13))

A - ASCII Puzzle：想题五秒钟，读题半小时。本质就是正常的拼图，题目所给的限制其实保证了你可以区分拼图是否在边界上，这样搜索量在 (n = 4) 时也最大只有 (2^4 imes 4!)。为了代码简单我删去了一些剪枝（结果一开始还 TLE 了）。

C - Cactus Automorphisms：建圆方树，找重心（一定没有对称边）。对于方点，如果不是重心，则只有两种同构方式（分别为正着摆放儿子、倒着摆放儿子），因为有顺序所以做两个字符串 hash，取较小值；如果是重心，则可以翻转儿子序列 + 旋转儿子序列，找到所有可能的字符串 hash 判一判。对于圆点，类似于树同构计数（草，我怎么把 “将 (x) 的方案数摊到 (x) 的质因子上” 这一步写错了）。

G - Green Energy：如果塔落在地形产生的阴影里，则可以将其挪到产生阴影的最高点，一定不劣。考虑以阳光方向为 (x) 轴建正交系，则塔的覆盖范围转化为 (y) 轴上的动线段，地形转化为塔对应线段的左端点范围区间。可以贪心地把高塔的左端点往右放，矮塔的左端点往左放。

H - Hack Protection：固定右端点，往前 and 只有 (O(log A)) 种取值。求异或前缀和，对于每种取值在动态开点线段树上查询区间和即可。

I - Interactive Interception：一共有 ((v+1) imes (p + 1)) 个决策点，每次尝试找到使得决策集合尽量均分的询问。为了方便，将询问的左端点设为最左边的点，这样子所有决策点可以分成 (O(v)) 个区间，然后枚举一下右端点在哪里即可。

K - Kabaleo Lite：枚举你的对手们想要最大化的，则 (n) 个堆可以分成 3 类：你想要最大化；你对手想要最大化的；其他的。再枚举你选择这 3 类中的哪一类，判断是否合法。细节较多（比如最后一个人的颜色必须存在于场上）。

L(2017-2018 ACM-ICPC, Central Europe Regional Contest (CERC 17))

C - Cumulative Code：对 (m) 的大小分类。(m) 较小的暴力查；(m) 较大的公差一定小，做个 dp。总时间复杂度 (O(2^{k/2} imes q imes log A))，听说可以少个 (O(log A))，但我不会。

D - Donut Drone：倍增不方便维护，考虑找循环节。平衡 “每次询问暴力找循环节” 与 “每次维护出修改后所有位置的循环节” 的时间，考虑维护第一列跳 c 步（一定又回到第一列）到哪一行，单次询问利用维护的信息可以做到 (O(R+C))。
修改看作改点的 next，此时对于某一列影响到的点一定是连续的，所以可以 (O(R+C)) 维护第一列哪些行的信息变化。
总时间复杂度 (O(MR+MC))（WA 的原因：直接修改第一列的 next 时出问题）。

E - Embedding Enumeration：以 1 为根时每个点最多 2 个儿子。记 (f_{i,j}) 表示以 (i) 为根的子树中，(i) 所在的行比另一行少 (j) 个连续的空格（其实应该配张图，但是我懒.jpg）。分情况讨论 (f) 的转移，发现大多数时候用到的是 (f_{i,0})，只有一条链时才会用到其他的。于是把一条链的单独拿出来做 dp，求出所有的 (f_{i,0}) 即可。时间复杂度均摊下来是 (O(n)) 的。

I - Intrinsic Interval：从左往右扫描并单调栈 + 线段树维护 (f_l =(max-min)-(r-l)) 是否为 0，如果是则 ([l, r]) 为连续段。由于 (f_lgeq 0)，所以等价于维护 (f) 的最小值。一种方法是离线，利用连续段的交仍是连续段的性质，可以先找到最小可能的右端点，再找最大合法左端点。

也可以增量法建析合树求 lca（以下没实现过，不清楚口胡得对不对）。

考虑维护当前析合树森林的根构成的栈，如果当前点能成为栈顶的儿子（此时栈顶一定是合点，记得还要判是否单调）就接上去。

否则先用 (f) 判断是否可以往前合并成更大的连续段，如果不行直接停止；如果可以，不断弹出栈顶直到成为连续段，新建点并向这些元素连边。如果新点只有两个儿子则为合点，否则为析点。

每次更新当前点并重复上述操作。

K - Kitchen Knobs：因为 7 是质数，如果数位不全相同，则最优方案唯一。求出转动次数并差分，问题转化为每次可以选择两个一加一减，或者选择一个加，全部变 0 的最少操作。可以转化为选出尽量多不交集合，满足每个集合内 (sum xmod 7 =0)。注意到贪心地选出 ({x,7-x}) 作为集合总是不劣的，因此 1 和 6、2 和 5、3 和 4 之间可以分别贪心地删去一种，最后只剩最多 3 种数，dp 即可。

L - Lunar Landscape：注意到坐标范围比较小，搞点类似于斜着二维差分的东西即可 (O(A^2+N)) 的时间内求出每个单位格的贡献。

M(2016-2017 ACM-ICPC, Central Europe Regional Contest (CERC 16))

B - Bipartite Blanket：hall 定理 + two points。

J - Jazz Journey：把所有点对分开处理，类似括号匹配的贪心。

N(2015-2016 ACM-ICPC, Central Europe Regional Contest (CERC 15))

C - Cow Confinement：考虑把牛到花的路径唯一化，即先尽量往右走，再尽量往下走。这样做的好处是，如果从右往左做扫描线，大多数路径都不会变化。维护时首先把新加入的矩形竖边界所在行清零，然后维护新加入的花的影响。如果矩形竖边是左边界，则矩形左下角还会对矩形下边界往上的点产生贡献，但是这样会算重，还要减去矩形右下角还会对矩形上边界往上的点的贡献（注意线段树的范围要开大点，否则会访问到非法位置）。

I - Ice Igloos：暴力找到所有可能的圆心。不知道为啥本机过了交上去过不了了，改成 long long 才过。

O(2014-2015 ACM-ICPC, Central Europe Regional Contest (CERC 14))

G - Virus synthesis：建出 PAM，对所有偶回文子串 dp。转移两种：一种从长度 ≤ len / 2 的偶回文后缀转移，倍增找即可；一种不是从后缀转移，则可以把两端去掉，因此就是 PAM 的父亲转移过来。不知道能不能线性。

L* - Outer space invaders：区间 dp，枚举最大的攻击在哪个时刻，它的贡献一定是 (max{d_i},[a_i,b_i]sub [l,r])。

P(2013-2014 ACM ICPC Central European Regional Contest (CERC 13))

A - Rubik's Rectangle：把相互可达的 4 个格子（特判 n, m 为奇数的情况）一起处理，有 4 种翻转会影响它们，它们都会改变这 4 个格子之间的逆序对奇偶性。因此可以决定行列翻转次数的奇偶性，如果奇偶性合法则一定有解。输出方案有点麻烦。

H - Chain & Co.：把矩形按法向量方向分为三类，则每一类必须分到一起。于是只需要判某两类是否相容，这个随便模拟一下就好了。

E - Escape：转化成 “先损失 (a) 再收益 (b)” 的形式，将终点收益设为 (+infin)，做树上贪心（即每次取出最优的点与父亲合并）判断最后是否需要先损失才能遍历完树上所有点（p.s.：延迟删除的堆一定要写严格偏序）。

Q(2017-2018 ACM-ICPC, NEERC, Northern Subregional Contest)

C - Consonant Fencity：枚举。

E - Equal Numbers：将数分为两类，一类是有倍数的，一类是没有倍数的极大值。两种情况：要么只动有倍数的，把这些数改成极大值；要么全部都可以动，把这些数改成所有数的 lcm，这种情况需要多操作一次。把这些数的出现次数从小到大排序然后贪心取即可。

F - Fygon 2.0：依大小关系建图，缩强连通，则 (k) 即 DAG 点数，而 (C=frac{cnt}{k!})（其中 (cnt) 是合法拓扑序数量，状压即可）。

R(2016-2017 ACM-ICPC, NEERC, Northern Subregional Contest)

B - Boys and Girls：特判全为 B/G 的情况。设 cntB = cntG = cnt 表示极大连续的 B/G 段数，设 sumB, sumG 表示 B/G 的总个数，设 oneB, oneG 表示单独一个 B/G 成段的数量。列方程，发现可以先解出 sumB, sumG。于是枚举 cnt，求出 oneB, oneG 的范围判断是否有解。构造根据以上信息随便怎么构造即可。

G - Gangsters in Central City：维护根的每棵子树内的所有点的 lca。

I - Integral Polygons：等价于求叉积之和为偶数的方案数。求一下叉积的前缀和，线性扫描 + 随便维护一下（不清楚为什么在 OJ 上过不了）。

S(2015-2016 ACM-ICPC, NEERC, Northern Subregional Contest)

D - Distribution in Metagonia：只需要让构造出来的 3 的幂次严格递减即可。

G - Graph：比较 trivial 的贪心。找到当前所有入度为 0 的点，从小到大依次加 “入边”（先不去确定入边对应的点），比较最大的入度为 0 与现在需要加 “入边” 的最大点，如果是入度为 0 的点大则直接加入拓扑序，否则拓扑序上一个点向需要加 “入边” 的最大点连边。

T(2014-2015 ACM-ICPC, NEERC, Northern Subregional Contest)

F - Fragmentation：离散化，缩相同连续段。则 (a_{i}) 与 (a_{i+1}) 之间不切断的充分条件为 (a_{i+1}=a_i+1)，且每对相邻权值 ((k, k + 1)) 在原序列中只能对应不切断一个地方。如果 ((k-1,k),(k,k+1)) 在原序列中不切断的地方相邻，则 (k) 的出现次数必为 1。因此出现次数为 1 的权值之间可能会有约束（选 (a) 不能选 (b)）。构造方案时从左往右，先处理出现次数为 1 的权值，具体看代码（你马的，少一行 break 调 1h）。

K - Kebab House：预处理出 (f_{i,j}) 表示 (i) 个位置塞 (leq j) 个白日梦，要求最后一个必须塞的方案数，这部分 (O(q^3))。对于 (n) 个段，定义 (g_{i,j}) 表示到第 (i) 道菜，还要过 (j) 时刻才能继续做梦。枚举第 (i) 道菜最后一个白日梦，利用 (f) 转移，这部分 (O(nqt))。注意第 (i) 道菜可以不做梦。

U(2013-2014 ACM-ICPC, NEERC, Northern Subregional Contest)

L - Lonely Mountain：有解当且仅当两平面最高高度相同。可以把贡献拆解成若干对三棱柱的交，手推一下 + 排序扫描即可。

J - J：把所有量存成 (f(X)=sum_{ileq 10} a_i X^i) 的形式，预处理 (s_i = sum_{j=1}^{N} X_j^i)，然后模拟。

【推广】 免费学中医，健康全家人
原文地址：https://www.cnblogs.com/Tiw-Air-OAO/p/13802431.html