牛客练习赛99题解

牛客练习赛99 A 越狱 原题链接 思路

若选取 X X X为数组中位数+1
min ⁡ ( ∑ i = 1 n [ a i < x ] , ∑ i = 1 n [ a i > x ] ) \min(\sum\limits_{i=1}^{n}[a_ix]) min(i=1∑n​[ai​<x],i=1∑n​[ai​>x])取最大值， 为数组长度的 1 / 2 1/2 1/2

算法标签

数学

代码

#include
#define int long long
#define rep(i, a, b) for(int i=a;ib;--i)
using namespace std;
const int N = 100005;
int a[N];
inline int read(){
   int s=0,w=1;
   char ch=getchar();
   while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
   while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
   return s*w;
}
void put(int x) {
    if(x<0) putchar('-'),x=-x;
    if(x>=10) put(x/10);
    putchar(x%10^48);
}
signed main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	int n=read();
	rep(i, 0, n){
	    a[i]=read();
	}
	sort(a, a+n);
	put(n/2);
	printf(" ");
	put(a[(n)/2-1]+1);
	return 0;
}

B 物流 原题链接 思路

设 A A A 到 C C C x x x吨，则花费 ( c 1 + c 4 − c 2 − c 3 ) x + k (c1+c4−c2−c3)x+k (c1+c4−c2−c3)x+k 的代价（k 是常数）。再结合 m a x ⁡ ( 0 , a − d ) ≤ x ≤ m i n ⁡ ( a , c ) max⁡(0,a−d)≤x≤min⁡(a,c) max⁡(0,a−d)≤x≤min⁡(a,c)，直接判断 x x x 前系数正负计算即可。

算法标签

数学 模拟

代码

#include
#define int long long
#define rep(i, a, b) for(int i=a;ib;--i)
using namespace std;
const int N = 100005;
int a[N];
inline int read(){
   int s=0,w=1;
   char ch=getchar();
   while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
   while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
   return s*w;
}
void put(int x) {
    if(x<0) putchar('-'),x=-x;
    if(x>=10) put(x/10);
    putchar(x%10^48);
}
signed main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	int t=read();
	while(t--){
	    int a=read(),b=read(),c=read(),d=read(),c1=read(),c2=read(),c3=read(),c4=read();
	    int t=c1+c4-c2-c3;
	    int r=min(a,c);
	    int l=max(0ll,a-d);
	    int ans=0;
        if(t>=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);
        put(ans);
        puts("");
	}
	return 0;
}

C 数的和与积 原题链接 思路

由题意， 需要构造等式
该等式左边为部分数字乘积
右边为所有数字累加后减左边乘积所需数
显然 2 和 4 无解。
考率到 ∑ i = 1 n i = n ( n + 1 ) 2 \sum\limits^{n}_{i=1} i=\frac{n(n+1)}{2} i=1∑n​i=2n(n+1)​ 。这样我们就可以证明当 n n n为奇数时 1 × n − 1 2 × ( n − 1 ) = ∑ i = 1 n i − 1 − n − 1 2 − ( n − 1 ) 1\times\frac{n-1}{2}\times (n-1)=\sum\limits^{n}_{i=1} i-1-\frac{n-1}{2}- (n-1) 1×2n−1​×(n−1)=i=1∑n​i−1−2n−1​−(n−1)
而当 n 为偶数时 1 × ( n − 2 ) 2 × n = ∑ i = 1 n i − 1 − ( n − 2 ) 2 − n 1\times \frac{(n-2)}{2}\times n=\sum\limits^{n}_{i=1} i-1-\frac{(n-2)}{2}-n 1×2(n−2)​×n=i=1∑n​i−1−2(n−2)​−n​。这样就找到了一个构造方案。

算法标签

数学 构造

代码

#include
#define int long long
#define rep(i, a, b) for(int i=a;ib;--i)
using namespace std;
const int N = 100005;
int a[N];
inline int read(){
   int s=0,w=1;
   char ch=getchar();
   while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
   while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
   return s*w;
}
void put(int x) {
    if(x<0) putchar('-'),x=-x;
    if(x>=10) put(x/10);
    putchar(x%10^48);
}
signed main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	int t=read();
	while(t--){
	    int n=read();
	    if(n==2||n==4){
	        printf("-1\n");
	    }
	    else if(n==3){
	        printf("1\n3\n");
	    }
	    else if(n&1){
	        printf("3\n1 %lld %lld\n", n-1, (n-1)/2);
	    }
	    else{
	        printf("3\n1 %lld %lld\n",n, (n-2)/2);
	    }
	}
	return 0;
}

D 礼物 原题链接 思路

考虑到 L C A ( u , v ) = w LCA(u,v)=w LCA(u,v)=w 当且仅当 u u u和 v v v 在 w w w的不同儿子的子树中或者其中至少一个是 w w w 且两个节点都在 w w w 的子树中。
于是我们可以很简单求出一个节点作为根的时候错解的运行时间。
考虑换根 dp。设原来的根和待换的根分别是 x , y x,y x,y。由于 L C A ( u , v ) = w LCA(u,v)=w LCA(u,v)=w 时 u , v u,v u,v 只会是 w w w子树中的节点，所以改变了 L C A LCA LCA 的点对它们原来的 L C A LCA LCA只会是 x x x 或 y y y。统计一下在 y y y 子树中的节点和其他节点形成的 LCA 为 x x x 的点对，将这部分对答案的贡献重新计算就完成了换根。

L C A ( i , j ) LCA(i,j) LCA(i,j)指编号为 i i i 和编号为 j j j 的节点的最近公共祖先的编号。 算法标签

数 dfs 构造

代码

#include
#define int long long
#define rep(i, a, b) for(int i=a;ib;--i)
using namespace std;
const int N = 1000005;
//dp[N] 存储错解运行时间 
//f[N] 存储当前节点的父节点
// siz[N] 存储子孙节点数          
int f[N], siz[N], dp[N];
vector ve[N];
int n,u,v, p;
inline int read(){
  int s=0,w=1;
  char ch=getchar();
  while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
  while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
  return s*w;
}
void put(int x) {
    if(x<0) putchar('-'),x=-x;
    if(x>=10) put(x/10);
    putchar(x%10^48);
}
void dfs1(int now, int fa){
    siz[now]=1;
    f[now]=fa;
    rep(i, 0, ve[now].size()){
        int y=ve[now][i];
        if(y!=f[now]){
            dfs1(y, now);
            siz[now]+=siz[y];
        }
    }
    rep(i, 0, ve[now].size()){
        int y=ve[now][i];
        if(y!=f[now]){
            dp[1]+=now*siz[y]*(siz[now]-siz[y]);
        }
    }
    dp[1]+=now*siz[now];
}
void dfs2(int now){
    rep(i, 0, ve[now].size()){
        int y=ve[now][i];
        if(y!=f[now]){
            int t=siz[y];
            // 换根
            siz[now]=n-siz[y];
            siz[y]=n;
            dp[y]=dp[now]+y*t*(n-t)*2-now*t*(n-t)*2;
            dfs2(y);
            siz[y]=t;
            siz[now]=n;
        }
    }
}
signed main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	n=read();
	rep(i,1,n){
	   u=read(), v=read();
	   ve[u].push_back(v);
	   ve[v].push_back(u);
	}
	dfs1(1, 0);
	dfs2(1);
	rep(i, 1, n+1){
	    if(dp[i]>dp[p]){
	        p=i;
	    }
	}
	printf("%lld %lld\n", p, dp[p]);
	return 0;
}

E NP-Easy问题 原题链接 思路

考虑 G G G 的反图。如果反图中存在 K 3 K_3 K3​ 或者 2 K 2 2K_2 2K2​作为子图的话，那么显然对于 K 3 K_3 K3​上的 3 个顶点，我们在原图上给它们一样的颜色；对于 2 K 2 2K_2 2K2​上的顶点，每一对在原图中染上相同的颜色，这样我们就已经找到了一个所用颜色小于等于 n−2 的染色方法。而这两种子图都不存在的显然是菊花图。
而当 G 的反图是菊花图时， K n − 1 K_{n-1} Kn−1​显然是 G 的子图。于是题目就转化为判断 G 中是否存在 K n K_n Kn​​和 K n − 1 K_{n-1} Kn−1​

算法标签

图论 贪心

代码

#include
#define int long long
#define rep(i, a, b) for(int i=a;ib;--i)
using namespace std;
const int N = 1000005;
int cnt[N];
inline int read(){
  int s=0,w=1;
  char ch=getchar();
  while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
  while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
  return s*w;
}
void put(int x) {
    if(x<0) putchar('-'),x=-x;
    if(x>=10) put(x/10);
    putchar(x%10^48);
}
signed main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	int t=read();
	while(t--){
	    int n=read(), m=read();
	    rep(i, 1, m+1){
	        int u=read(), v=read();
	        // 非完全图即不存在Kn
	        // m>=(n-1)*(n-2)/2 满足Kn-1存在条件
	        if(m!=n*(n-1)/2&&m>=(n-1)*(n-2)/2){
	            cnt[u]++;
	            cnt[v]++;
	        } 
	    }
	    // 完全图即存在Kn
	    if(m==n*(n-1)/2){
	        puts("0");
	    }
	    // 不可能存在Kn-1
	    else if(m<(n-1)*(n-2)/2){
	        puts("-2");
	    }
	    // 不存在Kn但满足Kn-1存在条件（可能存在Kn-1）
	    else{
	        int num=n*(n-1)/2-m;
	        int flag=0;
	        rep(i, 1, n+1){
	        	// 存在Kn-1
	            if(num==n-1-cnt[i]){
	                flag=1;
	            }
	        }
	        // cnt数组恢复 便于下次使用
	        rep(i, 1, n+1){
	            cnt[i]=0;
	        }
	        if(flag){
	            puts("-1");
	        }
	        else{
	            puts("-2");
	        }
	    }
	}
	return 0;
}

F 相等距离 原题链接 思路

2 到 5 的答案可以爆搜或手推得到。
这里有个显然的结论是一个点到另外两点的距离相等当且仅当这个点在那两点的垂直平分线上。于是我们就用选中的点的垂直平分线覆盖整个网格图即可。
由于用平行于网格图的线覆盖效率比较低，考虑用对角线覆盖。但是将一个对角线上的点全部选中后会存在两个点覆盖不到。
这时可以去掉一部分点，用剩下来的点构造这个方案。

算法标签

图论 构造

代码

#include
#define int long long
#define rep(i, a, b) for(int i=a;ib;--i)
using namespace std;
const int N = 1000005;
inline int read(){
  int s=0,w=1;
  char ch=getchar();
  while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
  while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
  return s*w;
}
void put(int x) {
    if(x<0) putchar('-'),x=-x;
    if(x>=10) put(x/10);
    putchar(x%10^48);
}
signed main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	int n=read();
    if(n==2||n==3){
        printf("4\n1 1\n1 %lld\n%lld 1\n%lld %lld\n", n, n, n, n);
    }
    else if(n==4||n==5){
        printf("5\n3 1\n2 2\n1 3\n4 1\n4 4\n");
    }
    else{
        printf("%lld\n1 1\n", n);
        rep(i, 3, n){
            printf("%lld %lld\n", i, i);
        }
        printf("%lld %lld\n%lld %lld\n", n-1, n-3, n-3, n-1);
        
    }
	return 0;
}

主要参考题解
原创不易
转载请标明出处
如果对你有所帮助 别忘啦点赞支持哈