2021牛客暑期多校训练营3,签到题BEFJ

举报
小哈里 发表于 2022/05/10 22:58:19 2022/05/10
【摘要】 题号 标题 已通过代码 通过率 团队的状态 A Guess and lies 点击查看 33/437 未通过 B Black and white 点击查看 785/5177 未通过 (最小生成树) C M...

题号 标题 已通过代码 通过率 团队的状态
A Guess and lies 点击查看 33/437 未通过
B Black and white 点击查看 785/5177 未通过 (最小生成树)
C Minimum grid 点击查看 291/759 未通过
D Count 点击查看 13/57 未通过
E Math 点击查看 1030/3674 通过 (数学,预处理)
F 24dian 点击查看 492/1301 未通过 (大模拟,dfs)
G Yu Ling(Ling YueZheng) and Colorful Tree 点击查看 51/193 未通过
H Ling Qiu, Luna and Triple Backpack 点击查看 5/30 未通过
I Kuriyama Mirai and Exclusive Or 点击查看 131/556 未通过
J Counting Triangles 点击查看 1362/4223 通过 (性质,结论)

B Black and white

题意:

  • 给出一个n*m的棋盘,每个点有被染成黑色的代价cij, 对于任意两行两列的四个相交方格,如果其中三个是黑色方格,那么可以零成本地将第四个方格染成黑色。求染黑棋盘的最低成本。
  • 由于格子的数量很多,权重由公式产生,A0 = a,A(i+1) = (Ai * Ai * b + Ai * c + d)% p,其中A(m*(i-1)+j)是第i行和第j列的网格的成本c(i, j)。

思路:

  • 对于⼀个位置(i, j) ,如果该格⼦是⿊⾊,我们连⼀条ai 到bj 的边。操作不改变连通性,由此容易证明,可以全 部染⿊等价于初始联通。求解最⼩⽣成树即可。复杂度为 O(n^2)。
  • 对于 n*m 的矩阵,需要 n+m-1 格子涂色,分别是每行对应一个格子,每列对应一个格子,减去重复的一个。
  • 考虑任意两行两列所成的四个坐标,若已经出现了三个坐标,则第四个就不需要了。
  • 考虑如何判断新加入点是否需要,即它不会由之前的坐标推出来。根据题目一行一点,一列一点,不如将行列看成点,现将两行点和两列点放在同一个连通块里,第四个坐标放进来,行坐标和列坐标连通,即不需要,用并查集维护,再根据边权从小到大去跑最小生成树即可。
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int maxn = 1e5+10;

int fa[maxn+10];
void init(int n){for(int i = 1; i <= n; i++)fa[i]=i;}
int find(int x){return x==fa[x]?x:fa[x]=find(fa[x]);}
void merge(int x, int y){x=find(x);y=find(y);if(x!=y)fa[x]=y;}

vector<pair<int,int> >G[maxn];

int main(){
	int n, m;  cin>>n>>m;
	LL a, b, c, d, p;  cin>>a>>b>>c>>d>>p;
	for(int i = 1; i <= n; i++){
		for(int j = 1; j <= m; j++){
			a = (a*a*b+a*c+d)%p;
			G[a].push_back(make_pair(i,j+n));//第i行和第j列有一条w=a的边
		}
	}
	LL ans = 0, cc = 0;  init(n+m);
	for(int i = 0; i <= p; i++){//从小到大枚举权值
		for(auto u : G[i]){
			int x = find(u.first), y = find(u.second);
			if(x != y){
				ans += i;
				merge(x,y);
			}
		}
		if(cc==n+m-1)break;
	}
	cout<<ans<<"\n";
	return 0;
}


  
 
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36

E Math

题意:

  • 给出一个n,计算有多少对正整数(x,y),使得xy+1|x^2+y^2, 1<=x,y<=n

思路:
在这里插入图片描述

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int maxn = 5e6+10;
const LL inf = 1e18;
LL a[maxn], cnt;
int main(){
	a[cnt++] = 1;
	for(LL k = 2; k*k*k<=inf; k++){
		LL x = k, y = k*k*k;
		a[cnt++] = y;
		while(y <= (inf+x)/k/k){
			x = k*k*y-x;
			swap(x,y);
			a[cnt++] = y;
		}
	}
	sort(a, a+cnt);
	
	int T;  cin>>T;
	while(T--){
		LL n;  cin>>n;
		cout<<upper_bound(a,a+cnt,n)-a<<"\n";
	}
	return 0;
}


  
 
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27

F 24dian

题意:

  • 给出n张牌,求凑出m点的方案数,输出方案。(每张牌为1-13, 过程需要有分数)

思路:

  • 按照题⾯模拟即可。暴⼒枚举第⼀次或最后⼀次的两数均可
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int maxn = 5e5+10;

int n, m, ans, as[maxn][5];
int ok; double a[5];
bool chk(double x){x-=(int)x;return x>1e-6&&x<1-1e-6;}
void dfs1(int cur, int flag){//枚举所有可行方案
	if(ok==3)return ;
	if(cur==n){
		if(abs(a[1]-m)<1e-6){
			if(flag)ok = 1;
			else ok = 3;
		}
		return ;
	}
	double A[5];
	for(int i = 0; i <= 4; i++)A[i]=a[i];
	for(int i = 1; i <= n-cur+1; i++){
		for(int j = 1; j <= n-cur+1; j++){
			if(i!=j){
				for(int k = 1; k <= 4; k++){
					int w = flag;
					if(k==1)a[i]+=a[j];
					if(k==2)a[i]-=a[j];
					if(k==3)a[i]*=a[j];
					if(k==4){
						a[i]/=a[j];
						if(chk(a[i]))w=1;
					}
					a[j] = 9e9;
					sort(a+1,a+n+2-cur);
					a[n+1-cur] = 0;
					dfs1(cur+1, w);
					memcpy(a, A, sizeof(a));
				}
			}
		}
	}
	
}
void dfs(int cur, int k){//枚举所有排列
	if(cur>n){
		ok = 0;
		dfs1(1,0);
		if(ok==1){
			ans++;
			for(int i=1; i <= 4; i++)as[ans][i]=a[i];
		}
	}else{
		for(int i = k; i <= 13; i++){
			a[cur] = i;
			dfs(cur+1, i);
		}
	}
}

int main(){
	cin>>n>>m;
	if(n<3){cout<<"0\n"; return 0;}
	dfs(1,1);
	printf("%d\n",ans);
	for(int i = 1; i <= ans; i++){
		for(int j = 1; j <= n; j++){
			printf("%d",as[i][j]);
			if(j!=n)putchar(' ');
		}
		cout<<"\n";
	}
	return 0;
}


  
 
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52
  • 53
  • 54
  • 55
  • 56
  • 57
  • 58
  • 59
  • 60
  • 61
  • 62
  • 63
  • 64
  • 65
  • 66
  • 67
  • 68
  • 69
  • 70
  • 71
  • 72
  • 73

J Counting Triangles

题意:

  • 按照给出的代码生成一张n个点的完全图,边分为0或1两种颜色,求图中有多少个满足非等边等腰且存在边颜色相同的三角形。

思路:

  • 注意到⼀个神奇的性质:每个三角形要么同色,要么有两边同色另⼀边异色。前者没有异色角,而对于后者,三角形有恰有两个异色角。
  • 因此异⾊⻆数/2 即为不符合条件的三⻆个数。⽤总数减去即可。复杂度 O(n^2)。
#include<bits/stdc++.h>
using namespace std;

//数据生成
namespace GenHelper{
    unsigned z1,z2,z3,z4,bb,u;
    unsigned get()
    {
        bb=((z1<<6)^z1)>>13;
        z1=((z1&4294967294U)<<18)^bb;
        bb=((z2<<2)^z2)>>27;
        z2=((z2&4294967288U)<<2)^bb;
        bb=((z3<<13)^z3)>>21;
        z3=((z3&4294967280U)<<7)^bb;
        bb=((z4<<3)^z4)>>12;
        z4=((z4&4294967168U)<<13)^bb;
        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];

//题目
typedef long long LL;
LL d[8005];

int main() {
	//int n, seed;
	LL n; int 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++){
			d[i] += edge[i][j];
			d[j] += edge[i][j];
		}
	}
	LL ans = 0;
	for(int i = 0; i < n; i++)
		ans += d[i]*(n-d[i]-1);
	cout<<n*(n-1)*(n-2)/6-ans/2<<"\n";
 	return 0;
}



  
 
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52
  • 53
  • 54
  • 55
  • 56
  • 57
  • 58
  • 59
  • 60
  • 61
  • 62

文章来源: gwj1314.blog.csdn.net,作者:小哈里,版权归原作者所有,如需转载,请联系作者。

原文链接:gwj1314.blog.csdn.net/article/details/119116371

【版权声明】本文为华为云社区用户转载文章,如果您发现本社区中有涉嫌抄袭的内容,欢迎发送邮件进行举报,并提供相关证据,一经查实,本社区将立刻删除涉嫌侵权内容,举报邮箱: cloudbbs@huaweicloud.com
  • 点赞
  • 收藏
  • 关注作者

评论(0

0/1000
抱歉,系统识别当前为高风险访问,暂不支持该操作

全部回复

上滑加载中

设置昵称

在此一键设置昵称,即可参与社区互动!

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。