xyq0220

未归档

题解(3)

/ 注册

全部文章 / 未归档（共101篇）

Codeforces 1272 A-E

Codeforces 1272 A-E A Three Friends 直接枚举所有情况，共\(3\times 3\times 3=27\)种。 code #include<bits/stdc++.h> #define fi first #define se second #de...

2019-12-13

0 322

2018CCPCFINAL B Balance of the Force 枚举最大值

题意 n个人能选择黑暗面和光明面，选择两个面分别能获得\(L_i\)和\(R_i\)的力量，有m对人不能选择同一面，问n个人的力量中的最大值-最小值尽可能小为多少。 \(1<=n<=2\times 10^5\) \(0<=m<=2\times 10^5\) \(1&l...

枚举

2019-10-26

0 395

Comet OJ - Contest #13 「佛御石之钵 -不碎的意志-」(困难版) 并查集

题意给一个$ n \times m$ 的网格，每个格子里有一个数字，非 \(0\) 即 \(1\)，行从上往下依次编号为 \(1, 2, \cdots, n\)，列从左往右依次编号为 \(1, 2, \cdots, m\)。给 \(q\) 次操作，每次给定一个以 \((x_1,y_1)\) ...

并查集

2019-10-25

0 402

codeforces 1249 D2 Too Many Segments (hard version) 贪心+树状数组

题意给定n个线段，线段可以相交，第\(i\)个线段覆盖的区间为\([l_i,r_i]\)，问最少删除多少个线段让覆盖每个点的线段数量小于等于k。分析从左往右扫每个点\(x\)，若覆盖点\(x\)的线段数cnt大于k，则贪心的删去覆盖点\(x\)的线段中\(r_i\)前\(cnt-k\)大...

树状数组贪心

2019-10-24

0 414

codeforces1213G Path Queries 并查集

题意给定n个结点的树，每条边有边权，有m个询问，每个询问给一个\(q_i\)输出树上有多少点对的简单路径上最大的边权不超过\(q_i\)。分析用并查集维护点集，同时维护大小。将所有边按边权排序，考虑每次从小到大加边，图中经过当前边的所有路径一定是以当前边的边权为最大值的，用并查集维护...

并查集

2019-10-23

0 411

codeforces1213F tarjan缩点+拓扑排序

题意给定两个长度为n的排列p和q，构造一个字符串s满足\(s[p_i]<=s[p_{i+1}]\)和\(s[q_i]<=s[q_{i+1}]\)，且满足字符串中不同字符的个数不少于k。分析建一个有向图，\(p_i\)到\(p_{i+1}\)连一条有向边，\(q_i\)到\(q...

tarjan 拓扑排序

2019-10-23

0 399

【模板】线性基求交

线性基求交 struct lb{ ll p[63]; lb(){ memset(p,0,sizeof(p)); } void clear(){ memset(p,0,sizeof(p)); } void ins(ll x){ for(int i=60;i>...

线性基

2019-10-05

0 433

大数模板

class BigNum { public: static const int MOD = 100000000; static const int BIT = 8, SIZE = 105; mutable int n,o; long long u[SIZE]; ...

高精度/大数

2019-09-27

0 377

HDU-2243 考研路茫茫——单词情结 AC自动机+矩阵快速幂

题意给n个模式串，问有多少个长度不超过L的字符串中至少出现一种模式串。分析有多少个长度为L的字符串中不出现任意一个模式串的题已经做过，构造一个矩阵\(A\)，答案\(s_n\)即为\(s_0*A^n\) 用矩阵快速幂算下就行了，这题的计算方法就显然是\(26^0+26^1+26^2+\...

AC自动机矩阵快速幂

2019-09-26

0 485

HDU-2222 Keywords Search AC自动机模板

题意给n个模式串，一个文本串，问文本串中出现了多少个模式串。分析 AC自动机模板 Code #include<bits/stdc++.h> #define fi first #define se second #define pb push_back #define lso...

AC自动机

2019-09-25

0 388