第四周训练总结
比赛
第一场牛客多校
只A了一道题
AC
- D：博弈论，比赛的时候，通过几个例子的检查，大胆的猜测出了答案，然后就A了
补题
- H：在比赛的时候想了很久，没有思路，最后通过讲解，学到了正序相交，正序包络，正序不交，反序包络，反序不交，反序相交之间的关系，重要的是把这里搞清楚，这道题基本就差不多了
- K：比赛时候想了好多思路，最后发现没有一个是对的。先生成bfs树，将非树边和树边分开讨论，如果非树边可以无限制加点，树边不加点，这里要特判叶子结点是否连接非树边，如果没连可以加点。整体的大思路就是如果加点在树边上，肯定会顶掉一些叶子节点，就算叶子足够浅，也是在叶子边上加点最优。
第二场牛客多校
A了2道
AC
- E：思维题，枚举x的位数，开方上取整和y比较就行
wa点在于x位扩张的终止条件：一开始感觉输出y是109，应该把x扩张到溢出即可，但是可能有些太大了，改成1018就对了
while(x <= 1e18) { // 这里如果是(x > 0)就会wa
int ans = check(x, cnt);
if(ans > 0 && ans < 1e9) {
std::cout << ans << endl;
return ;
}
else {
x *= 10;
cnt *= 10;
}
}
- I：构造，水题，判断总共是奇数行还是偶数行，偶数行每行4x4o交替放就行，奇数行要在最后一行1x1o交替放
补题
第一场杭电多校
AC2题
AC
- 1009：水题，直接粘个代码
scanf("%d%d%d", &n, &m, &d);
int num = m / n + (m % n > 0);
if(num >= d) printf("Yes\n");
else printf("No\n");
- 1005：
补题
- 1002：比赛时候wa了好多发，不知道哪里错了，最后拿官方数据对拍，一共1000组错了2组...感觉是被卡了；题目是一眼dp求最大点覆盖，标程是个无向图直接dp，我是先bfs一遍转化为有根树，然后dfs跑的树形dp，其实跟答案也大同小异，真不知道wa点在哪...
第二场杭电多校
自由训练
Codeforces Round 886 (Div. 4)
比赛比较简单，基本都是一眼题
简单说一下最后三个
- F - We Were Both Children
本道题的数据范围105，一直在考虑O(nlogn)算法，但是没啥思路，最后发现O(n2/k)直接过了，应该是没有卡常之类的 - G. The Morning Star
考的map应用，算是个小思维题，不过也没啥难度，用4个map记维度，再开4个map打标记就行 - H. The Third Letter
本场最难的题，考图论建模搜索，还没补，蹲一个题解，youtube上有个印度人讲的，实在是听不懂