Fat Old Eight's Blog

懂不懂什么叫 $O(\frac{n^2}{\omega})$ 啊。 题意 P5513 [CEOI2013] Board 思路 首先给每个节点编个号，类似于线段树，设当前节点为 $x$，则左儿子为 $2x$，右儿子为 $2x+1$。 这样我们就能用一个二进制数表示每个节点的位置。 并且容易发现，点 $x$ 和点 $y$ 之间的最短路为： $$ \min\limits_{a,b}{ (\l... Read More

加密文章。

寫在前面： 因爲 Feed，寫完之後被發到羣裏給大家欣賞了一番。 經過競標後更改了標題。 原標題：数据结构专题略解 一个数据结构的专题题解。 无详有略。 有些题可能以后会单独写一篇。 虽然是校内的专题但是都是在洛谷上面抓的就不加密了。 相逢是问候 势能... Read More

有趣。 以及要分清反轉和翻轉。 题意 试验板有 $n$ 行 $m$ 列，每个行列交叉处有一个节点。试验板每侧都有端口。左、右侧各 $n$ 个端口，上、下侧各 $m$ 个端口。每个端口是红色或蓝色。 端口可通过导线连接。 每根导线连接一红色端口和一蓝色端口，每个端口最多连一条导线。 导线的每个部分水平或垂直。 导线不能在节点之外的地方和其他导... Read More

傻波学校测评机，模拟赛直接吞我 25 分。 题意描述 题目链接 给定一个 $n$ 个点，$m$ 条边的有向图（不保证没有重边）,经过第 $i$ 条边花费 $w_i$ 的费用，定义一次操作的费用为： 选择一个起点 $s_i$，终点 $t_i$ 以及一条 $s_i$ 到 $t_i$ 的路径，访问路径上经过的所有点。这部分的代价为路径的费用。但是如果 $s_i \neq t_i$，则需... Read More

一道 2800，做了一个月。 首先题目给了我们极好的提示，是让我们求半径的最小值。此时我们就可以考虑将其转化为直径，定义一棵树的直径 $d=\max{a_u+a_v+d_v(v)}$。 此时半径 $r=\lceil\frac{d}{2}\rceil$。 证明较为显然且其他题解均有较为详细的证明，所以故不再赘述。 现在的问题转化为了求 $d$。 考虑修改对 $d$ 的影响，设原直径端点为 $u,v$，当 $d_x... Read More

开 unr 打的，一上来就开的 F…… 稍微参考了官方题解。 题意 给定 $n$ 张牌，正面的数为 $a_i$，背面的数为 $b_i$。 现在有 $m$ 个机器，参数为 $(x_i,y_i)$，有二分之一的概率翻转第 $x_i$ 牌，剩下的二分之一翻转第 $y_i$ 牌。 求出所有对于选取机器的集合 $S$ 中，使得所有牌正面的数之和的期望值最大。 思路 令最优... Read More

上课根据回忆重新推了一遍，发现不会同余方程了。 题意 给定 $n$ 组非负整数 $a_i, b_i$ ，求解关于 $x$ 的方程组的最小非负整数解。 $$ \begin{cases} x \equiv b_1\ ({\rm mod}\ a_1) \\ x\equiv b_2\ ({\rm mod}\ a_2) \\ … \\ x \equiv b_n\ ({\rm mod}\ a_n)\end... Read More

题目连接 感觉这题思路比较像 P2402，但是稍微复杂一些。 做法 首先我们假设没有天兵的情况。 不难想到，超能力是在每个兵都不能移动时使用，这样显然不劣。 其次，一定是骑兵与步兵互相交换。 于是可以先预处理出对于每个兵 $K_i$ 到目标格子 $T_j$，记为 $dis_{i,j}$。 然后，再二分超能力的使用次数，记为 $mid$。 这里进行建模： 源点向每个兵建一条边，容量为 ... Read More

题目描述 做法 首先晃眼一看：这不是网络流傻子题吗？ 于是立刻建了个图跑最大流： 建立源点 $S$，向第 $i$ 个点建立一条容量为 $p_i$ 的边； 建立汇点 $T$，第 $i$ 个点向 $T$ 建立一条容量为 $s_i$ 的边； 对于所有的 $i<j$，由 $i$ 向 $j$ 建立一条容量为 $c$ 的边。... Read More