何事秋。

分类

AC自动机(4) bfs/dfs(5) bitset(3) CF刷题(23) dp一般看规律(11) dp基本算法(12) KMP(2) LCA(1) LCT(4) Prufer(2) SAM(3) STL(1) tarjan(1) 主席树/线段树(14) 二分/三分(2) 二分图(1) 位运算(1) 偏序问题(2) 分块(1) 分治/点分治/边分治(2) 单调栈(2) 单调队列(1) 博弈/sg(3) 博弈论基本算法(11) 后缀数组(1) 启发式合并(1) 哈希(4) 回文自动机(2) 图论一顿套模板(3) 图论基本算法(31) 基本算法(2) 多项式(1) 套题(1) 字典树(1) 字符串基本算法(27) 容斥(1) 平衡树/堆(2) 并查集(3) 序列自动机(1) 快速幂/矩阵快速幂(1) 思维只会A+B(5) 投稿(2) 拓扑序(1) 数位dp(1) 数学不好先打表(4) 数据结构基本算法(69) 数据结构瞎乱写(8) 数论分块(1) 数论只会gcd(20) 数论基本算法(64) 暴力(1) 最短路(3) 期望/概率(1) 期望dp/概率dp(1) 构造(3) 枚举(3) 树形dp(3) 树链剖分(5) 模拟只会猜题意(5) 生成树(1) 签到题(2) 线性dp(12) 线性基(2) 组合数学(1) 组合数学靠运气(2) 结论题(2) 网络流/费用流(5) 网络流基本算法(5) 群论(2) 背包dp(1) 莫比乌斯反演(1) 莫队(1) 虚树(1) 计数类dp(1) 计算几何(8) 计算几何基本算法(15) 贪心刚好过样例(3) 随机化算法(2)

/ 注册

全部文章（共461篇）

7-3 2020 CCPC Wannafly Winter Camp Day1 C. 染色图

定义一张无向图 G=⟨V,E⟩ 是 k 可染色的当且仅当存在函数 f:V↦{1,2,⋯,k} 满足对于 G 中的任何一条边 (u,v)，都有 f(u)≠f(v)。定义函数 g(n,k) 的值为所有包含 n 个点的无自环、无重边的 k 可染色无向图中的边数最大值。举例来说，g(3,1)=0,g(3...

2020-09-04

0 405

7-1 2020 CCPC Wannafly Winter Camp Day1 A. 期望逆序对

有 n 个独立的随机变量，其中 xi 的值是一个从 [li ,ri ] 中随机选取的整数，即对于 [li ,ri ] 中的任何一个整数 j，xi =j 的概率都是 (ri −li +1)−1 。现在你需要给出一个长度为 n 的排列 p，那么可以得到一...

2020-09-04

0 575

7-6 2020 CCPC Wannafly Winter Camp Day1 F. 乘法（二分）

给出一个长度为 n 的数列和一个长度为 m 的数列，可以构造得到一个 n×m 的矩阵 C，其中 Ci,j =Ai ×Bj 。给出整数 K，你需要求出 C 中第 K 大的数的值。输入格式：第一行输入三个整数 n,m,K(1≤n,m≤105 ,1≤K≤n×m)。第...

2020-09-04

0 392

7-8 2020 CCPC Wannafly Winter Camp Day1 H. 最大公约数

这是一道钓鱼小王子，秒出的题，至今我也不会证明。有三个人，A,B,C，其中 A 和 B 共享了一个神秘的数字 k，已知 1≤k≤n。现在 A 和 C 说：“k 的值等于 x”。 C 不太信任 A，于是想向 B 确认一下 k 是否真的等于 x。B 虽然不想直接把 k 的值告诉 C，但是 B 允...

2020-09-04

0 401

笛卡尔树

例①、POJ 2201：题目：笛卡尔树：笛卡尔树中的每个节点有两个数据域key，val，对于数据域key，满足二叉搜索树性质，对于数据域val，满足最小堆性质。给出N个节点，1<=N<=50000，每个节点由一对key，val构成，判断能否根据这些节点构建一颗笛卡尔树，如果可以构建则...

2020-09-04

0 493

P5435 【模板】快速 GCD：

一种 O( 值域 )时间预处理 O(1) 时间求最大公约数( gcd )的算法 #include<iostream> #include<cstdlib> #include<cstdio> #include<algorithm> #include<...

2020-09-04

0 379

P4783 【模板】矩阵求逆

题目描述求一个N×N的矩阵的逆矩阵。答案对10^9+7 +7取模。输入格式第一行有一个整数N，代表矩阵的大小；从第2行到第N+1行，每行N个整数，其中第i+1行第j列的数代表矩阵中的元素aij 。输出格式若矩阵可逆，则输出N行，每行N个整数，其中第ii行第jj列的数代表逆矩阵中的元...

2020-09-04

0 440

P4929 【模板】舞蹈链（DLX）

题目背景本题是舞蹈链模板——精确覆盖问题题目描述给定一个N行M列的矩阵，矩阵中每个元素要么是1，要么是0 你需要在矩阵中挑选出若干行，使得对于矩阵的每一列j，在你挑选的这些行中，有且仅有一行的第j个元素为1 输入格式第一行两个数N,M 接下来N行，每行M个数字0或1，表示这个矩阵 ...

2020-09-04

0 687

P5903 【模板】树上 k 级祖先

给定一棵 n 个点的有根树。有 q 次询问，第 i 次询问给定 xi, ki，要求点 xi 的 ki 级祖先。保证ki合法。一、树链剖分——重链剖分 O（n+qlogn）： 7.46s #include<iostream> #include<cstdio> #i...

2020-09-04

0 490

P3919 【模板】可持久化数组（可持久化线段树/平衡树）

其实就是用主席树来实现的可持久化数组： #include<iostream> #include<cstdio> #include<algorithm> #include<cstring> #include<string> #include...

2020-09-04

0 348