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

$$\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 ...

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