CF1458C Latin Square CF1458C Latin Square 这里说一下逆排序就是如果说原来位置 $i$ 的数是 $p_i$ 那么现在位置 $p_i$ 的数就是 $i$。 直接变成三元组 $(i, j, a_{i, j})$ 也就是所有有关的信息。 之后直接记录并且修改即可，复杂度是 $O(n^2 + m)$ 的。 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100#include <bits/stdc++.h>using namespace std;//#define Fread//#define Getmod#ifdef Freadchar buf[1 << 21], *iS, *iT;#define ...

CF1458D Flip and Reverse CF1458D Flip and Reverse 题目还是挺清晰的，直接讲思路了。 首先考虑进行 $\tt dp$ 或者贪心，但是直接进行感觉上无法处理上述的限制。 那么我们从限制进行考虑，最好去掉的限制显然就是数字相同，那么如果说进行对于字符串进行前缀和之后两个前缀和相同的位置 $l - 1, r$ 其实对应一个合法的 $[l, r]$ 区间。 之后我们考虑区间翻转和反转正好就是反着遍历这段区间，那么我们对于权值 $s_i \to s_{i + 1}$ 进行连边，那么这个肯定是一个环。我们直接对于已知的每一个环进行贪心即可。 那么本质上就是原串构成的一个合法的欧拉序列。 那么我们只需要求最小的欧拉序即可。 显然因为要让字典序最小那么我们优先放 $0$ 其次放 $1$。 但是对于当前字符的贪心需要证明一个结论：对于原图任意一个欧拉回路可以通过字符串的任意变换得到。 首先对于一个欧拉回路，那么肯定不会出现两个环中间连接一条链的情况。肯定是若干个环进行连接，对于两个交错的环我们直接拆开即可。 或者换一个方法来说，因为一个点变成了环之 ...

$$\begin{aligned}\Large\text{摘星}\end{aligned}$$ 在最高的楼台上眺望是一种多么美妙的事情呀！他被人抬上这样的楼台，虽然是站在别人的肩上看仍旧感觉十分良好，话说 ”危楼高百尺，手可摘星辰“ 也确实距离月亮不远了。 “我可是诗人呀！” 他自言自语说着，向前走去。他自认为是一个著名的诗人，可能在周围的所有人中也仅仅只有我一个人也是这样认为的吧，据说他的诗刚刚写成的时候便嘶吼着要出书，可能不太符合其他人的审美吧。他的作品更多的时候就是在刚刚写成的时候就被一些外力因素化作灰烬。 “黑夜和光明一起，在黑暗后肯定是光明呀！” 他仿佛看穿了我一般，嘟囔着。“高楼之上，天街云月与光辉共色。金台祠里，绵缠的摆布、尸体密密麻麻。” 那么看起来他很自信呀，哎去年也是这样，只是近些天更加穷困罢了。 突然他颤抖着向我走来，别人不由得向后方退却一步，而我深知其只是惯例找我讨些许酒钱罢了。也不知道是什么时候便有了这样的习惯，我也从来没有反对只是默默将一张破旧的钞票送到其手上。 然而这一次他没有买酒，而是取了纸顺便说着：“其实我不是太阳，我没有其耀眼也不是月亮，没有其阴柔。 ...

生成排列和子集 这个只是单纯的总结，之后肯定还会搞的（如果没有退役的话）。 生成排列 不妨以生成 $1 \sim n$ 的排列进行举例子，我们对于每一个数字的上面先定一个箭头，表示其可以向那边走。 一个数字移动的条件是其箭头指向的相邻的数组比其要小。 例如 $\overset{\leftarrow}{1}\overset{\leftarrow}{2}$ 这个时候 $2$ 就是可以向左走一个位置的，也就是意味着下一个排列是 $\overset{\leftarrow}{2}\overset{\leftarrow}{1}$。 我们构造一个排列是从 $\overset{\leftarrow}{1}\overset{\leftarrow}{2} \dots \overset{\leftarrow}{n}$ 开始的。 每次找到最大的可以移动的数。 交换其和其箭头指向的数字。 交换所有 $i, i > m$ 的箭头的方向。 逆序对生成排列 对于一个数组 $b$，$b_i$ 表示第 $i$ 个位置的逆序对数量。 我们从左到右进行考虑。 首先写出 $n$，先钦定其为第一个数字。 ...

P1892 [BOI2003]团伙 说句实话这个题意真的有点 $\dots$，具体来说就是两个方面。 我的敌人和朋友的敌人不一定是朋友。 最终答案要求输出总共有几个团体。（来自某讨论区小朋友的错误） 直接扩展域并查集即可。 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677787980818283848586878889909192#include <bits/stdc++.h>using namespace std;//#define Fread//#define Getmod#ifdef Freadchar buf[1 << 21], *iS, *iT;#define gc() (iS == iT ? (iT = (iS = buf) + fread (buf, 1, 1 << 21, s ...

一句话解释哈夫曼树 我们考虑对于一棵叶子节点有权值的二叉树，设其总共的贡献是每个叶子节点的权值乘上深度。 那么我们需要构造一个使其贡献最小的二叉树，也就被称作最优二叉树。 我们考虑贪心对于每次选择权值和最小的两个点进行合并，之后其父亲，权值为两个节点的权值和即可。

Codechef Dynamic GCD Codechef Dynamic GCD 就是考虑维护链上 $\gcd$ 和链加。我们先考虑这个东西放到序列上怎么做，首先进行差分，之后因为 $\gcd$ 是不变的，但是区间加可以直接变成了单点修改用线段树进行维护即可。 对于树上的情况，我们直接使用树链剖分进行分成若干条链进行计算。 具体来说我们考虑对于一条链 $u, v, fa_u = v$，我们让节点 $u$ 的值变成 $a_v - a_u$ 即可。对于链头的情况我们直接作为原来的值即可。 但是会有一个问题，如果我们一条链没有被使用完成我们就需要知道最上面的那个值。 对于这个我们只需要维护一下被加的值即可，为了方便使用了标记永久化。 一些细节： 根据我们差分的定义，对于一个节点 $u$ 增加了 $c$ 的时候，其单点维护的 $\gcd$ 是要 $- c$ 的，其儿子是要 $+ c$ 的。当然对于 $u = \tt{top}_u$ 的情况例外。 我们进行最终计算答案的时候不要忘记计算最上面一个点的贡献，也不要多计算。 12345678910111213 ...

CF1043F Make It One CF1043F Make It One 首先看一下质因子个数最多只有 $6$ 个，考虑答案上界是多少。 122 3 5 7 11 133 5 7 11 13 17 不要忘记 $17$。 你们答案的上界就是 $7$。 我们考虑对于 $\gcd$ 进行卷积，那么我们需要使用容斥。 考虑反演：$$g = f \times I \f = g \times \mu$$ 原理就是 $I \times \mu = e$。 但是反演其实还有一种形式。$$g(n) = \sum_{i = 1, i \times n \le m} f(i \times n) \f(n) = \sum_{i = 1, i \times n \le m} g(i \times m) \times \mu(i)$$我们直接使用后面一种即可。 12345678910111213141516171819202122232425262728293031323334353637383940414243444 ...