CF - 洛谷仓库

8.24

https://codeforces.com/contest/2075

第一题花了不少时间，这种题不能一上来就瞎猜结论，要多想几种情况。

第二题也花了不少时间，因为理解错了蓝块如何更新红块，导致思路卡了。说明要多看题，没思路时再看一遍，说不定是理解错了。

写到第三题剩的时间就不多了，我写的就有些匆忙，思路还没理清，导致代码越来越难调。这告诉我刚有一些头绪时不要先急着写代码，可以结合样例，再试着自己构造个数据，验证下自己的思路。还有这种统计方案数的题一般都会用到各种加减乘除和数组，思路不能乱。

第四五题都没来得及写，时间管理需要调整，下次试试写一段时间没思路就跳题。

https://codeforces.com/contest/1978

（终于写出来四道题了）

第一题和第二题都是看一眼就很容易出结论的题，快速写完了。

我先开的第四题，卡了一下，就先去把第一题写了，然后调出来了第四题。第三题写了十来分钟，没有思路，就先去写了第二题，接着回来写出来了第三题。下次再试试按这种顺序。

第四题还好，第三题多花了不少时间，这种构造题可以自己构造几组数据观察一下。

此时还剩下三十分钟，我点开了第五题，第五题不难，我想出思路后写的却又慢又乱，比赛结束后三十多分钟才调出来。写题时时间不够了也不应该慌着写代码，不然写出来的代码又乱又难调，更浪费时间。

https://codeforces.com/contest/2085

这次写的慢，第二题分类讨论太多，思路有些乱，以后遇到这种题一时调不出来可以先做后面的。

第三题是一道数学结论题，由于一开始猜想错了，多花了不少时间。

刚开始写第四题的时候还以为是DP，后来发现最多可以取n/(k+1)个物品，然后就卡了，没能充分利用这个性质进行贪心。

8.25

https://codeforces.com/contest/2092

这次节奏还行，花了40多分钟A了前三道题，都是观察了样例以后可以猜出结论的题。

第四题花的时间有点长，不难，偏向于模拟。以后遇到这种题要先考虑好、理清思路后再开始写，我写的时候重复添加一个字母这个地方没想清楚，调了很久，结束后一秒才A。

第五题没时间写了。这道题的关键在于格子变色前后其奇偶性的变化是有规律的，还有计算答案时要用到二项式定理。

https://codeforces.com/contest/2064

前三题还是可以很快观察样例得出结论。

第四题涉及位运算，注意到异或不进位的特征，然后一位一位考虑就好。

赛后看别人的代码学到一个新函数 __lg(x)，可以取出 x 最大的二进制位，返回值为最大的整数 a 使得 x≥

2^a

，特别地，x=0 时值为 −1。

8.26

https://codeforces.com/contest/2059

第一题和第二题比较简单，第二题是结论题，可以通过简单的分类讨论快速得到答案，多观察观察样例就好。

第三题花的时间比较多，想出来影响答案的就是每组数结尾的1的个数就好了，代码还算比较简单。

第四题是图论题。图论题比较侧重算法的灵活应用，能想到两个点到达一个共有的边就有解就行，算法就用到了一个dijkstra，重在思路而不在算法。

https://codeforces.com/contest/2086

第一题和第三题都能很快A过，第二题花的时间有些长，还是由于一些细节处理的比较麻烦。

第四题没有写出来，经过观察很容易发现每个字母可放的位置分奇数位和偶数位，然后就卡了。后来看题解，这题用到的计数和dp都比较简单，重点是怎么想到。第五题还没做到。

9.5

https://codeforces.com/contest/2109

第一题第二题观察题目花的时间有些长。第三题是一道数学题，写了半天没写出来，赛后看也不难。像这种限制次数的交互题，要仔细观察题目给出的几种可用操作，充分利用到其性质。

第四题没写到，但是补题的时候发现图论题还是十分灵活的，最短路考的比较多的，而且一般不是最短路板子直接用，所以不能拘泥与以前学的算法。

第五题是一道dp，还用到了组合数的知识。

https://codeforces.com/contest/2020

第二题是一道结论题，可是我没看出来，分类讨论了很久,过了之后已经没有多少时间了。

第三题是位运算，一位一位处理就好，感觉比第二题简单些。

第四题没时间写了，我看完题觉得有思路，写完后发现看错条件了。这种对线上点进行看起来比较复杂的操作的题，一般都是记录下操作后，线性向前或向后递推，可以省去很多重复操作。

第五题是一道数学期望题。这道题的思路不复杂，就是需要卡会儿常，复习了滚动数组，还有这个：

CPP

ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);

https://codeforces.com/contest/1983

这次节奏还可以，但是仍然没有写出来第四题。

第一题很容易看出结论。

第二题观察可以得到b数组减a数组后同一列、同一列的1和2的个数应当相同，这样才可以相互抵消。但是观察样例1可以发现不只是这样。再想一想发现1可以由2个2合成、2可以由2个1合成，,接着就可以得出正解。思考时不能只盯着一个样例，要充分利用给出的样例。

第三题不难，但是我浪费了不少时间。正解就是罗列六种情况，挺容易想到。可我一开始有了一点思路后就直接写了，导致写的挺乱，调代码花了不少时间。

第四题我一开始想到了逆序对，但是同时又想到了一个看起来正确实则错误的思路，然后就在错误的道路上越走越远了。最后十分钟开始写逆序对的做法，树状数组add操作时范围写错了，就挂了。写代码时要注意细节，不能凭着自己对板子的印象写。

第五题又是一个期望题，以后再补吧。

9.8

https://codeforces.com/contest/2063

前两题都挺简单。

第三题一开始想了个错的做法，直接找出度数最大的点，将其删除后再找出度数最大的点。其实卡掉这个做法只需要一个链，但是样例里没有，于是我模拟完样例后就开始写了。这个写法还不太好写，我写了半天，结果wa on test 2。于是又分类讨论了半天，得到了正解。赛后看有的人的写法不需要那么复杂的分讨，仅是枚举了一下。

有的时候，在数据结构允许的范围里直接枚举可以省去很多事，1859的C题也是直接枚举的话不需要证明，也不用想什么情况最优。

学到了一个STL的用法。

CPP

std::multiset<int>mu{1,2,3,4,4};

for (auto it = mu.crbegin(); it != mu.crend(); ++it){
  cout<<(*it)<<" ";//倒序输出mu中元素，输出为4,4,3,2,1
}

还有

CPP

mu.erase(mu.find(d[v]-1));//删除迭代器
mu.insert(d[v]);//插入元素

9.11

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

A题、B题都是很容易想出结论。

C题一开始不会，暴力枚举了几个数，发现了规律，就过了。比赛后想找一找证明，发现很多人都是猜了一下过的。

关于看了三四十分钟D题没有注意到条件:

l_i \le a_i \le b_i \le r_i

这件事。

9.13

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

这次先写了20多分钟C题，挂了，就去写D题。

看了会题感觉没思路，花二十来分钟写了暴力，想观察一下规律，结果暴力没写出来。又观察了一会儿D题样例，猜了个结论，感觉非常对，写了三十分钟，结果又挂了。此时比赛还有四五十分钟结束，还以为要零题了。仔细调了会儿D题的代码，找了些细节上的错误，提交了n次后就过了。

看来通过观察暴力得出的解找规律的方法在这种输入和过程比较复杂题上不适用。还有第一遍写时一些细节处理要仔细。

只剩下三十多分钟了，又去调C题，可是由于我去写了一个多小时的D题，C题的思路有些忘了，调试的比较慢。调了十来分钟没调出来，就去花十分钟把A、B过了。又回头看C题，发现是long long 类型的输入数据用int存了，改完就过了。

所以一题如果有思路了，感觉还挺对，就尽量把它写完再去写别的题，中断一下会忘掉一些重要的细节。

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

这次先写的D题，一直没有思路，还剩三十多分钟时才写出来。其实思路很简单，样例和数据也有提示，就是四个数中用两次询问找出最值。

交互题debug适合自己造数据模拟。

没剩多少时间了，看C题也什么思路，就花十几分钟过了A和B。

赛后看C题的思路也不复杂，是一道找规律题(C题好多找规律题)。

9.15

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

D题看了会儿就想出了思路，即用一个桶记录

a_i

出现的次数，从前往后扫，当当前的数时最后一次出现时，则它（或前面和它数值相等的数）必须加入答案序列，为了让字典序最小，就在前面可以加入的数中取数值比当下的数合适、未加入过、且位置合适的数，奇数位要打输，偶数位要小数，用堆+删除标记就行。一看到这个题先考虑的是能不能用贪心，后来发现是字典序最小，就可以放心贪了。

然后又很快写出来了C题、B题和A题。

https://codeforces.com/contest/2144

两题，惨烈。

https://codeforces.com/contest/2104/submit 四题

第四题审题一开始出了点问题。

9.29

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

C题花的时间多了，不难，但是一些细节要考虑清楚再写。还有debug的时候不要想到哪里改哪里。

10.4

https://codeforces.com/contest/2146 3.5题

B题浪费了不少时间，题目给出的问题是是否存在至少三种不同的选择集合的方案，可以直接逆着想，要充分利用条件。

10.5

https://codeforces.com/contest/2143/my 三题

C题写了很久，题目中有些条件有时也没用，C题中给出“输入满足 u<v ”就没什么用。写关于树的题先考虑用dfs确定树的形状，不然要考虑的太多。

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

这次前四题写的挺快，主要得益于这次猜结论猜的比较准，没有想到错误思路浪费时间。

想到一个思路后先用一个简单的样例试一试，降低试错成本。

认真读题、模拟完样例后想到的第一个思路一般都挺正确（前提是没读错题）。哪怕没写出来或者wa了，也尽量不要再另想一个思路再改，一来时间不够，二来第一思路没想清，再想一个思路也是比较混乱的。

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

关于E题没有特判n==1导致正解爆零这件事。一开始猜了个结论，可是没考虑时间复杂度，感觉会T，写出来的代码确实T了，就去想别的办法了。这个结论是正确的，时间复杂度也正确，当n等于1时一些局部变量赋不到值会导致死循环，所以交上去的代码T了......下次一定把能特判的都特判掉，还有考虑时间复杂度时要严谨，不要凭感觉。

C题是一道交互题，花的时间有些多。交互题的询问次数限制会给出提示，要充分利用。

https://codeforces.com/contest/2003 3.4题

前三道题写完后还有很多时间。D题分两道，看起来没什么关联，又想快点写完去看E题，就直接写了Hard Version，结果没写出来。最后10多分钟去调了Easy Version，时间结束了才调好。Easy Version对Hard Version有启示，起码能帮助理解题意。

D2有点困难，我的思路大致正确，但是没有想到借助图论、递推之类的工具，而是纯模拟，然后思路就乱成一锅粥了...当遇到这种有明显的非线性的一对一有向转移关系的题，可以考虑用DAG拓扑序转移。

像这一题，虽然是树，但是在确定了树的形状之后，可以看成方向为叶子节点指向父节点的DAG，这时再按照拓扑序为每个节点赋值就简单多了。

10.6

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

第四题没写出来。其实并不复杂，在dfs递归的过程中就可以实现，但是赛时只想到了先把树的形状确定下来。做题还是要灵活。

C题是一个计数题，要记得划分好边界，不重不漏。

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

D题有一个点最后才注意到：

纸上依次写下三个数字 d，u 和 v。称结束后你的纸上的数字构成的数列为 a。输出可能的字典序最大的 a。

u和v也计入字典序，这样就可以确定用哪个直径。

C题思路很直接，但是我代码实现花了很久。我是先确定每一个位置的信息后再找一个位置处理，实际上也只用得上这一个位置的信息。可以把这个位置找出来后再确定这个位置的信息，代码复杂度会降低很多。有思路后可以再想想有没有什么地方可以优化，耽误不了太多时间，还有可能节省不少时间。

31https://codeforces.com/contest/2070 三题

这场比赛C题花了很久也没想到用二分......二分很好用，在答案具有单调性（还有别的思路怎么想都想不到）时可以尝试一下。

D题倒是挺简单（C题D题放反了吧），算是找规律，树的题可以画棵树看看，同时要考虑到一些特殊形状（比如星图和链）。n比较小的时候可以特判（比如2和3）。

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

这次前三题写得比白天快，但是D题怎么想也没有思路，最后尝试了一个时间复杂度不详、正确性不详、代码复杂度超标的思路，写了130多行。本来已经不报希望了，结果竟然在结束前30秒最后一次提交时过了。

这题确实没有别的特殊写法，我的思路是正确的，但是用了位运算优化过的代码只有二十几行，思路也更清晰。像这种有多个类似状态、需要处理类似& | 的操作的问题，不止可以用数组，也要想到位运算。

10.7

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

一个可以化简代码的东西：

CPP

goto G;
...
G:0;//跳过省略号中的代码片段，直接跳转到这里

这次的D题和E题都是看起来需要写很多，但是正确思路并不需要复杂的代码。(但是E题的数据范围很小，不像结论题，很有误导性)

实在想不出思路的时候可以打出暴力然后优化，有的时候看起来暴力的代码根本跑不满，有可能就是正解；还可以多自己构造几组数据，多猜几个结论试试。

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

C题可以用二分，这次想到了。之前有一题的答案没单调性，check写完了才发现，然后又发现不用二分只用枚举时间复杂度也对。想题的时候可以试试如果已知某个条件问题会不会简单很多，然后枚举或者二分这个条件。

https://codeforces.com/contest/1998

C题都写不出来了。 C一开始写的是二分，后来感觉有点麻烦，又换了个思路，写了半天发现有bug，又继续转战二分（还好上一份代码没删）。但是比赛结束后才调出来。一开始想好，最好不要换思路。

B题也想了很久，是一道结论很简单的题，但是样例有误导性。像这种多解构造的结论题，样例给出的答案一般和结论没什么关系。

D、E

https://codeforces.com/contest/2027 3.5题

有两道线性dp题，状态表示和转移都不难，也很容易想到用dp。 D1不难，但是D2的dp有些神奇，相当于要求出把dp转移时用贪心优化的部分，但是要是暴力的话就不叫优化了，会超时，于是还要再用队列优化这个求解过程。很左右脑互搏的一道题。最近做的题基本上不是贪心就是模拟，偶尔有几道二分，也要用到贪心。但是除了贪心以外优化的方法还有很多，想思路的时候要多想一些。

10.8

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

B题和C题花的时间都有些多，B题是一个细节——下标对应错了，找了半天才发现。

C题思路有问题，一开始想得太简单，挂了一次后在思路基本不对的代码上改，就相当于边写边想。这会导致很多代码前后细节对应不上，改起来很麻烦。下午那场的D题也是因为这个改了半天都没改出来。如果发现思路可能错了，不要着急先改代码，想好哪里错了、怎么写是对的再改。

D题留的时间不多，本来做好调不出的准备了，结果一次就过了。写D题的时候多用了几个函数，思路清晰了不少。

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

最近的比赛B题和C题写的时间都格外长，但是赛后看别人的代码和我的思路一样，却简洁不少，一来是代码思路清晰，分类讨论很少，二来是用了比较多的函数，码量减少了很多。

10.13

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

D题是一道dp，没想出来该怎么转移，因为在纠结下面的生物掉下去后对上面的生物的影响，觉得有后效性。实际上下面的生物掉不掉对上面的生物没有影响，因为上面的生物如果要掉的话，比下面的生物先掉更优，这个贪心就保证了无后效性，这个dp的转移过程用到了贪心优化。

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

C题一开始想了个做法，觉得没道理就去想别的做法了，三十多分钟后还没有思路，就把一开始想的做法写了出来，结果就过了......这是道结论题，这个做法是碰巧能检测出是否符合条件。

结论题的特征：1.怎么想都很麻烦. 2.看起来和什么算法都没关系. 3.数据范围没啥特征，可能有误导性的很小.

B题复习异或的性质：满足交换律. 异或题可以试试打表找规律.

D题复习哈希（好久没用过了，感觉没什么题用哈希优化能便利很多），但是有比哈希好写很多的方法，用到字符串相关的一些函数.

CPP

//字符串操作
string x;
int ans=-1;
for(int i=0;i<n;i++){
  x=s[0]+x;
  s.erase(s.begin());
  string p=s+x;
  if(p==a||p==b){
    ans=i+1;
    break;
  }
}

CPP

//hash
P[0]=1;
for(int i=1;i<=n;i++){
	P[i]=P[i-1]*3;
    ha[i]=ha[i-1]*3+s[i]-'0'+1;
    pha[i]=(s[i]-'0'+1)*P[i-1]+pha[i-1];
}
...
unsigned long long ha1=0,hh=0;
P[0]=1;
for(int i=1;i<=n;i++){
	ha1=ha1*3+ma[i]-'0'+1;
}
for(int i=1;i<=n;i++){
  hh=(ha[n]-ha[i]*P[(n-i)])*P[i]+pha[i];
  if(hh==ha1){
  return i;
}

10.16

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

CF

文章操作