背包
ABC436G - Linear Inequation 求 ∑i=1NAixi≤M\displaystyle\sum_{i=1}^N A_i x_i \le Mi=1∑NAixi≤M 的非负整数解数量。N≤100N\le100N≤100，Ai≤100A _ i\le100Ai≤100，M≤1018M\le10 ^ {18}M≤1018。 完全背包是多重背包的特化，即每种物品充分多的多重背包。多重背包有经典的二进制优化。具体而言，每个物品 iii 拆分为 logM\log MlogM 个，重量分别为 2mAi2^m A_i2mAi。如此，问题化为 01 背包。 考虑背包压缩：如果我们将 20Ai2^0 A_i20Ai 的物品全部统计了，那么以后将不会有重量为奇数的物品。因此，剩余容量 2k,2k+12k,2k+12k,2k+1 的方案可以合并至 kkk，然后令 MMM 减半。 12345678910111213141516171819const int V = std::ranges::fold_left(A, 0LL,...
未命名
ABC434F - Concat (2nd) NNN strings SiS_iSi. Find the second lexicographically smallest string when concatenating SiS_iSi in any order. Let S1′,S2′,…,SN′S'_1,S'_2,\dots,S'_NS1′,S2′,…,SN′ be the result of sorting in the order defined by X<YX<YX<Y iff XY<YXXY<YXXY<YX. If N=2N=2N=2, then the answer is S2′S1′S'_2S'_1S2′S1′. If there exists an integer 1≤i<N1 \le i < N1≤i<N such that Si′Si+1′=Si+1′Si′S'_i...
连续段插入型 DP
【P5999】求排列 ppp 的数量，满足 pip_ipi 两边的数同时小于或大于 pip_ipi，且 p1=Sp_1=Sp1=S, pN=Tp_N=TpN=T。 f(n,m)f(n,m)f(n,m)：前 nnn 小的值分成 mmm 段的方案数。 从小到大加入每一个数，考虑现在枚举到 nnn，若 n≠Sn \neq Sn=S 且 n≠Tn\neq Tn=T，则可以分三种情况讨论： 新开一段 若 n≠Sn \neq Sn=S 且 n≠Tn\neq Tn=T，以后 nnn 两侧的都比它大，与题意相符，转移 f(n,m)←(m−[n>S]−[n>T])f(n−1,m−1)f(n,m) \gets (m-[n>S]-[n>T]) f(n-1,m-1)f(n,m)←(m−[n>S]−[n>T])f(n−1,m−1)。 若 n=Sn = Sn=S 或 n=Tn = Tn=T，与题意相符，转移 f(n,m)←f(n−1,m−1)f(n,m) \gets f(n-1,m-1)f(n,m)←f(n−1,m−1)。 接在某一段头...
容斥
给定一个 N×NN \times NN×N 的正方形网格和一个整数 KKK。请计算有多少种合法的填数方案，满足所有数字都在 111 到 KKK 之间，且每行、每列的最小值均为 111。 f(i,j)f(i, j)f(i,j)：恰好有 iii 行和 jjj 列满足某种性质的方案数。 g(n,m)g(n, m)g(n,m)：强制选定 nnn 行和 mmm 列，并让它们必须满足该性质，而对其余元素不作任何限制的方案数。 g(n,m)=∑i=nN∑j=mM(in)(jm)f(i,j)f(n,m)=∑i=nN∑j=mM(−1)(i−n)+(j−m)(in)(jm)g(i,j)\begin{aligned} g(n, m) &= \sum_{i=n}^{N} \sum_{j=m}^{M} \binom{i}{n} \binom{j}{m} f(i, j) \\ f(n, m) &= \sum_{i=n}^{N} \sum_{j=m}^{M} (-1)^{(i-n) + (j-m)} \binom{i}{n} \binom{j}{m} g(i,...
Dilworth's Theorem
转化为最长不下降子序列，然后按照那个二分的思路，找到位置不要直接替换，而是存起来，最后每个位置的所有数就是一条链 Dilworth ABC457G - Catch All Apples Find the minimum number of robots needed to collect all apples. Each robot starts operating from time 000 and can move freely at a speed of at most 111. Each robot can collect apple iii if and only if it is at coordinate XiX_iXi at time TiT_iTi. If Ti<TjT_i < T_jTi<Tj, a single robot can collect both apple iii and jjj...
IntervalDP
LPS LPS(S)=LCS(S,reverse(S))\text{LPS}(S) = \text{LCS}(S, \text{reverse}(S))LPS(S)=LCS(S,reverse(S))，转为线性 DP 给定一个长度为 NNN 的字符串，为变成回文串，最少需要插入多少字符？ 给定一个长度为 NNN，有 KKK 种类型的括号的字符串，为变成 RBS，最少需要插入多少字符？（注意区分 K=1K=1K=1 与 K⩾2K \geqslant 2K⩾2） 本质不同的非空回文子序列数量 s[i]≠s[j]s[i] \neq s[j]s[i]=s[j] 时，f[i][j]=f[i+1][j]+f[i][j−1]−f[i+1][j−1]f[i][j] = f[i+1][j] + f[i][j-1] - f[i+1][j-1]f[i][j]=f[i+1][j]+f[i][j−1]−f[i+1][j−1] s[i]=s[j]s[i] = s[j]s[i]=s[j] 时 中间没有字符满足...
单调队列
CF1904D 任意次选择一个子区间 A[l…r]A[l\dots r]A[l…r]，全部替换为子区间的最大值。判断是否可以通过若干次操作将数组 AAA 变为数组 BBB。 对于每一个 B[i]B[i]B[i]，判断能否在 AAA 中 找到一个相等的元素 A[j]A[j]A[j]，且 iii 和 jjj 之间的所有 kkk 都满足 A[k]≤B[i]A[k] \le B[i]A[k]≤B[i]，且 B[k]≥B[i]B[k] \ge B[i]B[k]≥B[i]。 这等价于 A[j]⩾A[k]A[j] \geqslant A[k]A[j]⩾A[k]，且 A[j]⩽B[k]A[j] \leqslant B[k]A[j]⩽B[k]。 因此需要维护一个递减的队列，如果 A[j]<A[k]A[j]<A[k]A[j]<A[k]，则淘汰 A[j]A[j]A[j]。同时，如果 A[j]>B[k]A[j]>B[k]A[j]>B[k]，需要淘汰队头的...
数学期望
CF908D 每次以 PPP 的概率生成字符 0，以 1−P1-P1−P 的概率生成字符 1，并追加到初始为空的字符串末尾。当字符串中子序列 01 的出现次数 ≥K\ge K≥K 时停止生成。求最终字符串中 01 子序列出现次数的数学期望。K⩽1000K \leqslant 1000K⩽1000 f(c,s)f(c, s)f(c,s)：当前字符串中已经有 ccc 个字符 0，并且已经构成了 sss 个 01 子序列时的答案。 f(c,s)=Pf(c+1,s)+(1−P)f(c,s+c)f(c, s) = P f(c+1, s) + (1-P) f(c, s+c)f(c,s)=Pf(c+1,s)+(1−P)f(c,s+c) f(c,s)=s(s≥K)f(c, s) = s \quad (s \ge K)f(c,s)=s(s≥K) f(c,s)=s+c+P1−P(c≥K,s<K)f(c, s) = s + c + \dfrac{P}{1-P} \quad (c \ge K, s < K)f(c,s)=s+c+1−PP(c≥K,s<K) CF235B ...
枚举
数据结构题目基本思想：枚举一个查另一个 1221F. Choose a Square 给定 NNN 个 (Xi,Yi,Ci)(X_i, Y_i, C_{i})(Xi,Yi,Ci)。选取 a,ba,ba,b，最大化 S(a,b)=a−b+∑a≤Xi≤ba≤Yi≤bCiS(a, b) = a - b + \sum_{\substack{a \le X_i \le b \\ a \le Y_i \le b}} C_i S(a,b)=a−b+a≤Xi≤ba≤Yi≤b∑Ci S(a,b)=a−b+∑a⩽min{Xi,Yi}⩽max{Xi,Yi}⩽bCiS(a, b) = a - b + \sum_{a \leqslant \min\lbrace X_i, Y_{i} \rbrace \leqslant \max\lbrace X_i, Y_{i} \rbrace \leqslant b} C_i S(a,b)=a−b+a⩽min{Xi,Yi}⩽max{Xi,Yi}⩽b∑Ci 考虑代换为 S(a,b)=a−b+∑a⩽Li⩽Ri⩽bCiS(a,...