孙更欣

2024-2025学年负责人，ICPC银牌

查看所有作者

山东省赛游记--圆一定要是圆形的

2025年6月6日 · 阅读需 3 分钟

孙更欣

2024-2025学年负责人，ICPC银牌

周五

周五先去和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 开出来了。

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

总结

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

线下第二场题解

2025年2月23日 · 阅读需 8 分钟

孙更欣

2024-2025学年负责人，ICPC银牌

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$ 个元素的异或和相等即可。

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

线下第一场题解

2025年2月22日 · 阅读需 6 分钟

孙更欣

2024-2025学年负责人，ICPC银牌

这场的题目感觉出的还是很不错的，很多经典套路题和模板题的修改，感觉至少 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年成都站原题。

github学生包申请教程

2025年1月20日 · 阅读需 3 分钟

孙更欣

2024-2025学年负责人，ICPC银牌

账号绑定

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

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

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

之后打开这个页面

并往下滑找到

点击绿色的 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 进行申请。

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

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

vscode中一些好用的插件和配置推荐

2025年1月20日 · 阅读需 3 分钟

孙更欣

2024-2025学年负责人，ICPC银牌

插件篇

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",
	},
}

周五​

周六​

周日​

总结​

F​

I​

L​

A​

B​

G​

E​

J​

K​

C​

H​

D​

M​

A​

B​

L​

I​

E​

D​

H​

F​

C​

账号绑定​

获取学信网认证资料​

申请学生认证​

附加​

插件篇​

github copilot​

Competitive Programming Helper (cph)​

Material Icon Theme​

C/C++ Compile Run​

background-cover​

CodeSnap​

代码片段​

配置参考​

周五

周六

周日

总结

F

I

L

A

B

G

E

J

K

C

H

D

M

A

B

L

I

E

D

H

F

C

账号绑定

获取学信网认证资料

申请学生认证

附加

插件篇

github copilot

Competitive Programming Helper (cph)

Material Icon Theme

C/C++ Compile Run

background-cover

CodeSnap

代码片段

配置参考