江湖人是過河卒 路是不歸路 -- csp-s 2025 游記

總結: 打鐵了, 但是龍膽紫說 "江湖人是過河卒 路是不歸路", 所以我不會 exit 的.

day \(-1\)

睡不著, 打開 b 站看人直播 vp cf/atc, 我 vp div4 被炸死了.

感覺要寄.

day \(0\)

火車上用耳機聽著龍膽紫迷迷糊糊睡著了, 萬幸的是電腦沒丟. 左邊坐的是 sdzb 某校的 oi 教練.

晚上看考場, 和巨佬 SmartWind 在同一個考場, rp++.

回賓館在很多群里發了 rp-=~inf+1;.

day \(0.5\)

想起來雙指針還沒學, 切了幾個雙指針黃題.

problem:洛谷-P1638 problem:洛谷-P3029

下午進場, 遇見了大神 LZYao, %%%

day \(1\)

14:30 才發壓縮包密碼, 人杰地靈. 聽說 j 組是 上善若水, ccf 最近在修仙嗎?

先大致瀏覽了一遍題目, a 是貪心沒想到怎么貪, b 是個詭異的最小生成樹有點像分層圖, c 是弦論壓根不會, d 是 dp.

注意到 d 有幾個測試點是 pure \(s_{i}==1\) 的, 我懷疑輸出的就是取模后的階乘. 大概不到半小時寫完了缺省源和一個 ll fctrl(ll), 運行發現并不是取模的階乘, 于是放棄.

由于貪心是我非常薄弱的算法, 于是我選擇了寫 b.

有些數據點的鄉鎮的點權為 \(0\), 那么我們說在這個鄉鎮產生了作用當且僅當在最小生成樹里不是葉子, 可以證明.

于是先 kruskal 出最小生成樹, 判斷一個邊如果某個頂點的度為 \(1\) 則認為是葉子, 此時判斷是否是鄉鎮, 如果是鄉鎮就不管這條邊, 否則累加這條邊.

這個用 \(deg_{x}==1\) 判斷葉子的方法還是某次模擬賽我把 bfs 判葉子寫炸了后某大神教我的, 真是一個酣暢淋漓的判葉子啊.

代碼大賞 (這是考后寫的, 場上寫的碼風非常差).

#include<cmath>
#include<climits>
#include<cstdbool>
#include<cstddef>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<deque>
#include<iomanip>
#include<iostream>
#include<map>
#include<queue>
#include<tuple>
#include<vector>

using	lf=double;
using	us=size_t;
using	ll=ptrdiff_t;
constexpr	ll inf=0x3f3f3f3f3f3f3f3fl;
constexpr	ll mod=0x3b800001l;
constexpr	ll ver=1l<<14;

typedef	struct	_vtx	vtx;
struct	_vtx{
	vtx *top;
	ll val,deg;
	void add_edge(vtx*,ll);
	auto fnd(void)->vtx*;
}	v[ver];

std::vector<std::tuple<vtx*,vtx*,ll,_Bool>>e;

void	vtx::add_edge(vtx *y,ll z){
	e.emplace_back(this,y,z,0);
}

auto	vtx::fnd(void)->vtx*{
	if(top==NULL)
		return this;
	else	return top=top->fnd();
}

auto	kruskal(ll n,ll n2)->ll{
	std::sort(e.begin(),e.end(),[](std::tuple<vtx*,vtx*,ll,_Bool>&f,std::tuple<vtx*,vtx*,ll,_Bool>&g){
		return std::get<2>(f)<std::get<2>(g);
	});	for(auto &[x,y,z,f]:e){
		if(x->fnd()==y->fnd())
			continue;
		x->deg++,y->deg++,f=1;
		x->fnd()->top=y->fnd();
	}	ll s=0;
	for(auto &[x,y,z,f]:e){
		if(f==0)
			continue;
		if(v+n<x&&x->deg==1)
			continue;
		if(v+n<y&&y->deg==1)
			continue;
		s+=z;
	}	return s;
}

void	solve(void){
	ll n,m,n2;
	std::cin>>n>>m>>n2;
	while(m--){
		ll x,y,z;
		std::cin>>x>>y>>z;
		v[x].add_edge(v+y,z);
		v[y].add_edge(v+x,z);
	}	for(ll x=n+1;x<=n+n2;x++){
		std::cin>>v[x].val;
		for(ll y=1;y<=n;y++){
			ll z;
			std::cin>>z;
			v[x].add_edge(v+y,z);
			v[y].add_edge(v+x,z);
		}
	}	std::cout<<kruskal(n,n2)<<"\n";
}

auto	main(void)->signed{
//	freopen("road.in","r",stdin);
//	freopen("road.out","w",stdout);
	std::ios::sync_with_stdio(0);
	std::cin.tie(0),std::cout.tie(0);
	ll t=1;
//	std::cin>>t;
	while(t--)
		solve();
	return 0;
}

估分是裸 kruskal 的 \(4*4=16\) 分再加上鄉鎮權值為 \(0\) 的測試點的 \(8*4=32\) 分就是 \(48\) 分, 洛谷確實給了 \(48\), 希望 freopen("road.in","r",stdin); 不要出事.

不要致敬 Wild_Donkey 的 freopen("julian3.in","r",stdin); 了.

于是回來看 a, 此時還剩兩個小時.

在剛仔細看題時認為特殊性質之均勻隨機是無用的, 但注意到直接累計每個 std::max({a[i][1],a[i][2],a[i][3]}) 并輸出就能得分, 于是有了 \(10\) 分.

那么特殊性質之 \(a_{i,2}==a_{i,3}==0\) 也是比較容易的, std::sort(a+1,a+n+1,cmp); 后累計前半段輸出即可, 又到手了 \(5\) 分.

特殊性質之 \(a_{i,3}==0\) 是非常有難度的, 我想了很久也沒想法.

注意到有 \(n==200\) 的暴力分 \(45\) 分, 想了半小時 \(O(n^{2})\) 和 \(O(n^{3})\) 都沒有思路, 莫名的一直在往狀壓上想, 甚至想到了枚舉 \(S\subset U\) 后枚舉 \(T\subset(U\setminus S)\) 這樣詭異的狀壓.

然而這樣的狀壓其實就不如搜索了, 于是在最后 \(15\) 分鐘寫了個搜索.

dfs 也是好歹有 \(20\) 分, 加上剛才兩個特殊性質 (另一個特殊性質沒想出來) 加起來的 \(15\) 分, 獲得了 \(35\) 分.

代碼大賞.

#include<cmath>
#include<climits>
#include<cstdbool>
#include<cstddef>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<deque>
#include<iomanip>
#include<iostream>
#include<map>
#include<queue>
#include<tuple>
#include<vector>

using	lf=double;
using	us=size_t;
using	ll=ptrdiff_t;
constexpr	ll inf=0x3f3f3f3f3f3f3f3fl;
constexpr	ll mod=0x3b800001l;

auto	dfs(ll d,std::vector<std::tuple<ll,ll,ll>>&a,ll n,ll f,ll g,ll h,ll s){
	if(d==n)
		return s;
	auto [x,y,z]=a[d];
	ll v=f<n>>1?dfs(d+1,a,n,f+1,g,h,s+x):0;
	v=std::max(v,g<n>>1?dfs(d+1,a,n,f,g+1,h,s+y):0);
	v=std::max(v,h<n>>1?dfs(d+1,a,n,f,g,h+1,s+z):0);
	return v;
}

void	solve(void){
	ll n;
	std::cin>>n;
	std::vector<std::tuple<ll,ll,ll>>a(n);
	for(auto &[x,y,z]:a)
		std::cin>>x>>y>>z;
	std::cout<<dfs(0,a,n,0,0,0,0)<<"\n";
}

auto	main(void)->signed{
//	freopen("club.in","r",stdin);
//	freopen("club.out","w",stdout);
	std::ios::sync_with_stdio(0);
	std::cin.tie(0),std::cout.tie(0);
	ll t=1;
	std::cin>>t;
	while(t--)
		solve();
	return 0;
}

計算分數 \(35+48+0+0=83\), 于是結局就是打鐵了.

出考場時和 SmartWind 交流, SmartWind 認為是 黃藍紫紫.

day \(2\)

火車上看著窗外的農田和公路飛速后退, 聽著龍膽紫的 cypher, 莫名的想睡覺, 于是睡覺.

注意到洛谷給的顏色是 綠藍紫紫.

day \(3\)

發現洛谷把顏色降到了 黃藍紫紫, 非常生氣.

寫了游記.