P4003 无限之环 如果直接来做其实一点头绪都没有，于是我们可以点开 Infinity Loop 玩了一会。 玩的过程中发现一个明显的性质不管最终答案是什么样的，每个插头都是被另外一个插头配对的。 那么本质上就是每个格子的 $4$ 个位置有若干个是插头，每个插头需要被配对，每次旋转需要代价，求最小代价使得所有插头被配对。 显然对于一个插头我们被配对当且仅当其和 $1$ 个另外的插头配对。 我们考虑拆点限制这个 $1$，考虑使用费用流。 我们可以考虑对于每个格子拆成 $5$ 个点，一个点来限制其他点的 $1$ 次流量，然后剩下 $4$ 个点表示插头，因为需要有源点和汇点我们不妨仿照骑士共存问题进行染色。 考虑旋转是怎么表示的，本质上就是看这个 $1$ 的流流到哪里去，就是简单连边。 一个插头，相邻位置费用为 $1$，对面为 $2$。 $\tt L$ 形插头，考虑最上面的位置顺时针旋转 $1$ 次可以使最下面插头合法，所以是对面连边费用为 $1$。费用为 $2$ 的情况可以不考虑，因为本质上就是两次费用为 $1$ 的旋转。 三个插头，可以通过一次相邻旋转或者一次相对旋转，费用为 $1, ...

USACO - Au - T1 考虑要么是奶牛去匹配苹果要么是苹果取匹配奶牛。 有一个很简单的贪心，能接住就接。 考虑对于 $x = x, y = t$ 建立笛卡尔坐标系。 对于一个苹果 $(a, b)$ 其能被奶牛接住当且仅当其在 $y = x + b - a$ 的直线下方。 这个东西本质上就是一个三角形，考虑将平面旋转 $(a, b) \to (\frac{a + b}{\sqrt 2}, \frac{a - b}{\sqrt 2})$。 这个 $\frac{1}{\sqrt 2}$ 其实本质上是没有关系的，放缩一下答案不会变化。 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677787980818283848586878889909192#include <bits/stdc++.h>#include ...

USACO - Ag - T1 内向基环树森林，既然可以自己给定排列我们对于链的答案肯定是全部都能算上的。 对于环发现只会有 $1$ 个点没有算上贡献取最小的即可。 或者使用最大生成树也可以，因为本质上一个基环树断掉一条环上的边即可。 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879808182838485#include <bits/stdc++.h>#include <bits/extc++.h>using namespace std;using namespace __gnu_cxx;using namespace __gnu_pbds;namespace Legendgod { namespace Read {// #define Fread #ifdef Fread const ...

USACO - Cu - T1 发现翻转是改变一个区间的奇偶性，其声明只能对于偶数位置进行前缀区间翻转，所以考虑直接对于相邻两个数进行考虑。 翻转只会对于两个位置不同生效，考虑对于连续的一段一起翻转即可。 翻转贡献可能为 $1, 2$。看是否是一个前缀的形式。 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364#include <bits/stdc++.h>#include <bits/extc++.h>using namespace std;using namespace __gnu_cxx;using namespace __gnu_pbds;namespace Legendgod { namespace Read {// #define Fread #ifdef Fread const int Siz = (1 << 21) + ...

主要是 $\tt pbds$ 有很多封装好了的小常数代码，比自己手写会方便很多。 头文件 #include<bits/extc++.h>，需要使用命名空间 __gnu_pbds 平衡树【模板】普通平衡树 - 洛谷 $\tt STL$ 容器：tree 123tree<Key, Mapped, Cmp_Fn = std::less<Key>, Tag = rb_tree_tag, Node_Update = null_tree_node_update, Allocator = std::allocator<char> > Key: 储存的元素类型，如果想要存储多个相同的 Key 元素，则需要使用类似于 std::pair 和 struct 的方法，并配合使用 lower_bound 和 upper_bound 成员函数进行查找 Mapped: 映射规则（$\tt Mapped-Policy$）类型，如果要指示关联容器是 集合，类似于存储元素在 std::set 中，此处填 ...

Problem - 1508D - Codeforces 首先将 $a_i$ 放到排列上去，考虑对于 $a_i \to i$ 进行连边，本质上又是置换的情况。 考虑对于置换进行操作，对于同一个置换环进行一次交换就可以将环归位而且不会相交。 考虑对于 $(u, v)$ 在不同的环中，我们使用交换本质上就是将两个环合并到一起，但是如何保证不会出现相交的情况。 最终肯定是只有 $1$ 个环，然后来进行操作。 对于凸包的情况考虑随便选择一个点，之后其他点和当前点连线肯定是不相交的，所以我们合并环的操作只能使用相邻两个点。显然我们交换相邻两个点是肯定可以使其变成一个环的。 如果不是凸包的话，发现随便画个图就去世了。 如果发现不对的情况，可以先考虑什么情况是不对的，看看能不能进行处理。 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828 ...

Problem - 1290D - Codeforces $\text{my solution}$不妨考虑初始答案为 $n$，发现一个数是出现过的直接让答案 $-1$。 我们考虑如何查看一个数是出现过的。 我们先尝试能否让一个数和其他所有数进行匹配，考虑一个数消耗的次数是 $\frac{n- 1}{k -1}$。为了钦定顺序我们考虑位置 $i$ 只和位置在其前面的数进行匹配。 发现直接暴力匹配的话如果 $K$ 比较大会浪费掉很多查询次数，所以考虑如何利用 $K$。 如果考虑钦定了顺序，对于 $i \le K$ 的部分我们可以一次全部查完。 其次我们发现重置队列对于查询次数的影响还是很大的，能不能尽量少重置队列。 只要一个数没有出问题，其查询队列中可以包含符合范围的任意数。 如果后面的数和当前的数是不同的，查询队列是允许出现后面的数的。 注意每次加入数的时候可能会弹出数。 看看能不能倒着查询，就是让每个数被查询，考虑需要查询同一个块内的所有数，我们加入块之后。逐步加入原来的数。我们考虑同一块内的数倒着加入，然后依次查询前面的一个块。 我们只要保证块内的数互不相同，而且加入的数互不 ...

Problem - 1060F - Codeforces 考虑每个数如果被选择为最终的答案，要么是操作没有选择与其相连的边，要么是操作了这个边用 $\frac{1}{2}$ 的概率活下来了。 首先总边数是每次减少 $1$ 的，一个点被选择的概率只和该点周围连接了几条边有关。 设 $f(u, j)$ 表示在 $u$ 的子树中，对于所有删边顺序只对最后 $j$ 条边选择存活节点，根节点的编号仍然是 $u$ 的概率，节点 $u$ 的答案是 $\frac{f(u, n-1)}{(n-1)!}$。 考虑合并 $(u, v)$，我们只需要考虑 $u$ 还有 $v$ 的子树，我们同样设边的状态为 $g(i)$ 和上文相同。 枚举 $(u, v)$ 在什么时候被删除。 如果 $j \le i$ 意味着边收缩完成之后，新的编号已经确定，所以必须选择 $u$ 概率为 $\frac{1}{2}$，同时因为 $(u, v)$ 已经合并，所以最后的 $j -1$ 条边都需要选择 $u$，也就是选择 $v$。转移为： $g_i \leftarrow f(v, j - 1) \times \frac{1}{2}$。 ...