动态规划 题解 OI http://acm-uestc-edu-cn-s.vpn.uestc.edu.cn:8118/contest/172/summaryhttp://acm-uestc-edu-cn-s.vpn.uestc.edu.cn:8118/contest/172/summary A 首先考虑经典的 LCS 做法: 指考虑了 的前 个字符和 的前 个字符的答案. 本题...

数据结构 题解 OI http://acm-uestc-edu-cn-s.vpn.uestc.edu.cn:8118/contest/171/summaryhttp://acm-uestc-edu-cn-s.vpn.uestc.edu.cn:8118/contest/171/summary A 首先对于每个物品，连续整除 d，匹配到能打开的最小钥匙。在钥匙编号从大到小排序后，可以 完成这一...

图论 题解 OI http://acm-uestc-edu-cn-s.vpn.uestc.edu.cn:8118/contest/170/summaryhttp://acm-uestc-edu-cn-s.vpn.uestc.edu.cn:8118/contest/170/summary A POJ2914 Lutece 2710 Minimum Cut C 容易证明只有行号列号之和奇偶性相同...

图论 题解 OI https://www.luogu.com.cn/problem/P4208https://www.luogu.com.cn/problem/P4208 题意 求 个节点, 条边的无向图的不同的最小生成树个数. 问题本身的性质 多尝试几个样例可以发现, 同一个图的所有最小生成树中, 相同边权的边的数量是一定相等的. 通过 Kruscal 算法的贪心过程容易证明这个结论:...

图论 题解 OI https://www.luogu.com.cn/problem/P4716https://www.luogu.com.cn/problem/P4716 题意 最小树形图是有向图上，从给定的根节点出发到达所有节点的一颗生成树。 分析 求解最小树形图的一种算法是的朱刘算法。 考虑给除根节点外的每个点寻找一条最小的入边，如果找出的入边恰好构成一棵树，则容易证明这样的情况1是最优...

图论 题解 OI http://poj.org/problem?id=2914http://poj.org/problem?id=2914 题意 个点 条边（最多完全图）的带权无向图，问至少删去的边权之和，使删边后图不连通。（任意两点的最小割）。 分析 显然枚举两点用最大流最小割来求跑不过。介绍此类问题的模板做法：Stoer-Wagner 算法，主要思想是枚举寻找任意两点的最小割，每处理...

比赛 OI https://acm.uestc.edu.cn/contest/151/summaryhttps://acm.uestc.edu.cn/contest/151/summary A. 双十一 每种货物从最便宜的商店买即可。注意不要把 n 和 m 看反了。 12345678910111213141516171819202122232425int prices[MAXN][MAXN]...

OI 感觉这场 Div.2 有点水啊, 为什么我这个 AFO 的选手都能过 5 道题... A. Happy Birthday, Polycarp! 签到题, 不多说. 12345678910111213141516171819202122int main() { int tcnt = read(); for (int T = 1; T <= tcnt; T++) { ...

总结 OI Day 0 瘟疫公司真好玩. Day 1 早上起来没去学校直接去考场, 还是那个熟悉的清水河校区. 不过七点钟才起床到考场到的时候有点晚了, 简单看了两眼 CSP 考前急救, 大概把 cdfls 的人都膜了一圈就进去了. 进去之后发现和 dbw 和 dqw 坐的比较近, 遂膜之. 吐槽一下 dbw 和他的右桌之间的隔板没有了, 一览无余...(其实玻璃隔板, 有也一览无余), 然...

OI 背板 Exgcd 求逆元 123456789101112131415161718int64 exgcd(int64 a, int64 b, int64& x, int64& y) { if (b == 0) { x = 1; y = 0; return a; } int64 d = exgcd(b, a % b...