高速对拍 看了一下机房里面的同学对于对拍基本上有几种写法： 直接用 $\tt c++$ 搞一个对拍 写 $3$ 个程序，之后用一个 $\tt bat$ 来整合 每次通过 $\tt bat$ 中的 $\tt <$ 进行传入随机种子（其实也就是拍了第几组），这个效率还是挺高的。 根本不屑于对拍 其中很多的写法都是 Sleep(1000)也就是意味着每秒最多只能对拍一次。 网上还有一种比较主流的写法，就是每次调用系统的内存，因为这个是动态的进行对拍。但是显然后者会有较大的可能重复导致效率不高。 于是就有了某些优秀写法： 12auto *it = new unsigned int;srand(time(0) ^ (*it)); 也就是每次取一个新的内存地址，然后和系统时间进行某些操作，可以尽可能保证其正确性。 说人话就是平时应该够用了。 但是有些时候对于一个程序不是很确定的时候，我们可以尝试使用更加有些的种子。 具体来说我们可以使用某些精度较高的种子： 12auto tm = std::chrono::high_resolution_clock::now();tm.tim ...

大概是按照难度排序的吧。 [HNOI2002]公交车路线 题解 P5151 题解 CF718C 题解 P3702 题解 CF1182E 题解 P5303 逼死强迫症 题解 CF917C 题解 SCOI2009 题解 CF576D 题解 CF575A 题解 CF618G 题解 CF498E 题解 #2326. [HNOI2011]数学作业 题解 【NOI2013】矩阵游戏 题解 佳佳的 Fibonacci 题解 POJ 3613 Cow Relays 题解

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$。 但是对于当前字符的贪心需要证明一个结论：对于原图任意一个欧拉回路可以通过字符串的任意变换得到。 首先对于一个欧拉回路，那么肯定不会出现两个环中间连接一条链的情况。肯定是若干个环进行连接，对于两个交错的环我们直接拆开即可。 或者换一个方法来说，因为一个点变成了环之 ...

生成排列和子集 这个只是单纯的总结，之后肯定还会搞的（如果没有退役的话）。 生成排列 不妨以生成 $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 ...