A 本关考验你求最大值功夫

$20pts:$

直接暴力枚举 $a,b$ 并暴力统计 $\sum_{i=1}^n (x_i-a)\times (y_i-b)$ ，以此来更新答案，粗略观察一下，由于 $a,b$ 如果相差过大，那求和式子一定会随着它变大而变小，所以枚举的数量级和 $c$ 同级即可，复杂度 $O(nc)$ 。

$60pts:$

直接暴力枚举 $a,b$ ，更新答案的时候，我们可以改写一下求和式子：

$\sum_{i=1}^n (x_i-a)\times (y_i-b)=\sum_{i=1}^n x_i*y_i-a*\sum_{i=1}^n x_i-b*\sum_{i=1}^n y_i+n*a*b$

其中三个求和式都可以预处理，获得答案，则可以 $O(n)$ 预处理， $O(c)$ 枚举，复杂度 $O(n+c)$ 。

$100pts:$

我们更改求和式子后，得到了形如 $k_1*a+k_2*b+k_3*a*b+k_4$ 的式子，然后我们又知道 $a+b=c$ ，于是可以将要最小化值的式子中的 $a$ 都替换为 $c-b$ ，于是得到了一个一元二次方程，只需要求出这个一元二次方程的最值点带入即可，求点复杂度 $O(1)$ ，计算最值复杂度 $O(n)$ 。

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int M=1000005;
ll tx[M],ty[M];
int main()
{
//	freopen("max.in","r",stdin);
//	freopen("max.out","w",stdout);
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	ll n,c,sumx=0,sumy=0,dltl,dltr;
	cin>>n>>c;
	for(int i=1;i<=n;i++) cin>>tx[i];
	for(int i=1;i<=n;i++) cin>>ty[i];
	for(int i=1;i<=n;i++) sumx+=tx[i];
	for(int i=1;i<=n;i++) sumy+=ty[i];
	ll a=(n*c+sumx-sumy)/(n*2);
	dltl=(n*c+sumx-sumy)-a*n*2;
	dltr=(a+1)*n*2-(n*c+sumx-sumy);
	if(dltl<=dltr) cout<<a<<" "<<c-a<<"\n";
	else cout<<(a+1)<<" "<<c-(a+1)<<"\n";
	return 0;
}

B 本关考验你求最小值功夫

$40pts:$

暴力建图，筛质数，跑最小生成树，任意一种最小生成树算法均可，复杂度 $O(n^2)$ ，可以观察后手动排除一些边，可以骗到 $60pts$ 。

$60-100pts:$

首先考虑所有质数连通，一定是去连最近的质数，此时我们将质数连成了一条链，这是对于连通的质数集的最优方案，然后考虑如何把合数并入。

我们可以将合数挂到离自己最近的质数上去，并且两个质数之间也可以挂一个合数，那么我们可以将离两个质数差不多近的合数插在里面，其它的挂在质数上面，这样构造出的树即是最小生成树。

复杂度瓶颈就来到了筛素数，根号筛素数为 $60pts$ ，线性筛为 $100pts$ 。

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int M=10000005;
int zs[M],p[M];
void init(int n){
	for(int i=2;i<=n;i++)
	{
		if(!p[i])
		{
			p[i]=i;
			zs[++zs[0]]=i;
		}
		for(int j=1;j<=zs[0]&&i*zs[j]<=n&&p[i]>=zs[j];j++)
		{
			p[i*zs[j]]=zs[j];
		}
	}
	return ;
}
int main()
{
//	freopen("min.in","r",stdin);
//	freopen("min.out","w",stdout);
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	int n;
	ll ans=1,dlt;
	cin>>n;
	if(n==1)
	{
		cout<<0<<"\n";
		return 0;
	}
	init(n);
	for(int i=1;i<zs[0];i++)
	{
		dlt=zs[i+1]-zs[i];
		if(dlt&1) ans+=(1+dlt/2)*(dlt/2)+dlt-(dlt/2);
		else ans+=dlt/2*(dlt/2-1)+dlt;
	}
	for(int i=zs[zs[0]];i<=n;i++)
	{
		ans+=i-zs[zs[0]];
	}
	cout<<ans<<'\n';
	return 0;
}

C 本关考验你判断正误功夫

$10pts:$

只有一种字符，我们容易得知，只要不是长度为 $1$ ，一定可以删光。

期望 $20pts:$

由于 $T$ 为 $1$ ，在字符不同时随机输出 " $YES$ '' 或者 " $NO$ ''，期望获得 $10pts$ 。

$100pts:$

区间 $dp$ ，设 $dp_{l,r}$ 为下标 $l$ 到 $r$ 的子串能否完全删除，然后枚举断点 $k$ ，得到 $dp$ 方程。

对于所有情况：

$dp_{l,r}=max(dp_{l,k}\& dp_{k+1,r})$

如果 $s_l=s_r$ 时，还要附加上：

$dp_{l,r}=max(max(max(dp_{l+1,k-1}\& dp_{k+1,r-1}),dp_{l+1,r-1}),dp_{l,r})$

判断 $dp_{1,n}$ 是否为 $1$ 即可。

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int M=305;
bool dp[M][M];
string s,st;
void solve(){
	int n;
	cin>>n;
	cin>>st;
	s=" "+st;
	memset(dp,0,sizeof(dp));
	for(int len=2;len<=n;len++)
	{
		for(int l=1;l+len-1<=n;l++)
		{
			int r=l+len-1;
			for(int k=l;k<r;k++)
			{
				dp[l][r]=max(dp[l][r],(dp[l][k]&&dp[k+1][r]));
			}
			if(s[l]==s[r]) 
			{
				if(len<=3) dp[l][r]=true;
				else
				{
					dp[l][r]=max(dp[l][r],dp[l+1][r-1]);
					dp[l][r]=max(dp[l][r],dp[l+2][r-1]);
					dp[l][r]=max(dp[l][r],dp[l+1][r-2]);
					for(int k=l+2;k<=r-2;k++)
					{
						dp[l][r]=max(dp[l][r],(dp[l+1][k-1]&&dp[k+1][r-1]));
					}
				}
			}
		}
	}
	if(dp[1][n]) cout<<"YES\n";
	else cout<<"NO\n";
	return ;
}
int main()
{
//	freopen("judge.in","r",stdin);
//	freopen("judge.out","w",stdout);
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	int T;
	cin>>T;
	while(T--)
	{
		solve();
	}
	return 0;
}
/*
1
12
abcdeffdecba*/

D 本关考验你数数功夫

链 $10pts:$

为一条链，任选两个不同的点均为花，答案为 $\frac{n*(n-1)}{2}$ 。

菊花图 $10pts:$

为菊花图（不讨论同为链的情况），如果不是 $4$ 个点，答案为 $0$ ，否则答案为 $3$ 。

$100pts:$

观察易知，一个点在连了边之后，至多有两条边在连成的环上，那如果树上存在大于 $3$ 度的点，则答案必然为 $0$ 。

否则，如果没有三度点，图退化为链。

如果有一个三度点，那以三度点为根，三个子链可以互相连，设其为 $siz_1,siz_2,siz_3$

答案为 $siz_1*siz_2+siz_1*siz_3+siz_2*siz_3$ 。

如果有大于等于 $2$ 个三度点，那么所有的三度点必须都在环上，所以树上的三度点必须在一条链上，否则无解。我们取该链的两端离得最远的三度点，其链外部分的子树可以互相连，设其分别为 $siz_1,siz_2$ ，答案即是 $siz_1*siz_2$ 。

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int M=1000005;
struct node{
	int v,lst;
}t[M<<1];
int dp[M],du[M],upt,fa[M],tot,head[M];
ll siz[M],dep[M];
vector<ll>vt;
void add(int u,int v){
	t[++tot].v=v;
	t[tot].lst=head[u];
	head[u]=tot;
}
void dfs1(int u,int f){
	int v,flag=0;
	dep[u]=dep[f]+1;
	for(int i=head[u];i;i=t[i].lst)
	{
		v=t[i].v;
		if(v==f) continue;
		dfs1(v,u);
		flag=1;
	}
	if(flag==0) vt.push_back(dep[u]-1);
	return ;
}
void dfs2(int u,int f){
	int v,cntt=0;
	siz[u]=1;
	fa[u]=f;
	for(int i=head[u];i;i=t[i].lst)
	{
		v=t[i].v;
		if(v==f) continue;
		dfs2(v,u);
		siz[u]+=siz[v];
		if(du[u]==3&&dp[v]>=2)
		{
			cout<<0<<"\n";
			exit(0);
		}
		cntt+=dp[v];
	}
	if(cntt==0) dp[u]=(du[u]==3);
	else if(cntt==1) dp[u]=1;
	else if(cntt==2) upt=u;
	else 
	{
		cout<<0<<"\n";
		exit(0);
	}
	return ;
}
int dfs_vt(int u,int f){
	int v,flag=0;
	for(int i=head[u];i;i=t[i].lst)
	{
		v=t[i].v;
		if(v==f||dp[v]==0) continue;
		return dfs_vt(v,u);
	}
	return u;
}
int dfs_upt(int u,int f){
	int v,flag=0;
	if(du[u]==3) return u;
	for(int i=head[u];i;i=t[i].lst)
	{
		v=t[i].v;
		if(v==f||dp[v]==0) continue;
		return dfs_upt(v,u);
	}
	return 0;
}
void solve0(int n){
	cout<<1ll*n*(n-1)/2<<"\n";
	return ;
}
void solve1(int x){
	dfs1(x,0);
	cout<<(vt[0]*vt[1]+vt[0]*vt[2]+vt[1]*vt[2])<<"\n";
	return ;
}
void solve2(int n){
	upt=-1;
	dfs2(1,0);
	ll lsum,rsum;
	int dpt;
	if(upt!=-1)
	{
		for(int i=head[upt];i;i=t[i].lst)
		{
			int v=t[i].v;
			if(dp[v]==1) vt.push_back(v);
		}
		vt[0]=dfs_vt(vt[0],upt);
		vt[1]=dfs_vt(vt[1],upt);
		
		cout<<(siz[vt[0]]-1)*(siz[vt[1]]-1)<<"\n";
	}
	else
	{
		upt=dfs_upt(1,0);
		dpt=dfs_vt(upt,fa[upt]);
		lsum=siz[dpt]-1;
		for(int i=head[upt];i;i=t[i].lst)
		{
			int v=t[i].v;
			if(v==fa[upt]||dp[v]==0) continue;
			rsum=n-1-siz[v];
		}
//		cout<<upt<<" "<<rsum<<"\n";
		cout<<lsum*rsum<<"\n";
	}
	return ;
}
void solve(){
//	freopen("flower.in","r",stdin);
//	freopen("flower.out","w",stdout);
	int n,u;
	cin>>n;
	for(int i=1;i<n;i++)
	{
		cin>>u;
		add(i+1,u);
		add(u,i+1);
		du[i+1]++;
		du[u]++;
	}
	int cnt=0,id;
	for(int i=1;i<=n;i++)
	{
		if(du[i]>3)//有超过三度的点
		{
			cout<<0<<"\n";
			return ;
		}
		if(du[i]==3) cnt++,id=i;
	}
	if(cnt==0) solve0(n);//一条链
	else if(cnt==1) solve1(id);//一个三度点
	else solve2(n);//二个或二个以上三度点
	return ;
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	int T=1;
//	cin>>T;
	while(T--)
	{
		solve();
	}
	return 0;
}
/*
1
12
abcdeffdecba*/

2024牛客OI赛前集训营-普及组（第一场）题解

A 本关考验你求最大值功夫

B 本关考验你求最小值功夫

C 本关考验你判断正误功夫

D 本关考验你数数功夫