2021.牛客暑假多校 第三场 补题

  1. B 题 https://ac.nowcoder.com/acm/contest/11254/B 最小生成树

大意:给定一个n * m 的白色棋盘,现要将白色棋盘染成黑色,每个格子对应一个染色的价值,如果一个 “田字格” 已经有三个格子被染成了黑色,那么可以免费将第四个格子也染成黑色。问将棋盘全部染成黑色的最小花费是多少。

思路:比赛时一直在想贪心,说到底还是对此类题目不够敏感。对于很多问题,我们不妨从图的角度去思考问题,有时或许会达到意想不到的效果。我们把n行 m列看成一个个点的话,那么我们将第 x 行 y 列的格子染色就相当将 x , y 两点进行连通,对于相邻的四个格子 (x1,y1) (x1,y2) (x2,y1) (x2,y2)

如果我们把前三个格子染色,即相当于把 x1,y1,x2 连通,第四个格子是可以不用染色的,也就是说,我们我们使其全连通,没有环,并且使得权重之和最小,显然这就是最小生成树,用krusal 就可以做了。对于纵坐标的点我们可以全部加个偏移量 n 这样就不会出现重复的点了。

代码如下:此题明显是稠密图,最好用 prim 算法。下面是用kruskal 实现的代码

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N=5010;
int g[N][N];
int n,m,a,b,c,d,p,k;
struct node{
	int a,b,c;
	bool operator <(const node &W)const
	{
		return c<W.c;
	}
}e[N*N];
int fa[N*2];
int find(int x)
{
	if(fa[x]!=x)return fa[x]=find(fa[x]);
	return fa[x];
}
int kusal()
{
    //总共有 n+m 个点
	for(int i=1;i<=n+m;i++)fa[i]=i;
	int cnt=0;
	int res=0;
	sort(e+1,e+1+k);
	for(int i=1;i<=k;i++)
	{
		int a=e[i].a,b=e[i].b,c=e[i].c;
		a=find(a),b=find(b);
		if(a!=b)
		{
			cnt++;
			res+=c;
			fa[a]=b;
		}
		if(cnt==n+m-1)break;
	}
	return res;
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin>>n>>m>>a>>b>>c>>d>>p;
	int lst=a;
	for(int i=1;i<=n;i++)	
		for(int j=1;j<=m;j++)
		{
			g[i][j]=(1LL*lst*lst*b+1LL*lst*c+d%p)%p;
			e[++k]={i,j+n,g[i][j]};
			lst=g[i][j];
		}
	int t=kusal();
	cout<<t<<"\n";
	return 0;
}

总结:对于某些问题思考时,往图的方向去思考也是一种思维方式。

  1. C题 https://ac.nowcoder.com/acm/contest/11254/C

大意:有一个空的矩阵,现在需要在矩阵规定的位置填一些非负数,并使其满足要求的某行某列的最大值的情况。确保存在合法的填数方式。要求矩阵数字之和最小,输出最小的数字之和。

思路:类似于数独,在给出的特定的位置填上一些数字,并且满足要求某行某列的最大值是规定的值。通过题目我们就会发现,此题很复杂,模拟都很困难。对于此类 “牵一发而动全身” 的题,我们考虑从图论的角度去思考。对于最坏情况,显然我们对于每行每列要求的最大值都填上一个对应的数。现在要求填的数之和尽可能小,所以我们在满足要求的情况下,尽量去减少填的数字。这时我们会自然而然的想到,对于某行某列规定的最大值相同的情况,我们只需要在它们的交叉位置填上一个数就好了。这样我们就可以减少一个要填的数字,也就是说,对于某些最值相同的行列,我们把行看成一系列点,把列看成一系列点,每当行和列连一条边,我们就可以减少一个要填的数,对于多行和某一列的,填的数也是最多减少一个。换句话说,也就是行列 一 一 对应最大数量就是我们“有效减少 ”的数量。显然这是个最大二分图匹配问题,用匈牙利算法来实现。

总结:对于“牵一发而动全身”的问题,我们考虑从图论的角度思考问题,一步步分析问题。

  1. E 题 https://ac.nowcoder.com/acm/contest/11254/E 数学

大意:t 组测试样例,(1<=t<=1e5), 每次给定一个 n (1<=n<=1e18) 求满足以下条件的 (x,y) 的对数, 1<=x<=y<=n x 2 + y 2 x^2+y^2 x2+y2是 x y + 1 xy+1 xy+1 的整数倍。

思路:打表盯着数据看了半天,眼都瞪瞎了,就是找不出规律。但如果只是道规律题,也没有写这个题的总结的必要了,关键是这个题的分析方式,很巧妙。对于题目给出的条件,我们可以列出 x 2 + y 2 = k ( x y + 1 ) x^2+y^2=k(xy+1) x2+y2=k(xy+1) 其中 k 为正整数,如果我们把 y 当成常数的话,式子可以变形为 x 2 − k y x + y 2 − k = 0 x^2-kyx+y^2-k=0 x2−kyx+y2−k=0 根据韦达定理 有 x 1 + x 2 = k y x_1+x_2=ky x1​+x2​=ky x 1 x 2 = y 2 − k x_1x_2=y^2-k x1​x2​=y2−k

随着 x 1 x_1 x1​​ 的增大 , x 2 x_2 x2​​ 必然是减小 ,极限条件下 x 2 x_2 x2​=0 解得 x 1 = k y x_1=ky x1​=ky 代入原方程 的 k = y 2 k=y^2 k=y2 则 x 1 = y 3 x_1=y^3 x1​=y3

所以 ( y , y 3 ) (y,y^3) (y,y3)​ 为一组合法解 ,不妨记为 ( a , a 3 ) (a,a^3) (a,a3)

b 0 = a b_0=a b0​=a

b 1 = a 3 b_1=a^3 b1​=a3​ 此时代入方程得 k = a 2 k=a^2 k=a2 又因为 y = a 3 y=a^3 y=a3​ 代入我们的另一个根 b 2 = a 2 b 1 − b 0 b_2= a^2b_1-b_0 b2​=a2b1​−b0​ 是大于 b1 的 所以(b1,b2)又是一组解

b 2 = a 2 b 1 − b 0 b_2=a^2b_1-b_0 b2​=a2b1​−b0​ …依次类推

所以我们可以根据递推式,提前把表打好,排好序,用的时候二分查找就好了。

代码如下:

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const LL N=1e18+10;
LL a[3000010],cnt;
LL mx=1e6;
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	for(LL i=2;i<=mx;i++)
	{
		LL lt=0,nw=i,bk;
		while(1)
		{
			if(nw>(N+lt)/(i*i))break;
			bk=nw;
			nw=i*i*nw-lt;lt=bk;
			a[++cnt]=nw;
		}
	}
	sort(a+1,a+1+cnt);
	int _;
	cin>>_;
	while(_--)
	{
		LL n;
		cin>>n;
		int ans=upper_bound(a+1,a+1+cnt,n)-a;
		cout<<ans<<"\n";
	}
	return 0;
}

总结:重点在于此题的分析方式,根据单调性找到边界位置的解,然后反推回去。

  1. F 题 https://ac.nowcoder.com/acm/contest/11254/F 模拟题,dfs 爆搜

大意:先要从 1~13中选出 n 个数字,(1<=n<=4),每个数字可以多次用,可以将四个数字任意方式排序并任意插入加减乘除运算法,使得表达式的结果等于 m,(1<=m<=1e9)。但是在这四个数字加上若干运算符的结果等于 m 的集合中,必须每一个表达式运算过程出现小数才算一组合法解,求和合法解得个数, 并按字典序从小到大输出每组合法解。

思路:n<=4 直接爆搜就完事了。但是题目有“合法解”的要求,所以我们先确定 n 个数字,然后在插入符号,判断是不是合法解。为了好写,我们插入符号的爆搜中返回值,分三种情况就好了,无解返回 0,小数解返回1,整数解返回 2, 将每次返回值进行或运算,显然只有当最终结果为 1 的时候才是一组合法解。

  1. J 题 https://ac.nowcoder.com/acm/contest/11254/J 思维题

大意:有 n 个点的无向完全图,每条边有都有黑白其中一种颜色,现要找到 (a,b,c)三边,满足三边颜色相同,且 a<b<c 的三角形的个数。(n<=8000), 由于数据很多,采用给出的随机生成数据随机生成。

思路:显然暴力枚举是不行的,肯定超时。所以正难则反,我们考虑同色三角形的个数不好考虑,显然我们可以考虑异色三角形的个数。因为就两种颜色,所以异色三角形也就两种组色方式,(黑黑白)(黑白白),抓住共同点,其中必能引出黑白两种颜色的边,对于另外一条边,无论是黑还是白必定都会造成剩下两点的其中一点也是异色边。只要有一个点引出两条异色边那么必定能构成异色三角形,但是另外一个点也是这样的点,所以我们会重复,要除以2.

代码如下:

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
namespace GenHelper
{
    unsigned z1,z2,z3,z4,b,u;
    unsigned get()
    {
        b=((z1<<6)^z1)>>13;
        z1=((z1&4294967294U)<<18)^b;
        b=((z2<<2)^z2)>>27;
        z2=((z2&4294967288U)<<2)^b;
        b=((z3<<13)^z3)>>21;
        z3=((z3&4294967280U)<<7)^b;
        b=((z4<<3)^z4)>>12;
        z4=((z4&4294967168U)<<13)^b;
        return (z1^z2^z3^z4);
    }
    bool read() {
      while (!u) u = get();
      bool res = u & 1;
      u >>= 1; return res;
    }
    void srand(int x)
    {
        z1=x;
        z2=(~x)^0x233333333U;
        z3=x^0x1234598766U;
        z4=(~x)+51;
      	u = 0;
    }
}
using namespace GenHelper;
bool edge[8005][8005];
int cnt[80005][2];
int main() {
  int n, seed;
  cin >> n >> seed;
  srand(seed);
  for (int i = 0; i < n; i++)
    	for (int j = i + 1; j < n; j++)
        	edge[j][i] = edge[i][j] = read();


   for(int i=0;i<n;i++)
   		for(int j=i+1;j<n;j++)
   		{
   			bool x=edge[i][j];
   			cnt[i][x]++;
   			cnt[j][x]++;
   		}

   	LL sum=0;
   	for(int i=0;i<n;i++)
   			sum+=(LL)cnt[i][0]*cnt[i][1];

   	cout<<1LL*n*(n-1)*(n-2)/6-sum/2<<"\n";

 	return 0;
}

总结:正难则反,这种思维方式很重要。

上一篇:在canvas中绘制箭头


下一篇:miou