赴杭府师范庠序应信息学奥试，信笔记之。

xu_zhihao · 2025-11-19 14:44:03 · 生活·游记

绝密☆启封前

日负无穷

前夜卧即寐，睁目已晨。

丙组试

略言，估分八十九至九十二。

至考场，封条森严，甚异于昔。闻旧岁有考点因禁如厕被劾，故今岁不得设场，可叹。

开考铃响足十秒！展甲题，见无符整型（去岁有符，来岁岂无符长整乎？）。丁题失察，痛损二分。

前十五题中平，略难于旧岁，犹可措手。答毕时已十刻。

补全程序其一较去岁稍难，然陷阱浅显，末界之判当不计。补全程序其二目眩，误辨限界之性，损四分半（廿四、廿五题）。是题之难，实超去岁。

及见补全程序其三，竟为最长升列之模板，数字版尤简，殊无新意。时方十又三刻。

补全程序颇具甄别。其一几近送分，然困于审题，耗一刻方解。其二殊难，竟涉函式交互，贪心之证费一刻半，摩尔投票诚艰深！其释文鄙陋，致四十题误择。时已十一又二刻。

末刻查得二错，挽五分。改毕时考官已欲收卷。

终估百分减诸失，得八十九至九十二。

补：各地估分微异。

若此分不过，当封笔归隐。

顺讥CCF双卅三题之失，印卷前竟不覆检耶？

乙组试

尔无卵哉！

GESP超常，八级九分免试。

午后续修培优课，闻人言“乙组易于丙组”，惑而不解。

补GESP游记：前题皆易，一时毕。编程首题双ST表维之，次题初以搜法败，忽忆换根可记化，五分鐘成码，调两刻乃AC。幸CCF未卡菊图，拜谢！

估分八十九。

后数日查分，竟得九十。

前日

申时请假归，食毕疾驰车站。

车中遍温旧学，温毕恰至。

至杭师大门探考场，返宿。（客舍夜食甚佳）夜半心平无波，然寐而不酣，若见浮生万千...

当日

晨试

密文“上善若水”，堪笑CCF文采。

览四题，似皆平易。

甲、乙二题纯贪心摹拟，一刻成。

丙题微妙，思一刻乃悟右界左移则贡献不降，遂用无序图叠线性法。其码如左：

#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;
}

时已九又一刻。丁题见五百之限求策数，知为计动。套路在序排最大值，预处理前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;
}

然动规界设阔，常数陡增，过否在天。

至九又三刻毕，闭目养神。末刻无聊，戏扫雷。

补：丙组总码量不敌乙组甲题。

昼歇

骑单车食沙县，味美而口疮作痛。归寓假寐（未成眠），起而饮西洋参，复赴考场。

暮试

考官诵密码如梵音，懵懂三刻乃录。展甲题时已十四又半。键声如雷（幸备耳塞），觉今岁甲题艰甚。半时辰思动规未果，转贪心。赛前广习贪巧与即兴法，初欲杂动规而伪，忽悟反贪，证毕重构。初未用结构，混沌如团，息片时乃更。遂过大例。时十五又二刻。忆码如下：

#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;
}

此时犹从容...

启乙题见繁缛，似最短径而难理，转最小生树。证原图之费必在最小树上，然未明其用。见k≤10，疑与二幂相关。苦思乡邑化城之贡献，正难则反，递归乡邑状态而算其效。初版复杂度劣，未实现。时十六又三刻，心渐慌，默念“信力”（社师名言）。复得更劣之法，时十七又一刻。误记终时为十八点，大急！忽得第二性：唯原图最小树边可为贡献。激动几坠键。遂成终法：

取原图最小树边集
递归诸化城方案
合边集复求最小树
验贡献

复杂度可容，三刻码成，过大例。期分六五。时十七又三刻。忆码如下：

#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;
}

补：赛后知若预排序，可得满分。此題当评蓝，堪称史上最难乙二。

  #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;
}

余三刻，急作暴力。丙题初未解，先取丁题八分。细读丙题，方知仅可一转，时迫乃写十分之法。毕余五分，查文卷而终。

初觉今生尽毁，后见众皆如是乃安。

自估百分、六四、十、八，合百八二。

与 wzb 论乙题，彼未察第二性，惜哉。

归途单车链堕（赛时阳寿尽矣）。

论战酣忘携身份文牒，牒传教练群，为 zhr 赞“稚趣”，嘻。

洛谷估分

车中测之。

丙组：三百六四至四百。丁题常数巨而损分，憾甚。

乙组：百七四至二百四二。丙组所失尽偿于乙组矣。

今番超常乃尔。

日后

丙组成绩：四百分。拜谢 CCF 未卡常。

乙组成绩：二百十三分。可勾七级否？

此季自 \sqrt{4} 跃 \sqrt{7} 矣。

咕咕复咕咕。

赴杭府师范庠序应信息学奥试，信笔记之。

绝密☆启封前

日负无穷

丙组试

乙组试

前日

当日

日后