吴国庆

acm

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

/ 注册

全部文章 / acm （共50篇）

HDU-2243考研路茫茫 AC自动机 + 矩阵快速幂

hdu-2243 n个模式串，求满足长度小于等于k且至少包含其中一种模式串的串数（只包含小写字母） k<2^31-1 多模式串的计数问题，我们用AC自动机来解决那么问题来了 1）怎么求至少包含一种的串数？正难则反，我们用所有串数减去一种都不含的就是至少包含一种的方案 2）所有长度小于等...

2020-05-04

0 526

Codeforces Round #618 E. Water Balance 贪心

Water Balance 题意: n个数可进行以下操作任意次：选择区间【l，r】其中的A【i】都变成这个区间的平均数，要求最小字典序思路：由于最后答案使单调不减的那假设前i个元素答案以求出，看当前位置的元素能否对当前答案优化，即前面元素的个区间答案加上当前元素能否使区间均值变小，一...

2020-05-04

0 539

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

Codeforces Round #625 World of Darkraft: Battle for Azathoth

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

2020-05-04

0 579

Codeforces Round #629 (Div. 3)

第一次AK写篇题解庆祝一下~~ 文章目录 A.Divisibility Problem B. K-th Beautiful String C. Ternary XOR D. Carousel E. Tree Queries F. Make k Eq...

2020-05-04

0 531

Codeforces Round #630 (Div. 2) E. Height All the Same 思维

链接操作1可以将所有的高度变成0 or 1（像俄罗斯方块一样）并且这其中的0和1可以全局互换操作2和操作1可以移动这些1，并且将相邻的0 0 -> 1 1 那么问题就转换成，放置偶数个位置0，或偶数个位置1 所以当n*m%2==1时 0和1总会有一个是偶数否则，也可以简单的构造出一...

2020-05-04

0 497

Master of Data Structure 虚树

链接 m<2000 建虚树后暴力维护虚树中两点间的实际点的个数模拟即可巨丑的代码 #pragma GCC optimize(2) #include<bits/stdc++.h> #define ls rt<<1 #define rs rt<<1|1 ...

2020-05-04

0 533

Educational Codeforces Round 86 (Rated for Div. 2) E - Placing Rooks

链接想使所有格子全被覆盖，要么所有行都有棋子，要么所有列都有棋子。假设现在是所有行都有棋子，那么其中k对棋子互相攻击就可以看成n-k列放n个棋子。那么答案就为2*C(n,n-k)*把n个物品放n-k个集合的方案数。最后一项为第二类斯特林数，记S｛n,k｝为n个物品放k个集合的方案数公...

2020-05-04

1 603