Codeforce Round#544 div3题解

￡神魔★判官ぃ 2022-01-21 01:57 150阅读 0赞

#  A.Middle of the Contest #

## 1.题目描述 ##

[Problem A][],给出开始时间以及截至时间求出中间的时间

## 2.题目思路 ##

将开始时间以及结束时间都转化为分钟表示，相加除以2即为所得

#include <stdio.h>
    int main() 
    {
    	int h1, h2, m1, m2;
    	int m3, h3;
    	scanf("%d:%d", &h1, &m1);
    	scanf("%d:%d", &h2, &m2);
    	
    	int tot =(h1 * 60 + m1 + h2 * 60 + m2)/2;
    	h3 = tot / 60;
    	m3 = tot % 60;
    	if (h3< 10) 
    	{
    		printf("0%d:", h3);
    	}
    	else 
    	{
    		printf("%d:", h3);
    	}
    	if (m3 < 10) 
    	{
    		printf("0%d", m3);
    	}
    	else 
    	{
    		printf("%d", m3);
    	}
    	return 0;
    }

#  B.Preparation for International Women’s Day #

## 1.题目 ##

[ProblemB][]

## 2.题解 ##

首先题目可以简化为n个数，两两相加，满足(a+b)%k==0.

那么无论如何配对，无论a和b的取值是什么，我们都要满足a%k+b%k=0这个条件。

所以我们可以将题目简化，在读取每一个数n的时候，都mod k，并记录下，count\[n mod k\]

那么此时配对就变得简单，我们只需要找count\[i\]以及count\[m-i\],当两个都不为0的时候，sum+=min(mount\[i\],count\[m-i\]).

还有一种特殊的情况就是2\*i=k的时候，这种情况需要特判，sum+=(count\[i\]/2)

最后由于我们计算的时候都只计算了一组，所以最后结果需要\*2

## 3.代码 ##

#include <stdio.h>
    const int maxn = 200007;
    int box[maxn];
    bool visit[maxn] = { false };
    int count[107] = { false };
    int min(int a,int b) 
    {
    	if (a > b)
    		return b;
    	return a;
    }
    int main() 
    {
    	int n, m;
    	int sum = 0;
    	scanf("%d%d", &n, &m);
    	for (int i = 1; i <= n; i++) 
    	{
    		scanf("%d", &box[i]);
    		box[i] %= m;
    	}
    	for (int i = 1; i <= n; i++) 
    	{
    		count[box[i]]++;
    	}
    	sum += (count[0] / 2);
    		for (int i = 1; i <= m/2; i++)
    		{
    			if (i * 2 == m) 
    			{
    				sum += count[i] / 2;
    			}
    			else
    			{
    				if (count[i] && count[m - i])
    				{
    					sum += min(count[i], count[m - i]);
    				}
    			}
    		}
    	printf("%d", sum*2);
    	return 0;
    }

#  C.Balanced Team #

## 1.题目 ##

[ProblemC][]

## 2.解答 ##

先求出数组相邻两个数的差值，并存为另一个数组，那么此时，我们可以将问题转化为，求在转化过后的数组中连续和不超过5的数的最大的长度即可。

#include <cstdio>
    #include <algorithm>
    using namespace std;
    const int maxn = 200007;
    int num[maxn] = { 0 };
    int num2[maxn] = { 0 };
    bool cmp(int a,int b)
    {
    	return a < b;
    }
    int main() 
    {
    	int n;
    	scanf("%d", &n);
    	for(int i=1;i<=n;i++)
    	{
    		scanf("%d", &num[i]);
    	}
    	sort(num + 1, num + n + 1, cmp);
    	int count = 0;
    	int max = -1;
    	for(int i=1;i<=n-1;i++)
    	{
    		num2[i] = num[i + 1] - num[i];
    	}
    	bool flag = false;
    	int sum = 0;
    	int j = 0;
    	int o = 0;
    	int p;
    	for(int i=1;i<=n-1;i++)
    	{
    		o = sum;
    		sum =sum+num2[i];
    		p = sum;
    		if(o<p&&!flag)
    		{
    			flag = true;
    			j = i;
    		}
    		if(sum>5)
    		{
    			sum = 0;
    			count = 0;
    			i = j;
    			flag = false;
    		}
    		else 
    		{
    			count++;
    		}
    		if(count>max)
    		{
    			max = count;
    		}
    	}
    	if(n==1)
    	{
    		printf("1");
    	}
    	else
    	printf("%d", max+1);
    	return 0;
    }

# D.Zero Quantity Maximization #

## 1.题目 ##

[ProblemD][]

## 2.解答 ##

自己的思路，

构建结构体，并记录下d=a/b的值,对结构体数组关于d进行排序，再依次比对d的值，求出答案，没过emmm，考虑可能是精度问题，故舍弃

2.依然是构建结构体，此时不去管a/b的值，而是去求a和b的最小公因数r，并同时令a/r,b/r然后对结构体数组进行排序(以a的大小为序),然后再比较前后的值求解，没有通过，找不到原因+1；

3.放弃结构体，考虑stl中的map，以及pair类型

有关pair的用法参照pair传送门

map的用法参照map传送门

跟结构体用法基本类似，所以不是很能理解为什么第二种算法不对，emm可能这就是玄学吧，另外掌握了别的技巧还是蛮不错的。

#include <bits/stdc++.h>
    using namespace std;
    const int maxn=2*1e5+7;
    
    int gcd(int a,int b)
    {
    	if(b==0)
    	{
    		return a;
    	}
    	int r=1;
    	while(r)
    	{
    		r=a%b;
    		a=b;
    		b=r;
    	}	
    	return a;
    }
    
    int main()
    {
    	int n;
    	int a[maxn];
    	int b[maxn];
    	scanf("%d",&n);
    	for(int i=1;i<=n;i++)
    	{
    		scanf("%d",&a[i]);
    	}
    	for(int i=1;i<=n;i++)
    	{
    		scanf("%d",&b[i]);
    	}
    	map<pair<int,int>,int>test;
    	int special=0;
    	for(int i=1;i<=n;i++)
    	{
    		if(a[i]!=0)
    		{
    			int r=gcd(a[i],b[i]);
    			a[i]/=r;
    			b[i]/=r;
    		}
    	}
    	for(int i=1;i<=n;i++)
    	{
    		if(b[i]==0&&a[i]==0)
    		{
    			special++;	
    		} 
    		else if(a[i]==0)
    		{
    			continue;
    		}
    		else
    		{
    			test[{a[i],b[i]}]++;
    		}
    	}
    	int ans=0;
    	map<pair<int,int>,int>::iterator iter;
    	for(iter=test.begin();iter!=test.end();iter++)
    	{
    		ans=ans>iter->second?ans:iter->second;
    	}
    	ans+=special;
    	printf("%d",ans);
    	return 0;
    }

#  E.K Balanced Teams #

## 1.题目 ##

[E][]

## 2.解答 ##

这道题还是懵逼状态，所以参照了E题的官方题解，下面给出思路。（使用动态规划）

我们用dp\[i\]\[j\]来表示，有i个人，j个队伍时答案的最优解。

首先我们对学生序列按照从小到大进行排列，与此同时，我们记录此时从第i个学生开始，向后寻找学生组队，该队伍的人数最多能有多少。最后进行dp,详细看代码注释。

#include <stdio.h>
    #include <algorithm>
    using namespace std;
    const int maxn=5007;
    int num[maxn]={0};
    int dp[maxn][maxn]={0};//表示i个人，j个队伍的时候，所能容纳最多的人数 
    bool cmp(int a,int b)
    {
    	return a<b;
    }
    int max(int a,int b)
    {
    	if(a>b)
    	return a;
    	return b;
    }
    
    int main()
    {
    	int n;
    	int m;
    	scanf("%d%d",&n,&m);
    	for(int i=1;i<=n;i++)
    	{
    		scanf("%d",&num[i]);
    	}
    	sort(num+1,num+1+n,cmp);//按能力大小进行排序 
    	int cnt[maxn]={0};
    	for(int i=1;i<=n;i++)
    	{
    		while(i+cnt[i]<=n&&num[i+cnt[i]]-num[i]<=5)
    		{
    			cnt[i]++;//这里记录从第i个位置的同学开始的团队最多容纳学生的个数 
    		}
    	}
    	for(int i=1;i<=n;i++)
    	{
    		for(int j=0;j<=m;j++)
    		{
    			dp[i+1][j]=max(dp[i+1][j],dp[i][j]); //判断是从当前节点开始最好，还是从下一个节点开始最好 
    			if(j+1<=m)
    			{
    				dp[i+cnt[i]][j+1]=max(dp[i+cnt[i]][j+1],dp[i][j]+cnt[i]);//此处是利用上面求出的cnt[i]，人数超过cnt[i]的时候，就要多开一支队伍 
    				//为了使得总人数最大化，此处人数一定要加上cnt[i] 
    			}
    			
    		}
    	}
    	printf("%d",dp[n+1][m]);
    	return 0;	
    }

# F1.Spanning Tree with Maximum Degree #

## 1.题目 ##

## 2.题解 ##

题目是不难，只要读取图，然后找出度数最大的点，然后从这个点开始进行bfs操作即可。

但是在处理的过程中遇到了一些问题

1.想要建立二维数组来保存整张图的关系，结果发现图的边数太大，二维数组开不下，转用vector

2.在进行bfs的时候，由于是用数组来模拟队列，所以最后导致了空间超出。转用stl中的queue

3.在bfs的时候，因为多加入了一个判断是否已经遍历完当前点的循环，导致时间超出。

最终代码如下

#include <stdio.h>
    #include <algorithm>
    #include <vector>
    #include <queue>
    using namespace std;
    const int maxn=2*1e5+7;
    vector< vector<int> > g;
    bool visit[maxn]={false};
    int deg[maxn];
    int n;
    long long int m;
    void bfs(int number)
    {
    	queue<int>q;
    	q.push(number);
    	while(!q.empty())
    	{
    		int v=q.front();
    		q.pop();
    		for(int i=0;i<g[v].size();i++)
    		{
    			if(!visit[g[v][i]])
    			{
    				printf("%d %d\n",v,g[v][i]);
    				q.push(g[v][i]);
    				visit[g[v][i]]=true;
    			}
    		}
    	}
    }
     
    int main()
    {
    	scanf("%d%lld",&n,&m);
    	int a,b;
    	g=vector<vector<int> >(maxn);
    	for(long long int i=1;i<=m;i++)
    	{
    		scanf("%d%d",&a,&b);
    		g[a].push_back(b);
    		g[b].push_back(a);
    		deg[a]++;
    		deg[b]++;
    	}
    	int pos=1;
    	for(int i=1;i<=n;i++)
    	{
    		if(deg[i]>deg[pos])
    		{
    			pos=i;
    		}
    	}
    	visit[pos]=true;
    	bfs(pos);
    	return 0;
    }

#  F2.Spanning Tree with One Fixed Degree #

## 1.题目 ##

[F2][]

## 2.题解 ##

看的时候完全没有思路，所以直接看了官方的题解。

实现思路如下

Step1:

将一号节点从整个图中删去，然后从其他节点开始，搜索生成树，该操作的目的是寻找只与一号节点相连的点的个数，（即该点无法通过与一号店相连的其他点到达）我们将这个个数叫做cnt

Step2:

不存在的情况只有两种，一种是cnt>D的情况即只与一号点的相连的个数要比需要的多，此时肯定无法找到，可以参照下面的图理解一下。另外一种则是，本身与一号点相连的点的个数要小于D，这个就不做过多解释

Step3：

接下来一是我们要将上面找到的cnt个节点加入答案序列中，二是我们要将随意挑选D-cnt个节点加入答案序列，重新构造图，再从一号节点进行bfs即可。（由于此时只有D个节点与一号节点相连，所以一定满足情况）

标程实现

#include <bits/stdc++.h>
    
    using namespace std;
    
    int n, m, D;
    vector<vector<int>> g;
    
    int cnt;
    vector<int> p, color;
    vector<pair<int, int>> ans;
    
    mt19937 rnd(time(NULL));
    
    void bfs(int s, int bad) {
    	queue<int> q; 
    	q.push(s);
    	color[s] = cnt;//该步骤可以理解为上色过程，将联通的一块儿节点赋予相同的颜色
    	while (!q.empty()) {//bfs内容
    		int v = q.front();
    		q.pop();
    		if (p[v] != -1) {//此处为随机内容，主要目的是记录答案的值
    			if (rnd() & 1) ans.push_back(make_pair(p[v], v));
    			else ans.push_back(make_pair(v, p[v]));
    		}
    		for (auto to : g[v]) {
    			if (to == bad || color[to] != -1) continue;//如果是一号节点，或者已经属于另一块儿就不进行操作
    			p[to] = v;//记录下朝向的节点，方便上面处理答案序列
    			color[to] = cnt;//上色
    			q.push(to);
    		}
    	}
    	++cnt;
    }
    
    int main() {
    #ifdef _DEBUG
    	freopen("input.txt", "r", stdin);
    //	freopen("output.txt", "w", stdout);
    #endif
    	
    	cin >> n >> m >> D;
    	g = vector<vector<int>>(n);
    	for (int i = 0; i < m; ++i) {
    		int x, y;
    		cin >> x >> y;
    		--x, --y;
    		g[x].push_back(y);
    		g[y].push_back(x);
    	}
    	//读入数据 
    	p = color = vector<int>(n, -1);
    	cnt = 0;
    	for (int i = 1; i < n; ++i) {
    		if (color[i] == -1) {
    			bfs(i, 0);
    		}
    	}//统计"只"与1号节点相连的节点有多少 
    	
    	if (cnt > D || D > int(g[0].size())) {
    		cout << "NO" << endl;
    		return 0;
    	}//不满足的情况只有两种，第一个是1的度不足D，二是D要比只与1号节点相连的节点要少 
    	
    	sort(g[0].begin(), g[0].end(), [](int a, int b) {
    		return color[a] < color[b];
    	});//此处是为了下一步方便判断是否加入一号节点
    	
    	for (int i = 0; i < int(g[0].size()); ++i) {
    		if (i == 0 || color[g[0][i]] != color[g[0][i - 1]]) {
    			ans.push_back(make_pair(0, g[0][i]));//如果两个节点不属于同一颜色块儿，就加入答案序列 
    		}
    	}
    	
    	D -= cnt;//剩下的节点 
    	for (int i = 1; i < int(g[0].size()); ++i) {
    		if (D == 0)//剩下节点为0 
    		break;
    		if (color[g[0][i]] == color[g[0][i - 1]]) 
    		{	
    			ans.push_back(make_pair(0, g[0][i]));//再剩下的与1相连的节点中寻找剩下的节点 
    			--D;
    		}
    	}
    	
    	g = vector<vector<int>>(n);//初始化g，重构图 
    	for (auto it : ans) {
    		g[it.first].push_back(it.second);
    		g[it.second].push_back(it.first);
    	}//进行重新连接 即将多余的节点与1号节点的连接断开 
    	
    	ans.clear();清空答案序列，重新进行bfs，寻找答案序列
    	p = color = vector<int>(n, -1);//初始化p数组，以及颜色数组，由于只写了一个bfs此处可以方便操作，也可以考虑再写一个bfs
    	cnt = 0;
    	bfs(0, -1);//进行bfs 
    	shuffle(ans.begin(), ans.end(), rnd);//随机排列，但并没有必要
    	cout << "YES" << endl;
    	for (auto it : ans) {
    		cout << it.first + 1 << " " << it.second + 1 << endl;
    	}
    	return 0;
    }

[Problem A]: http://codeforces.com/contest/1133/problem/A
[ProblemB]: http://codeforces.com/contest/1133/problem/B
[ProblemC]: http://codeforces.com/contest/1133/problem/C
[ProblemD]: http://codeforces.com/contest/1133/problem/D
[E]: http://codeforces.com/contest/1133/problem/E
[F2]: http://codeforces.com/contest/1133/problem/F2