CF1385E Directing Edges CF1385E Directing Edges 题目描述： 给定一个图，有无向边和有向边。对于无向边进行定向，问能否给出一个方案使得定向后的图是无环的，图不一定要联通。 我们先不考虑无向边，对于有向边组成的图，不妨进行一次拓扑排序找到每一个节点遍历的先后顺序。 我们先判掉有环的情况，也就是存在一条边 $u \to v$ 而且点 $u$ 的遍历时间比 $v$ 要晚。 之后考虑我们肯定可以构造出一种合法的图，也就是对于所有的无向边我们考虑连接的两个几点，只要保证边 $u \to v$ 而且点 $u$ 的遍历时间比 $v$ 早即可。 具体实现的时候因为图不一定联通，所以我们不妨对于每一个节点进行 $\tt dfs$ 在搜索完儿子之后再将自己加入。这样可以保证及时搜索节点的顺序不同也可以保证是拓扑序列。 之后取反即可，因为现在是逆着的拓扑序。 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253 ...

LOJ #2269. 「SDOI2017」切树游戏 #2269. 「SDOI2017」切树游戏 没错我在某谷被卡掉了，之后会了全局平衡二叉树再更新那个做法。 不考虑修改怎么做。 设 $f(i, j)$ 表示以 $i$ 为根的子树（必须包含点 $i$）异或值为 $j$ 的方案数， $G(i, j)$ 以 $i$ 为根的子树的答案。 考虑更新。对于上一个答案 $f’(i, j)$ 当前儿子 $v$ 可以更新得到：$$\begin{aligned}f(i, j) = \sum_{j = k \otimes x} f’(i, k) \times (f(v, x) + 1)\end{aligned}$$其中 $\otimes$ 是异或运算，显然我们可以使用 $fwt$ 进行优化，不妨考虑 $f(i)$ 表示已经进行 $fwt$ 后的答案，$G$ 也是如此。这样我们最后只要 $ifwt$ 即可。 那么转移方程显然有 $f(i) = f’(i) \times (f(v) + one)$。 $G(i) = G’(i) + (f(v) + one)$ 之 ...

CF1344B Monopole Magnets CF1344B Monopole Magnets 多打 $CF$ 你也会懂一点英语。 笔者很菜，入手点是没有找到。就是考虑南磁铁不行的话，我们可以考虑一下两个黑色的格子的关系。也就是说如果这两个在同一个行的话，那么可以考虑到两个格子到当前行的南磁铁路径上肯定都是黑色的。 那么我们考虑是否会存在两个南磁铁的情况，如果存在那么肯定是为了处理有两段黑色的情况，但是下面的南磁铁同样是可以吸引上面的北磁铁，那么这种情况肯定是不行的。 所以可以得出第一个限制 每行每列最多只有一段黑色。 之后写了一下，发现过不了样例。样例提示我们这个限制还不够。 一开始想着特判一下 $1 \times n, n \times 1$ 的情况，但是发现对于 $2 \times n$ 的情况，同样会出现类似的不合法的情况。 具体来说就是如果一行是全部白色的，又因为这一行必须要填一个南磁铁。如果对于列来说填的位置是白色，而且这列是有黑色的，那么肯定是不合法的。会导致多刷点。 那么唯一合法的情况就是 如果存在一行是白色的，至少存在一列是白色的。 直接考虑这两种情况 ...

2500 + 构造题 CF1344B Monopole Magnets CF1344B Monopole Magnets | Legendgod’s Blog CF1385E Directing Edges CF1385E Directing Edges | Legendgod’s Blog CF1416B Make Them Equal CF1416B Make Them Equal | Legendgod’s Blog GCJ2015 还原集合 GCJ2015 还原集合 | Legendgod’s Blog CF1391D 505 CF1391D 505 | Legendgod’s Blog CF1380D Berserk And Fireball CF1380D Berserk And Fireball | Legendgod’s Blog CF1375E Inversion SwapSort CF1375E Inversion SwapSort | Legendgod’s Blog CF449C Jzzhu and Apples CF449C Jzzhu and ...

POJ 3613 Cow Relays POJ 3613 Cow Relays 真心想吐槽一下，这个不能用 $11$ 真的挺难受的。 首先看去像一个板子题，之后发现如果直接对于每个点建图的话时间是过不了的。 之后发现边的数量其实不是很多，一条边最多只有两个不同的点，所以实际上有用的点数是 $2m + 2$ 个。我们对于这个直接进行矩阵快速幂即可。 其实还有一个稍微难写一点的方法，我们考虑对于每一条边建立矩阵，之后如果两条边能互相到达就赋值为其权值，具体来说是 $i \to j, j \to z$ 边权分别是 $a_x, a_y$。那么图上 $G(x, y) = a_y, G(y, x) = a_x$。也就是具体表示走到了这条边的尽头的贡献。 那么我们发现 $n \ge 2$ 实际上我们考虑先让 $S$ 走到能走到的边的尽头作为答案矩阵。之后直接矩阵快速幂更新即可。 这个是我一开始想到的，后面发现其实离散化一下就可以了，所以就没写。 1234567891011121314151617181920212223242526272829303132333435 ...

SP1716 GSS3 - Can you answer these queries III SP1716 GSS3 - Can you answer these queries 也真是服了，浪费几分钟来搞这种题目。 直接线段树维护一下端点信息即可，具体来说就是左右端点的权值最大值，答案还有区间权值和。 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879808182838485868788899091929394#include <bits/stdc++.h>using namespace std;//#define Fread//#define Getmod#ifdef Freadchar buf[1 << 21], *iS, *iT;#define gc() (iS == iT ? (iT = (iS = ...

SP1716 GSS3 - Can you answer these queries III 可以初步理解一下动态 $\tt Dp$ 的思想，不用矩阵而已。题解 #2269. 「SDOI2017」切树游戏 题解，姑且先算完成吧，已经会全局平衡了，在码了。 全局平衡二叉树 树剖解法题解 说实在的这种码量还是少写吧，之后要以构造题为主

CF498E Stairs and Lines CF498E Stairs and Lines 肯定是状压，而且状压的就是轮廓线，我们考虑同时状压横着和竖着的情况。然后肯定需要进行矩阵快速幂复杂度还是很高的。 但是我们考虑我们当前位置和之前位置进行转移的时候使用的是竖着的线，而且横着的线仅仅在当前转移出现了，意味着肯定不会影响后面的计算。那么我们不妨枚举轮廓线，这样复杂度就是直接少了 $2^{7^3}$。 然后说几个细节，具体状态转移就自己推吧。我的写法是考虑当前位置和后面位置的衔接，对于也就是 $w_1$ 我们特殊处理一下 $w_0$ 也就是只有一个位置（存在竖线）是合法的。不然的话因为没有点所以只能是 $0$。 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879808182838485868788899091929394959697 ...