中国大学生程序设计竞赛（China Collegiate Programming Contest，简称CCPC)是由中国大学生程序设计竞赛组委会组织举办的年度性赛事，旨在激发高校学生学习计算机领域专业知识与技能的兴趣，鼓励学生灵活运用计算机知识和技能解决实际问题，有效提升算法设计、逻辑推理、数学建模、编程实现和计算机系统能力，培养团队合作意识、挑战精神和创新能力，培育和选拔出一大批素质优良、结构合理的高素质信息技术人才队伍，服务“两个强国”建设。（随便复制来的）。

这次比赛我们去的是济南站，本次CCPC比赛由山东大学承办，鹿老师负责了全城的规划。赛题由 SUA 完成，总体来说体验非常好，还顺便蹭了高中山大酒吧舞同学的一顿饭，更重要的是本次比赛学校全程报销?。

比赛队伍由我们的离散数学老师张老师带队（张老师给了充足的时间让我们出去玩太棒了），也幸亏是张老师带队，我才有时间和高中同学见面。

DAY -7 赛前准备

赛前济南站群里鹿老师便在紧锣密鼓的筹划本次比赛，本次比赛是应该是山大第一次承办CCPC比赛，但各位山大老师，协助工作的同学和志愿者们都诚意满满，体验十分满意

赛前唯一可以吐槽的点大概就是天梯赛上让我们PTSD的疯狂掉线的OMS了，但是在我们比赛的过程中，掉线情况基本没有发生。

现场比赛电脑使用的是笔记本+外接屏幕的方案，实际上卡卡的，编译起来比较慢，而且没有cph插件（用命令行难受啊！）

DAY -1 热身赛

参赛

正式比赛前一天，学校派了一辆大巴送我们前往济南，路上济南站开启了定位，发现很多群友已经到了国际会展中心附近。

在路上百无聊赖，坐在第一排随即开了几把非常火的杂交版植物大战僵尸，这个版本玩起来确实很有观赏性，但是就是难度实在是太大了，一波巨人过来这谁顶得住啊！玩了一会红温了，电池也红温了，然后开始无聊的刷手机。做了大概两个小时的车，终于到了目的地。

领了伴手礼，伴手礼还是比较好的，盒子中有一大堆赞助商的广告，一件参赛服，一个好看的书签，一个山大软件园的文创鼠标垫。

然后就是惯例的热身赛，依旧是我主要负责了配置系统环境，一开始我没看说明直接调，调错了东西，后来自己调过来了，还疑惑为什么别人都会配置VSC，之后问了LLYS大神才知道一开始我的操作就有错误，幸亏我也会调，热身赛也是四道题，我们队三个人每个人都写了一道练练手，很遗憾的是我写的题目以为是二分答案的题目，但是经过半个多小时的证明发现我的做法不对（成战犯了唉唉）。

赛场上的键盘太轻了，而且桌子有点晃，算是勉强能用的程度，旁边队伍名是逸误，哈哈哈哈看到的时候就笑出声来了。

旅游！

早已和山大年年副研究员打好招呼说我要让他爆金币，年年表示十分赞同（bushi），赛前实际上并不知道能不能有时间到处玩，热身赛之后我们就去了宾馆，之后的时间就属于我们自己了，和张老师报备之后马上就打车去了山大附近让年年给我爆金币。

年年带我去了山大附近的烧烤店吃烧烤

吃饱喝足年年提出去泉城广场逛一逛，反正我也没有什么事，就答应了，坐上了年年的小车去了济南地标性建筑泉城广场，非常巧的是我们刚到的时候正好是晚上八点半，音乐在我们刚刚抵达的 时候响起，泉水在此时喷出。看完泉水，我们又去拍了地标性建筑，

吃饱喝足玩尽兴，年年便骑着他的小电动车送我到了最近的公交站，坐公交的时候一位大爷主动让出身旁的座位让我坐下，过了一会他下车前又提前站起来让旁边的女生坐了下来，他真的我哭死，这就是我们好客山东。

唯一不太好的是年年似乎看错了地址，我也没检查，给我导航到错了，进去一个不认识的地方给赶出来了，幸亏本路痴有先见之明，在离开宾馆前早就发了位置，重新检查位置，发现偏了三公里，之后自己又多走了三公里路。

芙莉莲！

在回宿舍的途中，御剑同学突然问我要不要书，然后给我发了图。

受宠若惊问了御剑同学是不是真要给我买之后便选择了最新的七八卷，太感动了。

DAY 0 正式赛

题解

A. Printer

采用二分答案的策略来进行问题求解，但是注意极限数据。
这里提供一组极限数据

1
1000000000 1
1000000000 1 1000000000

题解代码：

#include<bits/stdc++.h>
using namespace std;
#define int long long
int n,m,x;
struct node{
    int t,l,w;
};
vector<node> q;
bool check(int ti){
    int ans=0;
    for(auto i:q){
        int al=i.t*i.l+i.w;
        ans+=i.l*(ti/al)+min(i.l,(ti%al)/i.t);
        if(ans>=x)return 1;
    }
    return 0;
}
void solve(){
    cin>>n>>x;
    q.clear();
    for(int i=1;i<=n;i++){
        int a,b,c;cin>>a>>b>>c;
        q.push_back({a,b,c});
    }
    int l=0,r=2e18+10;
    while(l<r){
        int mid=l+r>>1;
        if(check(mid))r=mid;
        else l=mid+1;
    }
    cout<<l<<'\n';
}
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    int t;
    cin>>t;
    while(t--)solve();
    return 0;
}

C. Colorful Segments 2

这题算是我这一场贡献最大的一道题目了.
主要思路就是将线段按左端点排序，若都不重叠那么就是 $n^{k}$ 种方案。
然后我们考虑有重合的方案，假设只有两条线段，而且这两条线段是互相重叠的，那就是 $n\times \left( n-1\right)$ 种方案。
对于每个线段，他能选择的颜色方案应该是 $n-x$ 种方案，所以开一个pq记录前面有几个线段的右端点比当前线段的左端点大就可以。

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define mod 998244353
vector<pair<int,int>> q;
void solve(){
    int n,k;
    q.clear();
    cin>>n>>k;
    for(int i=1;i<=n;i++){
        int a,b;cin>>a>>b;
        q.push_back({a,b});
    }
    sort(q.begin(),q.end());
    priority_queue<int,vector<int> ,greater<int>> pq;
    int ans=1;
    for(auto i:q){
        int l=i.first,r=i.second;
        while(pq.size()&&pq.top()<l)pq.pop();
        ans=ans%mod*(k-pq.size());
        pq.push(r);
    }
    cout<<ans%mod<<'\n';
}
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    int t;
    cin>>t;
    while(t--)solve();
    return 0;
}

F. Divide the Sequence

本体表面看起来是分割序列，我们实际可以换一种思路来考虑，分成一段就是数组的和，分成两段肯定是总体数组的和 and 后面某一段数组的和，分成三段就是 总体数组的和 and 后面某一段数组的和 and 再后面某一段数组的和。

那我们考虑两段的时候，就是最大化后面那一段的和，而这个最大的和可以用后缀和求出来，找出最大的一个后缀和求出来就可以了。

三段的时候就相当于找两个最大的后缀和，以此类推，我们每次加一个最大的后缀和然后pop出去就可以了

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define N 1000010
int q[N];
void solve(){
    int n;cin>>n;
    int sum=0;
    for(int i=1;i<=n;i++)cin>>q[i],sum+=q[i];
    priority_queue<int> pq;
    int tmp=0;
    for(int i=n;i>1;i--){
        tmp+=q[i];
        pq.push(tmp);
    }
    cout<<sum<<' ';
    for(int i=1;i<n;i++){
        sum+=pq.top();
        pq.pop();
        cout<<sum<<' ';
    }
    cout<<'\n';
}
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    int t=1;
    cin>>t;
    while(t--)solve();
}

I. Left Shifting

签到题

#include<bits/stdc++.h>
using namespace std;
#define int long long

void solve(){
    string s;
    cin>>s;
    int no;
    for(int i=0;i<s.size();i++){
        if(i==0)no=s.size()-1;
        else no=i-1;
        // cerr<<i<<' '<<no<<'\n';
        if(s[i]==s[no]){
            cout<<i<<'\n';
            return;
        }
    }
    cout<<-1<<'\n';
}
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    int t;
    cin>>t;
    while(t--)solve();
    return 0;
}

J. Colorful Spanning Tree

用Kruskal 算法进行解决，开小根堆每次找最小的的边尝试连接。这样能保证最后一定在一个集合里面。

1. u = v
   若颜色 u 所有点已在同一连通块内则跳过。
   否则连 $(q_{u} −1)$ 条边，标记这个颜色所有点在同一连通块内。
2. u ̸= v
   若颜色 u 和 v 在同一连通块内则跳过。
   否则若 u 和 v 所有点都不在同一连通块内，连 $(q_{u} + q_{u} − 1)$ 条边。
   否则若 u 所有点都不在同一连通块内，连 $q_{u}$ 条边。v同理。
   否则连 1 条边即可。
   连边结束后，u 和 v 的所有点必定在同一连通块内。

//请注意auto [x,y]用法是新版本特性，部分编译器可能会提示CE，请自行选择编译器版本
#include<bits/stdc++.h>
using namespace std;
#define int long long
typedef pair<int,int> pii;
typedef pair<int,pair<int,int>> piii;
void solve(){
    int n;cin>>n;
    vector<int> fa(n+1);
    for(int i=1;i<=n;i++)fa[i]=i;
    vector<int> q(n+1);
    priority_queue<piii,vector<piii>,greater<piii>> a;
    for(int i=1;i<=n;i++){
        cin>>q[i];
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            int x;cin>>x;
            a.push({x,{i,j}});
        }
    }
    auto find=[&](auto self,int x)->int{
        if(x==fa[x])return x;
        return fa[x]=self(self,fa[x]);
    };
    int ans=0;
    vector<int> st(n+1,0);
    while(a.size()){
        auto [x, tmp] = a.top();
        auto [i, j] = tmp;
        a.pop();
        if(i==j){
            if(st[i])continue;
            else ans+=(q[i]-1)*x,st[i]=1;
        }
        else{
            if(find(find,i)==find(find,j))continue;
            if(!st[i]&&!st[j]){
                fa[find(find,i)]=find(find,j);
                ans+=(q[i]+q[j]-1)*x;
                st[i]=1;
                st[j]=1;
            }
            else if(st[i]&&!st[j]){
                ans+=(q[j])*x;
                fa[find(find,j)]=find(find,i);
                st[j]=1;
            }
            else if(!st[i]&&st[j]){
                ans+=(q[i])*x;
                st[i]=1;
                fa[find(find,i)]=find(find,j);
            }
            else{
                ans+=x;
                fa[find(find,i)]=find(find,j);
            }
        }
    }
    cout<<ans<<'\n';
}
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    int t=1;
    cin>>t;
    while(t--)solve();
}

K. Matrix

构造题，我的思路是先填上最后四个2n,2n-1,2n-2,2n-3，除了这两行其余行每行都填上1,2,3,4……n-2，然后剩余的部分每列都填上n-1,n,n+1……2*n等。

#include<bits/stdc++.h>
using namespace std;
#define int long long
int q[100][100];
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    int n;
    cin>>n;
    int cnt=0;
    for(int i=1;i<=n-2;i++){
        int x=++cnt;
        for(int j=1;j<=n;j++)q[i][j]=x;
    }
    for(int i=1;i<=n-2;i++){
        q[n-1][i]=q[n][i]=++cnt;
    }
    q[n-1][n-1]=++cnt;
    q[n-1][n]=++cnt;
    q[n][n-1]=++cnt;
    q[n][n]=++cnt;
    cout<<"Yes\n";
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            cout<<q[i][j];
            if(j!=n)cout<<' ';
        }
        cout<<'\n';
    }
}

赛时赛后

赛时的塔斯汀太好吃了，这个鸡腿真的太好吃了，好评！

最后以六题的成绩拿下省赛银牌以及邀请赛铜牌，成绩还算可以，正常发挥，队长真的太强了┗|｀O′|┛ 嗷~~。

DAY ∞

吃吃吃

回来和队友吃了一顿火锅，算是对自己打两场比赛的庆功宴（啊呀，油滴到衣服上了！我的衣服！）

不断进步！

今年的团体赛算是打完了，收获了两块银牌两块铜牌，但我知道自己的实力确实不够，补的题目也不够多，因为是团体赛的缘故，有时把别人的成绩加在自己身上，但实际上自己做是做不出来的，加训，加训！