牛客练习赛 99 题解

码量很小，和之前我出的小白月赛有得一拼。

出锅了，我是***。

A.越狱

显然存在一个 $x$ 使得 $\sum\limits_{i=1}^{n} [x>a_i]+\sum\limits_{i=1}^{n} [x<a_i]=n$ ，故 $\min(\sum\limits_{i=1}^{n} [x>a_i],\sum\limits_{i=1}^{n} [x<a_i])\le \lfloor \frac{n}{2}\rfloor$ 。于是我们取 $x=a_{\lfloor\frac{n}{2}\rfloor}+1$ 即可。此时答案显然取到最优。

#include<bits/stdc++.h>
#define N 1000005 
using namespace std;
int n,a[N];
int main(){
	cin>>n;
	for(int i=1;i<=n;i++)cin>>a[i];
	cout<<n/2<<' '<<a[n/2]+1<<endl;
}

B.物流

设 A 到 C $x$ 吨，则花费 $(c_{1} + c_{4} - c_{2} - c_{3}) x + k$ 的代价（ $k$ 是常数）。再结合 $\max(0,a-d) \le x\le \min(a,c)$ ，直接判断 $x$ 前系数正负计算即可。

#include<bits/stdc++.h>
#define int long long
using namespace std;
int T,a,b,c,d,c1,c2,c3,c4,tmp,l,r,ans;
signed main() {
	cin>>T;
	while(T--){
		cin>>a>>b>>c>>d>>c1>>c2>>c3>>c4;
		tmp=c1+c4-c2-c3;
		r=min(a,c);
		l=max(0ll,a-d);
		if(tmp>=0)ans=c1*l+c2*(a-l)+c3*(c-l)+c4*(d-a+l);
		else ans=ans=c1*r+c2*(a-r)+c3*(c-r)+c4*(d-a+r);
		cout<<ans<<endl;
		
	}
}

C.数的和与积

显然 $2$ 和 $4$ 无解。

考率到 $\sum\limits^{n}_{i=1} i=\frac{n(n+1)}{2}$ 。这样我们就可以证明当 $n$ 为奇数时 $1\times \frac{n-1}{2}\times (n-1)=\sum\limits^{n}_{i=1} i-1-\frac{n-1}{2}- (n-1)$ 而当 $n$ 为偶数时 $1\times \frac{(n-2)}{2}\times n=\sum\limits^{n}_{i=1} i-1-\frac{(n-2)}{2}-n$ 。这样就找到了一个构造方案。

具体思考方法可以通过暴力看一些小的情况。

#include<bits/stdc++.h>
#define N 1000005
#define int long long
using namespace std;
int T,n;
signed main() {
	cin>>T;
	while(T--){
		cin>>n;
		if(n==2||n==4)puts("-1");
		else if(n==3)puts("1\n3");
		else if(n&1)cout<<3<<endl<<1<<' '<<(n-1)/2<<' '<<n-1<<endl;
		else cout<<3<<endl<<1<<' '<<(n-2)/2<<' '<<n<<endl;
	}
}

D.礼物

考虑到 $\text{LCA}(u,v)=w$ 当且仅当 $u$ 和 $v$ 在 $w$ 的不同儿子的子树中或者其中至少一个是 $w$ 且两个节点都在 $w$ 的子树中。

于是我们可以很简单求出一个节点作为根的时候错解的运行时间。

考虑换根 dp。设原来的根和待换的根分别是 $x, y$ 。由于 $\text{LCA}(u,v)=w$ 时 $u, v$ 只会是 $w$ 子树中的节点，所以改变了 LCA 的点对它们原来的 LCA 只会是 $x$ 或 $y$ 。统计一下在 $y$ 子树中的节点和其他节点形成的 LCA 为 $x$ 的点对，将这部分对答案的贡献重新计算就完成了换根。

#include<bits/stdc++.h>
#define N 1000005
#define int long long
using namespace std;
int n,f[N],siz[N],p,u,v;
vector<int>ve[N];
long long dp[N];
void dfs1(int now,int fa){
	siz[now]=1;
	f[now]=fa;
	for(int i=0;i<ve[now].size();i++){
		int y=ve[now][i];
		if(y==f[now])continue;
		dfs1(y,now);
		siz[now]+=siz[y]; 
	}
	for(int i=0;i<ve[now].size();i++){
		int y=ve[now][i];
		if(y==f[now])continue;
		dp[1]+=(long long)now*siz[y]*(siz[now]-siz[y]);
	}
	dp[1]+=(long long)now*siz[now];
}
void dfs2(int now){
	for(int i=0;i<ve[now].size();i++){
		int y=ve[now][i];
		if(y==f[now])continue;
		int tmp=siz[y];
		siz[now]=n-siz[y];
		siz[y]=n;
		dp[y]=dp[now]+y*tmp*(n-tmp)*2-now*tmp*(n-tmp)*2;
		dfs2(y);
		siz[y]=tmp,siz[now]=n;
	}
}
inline int read(){
    int x=0;
    char ch=getchar();
    while(ch<'0'||ch>'9')ch=getchar();
    while(ch>='0'&&ch<='9'){
        x=x*10+ch-'0';
        ch=getchar();
    }
    return x;
}
signed main() {
	n=read();
	for(int i=1;i<n;i++){
		u=read(),v=read();
		ve[u].push_back(v);
		ve[v].push_back(u);
	}
	dfs1(1,0);
	dfs2(1);
	for(int i=1;i<=n;i++)if(dp[i]>dp[p])p=i;
	cout<<p<<' '<<dp[p]<<endl;
}

E.NP-Easy问题

考虑 $G$ 的反图。如果反图中存在 $K_{3}$ 或者 $2 K_{2}$ 作为子图的话，那么显然对于 $K_{3}$ 上的 $3$ 个顶点，我们在原图上给它们一样的颜色；对于 $2 K_{2}$ 上的顶点，每一对在原图中染上相同的颜色，这样我们就已经找到了一个所用颜色小于等于 $n - 2$ 的染色方法。而这两种子图都不存在的显然是菊花图。

而当 $G$ 的反图是菊花图时， $K_{n-1}$ 显然是 $G$ 的子图。于是题目就转化为判断 $G$ 中是否存在 $K_{n}$ 和 $K_{n-1}$ 。

#include<bits/stdc++.h>
#define N 1000005
#define int long long
using namespace std;
int T,n,m,cnt[N],u,v,num,flag;
signed main() {
    scanf("%d",&T);
    while(T--){
        scanf("%d%d",&n,&m);
        
        for(int i=1;i<=m;i++){
            scanf("%d%d",&u,&v);
            if(m!=n*(n-1)/2&&m>=(n-1)*(n-2)/2)cnt[u]++,cnt[v]++;
        }
        if(m==n*(n-1)/2)puts("0");
        else if(m<(n-1)*(n-2)/2)puts("-2");
        else{
            num=n*(n-1)/2-m;
            flag=0;
            for(int i=1;i<=n;i++)if(num==n-1-cnt[i])flag=1;
			for(int i=1;i<=n;i++)cnt[i]=0;
            if(flag)puts("-1");
            else puts("-2");
        }
    }
}

F.相等距离

$2$ 到 $5$ 的答案可以爆搜或手玩得到。

这里有个显然的结论是一个点到另外两点的距离相等当且仅当这个点在那两点的垂直平分线上。于是我们就用选中的点的垂直平分线覆盖整个网格图即可。

由于用平行于网格图的线覆盖效率比较低，考虑用对角线覆盖。但是将一个对角线上的点全部选中后会存在两个点覆盖不到。

这时可以去掉一部分点，用剩下来的点构造这个方案。

#include<bits/stdc++.h>
using namespace std;
int n;
int main(){
	cin>>n;
	if(n==2||n==3){
		cout<<4<<endl;
		cout<<1<<' '<<1<<endl;
		cout<<1<<' '<<n<<endl;
		cout<<n<<' '<<1<<endl;
		cout<<n<<' '<<n<<endl;
	}
	else if(n==4||n==5){
		cout<<5<<endl;
		cout<<3<<' '<<1<<endl;
		cout<<2<<' '<<2<<endl;
		cout<<1<<' '<<3<<endl;
		cout<<4<<' '<<2<<endl;
		cout<<4<<' '<<4<<endl; 
	}
	else{
		cout<<n<<endl;
		cout<<1<<' '<<1<<endl;
		for(int i=3;i<n;i++)cout<<i<<' '<<i<<endl;
		cout<<n-1<<' '<<n-3<<endl;
		cout<<n-3<<' '<<n-1<<endl;
	}
}
/*
画个6*6的图理解一下:
AAAAAA
AAAABA
AAABAA
AABAAA
AAAAAA
BAAAAA 
这样会发现有如下标上*的点没有覆盖。 
AAA***
AAAA**
AAAAA*
AAAAAA
*AAAAA
**AAAA 
对于更大的情况，容易证明没有覆盖的点还是这些。 
AAAAAA
AABABA
AAABAA
AABABA
AAAAAA
BAAAAA 
上图就是构造方案。 
容易发现之前没有覆盖到的点都已经倍覆盖了。 
 
*/