Fat Old Eight's Blog

上课根据回忆重新推了一遍，发现不会同余方程了。 题意 给定 $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

写在前面 因为本人太菜，所以大部分东西都只有结论，没有证明。 以及如果真的想学习网络流的话，建议去看OI Wiki。 概述 一个网络 $G=(V,E)$ 是一张有向图，图中每一条边都有一个给定的权值 $c(x,y)$，称为边的容量，特别地，若 $(x,y)\notin E$，则 $c(x,y)=0$。图中还有两个特殊点，$S\in V$ 和 $T\in V(S\ne ... Read More

题意描述 链接 实现插入、删除、查找排名、查找第 $k$ 大、查找前驱、后继。 很明显的平衡树，但是这里我介绍一种非常规做法——分块。 虽然是 $n\sqrt{n}$ 做法，但是依据数据范围还是可以过的。 做法 首先我们需要处理一个难点：插入。因为一般的分块都是根据数组来实现，所以仅仅是插入就需要 $O(n)$ 的时间复杂度，并且会给维护带来一定的麻烦，这是所不能允许的。 所以需要上另外一种数据... Read More