Day24h

CF

2019 Multi-University Training(2) 2019牛客暑期多校训练营(1) Record My Feelings(5) 动态规划(23) 图论(4) 字符串(3) 数学(20) 数据结构(8) 未归档(5) 模板(23)

/ 注册

全部文章 / CF （共37篇）

Into Blocks (easy version)

G1 - Into Blocks (easy version) 参考：Codeforces Round #584 - Dasha Code Championship - Elimination Round (rated, open for everyone, Div. 1 + Div. 2) G1...

贪心

2019-09-21

0 512

Cow and Snacks

D. Cow and Snacks 参考：Codeforces 1209D. Cow and Snacks 思路：利用并查集，构建一个生成树，然后树的边数就是能够开心的客人的人数。用一个条件find(u)!=find(v)（我在代码里反了一下），来统计某一种味道的菜是否已经被...

并查集

2019-09-18

0 516

Paint the Digits

C - Paint the Digits 思路：这道题就只需要利用单调栈，将整个数组扫一遍，求得的最后的栈内元素（要求全部小于非栈内元素）的颜色为1，其余为2 那么怎么实现呢？求最后的栈内元素（要求全部小于非栈内元素）的方法：用一个变量记录下最小的被交换的栈元素（这里需要将由于元素相等而...

单调栈

2019-09-15

0 386

Remainder Problem

F. Remainder Problem 这个其实并不难，只是看看考察有没有分块的思路思路：用一个ans[i][j]来记录所有k=(1~5e5)中所有a[k]%i==j的和，在查询的时候可以达到复杂度位O(1) 当然因为数据很大，不能够分很多块，而且也没有必要分很多块，因为...

分块

2019-08-24

0 452

Number Of Permutations

Number Of Permutations 思路：利用容斥，首先所有可能的排列肯定是fac[n]，然后可能会有三种 bad 的情况： ①第一个元素的排列是非递减 ②第二种是第二个元素的排列是非递减 ③这两个可能出现的重叠情况，意思就是说同时导致①②成立这个时候我们利用容斥...

容斥原理

2019-08-23

0 479

Complete the Projects

F1. Complete the Projects (easy version) F2. Complete the Projects (hard version) 参考：Complete the Projects 简单说就是当 b>=0 是肯定是 a 小的优先的，需要注意的就是 b&l...

贪心 dp

2019-08-14

0 415

Remove the Substring

D2. Remove the Substring (hard version) 思路：其实就是贪心吧，先从前往后找，找到 t 可在 s 中存在的最小位置（pre），再从后往前找，找到 t 可在 s 中存在的最大位置（last），然后 last [ i+1 ] - pre [ i ] - 1...

贪心字符串思维

2019-08-14

0 436

Compress Words

E. Compress Words 直接套 KMP 即可（那为什么打 cf 的时候没有想到...），求出后一个单词（word）的前缀数组，然后从前面已得的字符串的末尾 - word. length () 开始查询利用前缀数组进行优化即可代码: // Created by CAD o...

字符串 KMP 前缀函数

2019-08-12

0 430

White Lines

D. White Lines 主要思路就是利用差分对于行：如果在某一个点上，向右下角涂掉 k*k 的矩形能够使得新出现一行 “B” 那么就在这个点上 +1（这里的加 +1 需要利用差分来完成）列同理，如果有现成的空白行，记录一下即可，最后直接加上代码： // Created b...

差分

2019-08-12

0 335

You Are Given a WASD-string...

C. You Are Given a WASD-string... 主要看的还是思维，分别求出在上下左右四个方向移动的最大幅度（ mov_up, mov_down, mov_right, mov_left ）然后对于垂直方向如果 mov_up == mov_down 那么 robot 最后的...

思维

2019-08-09

0 487