C Forest 题意：给定 nnn 个点 mmm 条带权边的无向图，问从中选出若干条边和全部的点构成的 2m2^m2m 张子图中，最小生成森林的边权值和。n≤16n \leq 16n≤16，m≤100m \leq 100m≤100。 解法：首先从小到大的对边进行排序，等边权的按照边编号排序，保证生成森林唯一。 从小到大依次加入每条边考虑贡献。考虑第 iii 条边 (u,v)(u,v)(u,v) 在哪些子图中会加入到生成森林中：u,vu,vu,v 不连通。考虑补集，设比它大的还有 lll 条边，则答案为 fi−1,SgU/S2lf_{i-1,S}g_{U/S}2^lfi−1,S​gU/S​2l...

A Array 题意：给定长度为 nnn 的序列 {an}\{a_n\}{an​}。现构造一个序列 {bm}\{b_m\}{bm​}，令 {c}\{c\}{c} 为 {bm}\{b_m\}{bm​} 序列的无穷拼接，要求 {c}\{c\}{c} 中每连续 aia_iai​ 个数字就得出现一次 iii。要求 {bm}\{b_m\}{bm​} 序列长度 m≤1×106m\leq 1\times 10^6m≤1×106。 解法：设最终长度为 MMM。首先注意到，对于每个数字，最少填放次数为 ⌈Mai⌉\left \lceil \dfrac{M}{a_i}\right \rceil⌈ai​M​⌉，因而...

D Fourier and Theory for the Universe D 题题意：记一个整数 NNN 是好的，当且仅当 N=∏i=1kpiαi\displaystyle N=\prod_{i=1}^k p_i^{\alpha_i}N=i=1∏k​piαi​​ 中 ∑αi\sum \alpha_i∑αi​ 为偶数，且 ∀j∈[1,k]\forall j \in [1,k]∀j∈[1,k]，2αj≤∑αi2\alpha_j \leq \sum \alpha_i2αj​≤∑αi​。求 [1,n][1,n][1,n] 区间中有多少个好整数。n≤1×1011n \leq 1\times 10^{1...

A Don't Starve 题意：给定平面上 nnn 个点，从原点出发直线前往这些点收集食物，收集完再前往下一个点。每当离开一个有食物的点后该点食物刷新，每次移动距离严格下降。问最多收集到多少食物。n≤2×103n \leq 2\times 10^3n≤2×103。 解法：根据距离作为边权构建完全图，按照边权从大到小排序。记 fif_{i}fi​ 为到达 iii 点时收集到的最大食物数量，则当边距离从大到小考虑时，对于边 (u,v)(u,v)(u,v)，其唯一可行转移为 fv←max⁡(fv,fu+1)f_v \leftarrow \max(f_v,f_u +1)fv​←max(fv​,fu...

M Monotone Chain M 题题意：给定平面 nnn 个点 (xi,yi)(x_i,y_i)(xi​,yi​)，找到两个向量 a,b\textbf{a},\textbf{b}a,b 满足 ∀1≤i≤j≤n\forall 1 \leq i \leq j \leq n∀1≤i≤j≤n，(OAi−a)⋅b≤(OAj−a)⋅b(\textbf{OA}_i-\textbf a)\cdot {\textbf{b}} \leq (\textbf{OA}_j-\textbf a)\cdot {\textbf{b}}(OAi​−a)⋅b≤(OAj​−a)⋅b。n≤1×105n \leq 1\times...

J Counting Fish Again J 题题意：在第一象限含坐标轴的无穷大方格纸上，可以画一条斜率为 −1-1−1 的线段 (u1,v1)→(u2,v2)(u_1,v_1) \to (u_2,v_2)(u1​,v1​)→(u2​,v2​)，或者擦除已经有的一条线段，问每次操作后鱼的个数。鱼形状如下： 操作次数 qqq 满足 q≤1×106q \leq 1\times 10^6q≤1×106。 解法：对于每一个截距的直线单独考虑，利用珂朵莉树的方法维护每条直线上的最长连续线段，只需要对每个最长连续线段所对应的鱼进行计数即可。注意到鱼尾和鱼身的连接点可以唯一确定一条鱼，因而对这一连接点进...

D、E Jobs D、E 题题意：有 nnn 家公司，第 iii 家公司有 mim_imi​ 个工作，对能力要求为 (aj,bj,cj)(a_j,b_j,c_j)(aj​,bj​,cj​)，其中 1≤aj,bj,cj≤4001 \leq a_j,b_j,c_j \leq 4001≤aj​,bj​,cj​≤400。若候选者能力值为 (x,y,z)(x,y,z)(x,y,z) 满足有一个工作符合 x≥aj,y≥bj,z≥cjx \geq a_j,y \geq b_j,z \geq c_jx≥aj​,y≥bj​,z≥cj​，则认为该候选者可以被该公司录用。qqq 次询问，每次给定一个候选者的能力值，...

B 2D Internet Angel B 题题意：给定内外同心圆，半径分别为 R1,R2R_1,R_2R1​,R2​，沿内侧圆外有一 nnn 边外接多边形 {Pi}\{P_i\}{Pi​}，与内侧圆的切点为 {Qi}\{Q_i\}{Qi​}，保证这一多边形完全在外侧圆内。记此外接多边形外与外侧圆内侧部分的点到多边形和内侧圆切点的最近距离为 XXX，求 E(X2)E(X^2)E(X2)。n≤1×105n \leq 1\times 10^5n≤1×105。 解法：过凸包顶点 Pi(xi,yi)P_i(x_i,y_i)Pi​(xi​,yi​) 和 Pi+1(xi+1,yi+1)P_{i+1}(x_...

A Task Computing 题意：给定长度为 nnn 的序列 {(wi,pi)}\{(w_i,p_i)\}{(wi​,pi​)}，从中选出 mmm 项并重新排列得到子序列 {a1,a2,⋯ ,am}\{a_1,a_2,\cdots,a_m\}{a1​,a2​,⋯,am​}，最大化 ∑i=1mwai∏j=1ipaj\displaystyle \sum_{i=1}^m w_{a_i} \prod_{j=1}^i p_{a_j}i=1∑m​wai​​j=1∏i​paj​​。n≤1×105n \leq 1\times 10^5n≤1×105，m≤20m \leq 20m≤20，pi∈[0.8,1...

C Easy Counting Problem C 题题意：给定字符集大小 Σ\SigmaΣ，和每个字符出现次数的下限 {ci}\{c_i\}{ci​}，qqq 次询问由 Σ\SigmaΣ 中字符构成的长度为 nnn 的字符串的个数。q≤300q \leq 300q≤300，n≤1×107n \leq 1\times 10^7n≤1×107，∑ci≤5×104\sum c_i \leq 5\times 10^4∑ci​≤5×104，∣Σ∣≤10|\Sigma| \leq 10∣Σ∣≤10。 解法：对于 ∑ci\sum c_i∑ci​ 较小的约束条件，可以考虑使用生成函数。本题中由于有次数限制并...

F NIO with String Game F 题题意：给定 nnn 个串 {Tn}\{T_n\}{Tn​} 和一个串 SSS，有以下四种操作： 给 TxT_xTx​ 的末尾增加一个字符； 给 SSS 串末尾删除 ppp 个字符； 给 SSS 串末尾插入 kkk 个字符； 查询 {Tn}\{T_n\}{Tn​} 中有多少个字符串字典序严格小于 SSS。 qqq 次操作，n,q≤5×105n,q \leq 5\times 10^5n,q≤5×105，字符串总长小于等于 2×1052\times 10^52×105。 解法：根据 {Tn}\{T_n\}{Tn​} 离线建立 Trie，加入最终...

E Falfa with Substring E 题题意：给定长度 nnn，问长度为 nnn 的纯小写字母串中出现 kkk 次 bit的字符串个数，需要对 k∈[0,n]k \in [0,n]k∈[0,n] 输出答案。n≤1×106n\leq 1\times 10^6n≤1×106。 解法：对于恰好类问题，通常将其转化为至少或至多。 若至少出现 kkk 次 bit，因为这个字符串不会重叠出现，因而可以将其绑定成一个特殊字符，等效于在 n−2kn-2kn−2k 个位置中选择 kkk 个位置填放 bit，剩余位置任选。因而至少 kkk 次出现的方案数为 Fk=(n−2kk)26n−3k\displ...

I let fat tension I 题题意：给定 nnn 个 kkk 维向量 {Xi}\{X_i\}{Xi​}，和 nnn 个 ddd 维向量 {Yi}\{Y_i\}{Yi​}，求 Yj′=∑i=1nXi⋅Xj∣Xi∣∣Xj∣Yi\displaystyle Y'_j=\sum_{i=1}^n \dfrac{X_i\cdot X_j}{|X_i||X_j|} Y_iYj′​=i=1∑n​∣Xi​∣∣Xj​∣Xi​⋅Xj​​Yi​。n≤1×104n \leq 1\times 10^4n≤1×104，k,d≤50k,d \leq 50k,d≤50。 解法： [Y1′Y2′Y3′⋮Yn′]=[X1...

C Link with Nim Game C 题题意：给定 nnn 堆石子 {an}\{a_n\}{an​} 玩 Nim 游戏，若该玩家必输则会尽量拖延时间，否则就会速战速决。问游戏会进行多少轮，并求出先手第一步的方案数。n≤2×105n \leq 2\times 10^5n≤2×105。 解法：判定输赢根据异或和是否为零。记 ⊕ai=w\oplus a_i=w⊕ai​=w。 若先手必胜，则先手必然尽量取石子，使得剩余异或和为 000。对于第 iii 堆石子，先手必然需要拿走 ai⊕(ai−w)a_i \oplus (a_i-w)ai​⊕(ai​−w) 个石子，才能使得异或和为 000。因而先...