CSP-S 2025 游记
JQKLUMARKAR · · 生活·游记
CSP - S 2025 游记 - JS - S00163
省流
\
可惜积了一肚子的德没用上。\
此处不含任何对现实的含沙射影。
追忆 - 摘抄
我常常追忆过去。\ 生命瞬间定格在脑海。我将背后的时间裁剪、折叠、蜷曲，揉捻成天上朵朵白云。\ 云朵之间亦有分别：积云厚重，而卷云飘渺。生命里震撼的场景掠过我的思绪便一生无法忘怀，而更为普通平常的记忆在时间的冲刷下只留下些许残骸。追忆宛如入梦，太过清楚则无法愉悦自己的幻想，过分模糊却又坠入虚无。只有薄雾间的山水，面纱下的女子，那恰到好处的朦胧，才能满足我对美的苛求。\ 追忆总在不经意间将我裹进泛黄的纸页里。分别又重聚的朋友，推倒又重建的街道，种种线索协助着我从一个具体的时刻出发沿时间的河逆流而上。曾经的日子无法重来，我只不过是一个过客。但我仍然渴望在每一次追忆之旅中留下闲暇时间，在一个场景前驻足，在岁月的朦胧里瞭望过去的自己，感受尽可能多的甜蜜。美好的时光曾流过我的身体，我便心满意足。\ 过去已经凝固，我带着回忆向前，只是时常疏于保管，回忆也在改变着各自的形态。这给我的追忆旅程带来些许挑战。\ 我该在哪里停留？我问我自己。
前言
本文章构思于 2025.10.16 的晚课。\
（说句闲话，这一天对我而言确实很特殊 —— 去年和前年的同一天，我都在学校参加集训，真的很巧合。同时也是苇草的生日，作为我开荒的主要角色，让我们祝她生日快乐）\
主要是前三年都参加了 J / S 组比赛，却一直没有写过游记，感觉有点遗憾。于是乎今年高一打算认真写篇游记。\
本文会经历可能的
- [x] 下发代码
- [x] 出分
- [ ] 获奖
Day \sqrt -1
初赛没考，GESP 过了 谁知道为什么我要给 熙熙艾福 送一大笔钱，可能是我是【】吧 )\
据说这次初赛很简单。You have no egg!\
我有一个纯化竞的同学都去考了。虽然没过线。
Day -15
上午月考考炸了……明天还有月考但是我感觉不重要了（？）还是紧着薄弱且重要的 OI 学吧。\
（这几天又要 whk 又要 OI，舟都没时间玩了 好想看看今天肉鸽 DLC1 到底有啥啊，以及到时候半周年 能不能在考场外面给我分配几个一起促的好友）\
得知复赛地点在南京，作为从来没有去过南京参加比赛的高一牲还是有些难受的，之前一直在苏州大学实验学校，当天开车半个小时就到了，今年估计甚至要提前去 & 坐高铁了。
- Upd on 2025/10/20：月考出分了，班排
10/19 ，至少不垫底。
Day -13
SCP 2025 第二轮（复赛 S 组）模拟：\ \
【MX - S8】梦熊 CSP - S 2025 模拟赛（同步赛）：\
校内 OJ 模拟赛：\ \ \
今天开始停课了，但是校内数理化生怎么都在开新课……\ 完蛋了回去要恶补 whk 了。\ 停课第一次模拟：\ \
停课第二次模拟：\ \
上午打打模板，重拾自己学过的东西。\ 停课第三次模拟：\ \
停课第四次模拟：\ \
上午停课最后一次模拟：\ \
早上生物钟 我们考场的监考志愿者衣服上别了个很明显的阿米娅徽章 (? 具体没看清施舍么类型的谷子) 诶。\
考场周围蚊子倒是不少，过程中也总是心烦意乱的。\
回去差不多
赛时(附代码)
概况
T1 贪心大概推了二十多分钟然后写代码调试了半天，差不多四五十多分钟把 T1 大样例都过了。\
T2 一眼没思路，先去瞅了眼 T3 / T4 发现后面都是不会的，只能骗分，而且即使骗分也感觉太麻烦了，就赶紧回来写 T2，注意到 我是 long long 信仰选手全开了 long long，其实只要一个结果变量开个 long long 就够了，但是本来做法也是假的只能祈祷能骗个更高的部分分了。\
T3 一开始没看懂，最后写了个
- Upd on 2025/11/8：突然想起来有个坑没填。出分了，
100+56+5+12=173
T1
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll T,n,Gp[5],a[5],ans;
priority_queue<ll> q[5],re;
struct node{
ll a,b,c;
ll first_max,second_max,delta;
ll final_choice;
}A[200005];
int main(){
freopen("club.in","r",stdin);
freopen("club.out","w",stdout);
scanf("%lld",&T);
while(T--){
scanf("%lld",&n);
Gp[1]=Gp[2]=Gp[3]=0;
q[1]=re,q[2]=re,q[3]=re;
ans=0;
for(ll i=1,cur_max;i<=n;i++){
scanf("%lld %lld %lld",&A[i].a,&A[i].b,&A[i].c);
a[1]=A[i].a,a[2]=A[i].b,a[3]=A[i].c;
sort(a+1,a+3+1);
A[i].first_max=a[3],A[i].second_max=a[2],A[i].delta=a[2]-a[3];
if(a[3]==A[i].a) A[i].final_choice=1;
else if(a[3]==A[i].b) A[i].final_choice=2;
else A[i].final_choice=3;
if(Gp[A[i].final_choice]==n/2){//Too many people
cur_max=a[2];//To go to the second one
if(q[A[i].final_choice].top()+a[3]>cur_max){//sorry bro, I have to replace you.
cur_max=q[A[i].final_choice].top()+a[3];
q[A[i].final_choice].pop();
q[A[i].final_choice].push(A[i].delta);
}
ans+=cur_max;
}
else{//Yes! I can join!
q[A[i].final_choice].push(A[i].delta);
ans+=a[3];
Gp[A[i].final_choice]++;
}
}
printf("%lld\n",ans);
}
return 0;
}
/*
How to find me(JS-S00163):
Bilibili & Luogu: JQKLUMARKAR
I'd like to write a few words, but I don't know how to type Chinese ans due to my bad English, so maybe I'll use some 'Chinglish' words.
(If you don't make sure what I'm saying, welcome to @JQKLUMARKAR on Luogu, and I'm glad to be shown on posts like'JS mi huo xing wei da shang'.)
(This is not a English writing.XD)
The third year in S, and first year as a senior high school student, I'm feeling very anxious and having a really hard time.
My target this year is to have 1= in both CSP-S & NOIp, but I think it was difficult.
I'm not good at competitions...since I've got 3*CSP-J 2= & 2*CSP-S 2=
And it's likely to be my last year in OI, which may could be called as 'AFO'.
I'll never forget the best time with OI, and the classmates with me.
It's 14:25 and it's time to start.
I'll also write the you_ji under each problem's code.
Even forgot to introduce myself...
Maybe I'll complete it if time is enough.
- 14:28
The password was down, but it's the morning's(wrong password), which means all the students can't read the problem on time...
-----Dividing Line-----
- 14:40
Finish reading.
I have totally no idea...
- 14:45
Maybe it's fan_hui_tan_xin?
Just try it, the time is rich but also rich.
(xiao_dian_jie_xi: rich -> zhen_gui/fu_zu)
- 15:02
Oh my godddddd!
The five given examples all AC!!!
Yes I know I can do it!
You're the best, just believe in your self.
Have a half of SNICKERS first(not an ad).
----- Dividing Line-----
- 18:25
Every thing is ready, gonna be end.
CSP-S 2025 JS-S00163 rp+=inf!!!!!
*/T2
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll n,m,k,ans=LONG_LONG_MAX,c[11],a[11][20005],fa[20005];
ll SPA=1;
bool choices[11];
struct node{
ll u,v,w;
bool operator<(const node t)const{
return w>t.w;
}
};
priority_queue<node> Edges;
ll find(ll u){return u==fa[u]?u:fa[u]=find(fa[u]);}
void merge(ll u,ll v){fa[find(u)]=find(v);}
void dfs(ll dep,ll sum){
if(sum>ans) return;
if(dep==k+1){
ll nodes=n;
priority_queue<node> MST;
MST=Edges;
for(ll i=1;i<=k;i++){
if(!choices[i]) continue;
nodes++;
for(ll j=1;j<=n;j++) MST.push({j,n+i,a[i][j]});
}
for(ll i=1;i<=nodes;i++) fa[i]=i;
for(ll u,v,w,cnt=0;!MST.empty() && cnt<nodes;){
node cur=MST.top();
MST.pop();
u=cur.u;
v=cur.v;
w=cur.w;
if(find(u)==find(v)) continue;
sum+=w;
merge(u,v);
cnt++;
if(sum>=ans) return;
}
ans=min(ans,sum);
return;
}
choices[dep]=1;
dfs(dep+1,sum+c[dep]);
choices[dep]=0;
dfs(dep+1,sum);
}
ll read(){
ll x=0,f=1;
char ch=getchar();
while(ch<'0' || ch>'9'){
if(ch=='-') f=-1;
ch=getchar();
}
while(ch>='0' && ch<='9'){
x=(x<<1)+(x<<3)+(ch^48);
ch=getchar();
}
return x*f;
}
int main(){
freopen("road.in","r",stdin);
freopen("road.out","w",stdout);
n=read(),m=read(),k=read();
for(ll i=1,u,v,w;i<=m;i++){
u=read(),v=read(),w=read();
Edges.push({u,v,w});
}
for(ll i=1;i<=k;i++){
c[i]=read();
for(ll j=1;j<=n;j++) a[i][j]=read();
if(c[i]) SPA=0;
}
if(SPA){
ll nodes=n;
ans=0;
for(ll i=1;i<=k;i++){
nodes++;
for(ll j=1;j<=n;j++) Edges.push({j,n+i,a[i][j]});
}
for(ll i=1;i<=nodes;i++) fa[i]=i;
for(ll u,v,w,cnt=0;!Edges.empty() && cnt<nodes;){
node cur=Edges.top();
Edges.pop();
u=cur.u;
v=cur.v;
w=cur.w;
if(find(u)==find(v)) continue;
ans+=w;
merge(u,v);
cnt++;
}
printf("%lld",ans);
return 0;
}
dfs(1,0);
printf("%lld",ans);
return 0;
}
/*
- 15:09
Finish reading and eating()
It's like MST problem, but with more complex choices.
(btw the volunteer in the room has got a chao_long_shan_de badge(Amiya) on his shirt, surprising though.)
Well I don't know the solution in such a short time, but maybe the features can help get at least 16 points?
- 15:18
Go to see T3&T4 first, later try T2.
- 15:28
OK I'm back, I think it'll spend too much time to write bao_li on T3&T4.
- 15:40
Here's my bao_li:
Since k=10,2^k to mei_ju all the possibilities, and use Kruskal (MlogM) to get the MST.
But for every possibilities, M=m+k*n=1.1e6, O(2^k MlogM) is unacceptable, what a pity.
RP+=inf, hope the data won't be too big...
- 16:04
Oh no, data2 used 1.5s, data3/4 more longer...(70s)
at least the answer is correct.
By using Fast IO, data2 1.3s...
Was it because I use Kruskal? But I don't know how to write Prim...
Just go to T3, time might not be enough.
- 17:55
change vector into priority_queue, data2 -> 1.1s ~ 1.2s
Why so close to the TLE line?
I think I've got all the pts I can, hope everything being great.
- 18:00
100+32+15+12=157...
WAIT I think I can get more points(by T2 for sure)!!!
- 18:04
YES I'VE DONE IT!!!
Well, don't be so exciting first.
Actually it less than 24 more pts.
Let's calculate the sum:100+56+15+12=183
Well, lower than my target......
But I think I may get the 1=.
Hope for the best, prepare for the worst.
*/T3
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll n,q,len,ans,flag=1;
ll sums[200005][3];
unordered_map<string,string> trans;
string s1,s2;
bool check(){
ll a_count=0,b_count=0;
for(auto&&c:s1){
if(c=='a') a_count++;
else if(c=='b') b_count++;
else return false;
if(b_count>1) return false;
}
a_count=0,b_count=0;
for(auto&&c:s2){
if(c=='a') a_count++;
else if(c=='b') b_count++;
else return false;
if(b_count>1) return false;
}
return true;
}
int main(){
freopen("replace.in","r",stdin);
freopen("replace.out","w",stdout);
ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
cin >> n >> q;
for(ll i=1;i<=n;i++){
cin >> s1 >> s2;
trans[s1]=s2;
if(!check()) flag=0;
else{
len=s1.size();
ll l1=0,l2=0;
while(l1<len && s1[l1]!='b') l1++;l1--;
while(l2<len && s2[l2]!='b') l2++;l2--;
sums[i][0]=l1+1;
sums[i][1]=len-l2-1;
sums[i][2]=l2-l1+200000;
}
}
while(q--){
cin >> s1 >> s2;
ans=0;
if(s1.size()!=s2.size()){
cout << "0\n";
continue;
}
if(flag && check()){
len=s1.size();
ll l1=0,l2=0,del;
while(l1<len && s1[l1]!='b') l1++;l1--;
while(l2<len && s2[l2]!='b') l2++;l2--;
del=l2-l1+200000;
for(ll i=1;i<=n;i++) if(l1+1>=sums[i][0] && len-l2-1>=sums[i][1] && del==sums[i][2]) ans++;
cout << ans << '\n';
continue;
}
if(s1.size()>5000 || n>=5000){//No, sir.
cout << "0\n";//Hey what if I can get 45 pts?
continue;//That would be so much fun.
}
len=s1.size();
ll l=0,r=len;
while(s1[l]==s2[l]) l++;
while(s1[r]==s2[r]) r--;
//so this time,[l,r] are different.
for(ll L=0;L<=l;L++)
for(ll R=r;R<len;R++){
string cur1="",cur2="";
for(ll i=L;i<=R;i++) cur1.push_back(s1[i]);
if(!trans.count(cur1)) continue;
for(ll i=L;i<=R;i++) cur2.push_back(s2[i]);
if(trans[cur1]==cur2) ans++;
}
cout << ans << '\n';
}
return 0;
}
/*
- 16:16
Starting bao_li.
Wow the memory limit is 2048Mib ???
- 16:28
Finish the bao_li.
data3/4 is too big...
Bro I thought the program was O(qn^2m) but it's O(q2^n).
- 16:34
Correction.(Restart actually)
Hopefully, after the correction it is O(qn^3) now.(but only 10pts...)
- 16:49
Now think of how feature B works.
Oh the feature B seem to be easy but I only have O(nq), which is 5 more pts.
(neng_xie_yi_dian_shi_yi_dian_le.)
It seems that I'm in deep depression.
No worries, think of you've already finish T1 and some T2, It's OK.
Oh I can't even get 5 pts...
any way, go to T4.
No, I found the mistake
- 17:17
I know that I was wrong, and I thought I've got the 5 pts.
*/T4
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod=998244353;
ll n,m,s[1005],a[1005],x[1005],ans;
int main(){
freopen("employ.in","r",stdin);
freopen("employ.out","w",stdout);
scanf("%lld %lld",&n,&m);
for(ll i=1;i<=n;i++) scanf("%1lld",s+i);
for(ll i=1;i<=n;i++) scanf("%lld",a+i),x[i]=i;
if(n<=10){
do{
ll sum=0,give_up=0;
for(ll i=1;i<=n;i++){
if(!s[i] || give_up>=a[x[i]]) give_up++;
else sum++;
}
if(sum>=m) ans++;
}while(next_permutation(x+1,x+n+1));
printf("%lld",ans);
return 0;
}
if(m==n){
for(ll i=1;i<=s[i];i++)
if(s[i]==0){
printf("0");
return 0;
}
sort(a+1,a+n+1);
if(a[1]==0){
printf("0");
return 0;
}
ans=1;
for(ll i=1;i<=n;i++) ans=(ans*i)%mod;
printf("%lld",ans);
return 0;
}
printf("0");//No, sir.
return 0;
}
/*
- 17:25
Finish reading.
OMG I think I don't have enough time, I would only try to get the highest pts if I can.
- 17:34
8pts got.
- 17:37
4pts got.
- 17:40
No any ideas.
I have to look back to T2, even T4 seems to be approachable to get more pts.
*/（这些都还没写，可能以后会补吧。）\ 补了，如果有什么英语语法错误是我糊涂了，因为考场虚拟机不会打汉字。
后记
结束了，一切都结束了。\
还总结啥呀 whk 停了一周进度都起飞了赶紧回去补吧。