[WC2018] 州区划分
题目链接： [WC2018] 州区划分 。
题目描述：
小 S 现在拥有 nnn 座城市，第 iii 座城市的人口为 wiw_iwi，城市与城市之间可能有双向道路相连。
现在小 S 要将这 nnn 座城市划分成若干个州，每个州由至少一个城市组成，每个城市在恰好一个州内。
假设小 S 将这些城市划分成了 kkk 个州，设 ViV_iVi 是第 iii 个州包含的所有城市组成的集合。定义一条道路是一个州的内部道路，当且仅当这条道路的两个端点城市都在这个州内。如果一个州内部存在一条起点终点相同，不经过任何不属于这个州的城市，且经过这个州的所有内部道路都恰好一次并且经过这个州的所有城市至少一次的路径（路径长度可以为 000），则称这个州是不合法的。
定义第 iii 个州的满意度为：第 iii 个州的人口在前 iii 个州的人口中所占比例的 ppp 次幂，即：
(∑x∈Viwx∑j=1i∑x∈Vjwx)p\left(\dfrac{\sum _ {x \in V _ i} w _ x}{\sum _ {j = 1} ^ i \sum _ {x \in V _ j ...
Palindrome Bo
有圣贤名曰 Sam ，曾云“ Really difficult. ”。
题目链接： HDU 2016 多校 。
题目描述：
定义一个子序列合法当且仅当：
子序列为回文子序列。
子序列为单谷子序列。
给定长度 n≤5000n\le 5000n≤5000 的序列 a(1≤ai≤n)a(1\le a_i\le n)a(1≤ai≤n) ，求其最长合法子序列长度以及本质不同的最长合法子序列个数。
我们先看第一问。可以发现，一个合法的子序列，结构必然是一个类似于“洋葱”的结构，即 ABCDEFGFEDCBA 这样的结构。
所以我们不妨考虑定义 fi,jf_{i,j}fi,j 表示当这个“洋葱”最外层为 iii 和 jjj （其中 ai=aja_i=a_jai=aj ）时的最大合法子序列长度。那么此时就有一个的显然的转移：枚举 i<x≤y<ji<x \le y<ji<x≤y<j 且 ax=aya_x=a_yax=ay ，则 fi,j=max{fx,y+2}f_{i,j}=\max\{f_{x,y}+2\}fi,j ...
Colorful Tree
题目链接： HDU 2017 Colorful Tree 。
题目描述：
有 nnn 个点的树，每个点有一个颜色 aia_iai ，求所有 (u,v)(u,v)(u,v) 满足 1≤u<v≤n1\le u<v\le n1≤u<v≤n 的点对的路径上的不同颜色的和。
n≤2×105,1≤ai≤nn\le 2\times10^5,1\le a_i\le nn≤2×105,1≤ai≤n 。
考虑对于枚举每一个颜色并计算它带来的贡献。对于枚举的颜色 ccc ，我们应该视所有 ai=ca_i=cai=c 的 iii 为关键点，那么这个颜色 ccc 的贡献就是所有经过了关键点的路径。
这个并不好算，我们考虑把它容斥为不经过任意一个关键点的路径。
此时问题就明了了：将所有的关键点去掉后的连通块的大小的平方和。
由于有关键点，我们对所有的关键点建立虚树。为了方便强行钦定 000 为根，连边 (0,1)(0,1)(0,1) ，并设 000 为关键点。
接下来就我们不妨自下而上考虑：对于一个关键点 uuu ，遍历它在原树上的儿子 vvv ，并计算 ...
[CSP-S 2026 初赛] 标准答案
神秘技巧。
题目链接： 标准答案 。
题目描述：
给定 nnn 名学生参加一场考试，考试共有 mmm 道选择题，每道题只有 A、B 两个选项。
第 iii 名学生的作答为一个长度为 mmm 的字符串。若最终公布的标准答案与该学生在某道题上的作答相同，则该学生在这道题上得 1 分，否则不得分。记第 iii 名学生最终得到的总分为 rir_iri。
每名学生还有一个预期得分 xix_ixi。现在需要构造一份标准答案，使
∑i=1n∣ri−xi∣\sum_{i=1}^{n}|r_i-x_i|
i=1∑n∣ri−xi∣
尽可能大。
n≤18,m≤300n\le 18,m\le 300n≤18,m≤300 。
考虑拆开绝对值，钦定集合 SSS ，则转化为最大化 ∑i∈S(xi−ri)+∑i∉S(ri−xi)\sum\limits_{i\in S}(x_i-r_i)+\sum\limits_{i\notin S}(r_i-x_i)i∈S∑(xi−ri)+i∈/S∑(ri−xi) 。由于绝对值的定义，必然存在一个 SSS 使得 S ...
[ICPC 2018 Jiaozuo R] Can You Solve the Harder Problem?
简单题。
题目链接： [ICPC 2018 Jiaozuo R] Can You Solve the Harder Problem? 。
题目描述：
给定序列，求所有子串去重后（这里指去掉重复的子串）的权值和。一个子串的权值定义为其内部最大值。
要求 O(nlogn)\mathcal{O}(n\log n)O(nlogn) 的做法。
由于子串 + 去重，考虑 SAM ，这样就可以考虑到所有的子串并去重了。
接下来只需要遍历 SAM 的每一个节点，然后去计算这个点所对应的所有子串的最大值之和。可以发现，一个 SAM 的节点对应的所有子串的右端点一样，所以我们可以做一个类似于历史和求子区间和的东西，从前往后扫描就行。
代码：
12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667 ...
Sweet Sugar
题目链接： Sweet Sugar 。
题目描述：
一颗 nnn 个点的树，每个点有点权 aia_iai ，求将树划分为若干个连通子图后点权和为 kkk 的子图的个数的最大值。
ai∈{0,1,2},n,k≤106a_i\in\{0,1,2\},n,k\le 10^6ai∈{0,1,2},n,k≤106 。
606060 分是显然的树形 DP 。
考虑最终的最优解的结构是什么。我们发现，当一个子树可以凑成长度为 kkk 的子图时，我们必然应该把它划分为一个连通子图。这是它为上级贡献是没有意义的。
所以我们可以得出如下伪代码：
12345678DFS(x):something <- 0for u in son[x]: DFS(u) ADD(x,u)if(Can_Get_K(x)) ans++ DELETE(x)
重点就在如何判断一个子树是否能拼成一个 kkk 的连通子图。
由于点权只有 0,1,20,1,20,1,2 ，所以考虑奇偶性相关。经过观察，我们发现如下性质：
如果一个子树满足它内部所有子树都不能拼出 kkk ，且其可以拼出 ≥k ...
[NOI2023] 字符串
题目链接： [NOI2023] 字符串 。
题目描述：
小 Y 了解到关于字符串的如下定义:
给定一个长度为 nnn 的字符串 s[1:n]s[1: n]s[1:n]，我们定义其子串 s[l:r]s[l: r]s[l:r]（1≤l≤r≤n1 \leq l \leq r \leq n1≤l≤r≤n）为选择 s[l],s[l+1],…,s[r]s[l], s[l+1], \dots, s[r]s[l],s[l+1],…,s[r], 将其顺次拼接得到的新字符串。
给定一个长度为 nnn 的字符串 s[1:n]s[1: n]s[1:n]，我们定义其翻转后的结果 R(s)R(s)R(s) 为将 s[n],s[n−1],…,s[1]s[n], s[n-1], \dots, s[1]s[n],s[n−1],…,s[1] 顺次拼接，也就是将字符串反序拼接得到的字符串。
给定两个长度均为 nnn 的字符串 a[1:n],b[1:n]a[1: n], b[1: n]a[1:n],b[1:n]，我们定义 aaa 的字典序小于 bbb 当且仅当存在 1≤i≤n1 \leq i ...
[ICPC 2018 Xuzhou R] Rikka with Subsequences
对于所有的 ∑aik\sum a_i^k∑aik 之类的东西，可以用组合意义转化为 kkk 个人选择，最后的方案数。
例题： [ICPC 2018 Xuzhou R] Rikka with Subsequences ， [NOI2009] 管道取珠 。
[ICPC 2018 Xuzhou R] Rikka with Illuminations
计算几何好难 /kel
题目链接： [ICPC 2018 Xuzhou R] Rikka with Illuminations 。
题目描述：
有 nnn 个点的凸包和 mmm 个光源。求最少多少个光源可以覆盖凸包的所有边。要求构造方案。
n,m≤103n,m\le 10^3n,m≤103 。
首先要做一步转化。注意到图形是凸包，所以每一个光源覆盖的区域实际上是一个凸包的边的连续区间。
所以问题变为：
如何计算每一个光源的覆盖区间。
环形最小区间覆盖问题。
Part I.
考虑计算一个边被一个光源覆盖的充要条件。
经过手动模拟和注意力后我们得出结论：当凸包的点逆时针排序后，一个边向量 AAA 被光源 ppp 照亮当且仅当 ppp 在 AAA 的右边。
所以就解决了。
注意由于是环，所以我们应该记录起点和长度，而非起点和终点。
像这样：
1234567891011for(int i=0;i<m;i++){ st[i]=len[i]=0; for(int j=0;j&l ...
序列奇偶
题目描述：
有 nnn 个数字，第 iii 个数字 viv_ivi 的范围在 [xi,yi][x_i,y_i][xi,yi] ，有 mmm 个限制，第 iii 个限制要求 (∑i=lrvi) mod 2=s(\sum\limits_{i=l}^r v_i)\bmod 2=s(i=l∑rvi)mod2=s 。
求有多少合法序列以及最小字典序合法序列。
n≤10,m≤40,0≤xi,yi≤109n\le 10,m\le 40,0\le x_i,y_i\le 10^9n≤10,m≤40,0≤xi,yi≤109 。
暴力可以获得 10%10\%10% 的分数。
我们发现 mmm 个条件都与 mod 2\bmod 2mod2 有关，于是我们考虑之前确定每一个数字的奇偶性，并计算每一个数字为偶数的方案数 ai,0a_{i,0}ai,0 ，奇数的方案数 ai,1a_{i,1}ai,1 ，计算公式如下：
ai,1=⌊(yi−xi+1)+(xi mod 2)2⌋ai,0=(yi−xi+1)−ai,1\begin{aligned}
a_{i,1}&=\lfloo ...
