> XP04 四期 本帖持续更新 请评论区留言
DAY -INF
报名。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
DAY -1
准备雷霆大行李并且加入了雷霆大“神秘物体”。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
DAY 0
上午进行了一个游戏的机的联。
下午上车。
孩子们我充电器被收了。
为啥收音机也收。
还好电学实验箱零件不收。老师：？
牌居然不收。
老师：影响思想的都要收。 我：毛爷爷像章也收吗？（）[1]
通过拿出雷霆狗玩偶震撼室友。
开营仪式居然是（我觉得是） 吴老师讲话。
回宿舍的路上：
我：那个保安追不上你，至于我为啥知道你别问。
班主任：（雷霆抓握）
给 UNO 自定义牌加了个用骰子的村规。（见附件）
晚上打牌，然后由于太困而进入深度睡眠忘记用药。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
DAY 1
请假了不用晨跑。好耶。
上午这个东西十分甚至九分的简单，都是 STL。
午饭非常的美味。
不是室友你怎么乱说话啊，我的手电筒 qwq。
进行了一个 UNO 的打。什么叫这把重洗了三次牌才打完。
下午讲 ST 表。
室友：不是你怎么看文章啊。
我：这个文章就是我写的。
模拟赛 rk3rk3rk3 544/700544/700544/700 T6唯二得分。
进行一个补题。
我说我看出 T7 是反悔贪心但是我不会写你信吗。
聊天室 1 / 2
不是，什么叫@AAA混凝土批发ppl哥(假的)其实是我 xmw 同学并且参加了同一个集训营而且我居然现在才发现。
（雷霆 Callback：之前的小说战神@six在某一期跟我一期 awa ）
继续进行一个 UNO 的打。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
DAY 2
半夜停电导致空调全部死亡然后就被热起来了。
不是这个雷霆牙膏到底怎么打开啊。
早饭依旧巨硬意大利面。
不是今天居然没有酸奶。
中午继续进行牌的打。
下午上课。
神秘休息，征集一篇《别样的丢沙包大赛》。
比赛系统笑传之常常爆。
然后就变成拿作业比赛了。
T1,T2 都是签子，T3两个 ST 表秒了。（T3 是往年 USACO）
T4 虽然是橙但目测不可做，跳 T5。
看似二维差分但是我不会，遂观看 T6。
T6 没有想到做法，观测T5。
注意到 T5 是往年集训题目，遂做出一发挂掉后调试得满分。
T6 注意到对于串 S 添加两个字符得到串 ASB 则 f(ASB)=f(S)+(A=B)f(ASB) = f(S) + (A = B)f(ASB)=f(S)+(A=B) 遂搜索得到 40 pts。
开摆。
T4 有人做出，结合橙难度说明我落入思维陷阱。回去思考。
注意到题目给出的样例中的 AB 令我落入了思维陷阱去做 O(N2)O(N^2)O(N2) 的统计，实际上对于任意子串最多子串一定是单个字符。
对于单个字符的计数显然可以通过 O(N)O(N)O(N) 的前缀和获取。
然后 10610^6106 写成 114514 挂了一发就过了。
目前分数为 540/600540/600540/600。
我去居然让 xrh 又拿到了 5pts5pts5pts 直接奋起争夺。
不是他怎么变成 70pts70pts70pts 了。
放弃争夺。
封榜，最终成绩 rk2rk2rk2 540/600540/600540/600。
晚饭是人类食物。
同桌被抓打游戏以后通过高级话术让老师认为他的粉末游戏是物理实验。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
DAY 3
晚上梦到被关拘留所了（异环八百年越狱失败出阴影了说是），起床以后：这有啥区别吗？
美味的早饭。
获得了室友的“物理实验”。
孩子们树状数组的区间修改单点查询太雷霆了，还好已经学会，看我帖子。
中午进行了一些高速 UNO。
和室友进行一些别样的高级自由搏击。
我去快速幂如此简单。
我去这个逆元是啥阴。
学会了。
不是这个模版默写居然挂到了 rk6rk6rk6 800/1100800/1100800/1100 阴不阴。
不是我错哪了。
换了一根烤肠。
室友是不是给。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
DAY 4
室友真的是给。
早饭居然是炒面，我的天哪炒面大人。
孩子们今天学动规，燃尽了。
神秘物体可以使用。
午饭能吃。
张斌你在杭州为啥还要给森林湖求雨，出不去了。
中午进行牌的打。
下午继续上课。
孩子们这期模拟赛 rk2rk2rk2 540/700540/700540/700。
上完课回宿舍打牌，头哥弄到了祂的东西。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
DAY 5
早上起床。
上午上课。
中午吃饭。
你问为啥写这么少就是今天真没啥写的啊，单调栈 / 队列我在 1eps\frac{1}{eps}eps1 年之前就学习了。
中午室友趴我床底下。
下午上课。
比赛。
下列部分可能包含一些赛时胡话：
T1,2 板子直接秒了。
T3 是啥阴啊一眼不可做题（记住这个结论）。
T4 又是啥阴。
T5 先跳，好像可做。
T6 一眼 dp，进行一个做。
（思考）
令 dpi,jdp_{i,j}dpi,j 为考虑前 iii 颗宝石，当前连续选取 jjj 颗。
转移方程为 dp[i][1] = max(dp[1 ~ i - 2][1 ~ j]) , dp[i][j] = max(dp[1 ~ i - 1][j - 1]) (2 <= j <= k)。
（这段我真不知道 LaTeX\LaTeXLATE X 咋打，会的能不能评论区留个代码谢谢喵）
转移时间复杂度懒得算了，总之就是很高。
注意到显然无法通过。
全局优化复杂度变为 O(nk)O(nk)O(nk) 显然还是过不去啊。
我感觉这个雷霆大区代码错了啊。
咋说呢，拉了一地。
不是咋还几把 RE 了，看来这把模拟赛要区了。
感觉我转移是对的，写个朴素暴力吧。
啊不对是我答案统计错了，这回至少答案是对的。
不是怎么 RE 了。
这数据是不是假了啊？
不是为啥爆内存是 RE 啊，何阴。
可以，喜提 60pts60pts60pts，正解先不想了。
去看看 T5。
直接打暴力。
不是你等会，为什么感觉这个 T3 实则非常简单（也记住这个结论）。
好像有性质。
算了还是去打暴力吧。
开 T5。
注意特殊性质。
Sub1 N,M≤1000N,M\leq1000N,M≤1000, 通过 O(NM) 暴力查询求解。
Sub2 Sj=TjS_j = T_jSj =Tj ，即营业时间为一个点，先不考虑。
Sub3 Sj=1S_j = 1Sj =1，将所有顾客按照右端点排序后二分，复杂度 O(NlogN+MlogN)O(NlogN + MlogN)O(NlogN+MlogN)。
Sub4 后一个营业时间窗口后于前一个，考虑双指针求解（遇到右端点数量 −1-1−1，左端点数量 +1+1+1）。复杂度 O(N)O(N)O(N)。
Sub5 没有特殊性质不做思索。。
成功通过 Sub1。
不是我 Sub3 怎么能挂了呢?
不是我突然意识到我输出的东西是错的，但是这个雷霆样例让我输出正确答案。
所以我 Sub3 为啥还是错的，666 这 IDE 是不是魔了。
注意到我好像对 Sub3 的判断了，实际上跑的是 Sub1 的函数。
Sub3 果然写了，注意到应该判断左端点而不是右端点。
咋还*。这么阴。
Bro 差点一拳给电脑飞了。
不是我调试忘删了。
好的还是不过。
好的发现二分写挂了，但是调整后还是不过。
隔壁怎么 AC T6 了，我压力很大啊。
不是隔壁咋看题目难度去了。
行了我滚回 T6 行了吧。
滚回来开题了，考虑优化成一维然后赌题目数据水。
为啥*一个点啊，等会去骗一下点。
不是我去这个 T3 也是垂死病中惊坐起啊，这不二分答案吗我还给跳了，我是伞兵。
你批发爷爷只用了 epsepseps 秒就接受了这题是雷霆大二分答案的事实。
显然二分一个最大值，然后贪心分配。
不是我二分答案还能挂掉?
好吧拆分写挂了。
这题加上前面这一坨游记类注释才 32 行，我是怎么一眼看出这玩意不可做的。 AC，回去条 T6。
顺手看了一眼面板，咋还是没人。
目前分数：100+100+100+0+12+90+0=402/700100 + 100 + 100 + 0 + 12 + 90 + 0 = 402 / 700100+100+100+0+12+90+0=402/700。
估计分数：100+100+100+50+56+100+0=506/700100 + 100 + 100 + 50 + 56 + 100 + 0 = 506 / 700100+100+100+50+56+100+0=506/700。
当前估计：100+100+100+0+12+100+0=412/700100 + 100 + 100 + 0 + 12 + 100 + 0 = 412 / 700100+100+100+0+12+100+0=412/700。
问就是 T4 真弄不了了，这把给了。
T6 这个点是大数据，考虑被 hack 掉的可能性。
我去居然不是 long long，那很有难度了。
算了不管了。
开 T7，此时还剩十分钟我能逆转吗？
epsepseps 秒鉴定出贡献法，左右两个单调栈求两边第一个比这个元素大的。
孩子们贡献法我真写不出来了，写个 O(N^2) 单调队列这把给了。
是的孩子们我逻辑还写挂了只拿了 10pts10pts10pts，这把给了。
还好不放榜，目前成绩以另类的方式上了 412412412，这把能入 rk5rk5rk5 我吃。
截止，给了。
不是什么叫 412/700412/700412/700 rk4rk4rk4，这把又有了。
回宿舍继续打牌。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
DAY 6
早上依旧比室友早起，不是我被子咋掉地上了啊。
今天学这个雷霆并查集和这个雷霆最短路和这个雷霆最小生成树啊，直接拿下。
哎不是居然不讲 Prim。
中午进行饭的吃。
象征性一根青菜。
下午最短路。
我去今天晚上考试。
> 下方依旧赛时碎碎念。
六百六十六今天是板子赛。
666，T1 居然是并查集板子。
不是这个板子是啥阴间数据啊，路径压缩了还不给过。
细节换 C 风格输入输出。
啊这里输出没换。
不是我给查询的 fa[x] 写成 x 了这期神了，严肃一发过然后开 T2。
ok 啊 T2 是 MST 板子，这必须一发拿下啊。
样例直接挂。
不是我怎么忘记并查集合并了啊。
啥叫 3A 4W 3TLE。
不是我怎么又把输入边的 m 写成 n 了。
好的现在上 505050 了。
哇还有 TLE 吃的。
不是 IO，那改 vector？
啥叫把 long long 撇了能多拿十分，跳了勿念。
不是啥叫我复制的并查集板子是错的。
这不就过了。
T3 是边权 ≥0\geq0≥0 的单源最短路，显然 Dijkstra，显然堆优化。
wq，居然写挂了。
bro 考试运比薄荷差。
不是我咋把起始点给 vis 了啊，这下对喽。
嗯这个 T4 等我思索一番，应该是跑 kkk 轮 Bellman-Ford 来的。
不是你等我回忆一下 Bellman-Ford 是咋写的，我记得应该是遍历边然后暴力转移吧。
ok，一发写挂。
奥两个 dist 数组的处理挂了，这下好了。
样例 2 炸啦！
不是这个地方为啥没转移过去。
破案，ldist 没转移。
不是，我咋把转移写循环外面了。
我去，红绿灯诶。
注意到判不可达炸了。
发现当前可以通过负权边从未到达节点转移，判断解决。
通过，剩一个小时开 T5。
负环，Bellman-Ford 板子，如果第 n 轮可以转移则有负环，否则没有。
我不行了，我咋把判断写到每个边的小循环里了。
十分钟速推 T5，目前还剩 49，剩下三题 一道 Floyd 一道背包动态规划一道莫名奇妙的最短路，先做 67。
T6 纯板子。
我去，这也能挂掉的。
吗，我又把输入边数量写成 n 了。
哇，还炸。
不是，何意味。
弄了点小判断过了。
T7。
是的我多测又没清空。
不是好像哪里有未定义行为啊。
奥 dp 开小了。
不是什么叫我前半段 WA 后半段 AC 啊。
不是我隔壁的大神居然不会写 Floyd。
不是！
我判断没法平分的地方没换行！！！！！！
被自己气笑了。
还剩半个小时开 T8。
我去隔壁居然写出来了。
不是那隔壁 AK 了啊，阴不阴？
正在关闭大脑进入绿皮思考状态。
完了呀我草，写挂了。
不是我输入边咋又写成 n 了。
直接 AK。
哎，你说这个玩意在原本基础上加了一层免费使用次数的维度并且把图纵向堆叠，
那这个玩意算不算三维最短路（不是）
舍友剩半个小时写的雷霆玩意：https://acgo.xiaomawang.com/discuss/post/90842
@书 @Wanderer @CarrotALittle
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
DAY 7
起床。
抢个酸奶，我戳，居然戳不开，我戳戳戳，哎居然冒了，蹦我一身。
上课。
中午回去打牌，神秘室友居然想 UNO 一挑三被我们直接拿下，
下午继续上课课课课课，玩神秘游戏我直接面壁者，这把根本不可能死的。
然后就是比赛。不是赛前为啥还要押出去活动。
> 胡话：
AUV，居然忘记写了。
T1 是雷霆大签子。
T2 居然一发过了？
坏了，T3 这个 LCA 是咋写的来着。
？何意味怎么挂了。
不是我交换为啥没套 depth 啊。
挖去居然 TLE 了，我已疾苦，立刻开始流解绑。
通过。
不是我在上 CSP 之前都不可能写 C 风格 IO 的好吧。
我去，这个 T4 怎么这么像红黑树。
不是这个输入为啥是爹地表示法啊。
隔壁的 T4 好像莫名写挂了。
隔壁过了，我还在运行错误是何意味。
不是，居然是玄学，为啥在 if 语句里面给数组里的元素赋值会运行错误啊。
不是，啥叫现在有 A B C 三个语句，运行 B 不报错，运行 A 不报错，运行 A + C 和 A + B 报错？
我已气笑，为啥我能把遍历边的 g[u] 写成 g[N] 啊。
一发过，浪费我二十分钟，气笑啦~（砸桌子）
当然作者还是没砸的，考试还要继续，实在不行考完再砸。
T5 是啥雷霆造物，先跳了。
T6 好像是动态规划，那还说啥了等会写爆搜了。
哎呦我 T7 又是啥阴间物体。
不行了，先爆搜 T6。反正老师说后半段是得分赛。反正保底 400pts400pts400pts 了，以我们班神人的平均水平肯定是考不到 rk998244352rk998244352rk998244352的。
啥叫 T6 有 50 个点，啥又叫我 A 了 15 个 拿了 30pts30pts30pts。
不是为啥还有 WA 啊。
算了不管了，开 T7。
我不行嘞，先写个朴素 LCA 然后取权。
我去？这能过啊？
剩下半个小时，开一下 T5。
T5 第一眼能写 O(n3)O(n^3)O(n3) 的暴力。
ok。
目前 100+100+100+100+50+30+100=580/700100 + 100 + 100 + 100 + 50 + 30 + 100 = 580 / 700100+100+100+100+50+30+100=580/700，估计 rk3rk3rk3，等结束。
不是怎么更新 T7 数据了，那不羁绊炸了。
不是坏了坏了，咋还炸啊。
不是为啥羁绊变 0pts0pts0pts 了。
那不羁绊炸了啊，给我干成 480480480 了，目测 rk8rk8rk8。
不是啥叫 ACGO 取的是提交最高分，然后我飞回 rk3rk3rk3 了。
这期神了。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
附件 1 UNO 自定义牌村规
开始之前掷骰子来决定这一局游戏使用的规则。
1. 普通万能牌
2. 万能 +6+6+6
3. 万能 +8+8+8
4. 反弹（回到上一个人的回合，如果有加牌则视为对这个人使用的）
5. 指定一个人 +5+5+5，如果此人仍然有可以打出的加牌则从此人继续，否则加牌后回到使用者的下一个人（游戏人数 ≥3\geq 3≥3） 或 将自己手牌选择 333 张给予对方（游戏人数 =2= 2=2）
6. 每次使用自定义牌时，在上面的 555 个规则中任选一个打出。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
1. 你知道为啥我不写尊称吗，因为尊称被 ACGO 打码了。 ↩︎
