周五​

周五先去和24学堂的学弟们吃了春水锅贴，之后去了中心校区打了一下午乒乓球，之后返回酒店休息。

周六​

周六上午一直在睡觉，下午去了软件园校区签到和热身，热身赛好多原题，尝试写去年昆明邀请赛的原题一雪前耻（最后也没写出来），当时思路对了但每写出来，这次还是没有，得加训了/fendou。

伴手礼很好看，卡皮巴拉很可爱，徽章只拿到了三个洪楼的，之后立下了第二天一定要做7道题的目标（最后也达成了）。

去吃软件园食堂，先去买了写水果和饮料，一边刷自己山大的学生卡一边说 “羡慕山大” （bushi），之后去吃了食堂的烧烤，感觉烧烤做的还是很不错的，比青岛校区的宵夜烧烤好很多。

之后返回酒店，看到晚上还有场 CF Div2，心血来潮就熬夜打了一场，还上了很多分，挺好的，也是幸好第二天早上起来了。

周日​

早上起来在酒店里吃了早饭直接前往软件园校区，看了开幕式。

正式赛前考虑到之前打比赛的时候 I 题一般都是简单题，然后就和队友说这把先做 I，这也为后面拿到首 A 埋下了伏笔。

比赛正式开始后先让队友读的 I 题，读完发现确实可做，另外发现了其他签到题，于是队友在验证 I 题的做法对不对，我在这个期间内签到了 L 题。

之后读了 H 题，把题目想复杂了就往后放了放想后面在做。

光速签到了 D 题，之后就开始苦战 A 题，和队友合力写出了正解，但代码写挂了，交上去一直 WA，但是 DP 思路又没有任何问题，后面队友开了 G 题我继续检查 A 题代码，花了大约不到 2h 的时间检查出来了 A 题代码的问题，遂去上厕所，上完厕所回来已经改好了。

后来读 H 题，发现之前把题目想复杂了，但一开始写代码没有注意到边权可能为 0 罚了几发，后面改过去了。

后面开始思考还有哪道题可以做，队友认为 E 题可做但我认为 K 题可做，最后我发现我做 K 的思路假了，一直没做出来，型号队友那边把 E 开出来了。

最后拿到了正式队伍的第八名，金奖+最快过题奖。

总结​

感觉这场的配合和发挥已经挑不出什么问题了，大家都尽可能的把水平发挥到了极致，也许还差那么一点运气，为自己鼓掌👏。

开局我签了L和I，董家豪签了D，宿子腾签了H，第一个小时没啥大问题。后面A在和董家豪商讨的时候略有卡顿，G和H也都并不是做的很快，只是基本维持正式榜第一这个水平。这个时候三个小时7题，如果只是夺冠的话这个速度是没问题的，但这个时候我们队伍出现了一些致命性的错误：一个是宿子腾去开K题了，并且提供了一个听起来很真的假做法（当时的情况下，因为强队比较少，较难的题开出来其实没什么参考价值，K也是只有那个高中生队伍过的，赛后看来不应该跟这个），因为做法错误浪费了很多机时，并且也多了一发罚时，同时董家豪开了J题；另一个是当时C题竟然没有任何一个人去认真思考过（加上榜也有些歪）。最后的结果就是宿子腾的K假了，然后我想到正解去写，因为一些奇怪的小细节调了很久。他们俩在这段时间就是在讨论J题也还是没有看C，中间是轮流用机子，我在调他们在写。我在K过了以后就在看看最后45分钟能不能再搞个什么题，M和B看了会儿浪费了时间，看到C其实五分钟就想到正解了，此时还有半个小时结束，他们俩J题写完样例不对，我想写C。但接下来就是传奇复刻23杭州站的经历：两个题轮流占机子最后都没过。

就结果来说，离冠军只是差十几分钟，这点似乎完全可以避免，只要前面H记得删freopen，或者K调快一些 or 少交一发。当然也可以说一堆环境因素，比如机房闷热导致注意力涣散写代码精度不够。但其实就比赛本身，这都不是最关键的，最关键的是三个小时那个时间节点，对于此类比赛的理解不够，在题目没有被开出来的情况下开题过于随意，因为竞争不够强烈所以对于题目的判断是失误的，一直以来跟榜的经验在这场比赛反而出了问题（最后开始写以后又没有再看榜修正策略，可以说基本错完了）。这场比赛9题/10题我觉得才应该是正常发挥，去说那十几分钟的罚时实在是意义不大。毕竟C和M都不是什么非常难的题，M只要有一个人去画画图找找规律可能就看出来了，C则是机时再给点就够（赛后几分钟就调出来了，其实就差一点点）。

总结了那么多，其实可能也没什么用。反思/补题这些事情都已经逐渐被淡化了，有的时候可能侥幸达到了一个小目标队伍就已经失去了动力了吧。这种事情就又让我想起来高中的时候被禁锢在“功利性学习”的牢笼里，被告知着“只有进了省队才对你升学有帮助”“没希望的同学乘早回归文化课”。可能矛盾就是从始至终，我既然从那个时候开始就不愿把升学和竞赛挂上钩，现在也没有理由因为得到个所谓的“金牌”就松懈吧。但想了想，虽然大学有了所谓自由选择的权利，但这个比赛终究不是个人的事情，总有人需要走他的正道，也有人有他的学业担忧。说白了，并不是大家都愿意去在这个事情上面花费时间，陪你去追逐他不曾寄予希望的事情的，我从这一刻才意识到昆明站的“金牌”实际上是一个多么大的一剂毒药。但非要说的话，最关键的是“自主学习”这件事情本身，竞赛也好，其他什么东西也罢，不该让自己怠惰下来。

这是关于直升机无数次启航，无数次坠毁，无数次从希望到失望、到绝望、到最终惊险着陆的故事。

2024年3月，helicopter团队正式组建，一名原OI选手，一名技术高手和一名转专业者乘直升机启航，误打误撞步入XCPC的世界。一次次训练赛，一次次磨合，三人逐渐形成默契。然而作为初学者，我们很快在2024年邀请赛排位赛中被打爆，无缘邀请赛，又在省赛排位中铩羽，以校区第11名的成绩宣告坠机。然而苍天有眼，2024年由于CCPC邀请赛与省赛撞车，前面的队伍都去打邀请赛，省赛资格顺延到第十名，此时善良有爱心关心后辈的学长选择打星，我们以倒数第一的成绩获得省赛资格，并在省赛获得银奖。

此后的暑期集训中，我们的知识逐渐丰富，水平逐渐提高，然而辛苦一个暑假却在最后的排位中遗憾榜尾，痛失区域赛资格。于是2024年下半年无任何作为。helicopter陷入低谷。

寒假狠狠加训之后，我们满怀信心参与邀请赛排位，然而场上决策失误，三人同一题写了三份代码，耽误大量时间还没有过题，导致排位靠后，似乎无缘邀请赛。我们把希望寄托于最后的省赛排位。省赛排位发挥得不错，封榜前排名第六，刚好能获得省赛资格，然而最后一小时没过题，解榜后发现自己被挤下去一名，兴奋转为沮丧，似乎我们又没有比赛可打。当时已经准备写退役小作文了。

5月迎来了转机。广西邀请赛与河南邀请赛发布，我们拿到了广西邀请赛的名额。在多次失败、多次位于坠机的边缘时，一缕曙光照射进来，直升机再次回到正轨。

游记部分

5月23日，我们乘飞机来到桂林。学校很大，食堂很多。报道过程很无趣，签完名字就走了，没有伴手礼。下午的热身赛确实让人红温，座位很挤，延迟了很长时间才进场，进场后看不到电脑屏幕，完全不知道环境。在志愿者的紧急修复之下，大家终于还是在第二天正常看到了屏幕。编程环境无话可说，VSCode十分神秘，当然我们已经见怪不怪了。不过DevC++的性能还可以，凑合用。

我们在正赛开始一分钟后才入场，开局一小时签到4题。然后开始罚坐。我想字符串的题，队友搞计算几何。一小时想到正解，然后我率先上机写字符串，成功WA，疑惑、分析，队友开始写几何。在研究了下字符串后发现需要枚举每个字符然后用字符串匹配算法，然后自信上机写KMP，交上去样例都没过，红温。队友的计算几何终于搞完，然而或许是精度原因交完就WA。于是我们在压抑中度过了没有过题的三个小时。

最后的颁奖典礼一言难尽，没有滚榜失去了很多乐趣，PPT现场改，发奖发错。。。看得出主办方想搞些创新，尽最大努力把比赛办好，然而时间太紧张，经验也不足，导致最后呈现的效果不是很理想，很多人体验糟糕。

尾声

这是helicopter的退役战，此后团队解散，大家都回到各自的生活。这趟短暂的XCPC旅程没有带给我们理想中的胜利，反而留下了很多遗憾。此后，我又将回到浑浑噩噩的，三点一线的生活中，做着做不明白的实验，学着学不明白的课，在学校、社会中随波逐流，回到刚转完专业的迷茫与混沌状态，坠入精神崩溃的深渊。然而，这场旅途似乎没有改变什么，却又悄然把什么东西种在心里。平淡如水的生活因为XCPC而变得不在平庸，无数次置之死地而后生的经历诠释着拼搏的意义，我们拼尽全力，放弃一切，只为热爱，木制的奖牌铭刻着属于我们的光阴。

也许追求本就没有意义，也许追求本身就是意义。

队伍：梦想家Sleeping Thinkers 队员：黄志强、黄天泽、刘慧剑 时间：2025.5.25

赛前：​

不应该在12306买机票，只会显示一部分机票。这导致当时看到的机票只有一种，于是买的机票比携程里的机票贵一些，时间又久(经停杭州)。于是买了7点10分起飞的机票，导致把23~26的课全部请假了，酒店又多买了一晚，23号早上还要4点起来去机场，太哈人了。

不要在机场吃饭，太贵了。一碗面43块，太哈人了。

热身赛时：​

应该以测试环境和设备优先。当时鼠标点得很费力，键盘和电脑打代码也卡卡的，当时没跟志愿者说明这个问题，第二天正式赛只换了鼠标，效率还是蛮影响的。

正式赛时：​

赛时签到题有三道，两道很快解决了，还有一道算日期差的有点麻烦，硬模拟过去的。应该学点python的黑科技的。

签到题解决完分头想简单题了，看题目开了一个图论(J)，一个计算几何(K)，一个数学题(B)。图论是简单的，但是队友战犯了，先预处理后读数据，硬说我板子有问题，于是J没过。

B，队友又战犯了，题目读错了还是思路想错了，WA了4发导致后面罚时巨大，给我一看换了个思路就过了。

K，计算几何从来没想过能开，所以没有准备板子。但是赛时的计算几何是比较简单的，于是在费时间手打一份，结合三分法原则是能过的，坏消息是太相信队友了，给了好多时间写B，后来计算几何没写完。

总的来说头一年打比赛草草结束，本来以为打铁的，没想到还有个铜，努力明年再战吧。

回顾一下赛时，我个人觉得最战犯也最需要改的问题是，一个明明很多人过了的题，队友卡着了，没去帮队友，而是写自己开的题。应该趁早去帮队友的。

赛后：​

比较后悔吃了三天的外卖，临走前想吃一下地方特色 桂林米粉，结果没买到。

和队友一起处理费用有点难算账，尤其是当钱不能被三整除时。明年应该单独拿一个银行卡出来，每人往里转相同数量的钱，然后使用这个账户的钱来支付一起的费用，等赛后再除以三算账。

队伍：ac不了打铁的我是不是m/mrc

Day -1​

七点到十点的飞机，到桂林时天已经黑了。学校很偏，坐了一个小时车，最后十几分钟都是崎岖的山路；酒店差不多在学校门口，周边店铺大多都关门了，因此没有吃晚饭，在便利店随便买了点。

睡前确认了第二天的行程安排，汇总了发票，发现打车平台提供的发票不包含高速费。上网搜索得知报销高速费需要单独支付，不能由司机垫付。太困了忘记汇报这个发现，导致伏笔到 d3 。

Day 1 热身赛​

13：00之前都能签到，领了牌子和衣服后找了家酸菜鱼对付。

原定 15：00-17：00 热身赛，按时到后发现大家都围在门口。查看赛事群，得知线被老鼠啃了，延误一小时。

提前发了题，口嗨 ak 了。

服务器断电了，再延误半小时。

16：30 进场，调试了设备和环境，写了缺省源。cd一直没过，赛后吃饭的时候发现是读错题了。

进学校时步行10分钟，离开学校时在 yhk 的领导下骑着车迷路了 20 分钟。

Day 2 正式赛​

签到 ADH ，注意到 B 题也有很多人签了，但是三个英语羸弱读出了三份不一样的题意，其中有两种都不太可做。争执了十分钟语法后按最简单的一种题意写了一发，过了。

看到 E 想到后缀自动机，但是不会写，乱搞了一会儿后缀 trie 树和神秘构造，无果；

看到 K 想到求根公式算交点再讨论交点相对位置，可能是精度炸了，调了半小时，无果；

看到 J 想到了一个双重树链剖分的写法，容易发现子节点> 1 的分叉点最多有 17 个，两个节点 $u$ 和 $v$ 的 $lca$ 一定在 { $u,v,$分叉点 } 中，维护分叉点集合，再用两个树链剖分分别维护新加入的点作为 lca 或另一个点作为 lca 的情况下对答案的贡献，一个区间加单点询问，一个单点加区间求和，太难写了先去开别的题了；

看到 G 想到用 01trie 同时维护 a 和 b，每个节点有四个子节点，0，表示 a 和 b 这一位各自的取值，再按位计数，然后爆栈了，赛后听讲题跟正解思路差不多，但是需要用另外一棵 01trie 预处理相等的情况；

看到 L 口胡了五分钟基本不等式和莫比乌斯反演，无果，脑嗨了一下枚举约数，没想完就结束了。

颁奖仪式因为技术原因没有滚榜。先是神秘延迟，再是 ppt 出错，然后名额计算分配也出错，总之相当的 ctbz，最后凭借超绝区分度和罚时混了个 ag 。

在广西吃到了相当正宗的热干面。

Day 3 返校​

离开前想着不能白来，约定好去市中心吃顿饭。本来说是要体验一下广西特色，不知道为什么最后选定了一家湘菜馆（）然后在广西吃到了还算正宗的湖南菜。

延误体质发力，返程时飞机稍微延误了40分钟。下次一定买延误险。

返校时问的 syf 打车，忘了再提醒他高速费的事，导致净亏高速费*2。

F​

奖励题，输出 $N-1$。

没过的都拉出去突突了。

I​

阅读题，

A contest date is too late for TOPC if it is not at least 35 days prior to Octobor 21, 2023. Please write a program to determine whether a tentative contest date is too late for TOPC.

L​

签到题，比预期中的发现时间要早。如果 $m\times s\geq n$ 则输出 $1$，否则输出 $0$。

A​

输出一个两边为 $1$，中间为 $0$ 的金字塔。

B​

暴力即可

枚举 $k$，之后删去其倍数，遇到需要保留的就break掉。

G​

排序，之后从小到大选三个数，以中间的数字为标准，修改两边的木棍，遍历一遍求最小值即可。

E​

首先预处理出从那些位置开始的 s 的子串刚好可以匹配 t,之后用前缀和维护，注意查询的时候右端点改为 $r-t.size()+1$。

J​

爆搜题，注意可能会爆int。

把士兵当作节点，士兵之间的关系当作边。

用dfs遍历图，如果发现一个士兵之前已经分配过营地，且当前给到的营地位置与上次不同则不满足，否则遍历下来没有矛盾的话就是可以满足。

K​

三国杀题，（恶趣味）。

经典背包DP 模型，$dp_{i,j,k}$ 表示前 $i$ 张卡牌中，两组牌的点数差值为 $j$ （可以为负），共$k$张牌选择翻倍。

状态转移方程如下：

$\begin{cases}dp_{i,j,k}=\max(dp_{i-1,j-t_i,k}+v_i)\\dp_{i,j,k}=\max(dp_{i-1,j+t_i,k}+v_i)\\ dp_{i,j,k}=\max(dp_{i-1,j+t_i\times2,k-1}+v_i)& k>0\\ dp_{i,j,k}=\max(dp_{i-1,j-t_i\times2,k-1}+v_i)& k>0\end{cases}$

#include<bits/stdc++.h>
#define int long long
#define N 110
using namespace std;
int n,k,v[N],t[N],dp[2][4610][N];
signed main(){
    scanf("%lld%lld",&n,&k);
    for(int i=1;i<=n;i++){
        scanf("%lld%lld",&v[i],&t[i]);
    }
    for(int i=0;i<=4600;i++){
        for(int j=0;j<=k;j++){
            dp[1][i][j]=dp[0][i][j]=-1e18;
        }
    }
    dp[0][2300][0]=0;
    for(int i=1;i<=n;i++){
        for(int x=0;x<=k;x++){
            for(int j=0;j<=4600;j++){
                dp[i&1][j][x]=dp[i&1^1][j][x];
                if(j>=t[i]){
                    dp[i&1][j][x]=max(dp[i&1][j][x],dp[i&1^1][max(0ll,j-t[i])][x]+v[i]);
                }
                if(j+t[i]<=4600){
                    dp[i&1][j][x]=max(dp[i&1][j][x],dp[i&1^1][min(4600ll,j+t[i])][x]+v[i]);
                }
                if(x&&j>=2*t[i]){
                    dp[i&1][j][x]=max(dp[i&1][j][x],dp[i&1^1][max(0ll,j-t[i]*2)][x-1]+v[i]);
                }
                if(x&&j<=4600-t[i]*2){
                    dp[i&1][j][x]=max(dp[i&1][j][x],dp[i&1^1][min(4600ll,j+t[i]*2)][x-1]+v[i]);
                }
            }
        }
    }
    int ans=-1e18;
    for(int i=0;i<=k;i++){
        ans=max(ans,dp[n&1][2300][i]);
    }
    printf("%lld",ans);
    return 0;
}

C​

我们考虑朴素的枚举做法，用一个链表暴力模拟，并判断当前的歌和上一首歌的风格的 GCD 是否为 1 即可，一直到一轮下来没有任意一首歌被删除为止。

但这样做的话很显然会超时，我们发现有些歌在上面暴力枚举的时候被重复计算了多次，但有些歌被重复计算多次，我们考虑如何将重复的计算优化掉。

我们不难发现，判断歌曲风格的关系是按一定顺序的，而且这个顺序与队列的 First in First out 的关系是相同的，我们考虑用一个队列进行维护，记录所有需要判断关系的歌曲的编号，这样在计算 GCD 时只需要计算队列中的，可以省去所有重复的计算。最后按队列模拟时删除的顺序输出即可。

#include<bits/stdc++.h>
using namespace std;
int n,T,sum,maxn;
bool v[100010];
struct node{
    int a;
    int l,r;
}a[100010];
struct nod{
    int x,y;
};
vector <int>ans;
signed main(){
    scanf("%d",&T);
    while(T--){
        scanf("%d",&n);
        for(int i=1;i<=n;i++){
            scanf("%d",&a[i].a);
            v[i]=0;
        }
        ans.clear();
        queue<nod>q;
        for(int i=1;i<n;i++){
            q.push(nod{i,i+1});
            a[i].l=i-1;
            a[i].r=i+1;
        }
        a[1].l=n;
        a[n].l=n-1;
        a[n].r=1;
        q.push(nod{n,1});
        sum=0;
        while(!q.empty()){
            int x=q.front().x,y=q.front().y;
            q.pop();
            if(v[x]){
                continue;
            }
            if(__gcd(a[x].a,a[y].a)==1){
                v[y]=1;
                int p=a[y].r;
                a[p].l=x,a[x].r=p;
                q.push(nod{x,p});
                ans.push_back(y);
            }
        }
        printf("%d ",(int)ans.size());
        for(int i=0;i<ans.size();i++){
            printf("%d ",ans[i]);
        }
        putchar('\n');
    }
    return 0;
}

H​

没想到赛时被新生做出来了，膜拜orz。

根据题目中建图的性质，我们可以考虑对一个数转化成二进制的形式，并记录每一位的 $1$ 的个数，若在某一位上，有至少 $3$ 个点这一位为 $1$，那么这三个点之间都有一条边，也就是形成了一个三元环，根据数据范围，把所有数转化成二进制后最多有 $64$ 位，根据抽屉原理，当 $n> 128$ 时，一定存在一位，该位为 $1$ 的点的个数超过 $3$，对于其他的情况，因为 $n\le128$，我们直接用 floyd 判最小环即可。

注意，$a_i$ 可能存在为 $0$ 的情况，我们要排除所有为 $0$ 的点，用非 $0$ 的点的个数作为 $n$ 进行判断。

D​

首先看到求最短路径的最大值，最小值最大，妥妥的二分答案。

根据题目中两个点之间连边的边权的性质，不难推断出最大值一定出现在相邻的两个点之间，不相邻的两个点之间可能存在更小的值，即使是有更大的值也不会成为边权。

两个点之间的最短路要么是两个点之间的边直达，要么是找一个最小的点，以最小的点作为中转站在两个点之间折跃，即点 $l$ 和点 $r$ 之间的最短路为 $\min( \min(1,n)\times2,\min(l,r))$。

在二分枚举答案时，假设当前枚举的答案为 $pos$ ，可以考虑设一个前缀和和一个后缀和，统计 $a_i\times2\le pos$ 的 $i$ 的数量，因为每个 $a_i\times2\le pos$ 的 $i$ 即是我们需要修改的点。

我们从 $1$ 到 $n-1$ 枚举，统计最小的 $pre_{i-1}+sub_{i+2}+ord(a_i<pos)+ord(a_{i+1}<pos)$，判断是否成立即可。

M​

防AK题，看上去这道题有很多不同的做法，我讲一下我的随机化做法：异或哈希。

因为这里只需要考虑区间内的数字的出现情况，不需要考虑他们的先后顺序，所以我们可以用异或运算来计算他们的哈希值。

为了避免异或值重复的情况，我们用梅森旋转算法将 $1\sim n$ 赋成一个随机值，用一个数组 $base_i$ 记录前 $i$ 个数的异或和，这样一会在判断该序列是否为一个自排列的时候会方便很多。

我们考虑枚举所有 $1$ 的位置，分别向左和向右搜索能达到的最大值，用这个最大值当做序列的长度，设这个最大值为 $m$，并判断序列内的异或和是否与前 $m$ 个元素的异或和相等即可。

为了节省时间复杂度，我们考虑利用前缀和进行优化，用前缀和模拟向左搜索的过程，再将整个序列倒过来模拟向右搜索的过程即可。

这场的题目感觉出的还是很不错的，很多经典套路题和模板题的修改，感觉至少 A,B,D,E,H,I,L都是可做题，下面简单讲一下题目：

A​

原题链接

内向型选手直接自己住一屋就好，不用考虑。

外向型选手必须住三人间，首先满足所有外向型选手，如果不是 3 的倍数就从综合型选手里补，这题就结束了。

B​

原题链接

最大子段和模板，找出最大子段和并一直在最大子段和的末尾插入最大子段和，之后最大值翻倍，这样一直加 $k$ 次。

注意子数组可以为空。

L​

原题链接

这道题可以考虑在原数据上变化，首先大于等于 $2$ 的数可以在原基础上任意变大或者减小，我们需要考虑其中为 $1$ 的值，因为 $1$ 只能增大不能减小。

用一个前缀和维护区间 $1$ 的个数，另一个前缀和维护区间内所有数的和。

每次判断所有数的和能不能令所有的 $1$ 增大即可。

I​

原题链接

也是一道简单题，但赛时似乎一直没人发现。

将数组 $a_i$ 与 $b_i$ 排序，之后令 $a$ 的后 $x$ 项与 $b$ 的前 $x$ 项对比，再令 $a$ 的前 $n-x$ 项与 $b$ 的后 $n-x$ 项对比，判断是否满足条件即可。

E​

原题链接

二分答案题。

通过二分枚举答案 $x$。

每次 dfs 遍历树，贪心，若当前子树的节点和已经大于 $x$（去掉已经分离出去的子树），则将该子树分离出来。判断分离出来的子树的个数是否大于 $k$ 即可。

#include<bits/stdc++.h>
#define N 200010
#define ls x<<1
#define rs x<<1|1
#define MID ((l+r)>>1)
#define mkp(a,b) make_pair(a,b)
// mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());
//#define int long long
//#define P pair<int,int>
using namespace std;
vector<int>G[N];
int T=1,n,k,cnt;
int dfs(int x,int fa,int ans){
    int res=1;
    for(int to:G[x]){
        if(to==fa)continue;
        res+=dfs(to,x,ans);
    }
    if(res>=ans){
        cnt++;
        return 0;
    }
    return res;
}
bool check(int x){
    cnt=0;
    dfs(1,0,x);
    if(cnt>k){
        return true;
    }
    return false;
}
void solve(){
    int l=0,r=100001;
    int ans=0;
    while(l<=r){
        if(check(MID)){
            ans=MID;
            l=MID+1;
        }
        else{
            r=MID-1;
        }
    }
    printf("%d\n",ans);
}
signed main(){
    scanf("%d",&T);
    while(T--){
        scanf("%d%d",&n,&k);
        for(int i=1;i<=n;i++)G[i].clear();
        for(int i=1;i<n;i++){
            int u,v;
            scanf("%d%d",&u,&v);
            G[u].push_back(v);
            G[v].push_back(u);
        }
        solve();
    }
    return 0;
}

D​

原题链接

单调栈模板。

我们考虑当 $s_i>s_{i+1}$ 时，删掉 $s_i$ 会使字符串的字典序变小。

根据字典序的定义，我们每次删掉最左边的满足上述条件的 $i$，得到的下一个字符串的字典序是所有的可能的情况中最小的。

朴素做法是 $O(n^2)$ 的，所以我们用栈来模拟位置 $pos$ 所在的字符串的情况，遇到上述情况就将栈中最后一个字符串弹出即可。

#include<bits/stdc++.h>
#define N 1000010
#define ls x<<1
#define rs x<<1|1
#define MID ((l+r)>>1)
#define mkp(a,b) make_pair(a,b)
// mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());
#define int long long
//#define P pair<int,int>
using namespace std;
char s[N];
bool v[N];
vector<int> p[26];
int T=1,n,pos;
void init(){
for(int i=0;i<26;i++) p[i].clear();
memset(v,0,sizeof(v));
}
signed main(){
scanf("%lld",&T);
while(T--){
    scanf("%s",s+1);
    n=strlen(s+1);
    scanf("%lld",&pos);
    init();
    int round=0,siz=n;
    stack <int> st;
    for(int i=1;i<=n;i++){
        while(!st.empty()&&pos>siz&&st.top()>s[i]){
            st.pop();
            pos-=siz;
            // cout<<pos<<endl;
            siz--;
            round++;
        }
        st.push(s[i]);
    }
    while(pos>siz){
        pos-=siz;
        st.pop();
        siz--;
        round++;
    }
    while(st.size()>pos){
        st.pop();
    }
    putchar(st.top());
}
return 0;
}

H​

原题链接

可以考虑倒过来处理查询。

倒过来之后把插入点改为将点的值修改为 $0$。

用树剖和线段树维护子树和即可。

F​

一道 $\mathcal O(n^4)$ 的 DP。

考虑设置状态 $dp_{i,j,k}$，其中 $i$ 表示前 $i$ 个瓶子，$j$ 表示其中选择了 $j$ 个瓶子作为容器，$k$ 表示剩余瓶子的容量。状态转移方程如下：

$dp_{i,j+1,k+b_i-a_i}=\min{dp_{i-1,j,k}}$

$dp_{i,j,k-a_i}=\min{dp_{i-1,j,k-a_i}}$

#include<bits/stdc++.h>
#define M 20000
#define N 200010
#define ls x<<1
#define rs x<<1|1
#define MID ((l+r)>>1)
#define mkp(a,b) make_pair(a,b)
// mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());
//#define int long long
//#define P pair<int,int>
using namespace std;
int T=1,n,m;
vector<int>a,b;
int dp[2][110][M+10];
signed main(){
    // scanf("%d",&T);
    while(T--){
        scanf("%d",&n);
        a.resize(n+1);
        b.resize(n+1);
        for(int i=1;i<=n;i++){
            scanf("%d",&a[i]);
        }
        for(int i=1;i<=n;i++){
            scanf("%d",&b[i]);
            b[i]-=a[i];
        }
        for(int i=0;i<2;i++)for(int j=0;j<=n;j++)for(int k=0;k<=20000;k++) dp[i][j][k]=1e9;
        dp[0][0][10000]=0;
        for(int i=1;i<=n;i++){
            int x=i&1;
            for(int j=0;j<=n;j++){
                for(int k=0;k<=M;k++){
                    dp[x][j][k]=1e9;
                }
            }
            for(int j=0;j<=n;j++){
                for(int k=0;k<=M;k++){
                    if(k+b[i]<=M){
                        dp[x][j+1][k+b[i]]=min(dp[x][j+1][k+b[i]],dp[x^1][j][k]);
                    }
                    if(k-a[i]>=0){
                        dp[x][j][k-a[i]]=min(dp[x][j][k-a[i]],dp[x^1][j][k]+a[i]);
                    }
                }
            }
        }
        for(int i=1;i<=n;i++){
            int ans=1e9;
            for(int j=10000;j<=M;j++){
                ans=min(ans,dp[n&1][i][j]);
            }
            if(ans<1e9){
                printf("%d %d\n",i,ans);
                return 0;
            }
        }
    }
    return 0;
}

C​

原题连接

24年成都站原题。

账号绑定​

首先找到账号的设置页面。

在此处添加自己的学生邮箱，注意一定要是学生邮箱。

然后进入钱包页面，完善自己的钱包信息并保存。

之后打开这个页面

并往下滑找到

点击绿色的 Enable two-factor authentication 按钮。

在手机应用商店下载 Authenticator。

扫描出现的二维码，完成认证即可。

这时候我们回到 GitHub 首页，就会发现出现一个 Join GitHub Global Campus 的页面。

获取学信网认证资料​

目前上传图片按钮疑似大概率不会出现，可以直接快进到最下面的申请学生认证部分。

登录学信网账号，在个人资料左侧找到在线验证报告。

我们将申请的在线验证报告截图保存，在下一步申请时会用到。

申请学生认证​

点击首页的 Join GitHub Global Campus，进入学生认证页面。

滑倒最下面，此时邮箱和学校名称已经为你自动补全。

最下面的 "How do you plan to use GitHub?" 可以填 Study。

点击 Continue，然后上传刚才保存的学籍验证报告图片，等待审核即可。

注意这里照片文件大小最好要小于0.8MB，否则有概率上传失败

大约 $3 \sim 4$ 天后会有邮件通知。

目前上传图片按钮貌似大概率不会出现，可以尝试拍摄学生证等措施。

附加​

都看到这里了，把 JetBrain 的也申请了再走吧。

打开连接：JetBrains 学生产品。

由于国内学生邮箱管理比较混乱，我们不能通过大学电子邮件地址和 GitHub 进行申请。

选择官方文件选项，按要求填写信息，上传刚才的学信网截图和学信网报告在线验证码即可。

这个申请速度比较缓慢，等待即可。

插件篇​

github copilot​

这个是必须要推荐的一个神级插件，一个非常好用的 AI 代码助手，目前普通用户有一定使用额度，但可以通过申请github学生包获取付费权益，如何申请github学生包可以查看 这里。

可以点击右下角的 github copilot 图标或者 ctrl+shift+P 之后输入chat打开聊天页面。

Competitive Programming Helper (cph)​

可以提前设置样例，并一键运行全部样例并自动对比答案是否相同，可以省去自己手输样例的时间和肉眼对比答案的时间，可以搭配这个浏览器插件使用，可以一键爬去页面的样例信息并创建好对应的 cpp 文件。

Material Icon Theme​

一个美化vscode图标的插件。

C/C++ Compile Run​

简化 windows 环境下运行cpp文件的插件。

background-cover​

给 vscode 添加图片背景，可以添加自己喜欢的二次元背景。

CodeSnap​

一键生成漂亮的代码截图。

代码片段​

可以在 vscode 左下角 管理-代码片段 处配置默认模板，功能类似于 devcpp 的缺省源，但用起来更加灵活。

配置参考​

{
	// Place your snippets for cpp here. Each snippet is defined under a snippet name and has a prefix, body and 
	// description. The prefix is what is used to trigger the snippet and the body will be expanded and inserted. Possible variables are:
	// $1, $2 for tab stops, $0 for the final cursor position, and ${1:label}, ${2:another} for placeholders. Placeholders with the 
	// same ids are connected.
	// Example:
	"Print to console": {
		"prefix": "codeforces",
		"body": [
			"#include<bits/stdc++.h>",
			"#define N 200010",
			"#define ls x<<1",
			"#define rs x<<1|1",
			"#define MID ((l+r)>>1)",
			"#define mkp(a,b) make_pair(a,b)",
			"// mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());",
			"//#define int long long",
			"//#define P pair<int,int>",
			"using namespace std;",
			"int T=1,n,m;",
			"signed main(){",
			"	scanf(\"%d\",&T);",
			"	while(T--){",
			"		$0",
			"	}",
			"	return 0;",
			"}"
		],
		"description": "Codeforces output to console"
	},

	"daily use code": {
		"prefix": "log",
		"body": [
			"#include<bits/stdc++.h>",
			"#define N 200010",
			"#define ls x<<1",
			"#define rs x<<1|1",
			"#define MID ((l+r)>>1)",
			"#define mkp(a,b) make_pair(a,b)",
			"//#define int long long",
			"//#define P pair<int,int>",
			"using namespace std;",
			"int T=1,n,m;",
			"signed main(){",
			"	scanf(\"%d\",&n);",
			"	$0",
			"	return 0;",
			"}"
		],
		"description": "Log output to console",
	},
}