何事秋。

CF刷题

AC自动机(4) bfs/dfs(5) bitset(3) 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)

/ 注册

全部文章 / CF刷题（共23篇）

Codeforces Round #291 (Div. 2) D. R2D2 and Droid Army （思维）

题目链接题面：题意：有n个机器人站在一排，每个机器人有m个属性值，第 i 个机器人的第 j 个属性值为 a [ i ] [ j ] 。我现在有一把能发射 k 发子弹的枪，我可以选择每发子***类（如果某发子弹的种类为 j ，则其只能对所有机器人的 j 属性值造成伤害，使所有机器人的 j...

2020-09-04

0 411

Codeforces Round #291 (Div. 2) E. Darth Vader and Tree （dp + 矩阵快速幂优化）

题目链接题面：题意：有棵无限大的有根树,每个节点都有N个孩子,每个孩子距离父亲节点的距离为di.求距离根节点距离<=x的节点个数。题解：注意到 di <= 100 我们设 dp [ i ] 为距离根节点为 i 的点的个数，sum [ i ] 为距离根节点小于等于 i ...

2020-09-04

0 664

Codeforces Round #289 (Div. 2) C. Sums of Digits （思维、贪心）

题目链接题意：给定一个由递增序列的每个数的各位数字之和组成的序列，还原这个递增数列，并且使递增数列的 an 最小。题解：贪心策略，尽量使当前的数接近上一个数且大于等于上一个数+1 假设 b[i]>b[i-1],那么就在上一个数的基础上，从低位到高位如果某一位不足9，就把某一位+...

2020-09-04

0 447

Codeforces Round #289 (Div. 2) E. Pretty Song （数论、概率）

题目链接题面：题意：给定一个字符串s，计算其中各子串中A、E、I、O、U、Y所占比例，输出比例之和。题解：假定sum[i]表示1~i中元音字母的个数，len表示字符串总长度，字符串从下标1开始。对于长度为1的子串，每个元音字母都要用1次，即(sum[len] -sum[0])...

2020-09-04

0 455

Codeforces Round #289 (Div. 2) D. Restoring Numbers （思维、构造）

题目链接题面：题意： v [ i ] [ j] = ( a [ i ] + b [ j ] ) %k 现在给定一个n*m的矩阵w，问w能不能由以上方式构造出来，若不能输出NO。若能输出YES，并且输出k，a1–an，b1–bm 贴一下官方题解：题解翻译：我们发现，如果 ai ，...

2020-09-04

0 384

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) 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