CSP复赛游记——杭师大一日游

xu_zhihao · 2025-11-01 22:28:53 · 生活·游记

绝密☆启用前

Day -inf

前一天也是一躺下来就睡着了，睁开眼就早上了。

CSP-J

省流，估分 89-92 分。

时间线来到考场，今年太仔细了，考场居然有封条。加分！有的说的是去年我在的考点似乎可能是因为考试时不让学生上厕所被举报了导致今年没能申请到考点（tang。

这次的开考铃声居然响了整整 10 s！然后开了 T1 发现 unsigned int（去年 int 今年 unsigned int 明年不会就是 unsigned long long 了吧）。 T4 忘记是咋写的了，痛失 2 pts。

前面 15 题我觉得中规中矩吧，反正比去年好多了，难度中偏上。写完时已是 10:10 了。

完善程序 1 比去年稍难，有点小坑，判断最后一个越界应该不算。完善程序 2 就是眼瞎了把限定 k 的正负性的题目的编号搞反了，痛失 4.5 pts（T24,T25）。评价一下，这次的完善程序 2 严格大于去年的。

但是看到完善程序 3 的时候感觉 CCF 又给我拉了坨大的，可以说是毫无新意，完全明显就是最长上升子序列模板，甚至简化成了数字版本。这就不太好评价了，但是还是比去年的同题难多了。此时时间是 10:55。

完善程序就很有区分度了。完善程序 1 几乎就是送分了，没有啥思维含量了，但是因为看错题目卡了整整 10 分钟！完善程序 2 就很有难度了，很难想象 J 组居然考函数式交互题。感性理解了 15 分钟左右才证明了贪心的正确性，摩尔投票还是太困难了！随口一提，完善程序 2 的算法解释是真的垃圾，导致 40 题选错了！此时时间已经到了 11:20。

最后 10 分钟极限查出 2 个错，挽回 2+3 pts。太刺激了，改完最后一个的时候监考老师都要开始收卷了。

最后预估得分 100-2-1.5-1.5-3-3=89 或 100-2-1.5-3-3=90.5 或 100-2-3-3=92 分。

upd：不同的地方估分有小差异。

这分数能不过我直接原地 AFO 了。

顺便锐评 CCF 双 T33 行为。出题人打印卷子之前都不会先再看一遍卷子吗？

CSP-S

You have no egg!

GESP 超常发挥了。 8 级 90 分免了。

上午 J 考完之后就回学校摆了一节培优班，然后口胡了一下 S，发现有部分人说 S<J 是咋回事。

算了就补一下 GESP 的游记吧。前面的题都很简单。写了大概 1h。编程题第一题很模板的双 ST 表维护一下就过了。第 2 题刚开是写搜索炸了，不会写换根 dp，想了一会发现可以记忆化，遂花了 5 分钟写记忆化，~~然后就是调了 20 分钟~~，输惨了。但是最后交上去的时候跑的飞快，愉快 AC。值得一提的是 CCF 没卡我菊花图，拜谢 CCF！

估分 89。

after inf days...

查分是发现居然 90。

Day 0

下午 3 点请假回家，吃了点东西，就狂飙到了动车站了。

在动车上把所有学的东西都复习了一遍，复习完时就差不多下车了。

坐地铁去到了杭师大门口蹲点考场后就回酒店了。（酒店夜宵好评）晚上发现自己一点都不紧张，但是晚上似睡非睡的，似乎梦到了好多东西...

Day 1

上午场

密码是上善若水绷不住了（CCF文学水平还是太权威了）。

开考时先看了 4 道题目的题面，发现都挺简单的样子？

T1,T2 纯贪心模拟，写了 15 分钟。

T3 有点微妙，想了 15 分钟，发现最右边区间的右端点越左的话对于答案的贡献肯定是不减的，所以就是贪心。用 unordered_map 叠了个 O(n) 的写法。如下：

#include<bits/stdc++.h>
using namespace std;
unordered_map<int,int>mp;
const int N=5e5+10;
int a[N];
int sum[N];
int main(){
  int n,k;
  cin>>n>>k;
  for(int i=1;i<=n;i++){
      cin>>a[i];
  } 
  int id=1;
  int last=0;
  int ans=0;
  while(id<=n){
      mp.clear();
      mp[0]=1;
      sum[0]=0;
      while(id<=n){
          sum[id-last]=sum[id-last-1]^a[id];
          if(mp[sum[id-last]^k]){
              ans++;
              last=id;
              id++;
              break;
          }
          mp[sum[id-last]]=1;
          id++;
      }
  }
  cout<<ans<<"\n";
  return 0;
}

此时为 9:05。T4 有点难想，看到 n \le 500 求方案数显然是 dp 的。比较套路的写法，对于最大值下功夫。容易联想到排序，那么 a_{i-1} \le a_i，可以简单预处理出前 i 个数凑出大于等于 j 的数的方案数。下附代码：

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=5e3+10;
int a[N];
int dp[N][N*2];
int mod=998244353;
signed main(){
  int n;
  cin>>n;
  for(int i=1;i<=n;i++){
      cin>>a[i];
  }
  sort(a+1,a+n+1);
  int ans=0; 
  for(int i=1;i<=n;i++){
      if(i>=3){
          for(int j=a[i]+1;j<2*N;j++){
              ans+=dp[i-1][j];
              ans%=mod;
          }
      }
      dp[i][a[i]]=1;
      for(int j=1;j<2*N;j++){
          dp[i][j]+=dp[i-1][j];
          dp[i][j]%=mod;
          dp[i][min(j+a[i],2*N-1)]+=dp[i-1][j];
          dp[i][min(j+a[i],2*N-1)]%=mod;
      }
  }
  cout<<ans<<"\n";
  return 0;
}

但是 dp 转移的时候最大值设大了，导致多了常数，能不能过靠天意了。

写完后时间来到了 9:50，检查完之后遂开始闭目养神，最后 30 分钟实在无聊玩了会扫雷。

UPD：只能说 CSP-J 的总码量不如 CSP-S T1 了。

中场休息

从考场骑自行车去吃了沙县，味道不错，但是奈何口腔溃疡太疼了。回酒店睡了一会（没睡着），起来后继续补西洋参，然后就出发去考场了。

下午场

还是监考老师标准拼音发音，真的听不懂，写密码被硬控了 3 分钟。开 T1。此时 14:32。此时键盘敲击声震耳欲聋（还好带了耳塞），感觉今年的 T1 难炸了，想了半个小时 dp 无果，遂考虑贪心，还好在比赛前大量复习过贪心和 Ad-hoc，本来考虑贪心+dp但是假了，后来一眼反贪（前半个小时在干嘛啊），简单证明了正确性就开始写了。刚开始没用结构体写成一坨了，休息了一下，重构代码。就过大样例了。此时时间是 15:40。附回忆代码：

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
struct node{
  int p[4];
};
node a[N];
vector<int>v[4];
int n;
int p;
bool cmp(int A,int B){
  int mxA=0,mxB=0;
  for(int i=1;i<=3;i++)if(i!=p)mxA=max(mxA,a[A].p[i]);
  for(int i=1;i<=3;i++)if(i!=p)mxB=max(mxB,a[B].p[i]);
  return a[A].p[p]-mxA<a[B].p[p]-mxB;
}
int solve(int id){
  int ans=0;
  for(int to:v[id])ans+=a[to].p[id];
  p=id;
  sort(v[id].begin(),v[id].end(),cmp);
  for(int i=0;i<v[id].size()-n/2;i++){
      int mx=0;
      for(int j=1;j<=3;j++)if(j!=id){
          if(a[v[id][i]].p[j]>mx){
              mx=a[v[id][i]].p[j];
          }
      }
      ans-=a[v[id][i]].p[id]-mx;
  }
  return ans;
}
int main(){
  int t;
  cin>>t;
  while(t--){
      cin>>n;
      for(int i=1;i<=3;i++)v[i].clear();
      for(int i=1;i<=n;i++){
          cin>>a[i].p[1]>>a[i].p[2]>>a[i].p[3];
      }
      for(int i=1;i<=n;i++){
          int mx=0;
          int id=0;
          for(int j=1;j<=3;j++){
              if(a[i].p[j]>mx){
                  mx=a[i].p[j];
                  id=j;
              }
          }
          v[id].push_back(i);
      }
      int ans=0;
      for(int i=1;i<=3;i++){
          if(v[i].size()>n/2){
              ans+=solve(i);
          }
          else{
              for(int to:v[i]){
                  ans+=a[to].p[i];
              }
          }
      }
      cout<<ans<<"\n";
  }
  return 0;
}

此时还一切正常...

开 T2 发现好复杂，本来感觉是最短路，但是不好处理，遂想到了最小生成树，容易证明原图的最小费用一定是在最小生成树上的。但是这时还没有发现有啥用，注意到了 k\le 10，这个性质和 ABC 有一场的题目好像，容易猜测复杂度和 2^k 有关。然后就是一直在思考什么情况下将乡镇城市化会对答案有贡献，发现好难想，人都要炸了。正难则反，递归哪些乡镇城市化，然后计算起贡献。这一版本的具体做法就是递归每一种乡镇是否城市化，最后将相关的边全部塞进边集中，然后跑一次最小生成树，求是否对答案有贡献。复杂度 O(2^k(m+nk) \log (m+nk))，这版代码实在太劣了，所以没有具体实现。此时时间为 16:54，这时心里已经有点开慌了，心里默念相信相信的力量（社会老师名言）。后来又想了个 O(2^k(m+n^2) \log (m+n^2)) 的做法，但是更劣了。此时时间为17:20。比赛结束时间记成了 18:00，紧张到我了，突然发现了第二个性质：只有原图中最小生成树上的边才可能对答案有贡献。这个性质非常有用，差点激动的把键盘摔在地上了。所以就得到了在考场上的最终做法：

在原图上一棵最小生成树上的边的信息存到一个新图上（带权边集记为 e）。
递归求出每一种城市化方案。
对于每一种方案，将相应的边与 e 组成的图求最小生成树。
对于每一种方案，计算并检验其是否对答案的贡献。

复杂度到了 O(m \log m+2^knk \log (nk))。实现花了 30 分钟，大样例一遍过了。期望得分 65 pts。时间到了 17:55。附回忆代码：

#include<bits/stdc++.h>
using namespace std;
const int N=1e4+10,M=1e6+10;
struct node{
  int u;
  int v;
  long long w;
};
node b[M];
long long c[30];
long long a[30][N];
int f[N];
vector<node>v;
bool cmp(node A,node B){
  return A.w<B.w; 
}
int find(int id){
  return f[id]==id?id:f[id]=find(f[id]);
}
int n,m,k;
int t[30];
vector<node>e;
long long ans=1e18;
void check(){
  long long cnt=0;
  e.clear();
  for(node to:v)e.push_back(to);
  for(int i=1;i<=k;i++)if(t[i]){
      cnt+=c[i];
      for(int j=1;j<=n;j++){
          e.push_back({n+i,j,a[i][j]});
      }
  }
  sort(e.begin(),e.end(),cmp);
  for(int i=1;i<=n+k;i++)f[i]=i;
  for(node to:e){
      int fa=find(to.u);
      int fb=find(to.v);
      if(fa!=fb){
          f[fa]=fb;
          cnt+=to.w;
      }
  }
  //cout<<"\n";
  ans=min(ans,cnt);
}
void dfs(int len){
  if(len==k+1){
      check();
      return;
  }
  t[len]=0;
  dfs(len+1);
  t[len]=1;
  dfs(len+1);
}
int main(){
  cin>>n>>m>>k;
  for(int i=1;i<=m;i++){
      cin>>b[i].u>>b[i].v>>b[i].w;
  }
  sort(b+1,b+m+1,cmp); 
  for(int i=1;i<=k;i++){
      cin>>c[i];
      for(int j=1;j<=n;j++){
          cin>>a[i][j];
      }
  }
  for(int i=1;i<=n;i++)f[i]=i;
  for(int i=1;i<=m;i++){
      int fa=find(b[i].u);
      int fb=find(b[i].v);
      if(fa!=fb){
          f[fa]=fb;
          v.push_back({b[i].u,b[i].v,b[i].w});
      }
  }
  dfs(1);
  cout<<ans<<"\n";
  return 0;
}

UPD：赛后发现利用类似离线思想，将排序预处理，即可满分。复杂度 O((m+nk) \log (m+nk)+2^knk)。这题属实应该评蓝，感觉是历史最难 T2 了。

赛后胡的正解：

  #include<bits/stdc++.h>
using namespace std;
const int N=1e4+10,M=1e6+10;
struct node{
    int u;
    int v;
    long long w;
};
node b[M];
long long c[30];
long long a[30][N];
int f[N];
vector<node>v;
bool cmp(node A,node B){
    return A.w<B.w; 
}
int find(int id){
    return f[id]==id?id:f[id]=find(f[id]);
}
int n,m,k;
int t[30];
vector<node>e;
long long ans=1e18;
void check(){
    long long cnt=0;
    for(int i=1;i<=k;i++)if(t[i]){
        cnt+=c[i];
    }
    for(int i=1;i<=n+k;i++)f[i]=i;
    for(node to:e)if((to.u<=n || t[to.u-n]) && ((to.v<=n || t[to.v-n]))){
        int fa=find(to.u);
        int fb=find(to.v);
        if(fa!=fb){
            f[fa]=fb;
            //cout<<to.u<<" "<<to.v<<"\n";
            cnt+=to.w;
        }
    }
    //cout<<"\n";
    ans=min(ans,cnt);
    return;
}
void dfs(int len){
    if(len==k+1){
        check();
        return;
    }
    t[len]=0;
    dfs(len+1);
    t[len]=1;
    dfs(len+1);
}
int main(){
    cin>>n>>m>>k;
    for(int i=1;i<=m;i++){
        cin>>b[i].u>>b[i].v>>b[i].w;
    }
    sort(b+1,b+m+1,cmp); 
    for(int i=1;i<=k;i++){
        cin>>c[i];
        for(int j=1;j<=n;j++){
            cin>>a[i][j];
        }
    }
    for(int i=1;i<=n;i++)f[i]=i;
    for(int i=1;i<=m;i++){
        int fa=find(b[i].u);
        int fb=find(b[i].v);
        if(fa!=fb){
            f[fa]=fb;
            e.push_back({b[i].u,b[i].v,b[i].w});
        }
    }
    for(int i=1;i<=k;i++){
        for(int j=1;j<=n;j++){
            e.push_back({n+i,j,a[i][j]});
        }
    }
    sort(e.begin(),e.end(),cmp);
    dfs(1);
    cout<<ans<<"\n";
    return 0;
}

时间只剩下了 30 分钟，开始打暴力了。T3 刚开始没看懂，就先写了 T4 8 pts 的部分分了。仔细阅读了 T3，才发现只能转换一次，因为时间不多了，就只写了 10 pts 的做法。写完之后就只剩下 5 分钟了，检查了一下 freopen 就结束了。

刚开始比完的时候还感觉这辈子没了，后来发现似乎都差不多就放心了。

比赛结束后自己的估分是 100+64+10+8=182。

和 wzb 大佬讨论了 T2，ta 没有注意到性质 2，r.i.p。

去地铁口时骑自行车掉链了（属于比赛阳寿用完了）

因为讨论的过于火热导致忘记带了身份证，然后就是身份证被发到了教练群了，被 zhr 大佬夸可爱了（嘻。

luogu 估分

在火车上测的。

CSP-J：100+100+100+[64,100]=[364,400]。气死我了，T4常数太大似乎挂了。

CSP-S：100+[64,80]+[10,50]+[0,12]=[174,242] 分。属于 CSP-J 的挂分全部给到 CSP-S 了。

这次属于超常发挥了。

Day inf

CSP-J：100+100+100+100=400。拜谢 CCF 没有卡常。

CSP-S：100+80+25+8=213 分。似乎能 7 勾了？

这个赛季似乎 \sqrt4 -> \sqrt7 了。

咕咕咕咕

CSP复赛游记——杭师大一日游

绝密☆启用前

Day -inf

CSP-J

CSP-S

Day 0

Day 1

Day inf