01Trie
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121struct Node { std::array<Node*, 2> next{}; int icnt = 0;};void insert(Node*& p, int val, int bit = 30) { if (!p) { p = new Node(); } p->icnt++; if (bit == -1) return; ...
1248
...
构造最优解
构造最优解 2196D 给定一个有两种类型的括号，长度为偶数的字符串。最少需要修改多少字符，才能让所有圆括号组成的子序列构成 RBS，且所有方括号组成的子序列构成 RBS？ 假设已经确定最终序列的匹配方式，那么一对位置的操作次数只可能是 0、1 或 2。 用栈进行同种括号匹配，代价为 0。 只有当一对括号两边都朝外时才会产生代价 2，考虑充要条件。考虑先将所有左括号两两匹配，然后将所有右括号两两匹配，这样操作的代价都为 1。此时若所有括号都匹配完成，那说明构造出了最优解。否则，一定会剩下左右括号各一个。如果初始所有左括号都在右括号之后，那么这种情况无可避免，最后配对时会产生代价 2。否则，一定可以通过调整配对方式使得剩下的左括号在右括号之前，所以最后将它俩合并有只会花代价 1，达成最优解。 因此，如果序列满足前缀为右括号，后缀为左括号，且两边数量都为奇数时，会产生一个代价 2 的配对。否则，不会产生。 1526D 给定一个仅包含 4 种字符的字符串 AAA。构造一个字符串 BBB，使得 BBB 是 AAA 的一个排列，且最大化通过交换相邻字符将 BBB 变为...
RBS
生成方式有两种：连接和加括号 前缀和保持非负 对应一棵孩子有顺序的树 CF2233C. Cost of a Bracket Sequence 给定 RBS SSS 和整数 KKK，删除最多 KKK 个字符，使得到的字符串的最长 RBS 子序列最短。给出方案。 先做一遍括号匹配，最后希望剩下 )))((，右括号与左括号有个分界点。重点是绝对不存在一对匹配的括号，左括号在左半区，右在右半区，所以所有匹配的括号对要么全在左半，要么全在右半。左半的括号对删左，右半删右。如此最优。 CF2210D. A Simple RBS Problem 对于 RBS SSS，任意次操作，选择两个不交的 RBS 子串，并交换位置。判断最终是否可以变换为 TTT。
DP
ABC435G. Domino Arrangement 有 NNN 个格子，最初都没有被涂色。 有 MMM 种颜色，第 iii 种颜色可以用来涂区间 [Li,Ri][L_i,R_i][Li,Ri] 中的任意多个格子，每种颜色的极长连续段长度恰好为 2，但可以有多个不相连的连续段。 求涂色方案。 N,M⩽5×105N,M \leqslant 5 \times 10^{5}N,M⩽5×105 状态：前 iii 个格子已涂色的子问题， fj,1/2f_{j, 1/2}fj,1/2：最后一个格子涂了颜色 jjj，且当前颜色 jjj 的连续段长度为 1/21/21/2 的方案数。 ggg：最后一个格子不涂任何颜色的方案数。 此外用扫描线维护 cjc_{j}cj：最后一个格子为颜色 jjj 是否合法，即是否满足 Lj≤i≤RjL_j \le i \le R_jLj≤i≤Rj。 转移： fj,2←fj,1f_{j, 2} \leftarrow f_{j, 1}fj,2←fj,1 fj,1←−fj,2+g+∑fj,2f_{j, 1} \leftarrow...
构造
CF2048E 二分图，左部 2N2N2N 个点，右部 MMM 个点。能否用至多 NNN 种颜色为 2MN2MN2MN 条边着色，满足图中没有单色环。 每种颜色构成一个森林，边数最多 2N+M−12N+M-12N+M−1。 Problem - 2094F - Codeforces（shift） Problem - 2101A - Codeforces（蛇形） 【12E】构造 N×NN\times NN×N 的矩阵（NNN 为偶数），只能使用 NNN 种不同的数字，且满足任一行（列）的数字互不相同，主对角线都是 0，且整体关于主对角线对称。 Trulicina gives you integers nnn, mmm, and kkk. It is guaranteed that k≥2k\geq 2k≥2 and n⋅m≡0(modk)n\cdot m\equiv 0 \pmod{k}n⋅m≡0(modk). Output a nnn by mmm grid of integers such that each of the following criteria...
Easy Ver.
...
Hard Ver.
...
Flow
...
房间
...