专栏文章

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

xxu_zhihao
生活·游记参与者 40已保存评论 42

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
42 条
当前快照
1 份
快照标识符
@mi6fsyaw
此快照首次捕获于
2025/11/20 04:10
3 个月前
此快照最后确认于
2025/12/01 20:40
3 个月前
查看原文

绝密☆启封前

日负无穷

前夜卧即寐，睁目已晨。

  • 丙组试

略言，估分八十九至九十二。
至考场，封条森严，甚异于昔。闻旧岁有考点因禁如厕被劾，故今岁不得设场，可叹。
开考铃响足十秒！展甲题，见无符整型（去岁有符，来岁岂无符长整乎？）。丁题失察，痛损二分。
前十五题中平，略难于旧岁，犹可措手。答毕时已十刻。
补全程序其一较去岁稍难，然陷阱浅显，末界之判当不计。补全程序其二目眩，误辨限界之性，损四分半（廿四、廿五题）。是题之难，实超去岁。
及见补全程序其三，竟为最长升列之模板，数字版尤简，殊无新意。时方十又三刻。
补全程序颇具甄别。其一几近送分，然困于审题，耗一刻方解。其二殊难，竟涉函式交互，贪心之证费一刻半，摩尔投票诚艰深！其释文鄙陋，致四十题误择。时已十一又二刻。
末刻查得二错，挽五分。改毕时考官已欲收卷。
终估百分减诸失，得八十九至九十二。
补：各地估分微异。
若此分不过，当封笔归隐。
顺讥CCF双卅三题之失，印卷前竟不覆检耶？

  • 乙组试

尔无卵哉！
GESP超常，八级九分免试。
午后续修培优课，闻人言“乙组易于丙组”，惑而不解。
补GESP游记：前题皆易，一时毕。编程首题双ST表维之，次题初以搜法败，忽忆换根可记化，五分鐘成码，调两刻乃AC。幸CCF未卡菊图，拜谢！
估分八十九。
后数日查分，竟得九十。

前日

申时请假归，食毕疾驰车站。
车中遍温旧学，温毕恰至。
至杭师大门探考场，返宿。（客舍夜食甚佳）夜半心平无波，然寐而不酣，若见浮生万千...

当日

  • 晨试
    密文“上善若水”，堪笑CCF文采。
    览四题，似皆平易。
    甲、乙二题纯贪心摹拟，一刻成。
    丙题微妙，思一刻乃悟右界左移则贡献不降，遂用无序图叠线性法。其码如左：
    CPP
    #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之方。码如下：
    CPP
    #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;
}
    然动规界设阔，常数陡增，过否在天。
    至九又三刻毕，闭目养神。末刻无聊，戏扫雷。
补：丙组总码量不敌乙组甲题。
  • 昼歇
    骑单车食沙县，味美而口疮作痛。归寓假寐（未成眠），起而饮西洋参，复赴考场。
  • 暮试
    考官诵密码如梵音，懵懂三刻乃录。展甲题时已十四又半。键声如雷（幸备耳塞），觉今岁甲题艰甚。半时辰思动规未果，转贪心。赛前广习贪巧与即兴法，初欲杂动规而伪，忽悟反贪，证毕重构。初未用结构，混沌如团，息片时乃更。遂过大例。时十五又二刻。忆码如下：
    CPP
    #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，疑与二幂相关。苦思乡邑化城之贡献，正难则反，递归乡邑状态而算其效。初版复杂度劣，未实现。时十六又三刻，心渐慌，默念“信力”（社师名言）。复得更劣之法，时十七又一刻。误记终时为十八点，大急！忽得第二性：唯原图最小树边可为贡献。激动几坠键。遂成终法：
    1. 取原图最小树边集
    2. 递归诸化城方案
    3. 合边集复求最小树
    4. 验贡献
    复杂度可容，三刻码成，过大例。期分六五。时十七又三刻。 忆码如下：
    CPP
    #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;
}
补：赛后知若预排序，可得满分。此題当评蓝，堪称史上最难乙二。
CPP
#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 未卡常。
乙组成绩：二百十三分。可勾七级否？
此季自 4\sqrt{4} 跃 7\sqrt{7} 矣。
咕咕复咕咕。

评论

共 42 条评论，欢迎与作者交流。

正在加载评论...