LCS——经典的 DP 问题，给定两个长度为 $n$ 的排列，试问二者的最长公共子序列。这是经典的区间 DP 问题， 首先考虑朴素做法，定义 $dp[i][j]$ 来表示第一个串的前 $i$ 位，第二个串的前 $j$ 的 $LCS$ 长度，易得状态转移方程： 如果两个序列没有新的相同元素 $dp[i][j] = \max(dp[i-1][j],dp…

这篇文章受密码保护，输入密码才能阅读

比赛补题 Codeforces Round 960 (Div. 2) 这次比赛可以看出最近的代码准确度又在下降，A - C 题不能快速的做出来，且一共吃了 6 发罚时，这说明了代码准确度练习较少已经到了非常严重的地步，最近难题看的较多又失去了对简单题的熟练度，其实也可以说明之前练的还不够，有一定的效果，但随着时间的推移有所反弹。 当然，心态可能也对…

题单 我也不知道为什么下划线一多 Latex 就要崩掉，我已经不想管了。 CSES - 1075 Permutations II 动态规划好题。 解法一（recommend) 定义 $F(i, j, k)$ $1$ 表示在 1 到 $i$ 的排列中，满足有 $j$ 对相邻的 $<i$ 的差为 $1$，$k = 1$ 或 $0$ 分别对应 $i…

数据结构（线段树为主） 题单 P6569 [NOI Online #3 提高组] 魔法值 首先看题目数据范围，$n \leq 100$ ，这种情况要么说明这道题的时间复杂度是比较高的，要么就和矩阵乘法脱不开关系。 阅读题目之后，我们发现可以应用 Floyd 最短路，也就是矩阵乘法的思想去描述每一轮每一个城市的魔法值。 故这道题应该先用邻接矩阵建图，…

杂 #include <bits/stdc++.h> #define rep(i, a, b) for(int i = (a), stOwxc = (b); i <= stOwxc; i++) #define per(i, a, b) for(int i = (a), stOwxc = (b); i >= stOwxc; i…

这篇文章没有摘要

${\color{Red} \mathrm{写的很垃圾，待补充} } $ Update on 2023.11.17 修改笔误，补充内容。 T1 题目大意 求 $m!$ 在模 $p$ 下的值，保证 $p$ 是素数。 分析与解答 考点：威尔逊定理。 由威尔逊定理可知，若 $p$ 为素数，则有$(p-1)! \equiv p-1\pmod{p}$。 可通…

T1 密码锁 // CSP-S 2023 密码锁 #include <bits/stdc++.h> using namespace std; using VI = vector<int>; int main() { #ifdef ONLINE_JUDGE freopen("lock.in", "…

环上最大独立集 题目描述 给出一个有 $n$ 个点的环，每个点有点权 $a_i$，求满足点集内任何两个点在环上不相邻，且点权和最大的点集的点权和。 注意点 $1$ 和 点 $n$ 是相邻的。 输入格式 第一行输入一个正整数 $n$，表示点的数目。 第二行输入 $n$ 个以空格隔开的整数，依次表示各个点的点权 $a_i$。 输出格式 输出一行一个整数…