Day24h

分类

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

/ 注册

全部文章（共131篇）

Vasya and Robot

C. Vasya and Robot 关键算法：二分、前缀和刚看到题的时候一点想法都没有... 先观察一下数据范围$(1≤n≤2⋅10^5)(−10^9≤x,y≤10^9) $ 可以用两个数组\(x[i],y[i]\)来表示在\(i\)操作完之后的机器人的位置 fo...

前缀和二分

2020-01-12

0 351

Monitor

Monitor 该题的目标对象是一个二维数组 ①该题没有给出二维数组的具体范围，而只是给出了\(n*m<=1e7\) 不能够直接定义数组，那么就可以进行动态开辟数组 vector<vector<int> > a(n+5,vector<int&g...

前缀和差分

2020-01-12

0 357

前缀和

前缀和一维：构建前缀数组： for(int i=1;i<=n;++i) a[i]+=a[i-1]; 应用场景： ①求 \(a[1]～a[i]\)的累加和 ans=a[i]; ②求\(a[i]～a[j](j>=i)\)的累加和 ans=a[j...

前缀和

2020-01-12

0 344

一维差分和二维差分

差分一维：原数组：\(c[i]\) 差分数组\(a[i]\)：表示\(i{\sim}n\)的数，每一个数\(c[j](i<=j<=n)\)都加上一个\(a[i]\) 应用场景： ①把从第\(k～n\)位的数都加上一个\(w\) a[k]+=w; ②...

差分

2020-01-12

0 619

Median on Segments (Permutations Edition)

E1. Median on Segments (Permutations Edition) 参考：CF1005E1 Median on Segments (Permutations Edition) 思维中位数为m的条件为，在那一段中，小于 m 的数的个数为 x 个，大于 m 的数有 y...

中位数思维

2020-01-11

0 433

Polycarp and Div 3

D. Polycarp and Div 3 参考：1005D - Polycarp and Div 3 做这道题要明白一些东西：能够被3整除的数，其数位之和为3的倍数如果把数分成一位一位，相邻三个不为0位置一定能够组成一个被3整除的数（111，112，121，122，...

2020-01-11

0 405

Dr. Evil Underscores

D - Dr. Evil Underscores 参考：Codeforces Round #613 (Div. 2) Editorial 其实比赛的时候就已经想到了基本上一样的解法，可是最后还是没有写出来... 具体思路就是分治，在二进制中，如果\(a_1{\sim}a_n\)...

分治

2020-01-11

0 480

Garland

C - Garland 参考：Codeforces Round #612 (Div. 2) A~E2 题解试了试暴力的方法，感觉不大行，所以转战dp 总共有四个状态\(dp[x][i][j][bj]\)，表示还有 i 个奇数，j 个偶数可以使用，x~n 位置的复杂度之和的最小值，且位...

dp

2020-01-08

0 452

Hyperset

B - Hyperset Codeforces Round #612 (Div. 2) A~E2 题解如果直接枚举的话，复杂度是\(O(n^3)\)，显而易见会超时，但是我们会发现一个道理，当其中两个确定的时候，另外一个也就已经确定下来了，而我们要做的工作只是去寻找有没有这样一个东西，与...

思维暴力

2020-01-07

0 442

Portals

D - Portals 参考：CF1271D Portals dp 贪心主要要明白两点：如果a和b都能够派兵前去把守c，且a>b，那么从a派兵去把守c是更优解派兵要派往分数最大的地方，要把有限的派兵机会用在最值的地方要实现这两步，要学会反悔贪心法，即如果当...

2020-01-07

0 423