如何【原神启动】 最后更新于 2025-05-01 22:32:01

据一位教练所说，有位高二选手 NOI 前玩了两天原神。 #### 2024.07.18 NOI2024D1T2 - dp 交互题的最小询问次数时，可以**沿操作顺序维护从起始到当前状态的最小代价**，也可以递归到子问题，维护当前子问题所需的次数。 - CF830D #### 2024.07.18 - CF1386A #### 2024.08.10 - 静态询问区间内所有点对的和 / 极值时，可以扫描线，以线段树维护当前点与之前每个点形成的点对答案，询问答案即为区间历史和 / 极值。（https://loj.ac/p/3033） - 区间可递推的问题可以用主席树的区间复制求得。（https://qoj.ac/problem/8240） - 维护区间的映射可以把区间拆成 $\cup[i,i+1]$ 后分别处理。（CF1707E） - P6109 - P8987 - CF1558F #### 2024.08.12 - 带势能的局部调整证明全局一定有解，可得势能最小为可行解。（gym102268J） - （闵可夫斯基和）分治合并。 - 合并类型的树上问题可以重链分治合并。（gym102331J） - 求一个序列进行若干次某操作后得到的最长/最大价值的满足某条件的子序列，可以考虑对于某特定的子序列，其初始合法条件或价值计算方法，或可以枚举其重要分界点在原序列中的位置。（gym103860I） - **CF1787H（$O(n^2)$）** - gym102331H - https://loj.ac/p/3919 - https://loj.ac/p/3972 - P9521 #### 2024.08.13 - gym542554H - gym542554I - gym542554A - CF1943D2 #### 2024.08.14 - 树上每个点有点权（点权是结构体，有大小关系，定义了有结合律的合并操作，且若干个点直接排序后合并结果最优），你需要决策树上所有点的选取顺序（必须是拓扑序），使得全部合并的结果最优，此时可以将所有点加入优先队列（队列中的元素代表的是一个连通块的点权并），每次取出最小元素，若其父节点已被选取则直接选取该元素，否则将其与父节点所在连通块的对应元素合并后重新加入优先队列。（uoj418） - 深度不超过 $m$，长为 $2n$ 的合法括号序列数量。（uoj424） - uoj418 - uoj424 #### 2024.08.15 - meet-in-middle 时，左侧对每种方案计算权值，右侧能够查询一种权值对应的方案数。（uoj425） - P9041 #### 2024.08.16 - CF1804H - CF1656I https://www.cnblogs.com/lpf-666/p/16602167.html #### 2024.08.17 - 随机化： - 通过随机赋权计算和/异或和的方式一次性完成多组检验（P4795，P8819，CF1746F） - 通过随机映射破坏出题人的特殊数据（P10539） - 随机赋权后对某种指标计数以判定是否有解（P9041） - 通过随机权值的某种数据特征使期望误差不大，然后多做几遍，四舍五入取均值（P4581） - P4581 - P6837 - **CF1924F** #### 2024.08.21 - qoj4890 #### 2024.08.26 - 变换恒定思想。（P10760） #### 2024.08.28 - 模拟费用流的基本模式： - 建图后按一定顺序加入某些边 - 处理流经这些边的负环 - 处理流经这些边的流 #### 2024.08.29 - 容斥的一般方法： - 一般容斥 - 全容斥（枚举每个元素是否钦定） - 线性容斥 - 差分容斥（如 $f_i-=\sum_{j=1}^{i-1}f_j$、$f_i-=C_i^jf_j$ 等） - 狄利克雷容斥 - 特殊容斥 - 树连通容斥（树上一个点集连通块数等于点数减边数） - 树连通容斥可用于判断区间交是否非空（覆盖的 $i$ 数量减覆盖的 $[i,i+1]$ 数量）（https://contest.ucup.ac/contest/1382/problem/7564） #### 2024.08.30 - P10738（oMin0 解法） #### 2024.09.19 - 覆盖替换贪心（https://qoj.ac/contest/1774/problem/9220） #### 2024.09.21 - https://uoj.ac/contest/82/problem/806 #### 2024.09.22 - 图表填充构造的归纳证明。（P10612） #### 2024.09.28 - 如果不幸先推出复杂度证明的结论而不是做法（如想到 $\sum_{i=1}^nC_{d_i}^2\leq C_n^2$ 后才想到 $O(\sum_{i=1}^nd_i)$ 的做法），则应考虑是否有复杂度基于结论的做法。（20240928C，动态无向图（加删边）判断是否有四元环，要求 $O(n^2+nq)$） - 高低位 meet-in-middle（20240928C，求 $\min x(x\in\N)$，使得 $(kx+b)\operatorname{or}s=s$） - 关于交互和构造的次数，一定不要先猜量级从而产生错误的认识。（https://contest.ucup.ac/contest/1803/problem/9432） #### 2024.10.04 祝她生日快乐！ - 背包保证重量总和时要想到不同重量数的量级，特别是有物品数乘背包大小复杂度算法时。（20241004D，file:///D:/3-%E7%8E%8B%E5%98%89%E5%BA%A6/%E4%BA%BA%E5%A4%A7%E9%99%84%E6%97%A9%E5%9F%B9/%E4%BF%A1%E6%81%AF%E5%AD%A6/%E8%81%94%E8%B5%9B/20241004/down%20(3)/down/statement.pdf） - 余数背包（20241004D） - **20241004D** #### 2024.10.5 - 贡献法：乘法项展开（20241005C） - 有数量的乘积时可以把数量拆成若干个 $1$ 的和。（uoj667） #### 2024.10.8 - 需要启发式合并 set 时可以考虑是否能使用左偏树。 #### 2024.10.10 - 足减问题考虑倍增分块。 - 绝对值转化：$\max_{i\in S}i-\min_{i\in S}i=\max_{i,j\in S}(i-j)$。（对于 $a_{1\cdots n}$，定义 $[l,r]$ 的价值为 $\max_{i\in[l,r]}a_i-\min_{i\in[l,r]}a_i$，对于 $k=1,2,\cdots,n$，求把 $a_{1\cdots n}$ 分成 $k$ 段的最大价值，要求 $O(n^2)$） - 组合思想：贪心约束、取劣得优、独立化、分量转换 - https://contest.ucup.ac/contest/1259/problem/6644 #### 2024.10.24 - 按位判断 - 高位贪心 - 末位枚举 - 末位（奇偶性）递归（https://contest.ucup.ac/contest/1812/problem/9479） - 末位倍增（CF1844G） - https://contest.ucup.ac/contest/1812/problem/9480 #### 2024.10.26 - **P10778** #### 2024.10.28 - **严格性思想（限制更严格，决策更劣）。**（CSP-S2024T4） #### 2024.10.30 - 拆解小量级的容斥。（CF1221G） #### 2024.11.1 - 多个版本同时进行树上 dp 时，若不同版本的转移有区间性，可以线段树合并。（CF1606F） #### 2024.11.5 - 生成函数的压缩、相乘、分母展开的流程。（**CF891E**） #### 2024.11.6 - qoj9464 #### 2024.11.8 - 和差二分转化：对于 $a_i+a_j\leq/\geq m$ 类型的限制，可以对 $\frac{m}{2}$ 作差转化为比较（$a_i\geq b_j$ 等价于 $(\frac{m}{2}+a_i)+(\frac{m}{2}-b_j)\geq m$）。（CF1842H） - CF1626F：12252240 -> 720720 的卡常。 #### 2024.11.11 - qoj9613 - ucup1828B - ucup1828K #### 2024.11.12 - CF1450E #### 2024.11.13 - 计数题加权的处理方法： - 对权值容斥。（ucup1828K） - 反推状态贡献系数。 - 权值的计算有乘法时进行分配律展开。（20241005C） - 将一个变量拆成若干 $1$。（uoj667） - 所有合法序列的方案数的 $k$ 次方可以同时 dp $k$ 个方案对应的合法序列数。（CF2038E） - $\sum_{i=1}^na_i=\sum_{k=1}^{+\infty}\sum_{i=1}^n[a_i\geq k]$。 - 随机实数可以考虑 dp 数的顺序。（CF1153F，CF1842H） - uoj667 - CF238E - **CF1514E** #### 2024.11.16 - **CF335F** #### 2024.11.19 - 维护阶段前 $k$ 小的搜索。（https://contest.ucup.ac/contest/1843/problem/9558） - 值域段预期 dp。（**P5999**） - CF1508F - P10712 - https://contest.ucup.ac/contest/1843/problem/9560 #### 2024.11.20 - 2-sat 约束大小关系。（CF1697F） #### 2024.11.21 - 枚举顺序：按序构造。（CF1740G） - 表面上非多项式的枚举顺序可能实际上是多项式的，列举枚举顺序时应当考虑。（P11290） - 枚举顺序：贡献点对被贡献集合/贡献集合对被贡献点。（P11291） - 可以采用区间修改对区间查询的方式处理贡献。 - 系数加优化（对区间加 $x_i$ 时改为维护 $a_ix_i+b_i$ 的参数 $a_i,b_i$）。（P11291） - **P11291** - https://pjudge.ac/contest/1811/problem/21859 - **https://uoj.ac/problem/892** #### 2024.11.25 - **CF1307F** #### 2024.11.26 - Kruskal 结构维护多点树形贪心。（P9984） - 树上一个点到一个点集的最远距离等于这个点到点集直径中点的距离加点集半径。（qoj9632） - 树上两个点集的并的直径端点只可能在原有两个点集的四个直径端点中。（qoj9632） - 对需满足一定大小关系（或需对极值计算贡献）的序列计数时可以按值域从小到大加数。（qoj9611） - CF1578J - CF827F - CF1797F #### 2024.11.2? - 两区间扫描线：需求所有子区间答案时可以对每个 $l'$ 维护所有 $r'\leq r$ 的答案，查询时查询所有 $l\leq l'\leq r$ 的答案。（P9058） #### 2024.12.1 - CF2023D #### 2024.12.2 - CF1342F #### 2024.12.8 - **CF576E** #### 2024.12.10 - 构造题在构造方案时（要求构造合法或额外要求在一定界限内）可以分步构造，每步后只需使剩余部分有解。 - 树形 dp 决策/求解与边有关的最优解。 - CF1267H #### 2024.12.11 - CF1876E #### 2024.12.12 - CF1054G #### 2024.12.14 - 有重复赋值操作时，可以时间倒流从而令每个位置仅第一次赋值有效。（P9117，CF1530H） - CF1530H #### 2024.12.15 - 当修改满足一定单调性但不利于维护时，可以时间倒流从而令单调性相反。（CF1580E） #### 2024.12.17 - 求 01 矩阵的所有极大全 1 子矩阵。（枚举下边界，对 1 高度建笛卡尔树）。 #### 2024.12.22 - P5048 - P5046 #### 2024.12.25 - CF840E #### 2024.12.29 - **CF1797F** #### 2024.12.30 - CF1463F #### 2025.1.1 - P11095 #### 2025.1.2 - 基于重链剖分的树上颜色段均摊。（CF1137F） - 需要维护点的先后顺序序列，修改为把一条到根的链提到最后时，可以用给整条链标记新的时间戳的方式。（CF1137F） - CF1137F #### 2025.1.3 - **AT_abc306_h** #### 2025.1.4 - 需要决策若干区间的位置，而它们具有括号性（只能包含和相离）时，可以区间（可能状压）dp 决策，转移为按括号树序。（P10197） - 区间的括号性（栈性）与队列性的利用（括号性指只能包含和相离，队列性指左右端点分别不降）。 - 区间二分图问题： - 可以用优先队列贪心构造一组解。 - 若有 $l_1=l_2,r_1\leq r_2$，则将 $l_2$ 增加 $1$ 后可行性不变（一般可用于解决多次询问）。（CF1965F） - 一个充要条件：任何区间包含的约束子区间数不超过区间长度。 - 背包的根号分治。（P6189） - dp 一个非增数列时，可以以如下两种方式转移：追加一个 $1$（或下限）；所有数加 $1$。（P6189） - CF1413F - AT_arc158_d - P10197 - CF1965F - P6189 #### 2025.1.5 - 可以考虑利用 $0$ 联通块的性质维护最短路等。（CF2057E2） #### 2025.1.19 - https://contest.ucup.ac/contest/1843/problem/9557 - https://contest.ucup.ac/contest/1843/problem/9555 - https://contest.ucup.ac/contest/1843/problem/9559 - **https://contest.ucup.ac/contest/1843/problem/9558** - https://contest.ucup.ac/contest/1843/problem/9554 #### 2025.1.23 - **P4720** #### 2025.1.29 - **P10527** #### 2025.2.4 - 需要对于每个 $k$，对 $a_1\bmod2^k,a_2\bmod2^k,\cdots,a_n\bmod2^k$ 排序时，可以从高位向低位归并排序，从低位向高位也可以。（P11651） - P6628 #### 2025.2.6 区间加、单点查可以做到 $O(kn^{\frac{1}{k}})-O(k)$，方式是 $k$ 层分块，每块分为 $n^{\frac{1}{k}}$ 个更小的块。（20250206T3） #### 2025.2.7 - **P10197** #### 2025.2.10 - 需要优化 dp 时，要打表寻找转移规律。 #### 2025.2.13 - **20250213T3** #### 2025.2.14 - 差分阶梯（将生成单调数组的方式转化为若干次前/后缀加/减一）。（AT_agc041_d） - 将可重集转化为完全背包。（AT_agc041_d） - 有多种合法条件时，尝试使其中一个成为另一个的充分条件以减少条件数。（AT_agc041_d） #### 2025.2.15 - 可以通过一个大数对若干小质数取模的结果来确定这个大数。 #### 2025.2.16 - 子集图交。（**CF1930F**） - https://www.luogu.com.cn/paste/2ew88gej - https://www.luogu.com.cn/paste/y3uj37bo #### 2025.2.17 - Boruvka 算法求特殊图的最小生成树。（CF1305G） - 需要查询与 $a_i$ 不同组的数的极值时，可以直接维护查询范围的极值以及某种意义上的“严格次极值”（与极值不同组的所有数的极值）。（CF1305G） - **需要同时维护树上不同版本的信息时可以线段树合并。**（20250217T2） #### 2025.2.18 - https://uoj.ac/problem/693 - **动态高斯消元**。（http://xsy.gdgzez.com.cn/JudgeOnline/problem.php?cid=2207&pid=2） #### 2025.2.19 - 邻接矩阵的 max+/min+ 矩乘。（https://loj.ac/p/539） - 求 size 不超过 $k$ 的树上背包时，复杂度为 $O(nk)$。 - **https://uoj.ac/problem/806** （https://www.cnblogs.com/zkyJuruo/p/17460509.html 的做法） #### 2025.2.21 - 整体二分维护转移单调性。（**http://xsy.gdgzez.com.cn/JudgeOnline/problem.php?cid=2185&pid=1** ） #### 2025.2.22 - 费用序（一般序）模拟费用流。（http://xsy.gdgzez.com.cn/JudgeOnline/problem.php?cid=2229&pid=0 ） - Hall 定理贪心处理二分图的模拟费用流。（http://xsy.gdgzez.com.cn/JudgeOnline/problem.php?cid=2229&pid=0 ） - 2-sat 判定集合划分是否有解。（http://xsy.gdgzez.com.cn/JudgeOnline/problem.php?cid=2229&pid=1 ） - 处理一对点的 lca 的相关问题时，可以将 lca 的信息转化为树根到 lca 的链的信息，然后一个点对一对点有贡献当且仅当这对点在这个点的子树内。（https://loj.ac/p/3626 ） - 二维差分不影响行列式。（https://loj.ac/p/3626 ） - https://loj.ac/p/3626 （ https://www.cnblogs.com/YunQianQwQ/p/17775501.html 解法） - **CF1909G** #### 2025.2.23 - P9070 #### 2025.2.24 - 仅在末尾修改的动态 RMQ 可以使用 ST 表降低查询复杂度。（CF1889C2） - P10201 - **CF1942F** - **P10365** #### 2025.2.25 - **https://uoj.ac/problem/935** - P9521 - https://contest.ucup.ac/contest/1780/problem/8943 - CF1728G #### 2025.2.26 - **CF1943D2** - **https://qoj.ac/problem/4890** （https://www.cnblogs.com/devout/p/16210575.html ） - https://contest.ucup.ac/contest/1259/problem/6644 - CF1342F - CF840E #### 2025.2.27 - **P7520** - https://uoj.ac/problem/515 #### 2025.2.28 - 当转移点不固定时，可以从每个点分块。（CF840E） - P3203 - https://uoj.ac/problem/703