Fat Old Eight's Blog

寫在前面： 因爲 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

题目描述 给⼀棵树，现在有两种操作： 标记某⼀个节点； 找到路径 $a$ 至 $b$ 中在第 $y$ 次操作到当前操作之间没有被标记的第 $k$ 个节点。 保证每个节点只会被标记一次。 完整题面 思路 首先用可持久化线段树维护树剖，对于修改操作直接修改即可，对于查询，直接在树剖上跳，如果未标记节点小于 $k$ 输出 -1，否则输出答案。 实现 这道题个人认为最大的... Read More

請使用學校通用密碼,大小寫敏感 1919810 efd23775cd584a163d0cba6bc13296097723d497 1lfsoTtdTVQHpt2HXr7JLr7m4uygMUbAaSb+iDhROQrZ2InVlGMdoyu/cN0dSi2+NCvh6... Read More