Thy's Blog

Debug 1234inline void debug() { cerr << '\n'; }template<typename Type, typename... Other>inline void debug(const Type& x, const Other&... y) { cerr << x << ' '; debug(y...); }#define DEBUG(a...) cerr << "[" << #a << "] = ", debug(a) Read In 1234567891011template<typename Type>inline void read(Type &res){ res = 0; int ch = getchar(), flag = 0; while (!isdigit(ch)) ...

Statement 给定可能含前导零的三个位数为 nnn 的整数 A,B,CA,B,CA,B,C，求出排列 ppp 的个数，使得三个整数的每一位经过排列映射后得到的 A′,B′,C′A',B',C'A′,B′,C′ 可以使 A′+B′=C′A' + B' = C'A′+B′=C′ 成立，答案对 109+710^9 + 7109+7 取模。 下文中定义位数从右向左，例如 A1A_1A1​ 表示 AAA 的个位上的数，AnA_nAn​​ 为最高位的数。 Solution 一道并不难的排列组合计数题，复杂就在处理不同数位之间的进位问题。 不进位的情况 先考虑不进位的情况，每一位之间都不会互相影响，同时由于 A′,B′,C′A',B',C'A′,B′,C′ 不能含有前导零，我们定义 zerozerozero 表示有 000 的列数。 答案简洁明了，第一列放非 000 列，后面随便放即可。 ans=(n−zero)×(n−1)!ans = (n - zero) \times (n - 1)! ans=(n− ...

Pre 一道并不难的图论模型题，前提是得要想得到图论。 Solution Subtask 111： 由于 n≤8n \le 8n≤8，直接将卡片的顺序进行全排列，再依次判断是否可行即可，预估时间复杂度为 O(n!×∑ki)O(n! \times \textstyle{\sum k_i})O(n!×∑ki​)。 Subtask 222： 由于卡片之间地约束条件很多，考虑搜索。理所当然地从上到下考虑，不妨先考虑第一张：第一张可以被选当且仅当该卡片上所有字母都可以和目标串匹配。一旦字符串上的某个位置 SiS_iSi​ 被匹配，我们标记掉这个位置，因为后面的卡片不会影响这个位置了。 不难发现，每一张卡片做出贡献的位置一定是目前第一次出现的位置，因此不必注意先后顺序。一旦可以有贡献并且合法，我们就进行下一层的搜索。 尽管理论时间复杂度为指数级别，但是真正的合法状态很少，可以拿到 505050 分。 Code 12345678910111213141516171819202122232425262728293031323334353637383940414243444546int n, m;cha ...

不进行没必要的解释，主要记录模板。 1234567891011121314151617181920212223242526272829303132struct Matrix{ int n, m, rec[N][N]; // 矩阵的长，宽和二维数组 Matrix(int _n, int _m) { n = _n, m = _m, memset(rec, 0, sizeof rec); } // 初始化函数 void reset() { n = 0, m = 0, memset(rec, 0, sizeof rec); } int* operator [] (int i) { return rec[i]; } // 重载数组 const int* operator [] (int i) const { return rec[i]; } // 重载数组 friend Matrix operator * (const Matrix ...

记录本人2024年看过的一些番剧 前言 写这篇 blog 的主要原因是停课在机房坐牢过于无聊，采取这种方式来消耗时间，同时也方便记录自己的入宅经理和感想。 对于记录的每一部番，我不仅会记录感想尽管有些忘得差不多了，同时也会从画质水准，剧情质量，内容深度，心里反馈以及等方面进行极端主观的评价和总评，不喜勿喷。 接下来记录大致按照时间顺序记录，这样更有意义。 3 ~ 5 月 直到今年三月以前，我是很少看番的，除了国产的刺客伍六七和我的三体，日番我也只看过 JOJO 的前四部，此阶段我选择的番都是有原因的。 龙与虎 算不上远古老番，但是也挺早了，找到这部番属实不易，其实是因为它的一首歌才知晓的，然后就不知不觉地看完了。一部很平常的校园日常恋爱番，主角五人都有个性，剧情没有突出优点，画质由于远古所以一般，唯一不理解的就是大河凭什么赢得过小实（真的惨）和亚美啊。 画质水准：★★★★★★☆☆☆☆ 剧情质量：★★★★★★★☆☆☆ 内容深度：★★★★★★☆☆☆☆ 心里反馈：★★★★★★★★☆☆（别问，问就是第一次看这类型的番产生了戒断反应，花了好几天才好起来） 总评：7.57.57.5 分 赛博朋 ...

Statement 给定一个长度为 nnn 的数组 aaa，定义函数 f(l,r)f(l, r)f(l,r) 表示区间 (al,al+1,…ar)(a_l, a_{l + 1}, \ldots a_r)(al​,al+1​,…ar​) 中不同值的个数，求： ∑i=1n∑j=inf(i,j)\sum_{i = 1}^n \sum_{j = i}^n f(i, j) i=1∑n​j=i∑n​f(i,j) 的值，其中 1≤∀ai≤n≤2×1051 \le \forall a_i \le n \le 2 \times 10 ^ 51≤∀ai​≤n≤2×105。 Solution 一道代码量极少的思维好题。 遇到这种区间求和问题，第一步先考虑找到所有区间之间的共同点，将原本 O(n2)O(n^2)O(n2) 的暴力转化成 O(n)O(n)O(n) 的算法，在这里先考虑暴力： 12345678auto add = [] (int x) { if (++ cnt[x] == 1) cur ++; };for (int i = 1; i <= n; i ++){ ...

差分约束系统与 2-SAT 将两者放在一起的原因是两者本质十分相像： 差分约束用于解多个二元不等式，其中要求变量为实数，不等式表示两个变量之差。 2-SAT 则用来解决布尔类型方程，每个方程同样只涉及两个变量。 差分约束系统 以模板题 P5960 【模板】差分约束 - 洛谷 为例，差分约束本质上是由多个形如： {xc1−xc1′≤y1xc2−xc2′≤y2⋯xcm−xcm′≤ym\begin{cases} x_{c_1}-x_{c'_1}\leq y_1 \\x_{c_2}-x_{c'_2} \leq y_2 \\ \cdots\\ x_{c_m} - x_{c'_m}\leq y_m\end{cases} ⎩⎨⎧​xc1​​−xc1′​​≤y1​xc2​​−xc2′​​≤y2​⋯xcm​​−xcm′​​≤ym​​ 组成的不等式组，对这个不等式进行求解或判断是否无解（或无穷解）。 问题转化 既然知道差分约束与最短路有关，我们考虑转化问题，我们在不等式组中单独拎出一个式子： xi−xj≤kx_i - x_j \le k xi​−xj​≤k 钦定 xix_ ...

前缀函数 前缀函数通常称为 border，一个字符串 SSS 的 border 定义为它的一个前缀子串 t(t≠S)t(t \ne S)t(t=S)，满足 ttt 既是 SSS 的前缀，也是 SSS 的后缀。下文的 border 均为 SSS 的最长 border 长度。 简单来说，对于一个字符串 S=abcabcdS = \texttt{abcabcd}S=abcabcd（下标从 111 开始），它的前缀函数为 [0,1,0,1,2,2,3][0, 1, 0, 1, 2, 2, 3][0,1,0,1,2,2,3]。 计算方法 单纯暴力 从左向右遍历一遍，每次循环一次长度，每次检查遍历一遍子串，复杂度为 O(n3)O(n^3)O(n3)。 边界优化 从左向右遍历的过程中，子串的大小每次只会增加 111，而原先的前缀不会改变，因此 borderiborder_iborderi​ 的长度最多只会比 borderi−1border_{i - 1}borderi−1​ 大 111，在这种情况下： S[i]=S[borderi−1+1]⇒S[1…borderi−1]=S[i−1−borderi ...

Manacher 算法 例题：P3805 【模板】manacher - 洛谷 | 计算机科学教育新生态 (luogu.com.cn) 给出一个只由小写英文字符 a,b,c,…y,z\texttt a,\texttt b,\texttt c,\ldots\texttt y,\texttt za,b,c,…y,z 组成的字符串 SSS ,求 SSS 中最长回文串的长度 。 Manacher 算法是一种快速找到字符串中所有回文串长度的线性算法。 奇偶回文长度统一处理 回文串存在两种形式：形如 abba\texttt {abba}abba 的偶数回文串以及形如 abbcbba\texttt {abbcbba}abbcbba 的奇数回文串。 我们令 fi(1≤i≤∣S∣)f_i (1 \le i \le |S|)fi​(1≤i≤∣S∣) 表示以第 iii 个字符串为中心形成的最长回文串，显然偶数回文串就不好处理了。 我们将每个字符之间用一个无关字符代替，例如 abba←!a!b!b!a!\texttt{abba} \leftarrow \texttt{!a!b!b!a!}abba←!a!b! ...

线段树 线段树是 OI 竞赛中最强大的数据结构之一，可以用来维护和、积以及最值等具有合并性质的信息。 一般线段树 P3372 【模板】线段树 1 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn) P3373 【模板】线段树 2 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn) 以模板一为例： 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061struct SegmentTree{ #define lc u << 1 #define rc u << 1 | 1 struct Tree { int l, r, sum, tag; inline int len() { return r - l + 1; } inline void addtag(int k ...