刚开的时候我还没有恰饭......
先去喝了个汤，然后肥来看题。
先去看A（重大失误）
复制三遍CE？？？？？？？？？？
公告一来天呐再见兄弟。
尝试填空，发现，如果这样直接按照给定的代码填空，复杂度是O(n^2logn)的，这是陷阱。
仔细分析了一波，数据随机+区间修改，突然想起这两天一直在研究的ODT，不过ODT只能处理区间赋值，这个貌似并不好做。
再想了一下，线段树貌似就可以了，加入一个线段看做区间+1，维护区间最大值最小值，当区间最大值由0变1时加一下答案，删除同理，由于数据随机，序列上相同高度的连续段是O(log)级别的，复杂度是对的。
没有立刻打，先看了一眼榜，C被切爆了。
C是个简单题，不过我切掉的时候已经14min了。
再看一眼榜，J被切爆了。
J就是一个暴力题，切掉的时候是18min。
再看一眼榜（我的手速已经慢到跟榜做题了），I被切爆了。
I题我推了一小会，前两天做了一道拆位异或线段树，但这一题我没有先想拆位，我想了一些奇奇怪怪的东西，最后老老实实拆位，切掉的时候36min
老规矩，看一眼榜，F被切爆了。
F是一个裸的树形dp，f[i]表示子树i下的叶子与根不连通的最小代价，显然f[i]=min(i到父亲边的权值,
f[j]，j是i的儿子)
切掉的时候46min，rank9，老规矩......
A有人切了，这个题我不一定打，虽然我会，但是细节应该很多...
B有人切了，点开一看，这不是裸的分层图最短路吗，看数据范围不大，直接spfa，然而一直wa？？？？？？？？？？？？？？？？？？？？
交了7发wa之后回去看榜，发现G题有人切。
G题gcd相关，看值域并不大，每个数只保留质因子就可以了，应该可以枚举质因子+容斥，但是这类题以前没有打过，我又是一个可怜的数论喳喳...
继续看榜，DEH都没人摸的样子...
看了一下D，二叉查找树的节点深度和，快速找到新插入节点的父亲在哪里就ok了，显然新插入节点的父亲只能是当时恰好比它大或比它小的第一个数。
结果一直wa？？？？？？？？？？？？？？
再去看E，求平均值最小环。
想到二分答案，然后每条边减去答案，有解则有负环，spfa找一下就好，1A，2h1min，rank5
H题一开始看错题，认为神仙，弃！
现在剩一个小时，我有一个一直wa的B，一个一直wa的D，和一个没开打的A。
A老实说不想去打了，如果像BD一样无尽wawawa，那我不是心态爆炸？
调D，换了打法之后，交了十几发终于切了，我都不知道怎么切的，2h11min，rank7
现在我只剩个B了，突然想起来我还没恰晚饭，先去恰饭。
边恰边想细节...没有什么收获，中途回来瞄了一眼，仔细再读了一遍题目，发现了两个坑点：
1.如果起点***，那么层数-1
2.如果终点***，层数+1
有一句话是，“能穿过k个***点”
穿过穿过穿过，到达n不算穿过。
好的，切了，2h37min，rank3
中途玩了一下手机，刷了刷知乎，想起下午炉石合了一套蓝白快攻贼，玩得蛮舒服，只是打不过战士德鲁伊和法师...
突然想起H题的式子有点熟悉，推了一波，天呐，每条边最多三种权值，对原图每个点拆成3个，用三种权值跑最短路就好了，边数很多用堆+dij就可以了！！！！！
可是只剩下13min了，不打了不打了，生气。
惦记着结束，不要被超不要被超，还是在2h50min的时候被超了一下，rank4...
哭哭，手速太慢+调题辣鸡，沉迷于看榜且跟榜做题，我本可以拿E的一血...我打ACM赛制比赛还没拿过一血...真是伤心呐。
E好像并不是很好想，如果我开场先看所有题，做题顺序应该是JCIFEBDHAG的，前面的题可能没有优势，但是E绝对可以一血，说不定还能歪榜嘻嘻嘻
我的学校怎么是北京化工大学啊？？？？？？？？？？？？？？？？我只是个高中生诶！而且远在南蛮...
最后，三玖天下第一。
全部评论
(1) 回帖