吴国庆

分类

acm(50) Codeforces(6) Xcpc(4) 未归档(2) 算法学习(6) 题解(38)

/ 注册

全部文章（共106篇）

Codeforces Round #556 (Div. 1) B - Three Religions DP

B - Three Religions DP Question：现有一个主串S 和三个空串 A,B,C(只含小写字母)。问每次操作后 S 是否能包含 A B C (在保证 A B C 串内字母顺序不变的情况下组成S的一个子序列) 操作是在某个串后面添加或删除字母一共q次操作 |A| ,|B|...

2020-05-04

0 537

Codeforces Round #619 (Div. 2) E. Nanosoft 前缀和

E. Nanosoft Question: 定义一个logo 形状颜色如下类推，现在有一个关于logo的颜色矩阵长n宽m 并有q次询问：r1,c1 r2,c2 直接最大的logo有多大 n,m<=500 q<=1000; Solution: 记录每种颜色数量的二维前缀和，那么对...

2020-05-04

0 592

Codeforces Round #532 (Div. 2) E. Andrew and Taxi 二分+拓扑序

Andrew and Taxi Question：给一n个节点m条边的有向有权图现可以改变其中一些边的方向总代价是这些边的最大值，问使该图无环的最小花费 n,m<1e5 Solution：由于代价为所有边的最大值，想到二分然后对所有大于mid的边进行拓扑排序后，如果没有环那mi...

2020-05-04

0 515

树链剖分入门

例题 POJ 3237（） BZOJ 3083 BZOJ 3531 BZOJ 3589 BZOJ 3626 将树上问题通过dfs序的性质转换为区间问题，从而对树上修改时就可转化为相应的区间修改。再通过引入重儿子，重链一系列概念将时间复杂度也变成了可以接受的层次通过两次dfs求出树上一系列的信息 ...

2020-05-04

0 552

二分图

总结二分图的最大匹配：匈牙利算法二分图的最小点覆盖数 = 二分图最大匹配数二分图最大独立集 = 总点数 - 二分图最大匹配数（有向无环图）不可重叠最少路径覆盖数=原图点数 - 二分图的最大匹配二分图多重匹配就是在匈牙利算法上加上一维 limit 的维度（可以引入源点和汇点进而转化成最...

2020-05-04

0 731

Codeforces Round #626 Instant Noodles

l链接 Answer ：本题突破口在于 gcd ⁡ ( ...

2020-05-04

0 482

Codeforces Round #625 World of Darkraft: Battle for Azathoth

链接 Answer ：可以把怪兽看成二维坐标上的一些点，每个点有一些权值。然后对于所有的x=ai（攻击）的轴上都有m个bi（防御）那么对于每一个bi它所能打死的所有怪兽就是当前的轴的左面所有y小于bi的怪兽所以问题就转化为一个区间求和+区间最大值的问题用线段树维护就好了坑点:把握好题目给...

2020-05-04

0 579

2017 CCPC 哈尔滨

8/13 Permutation A Simple Stone Game Geometry Problem K-th Number Palindrome Color a Tree X-Men Server Interview ...

2020-05-04

0 668

2017 icpc 沈阳

6/13 Little Boxes Rabbits Heron and His Triangle Infinite Fraction Path Tree Wandering Robots 链接就这几个题目来说感觉都偏技巧性，考验思维能力...

2020-05-04

0 686

2019 ccpc 哈尔滨

文章目录 Justifying the Conjecture Fixing Banners Keeping Rabbits Interesting Permutation Exchanging Gifts Binary Numbers Artful...

2020-05-04

0 830