何事秋。

分类

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篇）

Codeforces Round #289 (Div. 2) F. Progress Monitoring （计数类dp、记忆化搜索、区间dp）

题目链接题面：题意：给定一棵树的 dfs 方式和 dfs序，问满足这个dfs序的不同的树有多少棵。题解：表示状态： dp [ i ] [ j ] = numbers 表示 a [ i to j ] 这些节点，以 a [ i ] 为根所能构成的树的方案数。找出答案： ans =...

2020-09-04

0 441

Codeforces Round #292 (Div. 2) D. Drazil and Tiles （拓扑序）

题目链接题面：题意：给出一个N×M 的网格，一些位置是障碍，其他位置是空地，求是否存在一个用 1×2的骨牌（可以转成 2×1）铺满空地的方案，以及方案是否唯一。骨牌不能放到网格以外，不能重叠，不能覆盖在障碍物上。 N,M≤2000 题解：如果一个空地的周围四联通部分只有一个空...

2020-09-04

0 512

Codeforces Round #292 (Div. 2) E. Drazil and Park （RMQ）

题目链接题面：题意：给定一个圆，圆上有n个点，每个点有个属性 hi，第 i 个点与第 i + 1个点距离为 di 定义两个点之间的距离为 2*（hx + hy） + dis （x，y）。从 x 到 y 可以顺时针走也可以逆时针走，中途会途径其他点（位于所走一侧的x与y之间的点会被途径）...

2020-09-04

0 486

Codeforces Round #293 (Div. 2) D. Ilya and Escalator ( 概率dp )

题目链接题意： n个人排队按顺序上电梯，若某一时刻轮到某人上电梯了，他上电梯的概率为p，不上电梯的概率为 1-p，若他不上电梯，那么他后面的人不能上电梯。问，t 时间电梯上人数的期望。题解：感觉自己越来越垃圾了，这个题都不会了。设 dp [ i ] [ j ] 为 i 时间电梯上有 ...

2020-09-04

0 688

Codeforces Round #294 (Div. 2) E. A and B and Lecture Rooms （LCA）

题目链接题面：题意：给定一棵树。有m个询问，每个询问给出 a，b 两点，问树上到 a，b 距离相同的点有多少个。树上两点之间的距离为两点之间的最短距离。题解： ① a==b 那么 n个点与a，b的距离都相同 ans = n ②若dis（a，b）为奇数，那么没有任何点与a，b的距离...

2020-09-04

0 458

Codeforces Round #293 (Div. 2) E. Arthur and Questions （思维、贪心）

题目链接题面：题意：给你a1----an，k，要求a [ 1 ] + … + a [ k ] < a [ 2 ]+ … + a [ k+1 ] < a [ 3 ] + … + a [ k+2 ]<…，然后这里的 ai 有可能是 ?，要求你填 ? 的数字，使 a1~an ...

2020-09-04

0 1003

Codeforces Round #296 (Div. 2) E. Data Center Drama （欧拉路）

题目链接题面：题意：给定一张无向连通图，你需要添加最少的边并且给每条边定向使得每个点的入度和出度都是偶数。 into groups of two 一度在纠结是分成两组，还是每组两个。。。。。导致读题没读懂。题解：考虑欧拉回路。在欧拉图中，每个点的度数都是偶数，所以我们可以先把...

2020-09-04

0 731

VK Cup 2015 - Qualification Round 1 D. Closest Equals （主席树）

题目链接题面：题意：给定一个数组 ai，有m个询问，每个询问给定 l ，r 去区间 [ l , r ] 中相同的数字的最近距离。题解：考虑主席树。当前是第 i 个数据，即 a [ i ] , 设 p [ a [ i ] ] 是 a [ i ] 之前离 a [ i ] 最近的相同的...

2020-09-04

0 795

SDUT 4784 - 猜数字（区间dp）

题目链接题面：小明发现了一个好玩的游戏，他想和大家分享，游戏的名字叫做“猜数字”。游戏会告诉你一个数字n，表示答案在1到n之间，你每次可以猜一个数字，如果猜中了，获得游戏胜利，但如果猜错了，你将要花费你所猜数字的金币，并得知是猜大了还是猜小了。小明想知道，他至少需要准备多少金币能确保获得游戏...

2020-09-04

0 566

SDUT 4778 - Cut the tree （树上启发式合并）

题目链接题面： Cut the tree Description 给一个具有 N 个节点的有根树，以 1 号节点为根，节点编号从 1 开始，点有点权。树的第 H 层权值为深度为 H 的所有点的点权之和。树的总权值为所有层权值的最大值。问分别割掉以 1,2,…,N 为根的子树后，...

2020-09-04

0 422