动态规划 题解 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 算法，主要思想是枚举寻找任意两点的最小割，每处理...

线段树 题解 http://codeforces.com/problemset/problem/833/Bhttp://codeforces.com/problemset/problem/833/B 题意 将一个长度为 的序列分为 段, 使得总价值最大, 一段区间的价值为区间内不同数字的个数. 分析 的区间DP以及各种瞎搞显然(然而考试时还是写爆了). 定义 表示前 i 个数分成 ...

树状数组 题解 OI https://arc068.contest.atcoder.jp/tasks/arc068_chttps://arc068.contest.atcoder.jp/tasks/arc068_c 题意 有一趟列车有 个车站, 从 0 到 M 编号. 有 N 种商品, 第 i 种只在编号 的车站出售. 一辆列车有一个预设好的系数 d, 从 0 出发, 只会在 d 的倍数...

贪心 题解 OI http://codeforces.com/problemset/problem/360/Ehttp://codeforces.com/problemset/problem/360/E 题意 个点, 条边的有向图, 其中给定条边可以在给定范围内任意修改边权, 判断并输出是否存在一种方案使的最短路比短. 分析 先令所有的边权都取到, 然后从开始单源最短路. 然后每次考虑一条边...

DP 题解 OI http://codeforces.com/problemset/problem/1209/E2http://codeforces.com/problemset/problem/1209/E2 这是一道最近 Codeforces 比赛的题目, 当时在场上昏昏欲睡, 连小的点都没有想出来, 现在再看一下. 题意 给你一个的矩阵, 可以对每一列的元素循环移位, 求每一行的最...