2025.7.22 测试 总结

From nfls 2025 Summer Camp S+
题目后的括号 $(a,b)$ 表示 (难度，考场思考率)

T3 矩形坑洞覆盖 （easy+,80%）

link
题意
有一个长为 $holeH$ 宽为 $holeW$ 的矩形洞口。给定 $n$ 块木板 $(h_i,w_i)$，木板之间可以重叠，叠木板时允许木板旋转 $90°$，但最终放置时必须与坑洞的边平行。选的每块木板的四个角点必须严格位于坑洞边界之外（即不允许任何角点接触坑洞边界）。求完全覆盖洞口所需的最小木板数，无解则 $-1$ 。   $1\le n\le 50,1\le holeH,holeW,h_i,w_i\le 10^9$

思路
手玩多组样例可得一个贪心结论：横向和纵向如果各使用一部分木板是没有意义的，所以只考虑全是横向或者全是纵向排列的情况。于是直接模拟即可。

反思
场上有点看错题了。（-40pts）太久忘记贪心了。

代码

#include<bits/stdc++.h>
using namespace std;
const int maxn=55;
int h[maxn],w[maxn];
struct NODE{ int x,y; }a[maxn];
int main(){
	int hh,ww,n; cin>>hh>>ww>>n;
	for(int i=1;i<=n;i++)
		cin>>a[i].x;
	cin>>n;
	for(int i=1;i<=n;i++)
		cin>>a[i].y;
	int hm=0,wm=0;
	for(int i=1;i<=n;i++){
		if(a[i].x>hh&&a[i].y>hh) w[++wm]=max(a[i].x,a[i].y);
		else if(a[i].x>hh) w[++wm]=a[i].y;
		else if(a[i].y>hh) w[++wm]=a[i].x;
		if(a[i].x>ww&&a[i].y>ww) h[++hm]=max(a[i].x,a[i].y);
		else if(a[i].x>ww) h[++hm]=a[i].y;
		else if(a[i].y>ww) h[++hm]=a[i].x;
	}
	sort(w+1,w+wm+1,[](int a,int b){ return a>b; });
	int ans=0,sumw=0;
	for(int i=1;i<=wm;i++){
		sumw+=w[i];
		if(sumw>=ww){
			ans=i;
			break;
		}
	}
	sort(h+1,h+hm+1,[](int a,int b){ return a>b; });
	int ans2=0,sumh=0;
	for(int i=1;i<=hm;i++){
		sumh+=h[i];
		if(sumh>=hh){
			ans2=i;
			break;
		}
	}
	if(!ans&&!ans2) cout<<-1;
	else if(!ans) cout<<ans2;
	else if(!ans2) cout<<ans;
	else cout<<min(ans,ans2);
	return 0;
}

T4 ABBA替换（mid-,60%）

link
题意
给定一个只包含 $A,B$ 的字符串 $st$，对于每次操作同时替换当前串中所有的 AB 为 BA ，求到不能操作为止进行了多少次操作。   $1\le |st|\le 7\times 10^6$

思路
易知字符串的最终形态为 BB……BA……AA 。观察原串和现串中字符的位置，只考虑 B （A 也同理）。
单独看每个 B 的贡献 ，考虑与答案之间的关系。显然每个 B 到达最终位置的步数为 $po{s}_{i_{now}}-po{s}_{i_{first}}$ ；但若这个 B 与上一个之间隔了 A 则步数也可以是 上一个 B 的步数 + 1 。求所有 B 步数的最大值即可。

反思
没有想到拆开考虑每个 B 的贡献。当然这题也可以找规律。

代码

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int maxn=7*1e6+5;

ll n,seed,threshold;
string st;
string Init(){
	ll state=seed;
	string s=st;
	while(s.size()<n){
		state=(state*1103515245+12345)%(1ll<<31);
		s+=(state<threshold?'A':'B');
	}
	return s;
}

int a[maxn],f[maxn];
int main(){
	cin>>st>>n>>seed>>threshold;
	st=Init();
	int cnt=0;
	for(int i=0;i<n;i++)
		if(st[i]=='B') a[++cnt]=i;
	for(int i=1;i<=cnt;i++){
		f[i]=a[i]-(i-1);
		if(i>1&&a[i-1]!=i-2) f[i]=max(f[i],f[i-1]+1);
	}
	cout<<f[cnt];
	return 0;
}

T5 [POI 2005] SAM-Toy Cars（mid-,95%）

link
反思
挺不错的贪心，但是不会证。

T7 [SCOI2006] zh_tree（mid+,40%）

link
思路
首先有一个记录深度的 $O(n^3)$ 暴力。发现转移没法优化，考虑优化状态，深度这一维。
于是推一下式子： 记 $S=\sum d_i$ ，$结点i的深度为r_i$ 。
$$\begin{array}{rl}ans& =\sum h_i\times f_i\\ & =\sum \frac{k\times r_i\times d_i+c\times d_i}{S}\\ & =\frac{k\times \sum r_i\times d_i}{S}+c\end{array}$$
所以也就是求 $\sum r_i\times d_i$ 的最小值。同 [NOIP 2003 提高组] 加分二叉树 ，区间DP 就好。

反思
场上没缕清思路就开写了，导致搜索的时候将暴力和正解混在了一起，加上中途有一些小错误降脂调试，喜提 0 pts 。

代码

#include<bits/stdc++.h>
using namespace std;
const int maxn=303;

int sum[maxn];
double f[maxn][maxn],ft[maxn],k,c,a[maxn];
double Dfs(int l,int r){
	if(l>r) return 0.0;
	if(f[l][r]!=1000000000.0) return f[l][r]; 
	if(l==r) return f[l][r]=a[l];
	for(int i=l;i<=r;i++)
		f[l][r]=min(f[l][r],Dfs(l,i-1)+Dfs(i+1,r));
	f[l][r]+=1.0*(sum[r]-sum[l-1]);
	return f[l][r];
}

int main(){
	int n; cin>>n>>k>>c;
	for(int i=1;i<=n;i++){
		cin>>a[i];
		sum[i]=sum[i-1]+a[i];
	}
	for(int i=1;i<=n;i++)
		for(int j=1;j<=n;j++)
			f[i][j]=1000000000.0;
	Dfs(1,n);
	printf("%.3lf",1.0*k*f[1][n]/sum[n]+c);
	return 0;
}

T8 CF627D Preorder Test （mid+,5%）

link
题意
给出一棵无根树，每个节点有一个权值。你可以指定树根和访问顺序，使得 $dfs$ 序中前 $k$ 个结点的权值最小值最大，求出这个值。   $2\le n\le 2\times 10^5$

思路
求 最小值最大 第一反应是二分答案。
考虑怎么样判断二分值 $mid$ 是否可行。贪心想法，如果子树内的值都 $\ge mid$ ，那就先访问这棵子树，称为合法子树。进行 树形DP ，记 $f_i$ 表示 子树 $i$ 中访问完所有合法儿子子树后再访问一条合法最长链时访问过的结点数量。容易知这条最长链链尾的下一个结点的值就 $<mid$ 了。这样枚举树的根可以做到 $O(n^{2}logn)$ 。
继续优化，发现瓶颈在于枚举数根，考虑换根的影响。其实我们对于一颗以 $i$ 为根的树不一定要从 $i$ 开始访问。可以从次长链的末端开始访问，最后到达最长链的末端，这样一定最优。这时树的根就是权值最小的结点。这样复杂度就是 $O(nlogn)$ 了。

反思
想到 二分 很关键，然后要会 $O(n^{2}logn)$ 的暴力，不断优化没必要的试根，找到最优解。

代码

#include<bits/stdc++.h>
using namespace std;
const int maxn=2e5+5;

int idx,head[maxn];
struct EDGE{ int v,next; }e[maxn*2];
void Insert(int u,int v){
	e[++idx]={v,head[u]};
	head[u]=idx;
}

int ans,f[maxn],siz[maxn],a[maxn];
void Dfs(int x,int fa,int d){
	siz[x]=1,f[x]=(a[x]>=d?1:0);
	for(int i=head[x];i;i=e[i].next){
		int v=e[i].v;
		if(v!=fa) Dfs(v,x,d);
	}
	int ma=0,ma2=0;
	for(int i=head[x];i;i=e[i].next){
		int v=e[i].v;
		if(v!=fa){
			siz[x]+=siz[v];
			if(a[x]>=d){
				if(f[v]==siz[v]) f[x]+=f[v];
				else{
					if(f[v]>ma) ma2=ma,ma=f[v];
					else if(f[v]>ma2) ma2=f[v];
				}
			}
		}
	}
	if(a[x]>=d) f[x]+=ma;
	ans=max(ans,f[x]+ma2);
}

int k,root;
bool Check(int x){
	ans=0;
	Dfs(root,0,x);
	return ans>=k;
}

int main(){
	int n; cin>>n>>k;
	int r=0;
	for(int i=1;i<=n;i++){
		cin>>a[i]; r=max(r,a[i]);
		if(i==1||a[i]<a[root]) root=i;//!!! 
	}
	for(int i=1;i<n;i++){
		int x,y; cin>>x>>y; 
		Insert(x,y),Insert(y,x); 
	}
	int l=0,mid; r++;
	while(l+1<r){
		mid=(l+r)>>1;
		if(Check(mid)) l=mid;
		else r=mid;
	}
	cout<<l;
	return 0;
}

总结

3h 8problems 的训练赛还是很超前了。暴力 —> 优化 —> 正解 的思维很重要。