CF2

· · 个人记录

edge https://www.microsoft.com/zh-cn/edge/download?form=MA13FJ

10.16

https://codeforces.com/contest/1990 四题

今天写前三题的时间不是特别长，D题写的也挺快，感觉写的再快点就能写出E题了。

写代码时用inline可以优化一些空间。

10.17

https://codeforces.com/contest/2056 三题

https://codeforces.com/contest/2140

10.18

https://codeforces.com/contest/1935

有序多重集合用multiset

https://codeforces.com/contest/1928

D题三分，但是我用的是二分，判了一下mid和mid+1的大小。 C题想了很久，其实就是统计一下因子个数，应该统计的式子我也推出来了，但是就是没想到统计因子个数对应计数答案，计数的时候要想清楚数量间的对应关系。

学到了一种新的计数方法。当统计的数会有重复，总数不是特别大，值域又不小时，可以用set去重，得到集合的size就是要统计的数的个数。

https://codeforces.com/contest/1918 单调队列写挂了，写单调队列时要注意，队列中一般存储的是要用到的元素的下标，或者直接用结构体把要用到的东西都存起来。不要把队头队尾的标记l,r和要用到的东西弄混。

这次写C题的时候想到了异或题按位分析，但是由于贪心与上界，应该从高位往低位考虑。其实就再改动一下就好，但是在改的时候用这些long long类型的位运算没开long long，数据对不上，就改了很久。

10.20

https://codeforces.com/contest/1922 三题

这次的D题是一道模拟题，学到了一个函数：

vector<int>g;
sort(g.begin(),g.end());
g.resize(unique(g.begin(),g.end())-g.begin());//排好序后的g函数去重
g.reserve(a); // 预分配a个元素的内存，提高程序性能

B题挂了很多次，因为我用的组合计数统计，实际上推一个式子就好，用组合计数会爆long long，所以如果没有给模数，就尽量不要用组合计数，如果能推式子也尽量不要用组合计数。

https://codeforces.com/contest/1917 D题 D题需要推结论，然后结合树状数组写。这题有一个很好的树状数组应用，即统计时将不能对答案造成贡献的数及时删去。

还有推结论时从特殊到一般推，式子写的工整写，更容易发现规律。

10.23

https://codeforces.com/contest/1913 三题

https://codeforces.com/contest/1905 三题

这两场比赛的D题都可以用单调栈。

10.24

https://codeforces.com/contest/1997 四题

E题有一个性质没想到：在越小的战斗次数下，怪物越有可能会逃，即可以与怪物战斗的战斗次数具有单调性。想到这个就可以二分了，每个怪物二分出不会使它逃跑的战斗次数的最小值，然后在询问的时候直接判断。

这个二分的check要用到树状数组，check(x)即为查询升级战斗次数为x时（当前怪物之前）不会逃跑的怪物个数，除以x，得到到达当前怪物时的等级，比当前怪物的等级大return 0，否则return 1。

10.25

https://codeforces.com/contest/2055 三题

C题看漏条件，多花了不少时间。

D题可以贪心，我用的二分，check里有一个点一直没有调出来，就是乌鸦在一个稻草人之后往后跳的最大值取决于位置小的那个，因为位置大的不能再使乌鸦瞬移。（代码能力）

关于这题的贪心做法，有一点需要注意，贪心算时间时应注意每次时间的增加量的计算，因为两边的稻草人都会向乌鸦移动，所以实际时间会除以二，这就是答案乘2的由来。 这里可以用到一个小优化，既然最后答案要乘以二，那么为了避免浮点数，不如一开始就把所有数据都乘以二。

https://codeforces.com/contest/1993 三题

这次的D题用到二分加dp，二分挺好看出来，check的写法需要好好想。首先是check里常用的一个技巧，设中位数为x，将所有大于x的数设为1，小于x的数设为-1。

接着是状态表示，f[i]表示前i个数删掉⌊\frac{i-1}{k}⌋个长度为k的区间后剩下的数之和最大值。状态转移如下：若（i-1）%k=0,则可以把b[i]算入第（i-1）/k个区间，这样前面就能多出来一个数，即f[i]=f[i-k]，还可以删掉前i-1个数，仅保留b[i]。若（i-1）%k！=0，则可以将b[i]算入答案，即f[i]=f[i-1]+b[i]，这时如果i>k的话，还可以将b[i]算入前一个区间，前面可以多出来一个位置，即f[i]=f[i-k]。这些情况取最大值，最后判断的到的f[n]的正负，即能得到在n个数中被删掉⌊\frac{n-1}{k}⌋个长度为k后剩下的数的正负，这代表了x能否成为中位数。

写这题的时候要读好题干中的删除操作。这里的删除十分固定，首先是一次删掉的个数一定，其次是前i个数须删掉的个数一定，为⌊\frac{i-1}{k}⌋*k，这两点奠定了一维dp状态表示和转移的基础——即只需要枚举i就能得到dp转移所需的信息。

10.27

https://codeforces.com/contest/1988 三题

int x=*std::min_element(dp+1,dp+20);//数组dp[1]-dp[20]中的最小值

int x=*std::max_element(dp+1,dp+20);//dp[1]-dp[20]中的最大值

这里的D题有一个技巧:证明出（或看出）dp的某个状态能取到的值很小，然后枚举这个值，进行转移。

https://codeforces.com/contest/2120 三题

D题是一道数学题，推了半天也没推出来一列多久循环一次。 其实总共有多少种排列方式并不重要（我一直在这上面算），只需要知道对手每一行都会排a个相同的数，只需要知道这a个相同的数会被分散到那些位置就行，总共有n个位置，答案就是C_n^a，而每一列这a个相同的数还有可能不是同一个数，再将答案乘以k，此时所得到的x代表最多每x列会出现一列有a个相同的z（1<=z<=k）,接下来用鸽巢原理求解。

A题输入限制了l和b的值，不需要写很多代码进行分类讨论.

10.30

https://codeforces.com/contest/2156 三题

写ABC题花了一个多小时，主要是因为C题一开始的思路错完了，但是有一个启发，如果想到了二分，发现check写起来确实简单不少，但是如果证明不出答案有单调性，可以用O(n)枚举，然后优化check。

写D题的时候还有三十到四十分钟，但是因为有思路了，觉得还挺好写，但是写了很久都没有调出来，我声明了太多变量和判断语句，调代码的时候需要考虑的情况很多。实际上，在时间复杂度允许的情况下，尽可能的多利用现在已知的条件会更优，并且尽可能减少判断语句，合并判断的分支，使代码更严谨。

11.3

https://codeforces.com/contest/2154 三题

C题和D题的思路都不算难想，就是有一些细节一开始没有想到，后期写代码的时候调有些慢。不要太依赖样例，自己多想一些情况调试起来更快，还可以试试在写之前就想。

https://codeforces.com/contest/2154/problem/E

11.27

cf复活赛 https://codeforces.com/contest/2166