欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

武汉工程大学第一届程序设计女生赛(牛客contest 4746)解题报告 Apare_xzc

程序员文章站 2022-05-14 08:13:52
...

武汉工程大学第一届程序设计女生赛解题报告

xzc 2020.3.8


武汉工程大学第一届程序设计女生赛(牛客contest 4746)解题报告 Apare_xzc


比赛链接:武汉工程大学第一届程序设计女生赛


A. Multiplication (101/861)

武汉工程大学第一届程序设计女生赛(牛客contest 4746)解题报告 Apare_xzc
武汉工程大学第一届程序设计女生赛(牛客contest 4746)解题报告 Apare_xzc

分析:

         问x平方几次后就会>=n, 按题意模拟即可。签到题。

代码:

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
int main()
{
	int T;
	LL k,n;
	cin>>T;
	while(T--)
	{
		cin>>n>>k;
		int ans = 0;
		while(k<n)
		{
			k = k*k;
			++ans;
		}
		cout<<ans<<endl;
	} 
	return 0;	
} 

B. Spread (28/520)

武汉工程大学第一届程序设计女生赛(牛客contest 4746)解题报告 Apare_xzc
武汉工程大学第一届程序设计女生赛(牛客contest 4746)解题报告 Apare_xzc

样例输入:

1
5 2 2
1 3
1 2
4 5

样例输出:

3

分析:

        n个人中有m个人确定被感染。他们之中有t对接触。求所有存在感染风险的人数(包括那m个)。
        用并查集合并所有直接和间接接触过的人,把n个人分成若干的集合。对每个集合的总人数进行计数。m个已经确认感染的人所在集合的总人数即为答案。注意不要多算。

代码:

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 2e5+10;
int pre[N];
void init(int n) //初始化 
{
	for(int i=0;i<=n;++i) pre[i] = i;
}
int Find(int x)
{
	return x==pre[x]?x:pre[x]=Find(pre[x]);
}
void join(int x,int y)
{
	if(x>y) swap(x,y);
	int fx = Find(x), fy = Find(y);
	if(fx!=fy) pre[fy] = fx;
}
int main()
{
	int T,n,m,t,x,y,fa;
	scanf("%d",&T);
	while(T--)
	{
		scanf("%d%d%d",&n,&m,&t);
		vector<int> v;
		for(int i=1;i<=m;++i)
		{
			scanf("%d",&x);
			v.push_back(x);
		}
		init(n);
		while(t--)
		{
			scanf("%d%d",&x,&y);
			join(x,y);
		}
		int ans = 0;
		unordered_map<int,int> cnt; //记录集合人数 
		unordered_map<int,int> mp; //记录集合是否有被确诊的人 
		for(int i=1;i<=n;++i)
			++cnt[Find(i)]; 
		for(int i=0;i<m;++i)
			mp[Find(v[i])] = 1;
		for(auto xx:mp)
			ans += cnt[xx.first];
		printf("%d\n",ans);
	}
	
	return 0;	
} 

C. Transport (24/103)

武汉工程大学第一届程序设计女生赛(牛客contest 4746)解题报告 Apare_xzc
武汉工程大学第一届程序设计女生赛(牛客contest 4746)解题报告 Apare_xzc

样例输入:

1
3 3
...
.**
...
1 3 1 1 3 3

样例输出:

6

分析:

        简单bfs, n行m列的矩阵,星号不能走,点号可以走,问从指挥部到小区再到医院的最短路成。若不可达,输出-1。
         我们可以从小区出发,bfs, 记录第一次到指挥部和第一次到医院的步数,相加即为答案。

代码:

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 1005;
char a[N][N];
bool vis[N][N];
int n,m; 
struct Node{
	int x,y,step;
	Node(){}
	Node(int xx,int yy,int s):x(xx),y(yy),step(s){}
}node;
int X1,Y1,X2,Y2,X3,Y3;
int dx[] = {1,-1,0,0};
int dy[] = {0,0,1,-1};
bool ok(int x,int y)
{
	return (x>=1&&x<=n&&y>=1&&y<=m&&a[x][y]=='.'&&!vis[x][y]);
}
int bfs()
{
	int ans1 = -1, ans2 = -1;
	for(int i=1;i<=n;++i)
		for(int j=1;j<=m;++j)
			vis[i][j] = false;
	int x,y,step,xx,yy;
	queue<Node> Q;
	Q.push(Node(X2,Y2,0));
	vis[X2][Y2] = 0;
	while(!Q.empty())
	{
		if(ans1!=-1&&ans2!=-1) return ans1+ans2;
		node = Q.front();Q.pop();
		x = node.x, y = node.y, step = node.step;
		for(int i=0;i<4;++i)
		{
			xx = x+dx[i], yy = y+dy[i];
			if(!ok(xx,yy)) continue;
			if(xx==X1&&yy==Y1)
			{
				if(ans1==-1) ans1 = step+1;	
				if(ans2!=-1) return ans1+ans2;
			}	
			else if(xx==X3&&yy==Y3)
			{
				if(ans2==-1) ans2 = step+1;
				if(ans1!=-1) return ans1+ans2;
			}
			vis[xx][yy] = true;
			Q.push(Node(xx,yy,step+1));
		} 
	}
	return -1;
	
}
int main()
{
	int T,step1,step2;
	scanf("%d",&T);
	while(T--)
	{
		scanf("%d%d",&n,&m);
		for(int i=1;i<=n;++i)
			scanf("%s",a[i]+1);
		cin>>X1>>Y1>>X2>>Y2>>X3>>Y3; 
		printf("%d\n",bfs());
	}
	return 0;	
} 

D. OneTrunKill (0/1)

武汉工程大学第一届程序设计女生赛(牛客contest 4746)解题报告 Apare_xzc
武汉工程大学第一届程序设计女生赛(牛客contest 4746)解题报告 Apare_xzc
武汉工程大学第一届程序设计女生赛(牛客contest 4746)解题报告 Apare_xzc

分析:  0/1的大模拟,没做,跳过吧


E. SSR (10/82)

武汉工程大学第一届程序设计女生赛(牛客contest 4746)解题报告 Apare_xzc武汉工程大学第一届程序设计女生赛(牛客contest 4746)解题报告 Apare_xzc

样例输入:

2
2
4

样例输出:

2
2
4

分析:

        恰好一半人抽到SSR的概率。总共的情况为2^n种,我们调出一半人抽SSR的方案数为C(n.n/2) ,概率为C(n,n/2) / 2^n, 注意出发取模要乘以逆元

代码:

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 1e6+10;
const int mod = 1E9+7;
void exgcd(LL a,LL b,LL&d,LL &x,LL&y);
LL fast_pow(LL a,LL b,LL mod);
LL getNi(LL a,LL m);
LL fac[N] = {1},rev[N]; 
void init()
{
	for(int i=1;i<=1000000;++i)
		fac[i] = fac[i-1]*i%mod;
	rev[1000000] = getNi(fac[1000000],mod);
	for(int i=1000000-1;i>=1;--i)
		rev[i] = rev[i+1]*(i+1)%mod;
} 
LL C(int n,int m)
{
	if(n<m) return 0;
	if(m==0||m==n) return 1;
	return fac[n]*rev[m]%mod*rev[n-m]%mod;
}
int main()
{
	init(); 
	int T,n;
	cin>>T;
	while(T--)
	{
		cin>>n;
		int m = n/2;
		LL tot = fast_pow(2ll,n,mod);
		tot = getNi(tot,mod);
		LL up = C(n,m);
		up = up*tot%mod;
		cout<<up<<endl;
	}
	
	return 0;	
}
void exgcd(LL a,LL b,LL&d,LL &x,LL&y){
	if(b==0) {
		d = a; x = 1; y = 0;return;
	}
	exgcd(b,a%b,d,y,x);
	y -= (a/b)*x;
}
LL getNi(LL a,LL m)
{
	LL d,x,y;
	exgcd(a,m,d,x,y);
	return (x%m+m)%m;
}
LL fast_pow(LL a,LL b,LL mod)
{
	if(a==0) return 0;
	LL ans = 1;
	while(b)
	{
		if(b&1) ans = ans*a%mod;
		a = a*a%mod;
		b>>=1;
	}
	return ans;
}


F. 非对称加密算法RSA (11/38)

武汉工程大学第一届程序设计女生赛(牛客contest 4746)解题报告 Apare_xzc
武汉工程大学第一届程序设计女生赛(牛客contest 4746)解题报告 Apare_xzc武汉工程大学第一届程序设计女生赛(牛客contest 4746)解题报告 Apare_xzc

分析:

        RSA,抢了个FB。 题目很长,简化以后,就是给一个p,q , 然后n = p*q, n的欧拉函数Fai(n) = (p-1)*(q-1), 求d关于Fai(n)的乘法逆元,并用x^e%n加密明文x 。

代码:

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 2e5+10;
const int mod = 1E9+7;
void exgcd(LL a,LL b,LL&d,LL &x,LL&y); //拓展欧几里得 
LL fast_pow(LL a,LL b,LL mod); //快速幂 
LL getNi(LL a,LL m); //用拓展欧几里得求逆元 
int main()
{
	LL p,q,x,Fain,n;
	const int e = 65537;
	cin>>p>>q>>x;
	n = p*q; //计算n 
	Fain = (p-1)*(q-1); //计算Fai(n) 
	LL d = getNi(e,Fain); //d 是 e 关于 Fai(n)的乘法逆元 
	cout<<d<<endl; //输出d 
	cout<<fast_pow(x,e,n)<<endl; //密文为 x^e % n 
	
	return 0;	
} 

void exgcd(LL a,LL b,LL&d,LL &x,LL&y){
	if(b==0) {
		d = a; x = 1; y = 0;return;
	}
	exgcd(b,a%b,d,y,x);
	y -= (a/b)*x;
}
LL getNi(LL a,LL m)
{
	LL d,x,y;
	exgcd(a,m,d,x,y);
	return (x%m+m)%m;
}
LL fast_pow(LL a,LL b,LL mod)
{
	if(a==0) return 0;
	LL ans = 1;
	while(b)
	{
		if(b&1) ans = ans*a%mod;
		a = a*a%mod;
		b>>=1;
	}
	return ans;
}


G. 网络线路选择 (3/28)

武汉工程大学第一届程序设计女生赛(牛客contest 4746)解题报告 Apare_xzc
武汉工程大学第一届程序设计女生赛(牛客contest 4746)解题报告 Apare_xzc

分析:

        n个格子,每个可以涂m种色,求存在相邻两格同色的方案数
        若n为1,则没有相邻的,答案为0
        若m为1且n>1,则只有1种方案,都涂这唯一一种颜色。
        一般的情况,我们可以用所有方案减去不连色的方案。所有方案为m^n, 不连色的方案为:m*(m-1)^(n-1) 。注意模数很大,可能会溢出,用快乘稳妥。

代码:

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
LL fast_pow(LL a,LL b,LL mod);
LL fast_Mul(LL a,LL b,LL mod);
int main()
{
	int T = 0;
	LL m,n,p,mod;
	cin>>T;
	while(T--)
	{
		cin>>n>>m>>p;
		mod = n*p;
		if(n==1)
		{
			puts("0");
			continue;
		}
		if(m==1)
		{
			cout<<1%mod<<endl;
			continue;
		}
		LL tot = fast_pow(m,n,mod);
		LL t = fast_pow(m-1,n-1,mod);
		t = fast_Mul(t,m,mod);
		tot = ((tot-t)%mod+mod)%mod; 
		cout<<tot<<endl;
	}
	
	
	return 0;	
} 

LL fast_pow(LL a,LL b,LL mod)
{
	if(a==0) return 0;
	LL ans = 1;
	while(b)
	{
		if(b&1) ans = fast_Mul(ans,a,mod);
		a = fast_Mul(a,a,mod);
		b>>=1;
	}
	return ans;
}
LL fast_Mul(LL a,LL b,LL mod)
{
	LL ans = 0;
	if(a==0||b==0) return 0;
	if(a<b) swap(a,b);
	while(b)
	{
		if(b&1) ans = (ans+a)%mod;
		a = (a<<1)%mod;
		b>>=1; 
	}
	return ans;
}

H. 神奇的硬币II (3/31)

武汉工程大学第一届程序设计女生赛(牛客contest 4746)解题报告 Apare_xzc武汉工程大学第一届程序设计女生赛(牛客contest 4746)解题报告 Apare_xzc

样例输入:

5 5
3 5 6 3 8
3 5 6 3 8
3 2 5 1 6

样例输出:

1

分析:

        n个硬币,m个物品,每个硬币有价值v和能量e, 每个物品有重量w。如果硬币价值>=物品重量,物品能量就要加上硬币的能量。求能量最大,id最小的物品。
        我们可以对硬币进行处理,能量为0的不影响结果,可以去掉,面值相同的硬币可以视为一个,把能量相加到一个里面即可。然后我们按硬币价值从大到小排序,求关于能量的前缀和。每个物品,我们二分出价值大于物品质量的第最小价值硬币,前缀和即为该物品的能量。计算能量时顺便维护最大值级id即可。

代码:

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 1E6+10;
int VV[N],EE[N];
LL sum[N];
struct Node{
	int v,E;
	bool operator < (const Node& rhs)const{
		return v < rhs.v;
	}
}node[N];
struct P{
	int id,w;
	P(int _id=0,int _w=0)
	{
		id = _id;
		w = _w;
	}
	bool operator < (const P& rhs)const{
		return w < rhs.w;
	}
}pp[N];
int main()
{
	int n,m,E;
	cin>>n>>m;
	for(int i=1;i<=n;++i)
		scanf("%d",VV+i);
	for(int i=1;i<=n;++i)
		scanf("%d",EE+i);
	int cnt = 0; 
	for(int i=1;i<=n;++i)
	{
		if(EE[i]!=0) ++cnt,node[cnt].v = VV[i],node[cnt].E =EE[i];
	}
	n = cnt;
	sort(node+1,node+n+1);
	int p = 1;
	for(int i=2;i<=n;++i)
	{
		if(node[i].v==node[p].v)
		{
			node[p].E += node[i].E;
		}
		else 
		{
			++p; node[p].v = node[i].v, node[p].E = node[i].E;
		}
	}
	n = p;
	for(int i=1;i<=m;++i)
		scanf("%d",&pp[i].w),pp[i].id = i;
	if(n==0)
	{
		puts("1"); return 0;
	}
	sort(pp+1,pp+m+1);
	if(node[n].v<pp[1].w)
	{
		puts("1"); return 0;
	}
	sum[n] = node[n].E;
	for(int i=n-1;i>=1;--i)
		sum[i] = sum[i+1]+node[i].E;

	LL Maxx = -1e17;
	int id = -1;
	int left = 0,right = n,mid;
	
	for(int i=1;i<=m;++i)
	{
		if(pp[i].w>node[n].v)
		{
			if(Maxx<0||Maxx==0&&id>pp[i].id)
			{
				Maxx = 0, id = pp[i].id;
			}
			continue;
		}
		left = 0, right = n;
		while(right-left>1)
		{
			mid = (left+right)>>1;
			if(node[mid].v>=pp[i].w) right = mid;
			else left = mid;
		}	
		if(Maxx<sum[right]||Maxx==sum[right]&&pp[i].id<id)
		{
			Maxx = sum[right];
			id = pp[i].id;
		}
	}
	cout<<id<<endl;
		
	return 0;	
} 

I.神奇的硬币I (21/154)

武汉工程大学第一届程序设计女生赛(牛客contest 4746)解题报告 Apare_xzc
武汉工程大学第一届程序设计女生赛(牛客contest 4746)解题报告 Apare_xzc

分析:

        其实就是求能买到物品的价值最小的硬币能买到几个。我们可以对硬币价值排序,对物品重量排序,二分查找到能买到物品的最小价值的币。然后看重量小于该币值的物品有几个,再次二分可得到答案。

代码:

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 1E6+20;
int v[N],w[N];
int main()
{
	int n,m;
	while(cin>>n>>m)
	{
		for(int i=1;i<=n;++i)
			scanf("%d",v+i);
		for(int i=1;i<=m;++i)
			scanf("%d",w+i);
		sort(v+1,v+1+n);
		sort(w+1,w+1+m);
		if(v[n]<w[1])
		{
			puts("-1");
			return 0;
		}
		int idd = lower_bound(v+1,v+1+n,w[1])-v;
		int id = upper_bound(w+1,w+1+m,v[idd])-w-1;
		printf("%d\n",id);
		
	}
	
	return 0;	
} 

写完了。
2020.3.8 20:47 xzc