2025GDCPC广东省赛游记（附赛时代码）

我觉得算是给swan的自证之旅画上一个句号吧...说实话HDU给我带来的不止是排位上的压力，更多的是对自己能力的怀疑，特别是pluto不明说但是我很清楚的看不起（没有责备本人的意思），evil和jxj之类的总感觉看到我就是看小丑的眼神（我觉得主要是自己自卑所以觉得所有人都讨厌自己），连约饭都没人陪我了呜呜

我感觉全世界都开始怀疑我vp的时候全部都在抄题解，然后cf的分数也是作弊得来的，我不配打acm之类的，这种主要是自己给自己的压力犹如顿刀子割肉般没日没夜的折磨我，被队友抛弃被自己否定

转机就算是南昌吧，你也可以看到南昌结束之后swan疯狂的强调自己的贡献啥的（也跟猫猫道个歉），其实也是希望能像其他人证明自己，说这个铜牌我没有拖后腿云云，总之感觉自己这一个学期都被沟槽的HDU毁了，陷入了一种很恐怖的给自己上压力的恶性循环。直到省赛，所有人同台竞技，然后能打到校内第三的这个位置，我才算是长出一口气，才好意思舔着个脸再去问猫猫或者鸡哥愿不愿意捞我这种事情

emo的回顾到此结束，还是回顾下比赛历程吧，这场我们队真的算是大起大落大起大落，好在最后极限翻盘。比赛前一个比较错误的战略就是让sherlock去写签到去了，然后WA了一发换我重新敲才过了，这个时候我队已经陷入了不小的罚时劣势，此乃一落。然后cmjj的模拟一发过，除了大哥队率先进入两题区，此乃一起。现在签到结束了，两道铜牌题卡住了，被其他几个队快速追上，虽然中间sherlock先过了个H但是在比起铜牌题全出还是差一题，再次掉到银牌岌岌可危的位置。H过的时候一小时出头，然后直到3小时15分钟才终于出了G，但是这个时候的罚时劣势已经巨大，封榜前已经是73名，而银牌线是79名，如果出不了题那银牌都拿不到。在此之前swan的J题还wa了好几发，然后开始研究I，很长时间没有机时的sherlock居然一直在看我的代码（太感动了呜呜），然后找到了错误原因，在封榜之后开敲。而sherlock敲的同时我这边I也找到了正确的容斥方式，两个人就开始抢电脑，最后两个人连续三分钟内连开两题成功跻身六题区（还藏了一手演pluto）

最后说一下参赛环境吧，我们是在广州外语外贸大学的赛点参赛的，虽然主办方的教练们都在群里哭穷，我们对省赛的期望也不是特别高。但是真的是相当出乎意料地优秀的参赛体验，比起去年几十万经费的港科广真的好了不是一点半点，PTA的经典连接不上服务器我觉得可以接受吧，然后麦麦是热的就已经赢了南昌太多，更别说去年某校的减脂三明治了。本来大家以为没有牌子没有滚榜啥的，最后居然是在我们这个赛点线下滚了榜，牌子也说之后会寄到学校，赛时的气球也安排到位了，总之我觉得这算是我人生中第二棒的一次参赛体验了（中大校赛免费参赛还送衣服送杯子送麦麦这个真的是很难超越了），感谢所有为比赛付出的老师，志愿者和后勤工作人员们

然后把代码贴一下吧，签到我没存懒得存

I题

#include <bits/stdc++.h>
#define all(a) a.begin(),a.end()
using namespace std;
typedef long long ll;
typedef double db;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
/*ll mod=1e9+7;
ll N=1e5+10;
ll fact[N],infact[N];
void ini(){fact[0]=infact[0]=1;for(int i=1;i<N;i++){fact[i]=fact[i-1]*i%mod;infact[i]=qpow(fact[i],mod-2);}
}
ll C(lla,ll b){if(a<b) return 0;return fact[a]*infact[b]%mod*infact[a-b]%mod;
}*/void solve(){ll n; scanf("%lld",&n);vector<vector<ll> > cnt(4,vector<ll>(1e6+10,0));map<tuple<ll,ll,ll>,ll> mp;vector<tuple<ll,ll,ll> > qq;for(int i=0;i<n;i++){ll a,b,c; scanf("%lld%lld%lld",&a,&b,&c);cnt[1][a]++; cnt[2][b]++; cnt[3][c]++;mp[{a,0,c}]++; mp[{a,b,0}]++; mp[{0,b,c}]++;qq.push_back({a,b,c});}ll ans=0;for(auto [a,b,c]:qq){// 我在这里考虑的是最后的东西和a,b,c完全一致 ll x=cnt[1][a]-mp[{a,0,c}]-mp[{a,b,0}]+1;ll y=cnt[2][b]-mp[{a,b,0}]-mp[{0,b,c}]+1;ll z=cnt[3][c]-mp[{a,0,c}]-mp[{0,b,c}]+1;ll d=mp[{0,b,c}]-1,f=mp[{a,0,c}]-1,e=mp[{a,b,0}]-1;//printf("%lld %lld %lld %lld %lld %lld ",x,y,z,d,e,f);//printf("add %lld ",x*y+y*z+x*z);//printf("add %lld ",(d+e+f)*(d+e+f-1)/2);//printf("add %lld\n",(a+b+c)*(d+e+f));//printf("add %lld\n",x*y+y*z+x*z+(d+e+f)*(d+e+f-1)/2+(a+b+c)*(d+e+f));ans+=x*y+y*z+x*z+(d+e+f)*(d+e+f-1)/2+(x+y+z)*(d+e+f);}printf("%lld\n",ans);
}int main(){int T=1;//scanf("%d",&T);while(T--){solve();}return 0;
}

J题

#include<bits/stdc++.h>using namespace std;
#define int long long 
const int N=1e6+10;
const int MOD = 998244353;int qpow(int num,int k)
{int res = 1;while(k){if(k % 2) res = res * num;num = num * num;k = k >> 1ll;}return res;
}int a[N];
int e[N],ne[N],h[N],w[N];
int idx;
int ans[N];struct Node
{int time;int tar;int val;bool operator < (const Node &other) const {return time > other.time;	}
};void add(int x,int y,int z)
{e[++idx] = y, ne[idx] = h[x] , h[x] = idx,w[idx] = z;
}void solve()
{int n,m,k;cin>>n>>m>>k;for(int i=1;i<=n;i++) cin>>a[i],ans[i] = MOD * MOD;//cout<<n<<"\n";priority_queue< Node , vector<Node> >q;for(int i=1;i<=k;i++){int t,num;cin>>t>>num;for(int j=1;j<=num;j++) {int x;cin>>x;q.push({t,x,0});}}for(int i=1;i<=m;i++){int x,y,z;cin>>x>>y>>z;add(x,y,z);}for(int i=1;i<=n;i++){if(a[i] == 0){//cout<<i<<"\n";ans[i]=0;for(int j=h[i];j;j=ne[j]){q.push({w[j],e[j],1});}}}while(!q.empty()){auto [time,index,val] = q.top();//cout<<time<<" "<<index<<" "<<val<<"\n";q.pop();if(a[index] == 0) continue;if(val == 1) a[index] --;if(val == 0) a[index] = 0;if(a[index] == 0){ans[index] = time;for(int i=h[index];i;i=ne[i]){int son = e[i];if(a[son]!=0){q.push({time+w[i],son,1});}}}}//cout<<n<<"\n";for(int i=1;i<=n;i++){if(ans[i] == MOD * MOD) cout<<-1<<" ";else cout<<ans[i]<<" ";}
}signed main()
{int t=1;//cin>>t;while(t--){solve();}
}

F题

#include <bits/stdc++.h>
#define all(a) a.begin(),a.end()
using namespace std;
typedef long long ll;
typedef double db;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
void solve(){ll n,m,t;cin>>n>>m>>t;ll k;cin>>k;ll tn=0,ttime=0;map<char,ll> mp,cnt;priority_queue<ll,vector<ll>,greater<ll> > qu;for(ll i=1;i<=k;i++){ll tt;char c;string str;cin>>tt>>c>>str;if(cnt[c]) continue;if(str=="ac"){ttime+=(tt+mp[c]*20);tn++;cnt[c]=1;}if(str=="rj"){mp[c]++;}if(str=="pd"){cnt[c]=1;qu.push(tt+mp[c]*20);//cout<<"qu push "<<tt+mp[c]*20<<" "<<c<<"\n";}}if(tn>m||tn==m&&ttime<t){cout<<"0"<<"\n";return ;}//cout<<tn<<" "<<ttime<<"\n\n";ll g=0;while(!qu.empty()){g++;tn++;ll tp=qu.top();//cout<<"top:"<<tp; ttime+=tp;qu.pop();//cout<<" "<<tn<<" "<<ttime<<"\n";if(tn>m||tn==m&&ttime<t){cout<<g<<"\n";return ;}}cout<<"-1"<<"\n";return ;
}int main(){ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);int T=1;cin>>T;while(T--){solve();}return 0;
}

H题

#include<bits/stdc++.h>using namespace std;
#define int long long 
const int N=1e6+10;
const int MOD = 998244353;int qpow(int num,int k)
{int res = 1;while(k){if(k % 2) res = res * num;num = num * num;k = k >> 1ll;}return res;
}int sum[30];
int a[N];
int dp[30];void solve()
{int n,k;cin>>n>>k;string s;cin>>s;for(int i=0;i<n;i++){int now = s[i] - 'a';int num = 1;for(int j=0;j<26;j++){num = (num + sum[j]) % MOD;}num = (num - dp[now] + MOD) % MOD;dp[now] = (dp[now] + num) % MOD;//cout<<i<<" "<<num<<"\n";a[i] = num;if(i >= k) sum[s[i-k]-'a'] = (sum[s[i-k]-'a'] + a[i-k]) % MOD;}int res =0;for(int i=0;i<26;i++) res = (res + dp[i]) % MOD,sum[i]=0,dp[i]=0;cout<<res<<"\n";
}signed main()
{int t=1;cin>>t;while(t--){solve();}
}

D题

#include<bits/stdc++.h>using namespace std;
#define int long long 
const int N=1e6+10;
const int MOD = 998244353;int qpow(int num,int k)
{int res = 1;while(k){if(k % 2) res = res * num;num = num * num;k = k >> 1ll;}return res;
}int dp[N];
int a[N];
int ask[N];void solve()
{int n,m;cin>>n>>m;map<int,int>mp;for(int i=1;i<=n;i++) cin>>a[i],dp[a[i]]=1;int now = 0;int maxvalue=0;for(int i=1;i<=a[n];i++)	{if(now +1 <= n && i == a[now+1]) now++;dp[i] = dp[i - a[now]] + dp[a[now]];mp[dp[i]]++;maxvalue = max(maxvalue,dp[i]);//cout<<i<<" "<<dp[i]<<"\n";}//for(int i=1;i<=maxvalue;i++) cout<<mp[i]<<"\n";for(int i=2;i<=maxvalue;i++) mp[i] += mp[i-1];for(int i=1;i<=m;i++) cin>>ask[i];for(int i=1;i<=m;i++){if(ask[i]<=maxvalue) cout<<mp[ask[i]]<<" ";else cout<<mp[maxvalue]<<" ";}
}signed main()
{int t=1;//cin>>t;while(t--){solve();}
}