前言 “🐘💼🔔”

总结

棒棒🍭题

想了十多分钟，看到周围的人都开始动键盘了。以为十分简单，此时压力倍增。想到正着推，写了一半发现直接维护不了，用树状数组刚好。简单的棒棒🍭🍭🍭题！！！

葡萄🍭题

想到BFS求距离，离线一下询问，再启发式合并一下，40min写完代码，一遍过了小样例，但大样例差一点。瞪了1h毫无变化。只能将就一下去开后面的题了。错因也不复杂，大概是BFS的顺序问题，没救了。

🍭🍭🍭题

小想一下，发现根据sqrt(n)分成分组背包和完全背包，n^2暴力拿下，调了一会，大概花费40min。

🍭🍭🍭🍭题

最后十分钟随便打暴力。

得分：100+30+50+20

评价：T2遗憾离场

餹粉：小🍭

Day5 总结

Part.1 赛时历程

粗略的看了一眼四道题，感觉 $T4$ 有点眼熟，难度一半。

$T1$ 思考了一会，就想到了一个贪心策略，每次交换两个最近的，随后优化了一下，按照栈的顺序加入，先匹配到"右括号"的就交换，可以证明一定没有比这个更优的策略了。然后就按照这个写，发现测大样例有问题，于是开始构造，发现有可能是在栈内的已经匹配到“右括号”没有弹干净，写了一个 $O(n^2)$ 暴力检验了我的想法，同时构造了一个样例：

4
3 2 1 4 2 3 1 4

然后思考，这道题不会需要用二位数点吧？

最后发现，不用树状数组难以维护。（$9:09:43$）

$T2$ 开始看的时候没有什么思路，后面发现只要取边的最大值而不是边的和，然后瞬间就会了，直接 建图 + kruscal 最小生成树 + lca 就可以直接写完，但是总是过不了大样例，调急了，所以先放了一下，写 $T3$ 去了（$10:27:02$）

$T3$ 随手写了一个背包，时间复杂度 $O(n^2)$。后面没有进一步优化的思路了。($10:33:54$)

$T4$ 正解没想法，然后观察了一下部分分，发现有 $60 pts$ 非常好拿，于是先写了两个 $subtask$ ，发现少些了一个，就多加了一个 $subtask$，但发现没有开 $long\ long$ ，喜提 $CE$：

#define int long long
for(int j = 1;j <= n;j ++){
    int lt = max(j - i + 1,1),rt = min(j,n - i + 1);
    ans[j] = max(ans[j],T[i - L].query(1,1,n - i + 1,lt,rt));
}

在 $11:07:14$ 时写完。

回过头来写 $T2$，发现了一个很糖的问题：

int dx[] = {0,0,1,-1};
int dy[] = {1,-1,0,0};
for(int i = 0;i < 3;i ++){
    int nx = px + dx[i],ny = py + dy[i];
    if(!check(nx,ny)) continue;
    if(dis[nx][ny] > dis[px][py] + 1){
        dis[nx][ny] = dis[px][py] + 1;
        vis[nx][ny] = c;
        q.push({c,nx,ny});
    }
    if(vis[nx][ny] && vis[nx][ny] != c){
        // cout << vis[nx][ny] << " " << c << " " << dis[px][py] + dis[nx][ny] << '\n';
        edge.push_back({dis[px][py] + dis[nx][ny],vis[nx][ny],c});
    }
}

就发现建图时就错了，改正了这一个错误后，我灵机一动，觉得边数太多了，考虑四色定理，应该就只会建 $4P$ 有效边。但是我在去重时使用了 $set$ 增大了常数，最终喜提 $TLE$。（$11:30:03$）

后面一段时间思考 $T3$ 的优化，没有得到结果。

Part.2 赛后总结

估分 $100 + 100 + 50 + 60 = 310$

实分 $100 + 70 + 50 + 0 = 220$

挂分有点严重。$T2$ 卡的有点久。

Part.3 改进

提交前一定要测一遍。

一定要计算时间复杂度与常数。

🍭🍭🍭

给到棒棒糖级别 估分22+70+10+10 实际22+0+5+0

第一🍭敬自己连续两天爆 第二🍭敬向军和我一起卡T1 第三🍭敬码力想出T2写不出 T1 开局10min浅度思考后，写了一点树状数组5min， 然后因没想到栈的那一步，于是删掉树状数组，跑了，后来在比赛后段回来花10分钟想了一下，没想出来，于是有了22的骗分 T2 首先读完题自然想到每个点的最小生成树，然后考虑怎么把有限边在时限内存下来，先写了一个朴素bfs，然后观察，发现可以同时存多个起点只跑一遍，然后2h写+调，最后结果期望70因为没调出来lca，多了一个n T3+T4 共花45分钟，写了塘市暴力🍭 自己的代码水平真的是 大区拱拱拱 还是写少了

结结 这两天的状态不好，就是贪心想不出，暴力打不满，所以后面该多做一点黄色绿色的贪心了

估分：100+0+10+10，实际：61+0+10+10

T1卡在怎么找一对情侣中单个的人，后来想偏了，一开始写了一发暴力，有70分，改了半天，假的，成61分了。

T2，T3,t4都只有最爆的暴力。T3的dP想挑战一下来着，失败了。。。

T1有数据结构是没想到的。T3仍想挑战。T2会不太爆的暴力，没时间，不想写了。下次注意。。。。。。

空悲切

估分：100+10+30+40 = 180

结局：100+60+30+30 = 220

这回抱着必胜的决心来写T2，结果只有铩羽而归 T_T

T1

（话说前天才是七夕，为啥不把这道放前天

这道题写了挺久的，先想到贪心选距离最近的情侣，但是。

我选择了每次重新找出来距离最近的，复杂度 $O(n^2)$ ，然后就冷暴力它一会儿去看T2。

看完T2题意后突然想到不用每次都重新找，直接排完序过后依次修改算答案就行了。

$10min$敲完树状数组交了

T2

最开始就被这个巨大的图吓死了，于是读完题先回去写T1。

然后 be calm down 想到kruskal重构树处理最后的询问。

但是依旧被建图卡住$30min$，先放在这里让它自己反省一会，看后面的题去了~

最终还剩一个半小时成功回归，把询问部分先写了。

开始拼命想这个建图该怎么建，中间写了好多莫名其妙的算法。

可是生命中免不了的遗憾，最后还是没有想出来。

随便挑了一个能过所有小样例的代码交了。

不幸中的万幸：本来期望10pts的得了60pts

是不是中间两个特殊点太水了，其实我感觉我当时写的那个建图有可能是错的

T3

读题，写个暴力润润润

T4

惊喜╰( *°▽° )╯，好多简单的特殊点可以写。

然后就敲了一个暴力，敲了一些特殊点。

但是，为什么暴力错了啊-_-?

终

差不多吧

怎么打的还是这么糖（悲。

极罕见的整场都在写代码。

开场看到 A 秒写 $O(n^3 \log n)$ 做法然后看原 B（现 C），发现 $23'333'333$ 不是素数，并不能组合数学搞，那这个二进制优化一下还是能搞老多分的吧，然后开始写，中途不知道想到了啥玩意来着还是突然知道 A 怎么优化一下了然后没写了回去又秒搓了一个 $O(n^2 \log n)$。

此时 swap(B,C)，就又开始看现B，emm 其实知道是 Kruskal 重构树的捏，但是明确知道自己不熟悉这个东西了捏（代码源结营测试的 Kruskal 重构树也没搞出来），然后就花 30min 写了个多源 BFS + Floyd，$O(HWP+P^3+Q)$ 的，写完之后突然感觉自己知道 $Q=1$ 怎么搞了，但是当时脑雾了我竟然觉得 $HW \le P$，也是倒反天罡的来的，然后又花 30min 写了个 $O(HMPQ)$ 的，写完后意识到了问题，但是死马当活马医还是给 $O(HWP+P^3+Q)$ 的做法融合起来一起交上去了。

此时比赛已过将近一半，然后这个 C 突然会了原本自己想写的做法，飞速写 $O(n^2 \log n)$，当时还是写了二进制优化的，但是没判重，也不想调了把二进制优化注释了发现也能过 $n=10^4$，遂直接交了。

然后 D，我靠这么多子任务送的，开始搓 + 调了较为长一段时间，写了个 40pts 的。

最后 20min 突然完全会 A 了，赶紧写，3min 搓了一棵线段树，然后就不知为何线段树会返回负数了，赛时并没有调出来，赛后发现是单点加写成单点赋值了（悲。

A：评测姬跑的快捏。

B：$P \times P$ 的数组开成 $H \times W$ 的了捏。

D：暂时未知。

不指望自己能写出 Kruskal 重构树惹。

这真的有 NOIP 的难度吗。

锻炼代码能力，提高代码正确性，复习久远知识点。。。

投诉：

• 应每一个子任务都有一个对应的大样例。

状态不是很好，昨晚睡晚了。

估分 $100$，$0$，$0$，$10$； 实际 $100$，$0$，$10$，$10$。

先看的 $\text{A}$ 题，看着眼熟但是不知做法。也想过贪心，思考了半个小时写先了个暴力，再思考了十分钟后没有思路跳去了 $\text{B}$ 题。因为我看见了城市可以补水的条件，把宽搜写成了深搜。写了二十分钟后发现时间复杂度特别高被诈骗了，但我没管那么多。测样例发现输出全是 INT_MAX，微调了三十分钟写红温了。突然觉得 $\text{A}$ 有些许思路，再回去写 $\text{A}$，发现了树状数组的写法，过了大样例后交。

然后我写 $\text{C}$ 题，题意简单我就开始自己造数据找找规律。推了大概一个多小时后有了一个错误的式子，还是决定打表拿前 $10\%$ 数据的分。

离结束只有半小时了，我开始看 $\text{D}$ 题。稍微思考一会就发现已经要结束了，看一眼数据范围提示发现有 $10\%$ 数据保证 $\forall i\in\left[1,n\right]\cap\mathbb{Z},a_i=0$，于是我全部输出 $0$ 骗取 $10$ 分。

以后看题应该先搞清楚大致核心方向再写暴力，如避免我最短路用 $\text{dfs}$。

今日总结

今日比赛分数为 61+0+10+0，预计分数 64+0+10+50 首先第一题，我想了40-50分钟左右，我想到了前4个点的做法，但是我想着先写完后面3题的暴力，于是往后写了。

然后开始写第二道题，一直想到了9点30左右，我还没想到做法，与实现去写了后面两道题。

然后开始写第三题，刚开始时我读错了题，以为他要求所有的不同礼物数量不同，但是很快就发现了这个问题，但是由于剩余的时间已经不多了，于是我就去写第四题的暴力。

写第四题时我发现我可以写第1，2，4，5，7的点，花费一些时间去完成了暴力，但是写错了。

最后在40分钟内，我又开始写第二题，在我的大脑风暴下，任然对完成代码有点问题。不太好写，最后没写完。

小结：今天的节奏不太好，我今天的暴力也没写好，需要在这两点改进。

100+0+30+30

1.T2想出来了，大体没问题，有细节问题

2.T3 ,n属于(1000,10000]的可以打表的，应该可以多拿20分

3.T4 暴力的20分没对，很疑惑，待会在看看

4.T1 写的比较快，虽然T2没写出来，T3 T4的暴力打了，也不至于分很低

26+10+30+0=66分，t1几乎想了一场都不会，提出了一堆假的贪心，t2没怎么想，打了10分暴力，t3观察到了是多重背包和完全背包两部分，发现多可以nsqrt(n)做，但是不会写单调队列优化的多重背包，如果二进制优化只能50，由于第一题浪费了很多时间所以只打了最基础了30分暴力，t4暴力打挂了

(100+0+0+0)
2h + 2h + 0 + 0
比赛时第一题不知道如何贪心能够过题， 试了好几个贪心，浪费了时间
第二题没想考虑点，只考虑建筑物，用log次bfs，没有调出来
第三题没有看
第四题没有看
第二题用了代码更长的st+轻重链剖分
剩余时间不够