CSP 2025 游记

内容分享2小时前发布

0 0 0

考场

考前复习了各种模板，并且前一晚睡得很好，觉得无敌了。

11.1 14：00 见到了很多人，发现考场2全神人（SFLS Vs SZ）才发现我们学校那么多人。好在我在 3 考场，没有压力。

14：25 进考场，卡点才让我门进，（铺垫

14：30 开打，把模板敲了，看了四道题

15：00 发现只会 T1 炸了！

15：30 T1 过大样例。开始思考 T2 和 T4，因为对 T3 莫名其妙的字符串恐惧症。

16：00 发现 T4 越看越难，神题，部分分也不好拿。乖乖回去写 T2。

首先：考虑到边很大，但是 kkk 和 nnn 都很小，那么是不是可以考虑从这边入手。而且我们对乡村的边，很难实现第一个边让他加个权，后面的就不加。

首先 kkk 这个数据显然是给你状压的，那你状压完不可能是暴力啊。不然那不炸了。

所以，如果我们先预处理出没有任何 kkk 的最小生成树。然后我们发现，不管怎样加额外点，都不会用到这个最小生成树之外的边。（这里尝试证明了半天，发现没找出反例，但应该是对的）

于是把最小生成树上的边都处理下来，状压暴力新建对应点的对应边。然后边数不会超过 n+k∗nn + k * nn+k∗n。这个时候就再跑 kruskal 然后加上用了的乡村建造的贡献。

时间复杂度 O(mlog⁡m+2k×(kn)log⁡kn)O(m log m + 2^k imes (kn) log kn)O(mlogm+2k×(kn)logkn)。

16：30 过 T2 大样例，1.2s 感觉还好，毕竟本地一般都慢一些。开始仔细研究 T3。发现有个很划算的暴力。就是直接 KMP，就是在每一个询问暴力查所有 S 对应的匹配位置，然后把这个匹配位置找出相同重复的，统计即可。（~~考前刚写了一遍 kmp，但还是忘了，重新手推了一遍，但愿别挂~~。这样的时间复杂的可以过前面的小数据，也可以过 A 性质 q=1。

18：00 终于把 KMP 调出来了，前两个样例都过了，但是样例都比较小，没有什么参考意义。然后又发现 B 性质直接判断距离然后存个MAP就可以，发现时间有点紧了。我还得把询问离线下来，在做一个特殊的 B 性质判断。

18：15 写完了 B 性质，但是 B性质给的样例竟然挂了。而且差的很多。

18：20 突然间意识到，有可能替换串比原串要大，这个时候不合法。所以我重构了一遍，就是将替换串的长度递增排序，然后动态标记它的距离的数量，然后还有再动态的时候记录原串的答案。

18：25 正在把排完序的答案按照 id 重新放进一个数组。然后监考老师：考试结束，再写作弊了。？？？？不是为啥啊，我脑子一片空白，就差一行输出。又怕作弊禁赛三年。所以立马把freopen打开。然后一堆运行的数据和文件都没来得及删。

18：30 早知道当时把输出写完了，不要理监考老师，毕竟判定时间是 18：30 才算作弊的。由此 270 -》 245。为社么不是250呢？因为有一个点是 AB 的性质同时存在，这个时候我会把它判到 B 性质的代码中，然后就没有输出。如果我当时把判断的也注释掉，就会250了。

~~好歹不是250~~

18：31 看到了各位，Empty_Dream T3 写的哈希，所以他应该 [250,300] ，说是大样例飞快。~~CCF 你数据强点把他卡爆就行了~~；Ziyistudy 说他炸了，然后不说话；2020luke 说差不多也是 250；Frank08 说 T2 看错题了，然后 T3 25pts；liboya5074 说 T2 不会，并条了一场，160pts。

我还以为我要输了，现在发现只要不挂分就赢了。~~（但就怕他挂啊~~

大概会是：

100 + 100 + [0,45] + 0

11.2 说是不公布代码了。所以我凭记忆重写一遍吧：

复盘

T1 : 重写完样例过了，交： 80pts？？？？？？有个细节假了。就是判断等于的一些地方会假（前面处理的时候是 if , else if, else，后面是 if if if，所以会有相等的情况挂）。调了一下过了。~~祈祷CCF 数据放水~~

考场代码大概长这样：（Luogu 80pts）（yundou 70pts）


int a[N][5],n;
int cnt[5];
void solve(){
    cin >> n;
    For(i,1,n){
        cin >> a[i][1] >> a[i][2] >> a[i][3];
    }For(i,1,3)cnt[i] = 0;
    int ans = 0;
    For(i,1,n){
        if(a[i][1] >= a[i][2] && a[i][1] >= a[i][3]) cnt[1] ++,ans += a[i][1];
        else if(a[i][2] >= a[i][1] && a[i][2] >= a[i][3]) cnt[2] ++,ans += a[i][2];
        else cnt[3] ++,ans += a[i][3];
    }if(cnt[1] <= n/2 && cnt[2] <= n/2 && cnt[3] <= n/2){
        cout << ans << endl;return ;
    }if(cnt[1] > n/2){
        vector<int>v;
        For(i,1,n){
            if(min(a[i][1]-a[i][2],a[i][1]-a[i][3]) >= 0) v.pb(min(a[i][1]-a[i][2],a[i][1]-a[i][3]));
        }sort(v.begin(),v.end());
        for(int i = 0;i < cnt[1]-n/2;i++) ans -= v[i]; 
    }if(cnt[2] > n/2){
        vector<int>v;
        For(i,1,n){
            if(min(a[i][2]-a[i][1],a[i][2]-a[i][3]) >= 0) v.pb(min(a[i][2]-a[i][1],a[i][2]-a[i][3]));
        }sort(v.begin(),v.end());
        for(int i = 0;i < cnt[2]-n/2;i++) ans -= v[i]; 
    }if(cnt[3] > n/2){
        vector<int>v;
        For(i,1,n){
            if(min(a[i][3]-a[i][2],a[i][3]-a[i][1]) >= 0) v.pb(min(a[i][3]-a[i][2],a[i][3]-a[i][1]));
        }sort(v.begin(),v.end());
        for(int i = 0;i < cnt[3]-n/2;i++) ans -= v[i]; 
    }cout << ans<<endl;
}

100pts:


int a[N][5],n;
int cnt[5];
void solve(){
    cin >> n;
    For(i,1,n){
        cin >> a[i][1] >> a[i][2] >> a[i][3];
    }For(i,1,3)cnt[i] = 0;
    int ans = 0;
    vector<int> v1,v2,v3;
    For(i,1,n){
        if(a[i][1] >= a[i][2] && a[i][1] >= a[i][3]) cnt[1] ++,ans += a[i][1],v1.pb(min(a[i][1]-a[i][2],a[i][1]-a[i][3]));
        else if(a[i][2] >= a[i][1] && a[i][2] >= a[i][3]) cnt[2] ++,ans += a[i][2],v2.pb(min(a[i][2]-a[i][1],a[i][2]-a[i][3]));
        else cnt[3] ++,ans += a[i][3],v3.pb(min(a[i][3]-a[i][2],a[i][3]-a[i][1]));;
    }if(cnt[1] <= n/2 && cnt[2] <= n/2 && cnt[3] <= n/2){
        cout << ans << endl;return ;
    }if(cnt[1] > n/2){
        sort(v1.begin(),v1.end());
        for(int i = 0;i < cnt[1]-n/2;i++) ans -= v1[i]; 
    }if(cnt[2] > n/2){
        sort(v2.begin(),v2.end());
        for(int i = 0;i < cnt[2]-n/2;i++) ans -= v2[i]; 
    }if(cnt[3] > n/2){
        sort(v3.begin(),v3.end());
        for(int i = 0;i < cnt[3]-n/2;i++) ans -= v3[i]; 
    }cout << ans<<endl;
}

最后：CCF 实际65pts，~~rp 不够~~

T2 ：发现常数有点大。。感觉悬。luogu 80 TLE


int n,m,k;
struct node{
    int u,v,w;
}edge[M];
int c[15][N];
int f[N];
int find(int x){return x == f[x] ? x : f[x] = find(f[x]);}
bool cmp(node a,node b){return a.w < b.w;}
vector<node> v;
int ans = 0;
void init(){
    sort(edge+1,edge+1+m,cmp);
    For(i,1,n) f[i] = i;
    For(i,1,m){
        if(find(edge[i].u) != find(edge[i].v)){
            f[find(edge[i].u)] = find(edge[i].v);
            v.pb(edge[i]);
            ans += edge[i].w;
        }
    }   
}void kruskal(int z){
    int add = 0;
    vector<node> nw; 
    nw = v;
    int cnt=n;
    For(i,1,k) if((z >> (i-1)) & 1) {
        add += c[i][0];
        ++cnt;
        For(j,1,n) nw.pb({cnt,j,c[i][j]});
    }sort(nw.begin(),nw.end(),cmp);
    For(i,1,cnt) f[i] = i;
    for(auto it:nw){
        if(!cnt) break;
        if(find(it.u) != find(it.v)){
            f[find(it.u)] = find(it.v);
            add += it.w;
            cnt --;
        }
    }
    ans = min(ans,add);
}   
void solve(){
    cin >> n >> m >> k;
    For(i,1,m){
        cin >> edge[i].u >> edge[i].v >> edge[i].w ;
    }
    For(i,1,k) For(j,0,n) cin >> c[i][j];
    init();
    For(z,0,(1<<k) - 1){
        kruskal(z);
    }cout << ans << endl;
}

考试的时候想到要不要把sort提出来，但是目测时间复杂度十分充裕，所以懒得修了。

所以事实上只需要把sort提出来就可以过了。


int n,m,k;
struct node{
    int u,v,w;
}edge[M];
int c[15][N];
int f[N];
int find(int x){return x == f[x] ? x : f[x] = find(f[x]);}
bool cmp(node a,node b){return a.w < b.w;}
vector<node> v;
int ans = 0;
void init(){
    sort(edge+1,edge+1+m,cmp);
    For(i,1,n) f[i] = i;
    For(i,1,m){
        if(find(edge[i].u) != find(edge[i].v)){
            f[find(edge[i].u)] = find(edge[i].v);
            v.pb(edge[i]);
            ans += edge[i].w;
        }
    }   
}void kruskal(int z){
    int add = 0;
    For(i,1,k) if((z >> (i-1)) & 1) {
        add += c[i][0];
    }
    For(i,1,n + k) f[i] = i;
    for(auto it:v){
        if(it.u > n && !((z>>(it.u - n - 1)) & 1)) continue;
        if(find(it.u) != find(it.v)){
            f[find(it.u)] = find(it.v);
            add += it.w;
        }
    }
    ans = min(ans,add);
}   
void solve(){
    cin >> n >> m >> k;
    For(i,1,m){
        cin >> edge[i].u >> edge[i].v >> edge[i].w ;
    }
    For(i,1,k) For(j,0,n) cin >> c[i][j];
    init();
    For(i,1,k) {
        For(j,1,n) v.pb({i + n,j,c[i][j]});
    }sort(v.begin(),v.end(),cmp);
    For(z,0,(1<<k) - 1){
        kruskal(z);
    }cout << ans << endl;
}

T3 : 实测CCF 是 CE了。原因是我最后写的B性质代码由于没有编译检测~~（可爱的监考老师卡时间）~~所以有一个结构体的 ” . “点错位置了。直接寄。

但是还有个小错误，就是一个初始话，是在调试的时候把他改错的。也就是我统计最大相同前后缀的时候，fff 与 bbb 设为了-inf 和 inf，事实上 0 和 n 才是对的。所以在这个时候如果 sss 等于 ttt 的时候就寄。~~并且考试时手推的KMP好像挂了哎~~。

改完之后还有 30pts 哎。为啥不是50 pts？

tle 30 CODE:（理论上来说不应该是 A 性质都不会有问题吗）


int n,m;
string s1[N],s2[N];
int nxt[M];
vector<int> kmp(string s,string t){
	vector<int> v;
    int n = s.size();
	int m = t.size();
    if(m > n) return v;
    For(i,0,m) nxt[i] = 0;
	s=' ' + s;
	t=' ' + t;
	int j = 0;
	For(i,2,m){
		j = nxt[i - 1];
		while(j && t[i] != t[j + 1]) j = nxt[j] ;
		if(t[i] == t[j + 1]) j ++;
		nxt[i] = j;
	}
	j =  0;
	for(int i = 1;i <= n;){
		while(j && s[i] != t[j+1]) j = nxt[j] ;
		if(s[i] == t[j + 1]){
			++j;
		}if(j == m){
			v.pb(i - m + 1); j = nxt[j];	
		}++i;
	}return v;
}
void solve(){
    cin >> n >> m ;
    For(i,1,n) cin >> s1[i] >> s2[i] ;
    while(m--){
        string t1,t2 ;cin >> t1 >> t2 ;
        if(t1.size() != t2.size()) {
            cout << 0 << endl; continue;
        }
        int ans = 0;
        int f = 0,b = t1.size() + 1;
        For(i,0,t1.size()-1) if(t1[i] != t2[i]) break;else f=i + 1;
        For_(i,t1.size() - 1,0) if(t1[i] != t2[i]) break;else b = i +1;
        // cout << "fb" << f<<" " << b<< endl;

        For(i,1,n){
            vector<int> v1 = kmp(t1,s1[i]);
            vector<int> v2 = kmp(t2,s2[i]);
            map<int,int> mp;
            for(auto it:v1) mp[it] ++;
            for(auto it:v2) {
                if(mp[it] && (it<=f + 1 && it+(int)s1[i].size() -1 >= b - 1) && it+(s1[i].size()) - 1 <= t1.size()) ans ++ ;
            }
        }cout << ans << endl;
    }
}signed main(){
	// freopen("std.in","r",stdin),freopen("std.out","w",stdout);
    // ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
	int T=1;
	// read(T);
	For(_,1,T) {
        // cout<<"--------test"<<_<<":
";
        solve();
    }return 0;
}

然后我发现好像是最后的时候用了 MAP，然后导致 5e6 在带个 log。但是改成数组+动态初始化依然 tle 啊。

然后发现 KMP 的时间复杂度是 |s| + |t|的，所以每一个询问里面相当于我要重复做 n 遍 t，所以就炸了。

所以这个做法打满也就30 pts 吧。

50pts 得 AC 自动机。

T4：
不管了，反正也 0PTS

最后发现 ZIYISTUDY 100+80+50+0
2020LUKE 100+80+25+20
合着就我挂分是吧投降！

AFO ~~