MiQiu

E - Endless Holidays 题意 有 NNN 个城市，MMM 条双向道路。一个星期有 WWW 天。 每个城市都有自己的假期安排。高桥每天可以选择 留在该城市 或者 相邻的城市。 问：高桥能否从第 111 天，找到一种策略，使得他永远在放假。（羡慕了） N≤105,M≤105,W≤10N \leq 10^5, M \leq 10^5, W \leq 10N≤105,M≤105,W≤1

F - Plan Holidays 题意 高桥想安排 NNN 天的假期。最开始都不是假期。操作1：花 AiA_iAi​ 的代价让第 iii 天变成假期。 操作2：如果第 i−1i-1i−1 天和第 i+1i+1i+1 天都是假期，那么可以免费让第 iii 天变成假期。问：要制造一个长度至少为 KKK 的连续假期，最少需要多少代价？ 数据规模满足 N,K≤2×105N,K\le 2\times 1

前记 本次赛时顺利切到 F 题，G 题由于缺乏生成函数的前置知识惨败。有趣的是，这次的题目在背景上都充满了连贯性：A、B 题都和骰子有关，C、D 题都是字符串相邻去重计数，而 E、F、G 题全在讨论如何放假（高桥是有多想放假啊 雾）。 A - Dice 题意 投掷三个骰子，给定一个 x，问三个骰子的点数总和能否为 x。 1≤x≤201 \leq x \leq 201≤x≤20 思路 简单猜想一

Dilworth定理 即：对于任意有限偏序集，其最大反链中的元素数目 等于 最小链划分中链的数目。 前置知识 1. 偏序集 一个集合 SSS 和其上的二元关系 ≤\le≤ 构成一个偏序集 (S,≤)(S, \le)(S,≤)，如果该关系满足以下三个性质： 自反性：∀a∈S,a≤a\forall a \in S, a \le a∀a∈S,a≤a。 反对称性：∀a,b∈S\forall a,

A. New Gomoku 1. 题意 A 和 B 轮流下五子棋，问双方连成五子的数量。 2. 思路 观察到棋盘不大，所以直接对每个新落下的棋子暴力扩展就行，然后累加贡献值，注意多组数据的清空。 3. 代码部分 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515

E. CCPC String 1. 题意 给定一个字符串，含有 C | P | ?，问最多能组成多少个 CCPC，也可以是 CCCCPCC，等。 2. 思路 发现核心限制条件其实是 P 的位置，所以重点在判断两个 P 之间的距离。在字符串前后各加一个 P 作为哨兵，然后二分查询每个不是 C 的前后继 P 即可。总贡献值为 min(left/2,right)min( left / 2, right

Easy 1010 Sort 题意： 给定一个二维数组，每一行选一个值，问能否凑出一个严格递增的序列。 思路： 贪心即可，每一行找到最小的满足条件的值，即可。 1007 Turn Of A Page 题意： 给定一个序列和一个特殊值，问能否对原序列重排后，使得所有位置的某一部分前缀和等于这个特殊值。 思路： 刚开题的时候想了半天，第一个想法是降序排序，然后用滑动窗口维护。WA了之后，重新分析题目，

一、容斥原理引入 Ex.1 P3197 越狱 1. 题面梗概 共有 nnn 个盒子，mmm 个物品，求相邻两个盒子物品相同的情况。 m≤108,n≤1012m \leq 10^8, n \leq 10^{12}m≤108,n≤1012 2. 逻辑推导 由于本题的 n,mn, mn,m 数量级都很大，猜测答案是一个和 n,mn, mn,m 相关的表达式，但是如果直接统计满足条件的情况很困难，此时

一、错排 Ex. 1 P4071 排列计数 1. 题面梗概 求有多少种从 111 到 nnn 的排列 aaa，满足序列中恰好有 mmm 个位置 iii，使得 ai=ia_{i} = iai​=i。 多测 T≤5×105,n,m≤106T \leq 5 \times 10^5, n,m \leq 10^6T≤5×105,n,m≤106 2. 逻辑推导 不妨先来考虑 m=0m = 0m=0 的情况

组合计数 - 常见模型 Ex. 1 P5520 青原樱 1. 题面梗概 有多少种方案在 nnn 个位置种 mmm 株不同的树，使得树两两不相邻。 n≤2×106,m≤106n \leq 2 \times 10^6, m \leq 10^6n≤2×106,m≤106 2. 逻辑推导 对于本题来说，直接对着构造取计数看起来会很困难。因此可以考虑使用一些其他的方法来进行解题。 采用插空的方法，由于需