Fat Old Eight's Blog

一道 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

数论全家桶？ 题意描述 完整版 简单版： 给定 $g,n(g,n\le10^9)$，求 $g^{\sum_{d\mid n}{C_{n}^{d}}} \mod{999911659} $。 做法 首先根据欧拉定理推出： $$ g^{\sum_{d\mid n}{C_{n}^{d}}} \equiv g^{\sum_{d\mid n}{C_{n}^{d}}\mod{999911658}} (\bmod{99... Read More

前因 今天端午放假，明天返校，一般来说，今天怎么说都会出勤，但是考虑到以往清明、五一出勤的经验，今天肯定很多人，所以不如不去。于是在洛谷犇犇上面发了一句： 不出意外明天會直播寫UVA12421，主要明天可能會沒事干 然后，不出意外地，出意外了，主要是舟太好玩了，然后有两把都寄在第六... Read More

题意 题目链接 给定两颗结点数为 $n$ 的树 $T1$ 和 $T2$，定义 $dis(T,x,y)$ 表示在树 $T$ 上 $x$ 到 $y$ 的路径上所有边的权值和。 现在求 $\forall x \in [1,n] , \min\limits_{1\le y\le n,x\neq y}dis(T1,x,y)+dis(T2,x,y)$。 一道相当好的题。 此题 $O(n\log^2{n... Read More

其实谈不上学习笔记。 在谈平衡树之前，我们需要知道一种二叉树： 二叉查找树（BST） 性质 二叉查找树满足一种性质，即对于该树上的任意一个节点： 该节点的权值不小于它左子树上所有节点的权值。 该节点的权值不大于它右子树上所有节点的权值。 显然一颗 BST 的中序遍历就是一个权值非严格单调递增的节点序列。 在一颗 BST 上面，可以实现 插入、删除、查找排名、查找第 ... Read More