2021年北京理工大学ACM CLUB清明节组队训练赛_acm club的会员越来越多了,为此,acm club想为会员们准备一个晚会,晚会节目由会员

目录

• 比赛链接
• C.Corrupted Contest
  • 题意
  • 解题思路
  • Code
• E.Efficiently Elevated
  • 题意
  • 解题思路
  • Code
• H.Hungry Henk
  • 题意
  • 解题思路
  • Code
• I.Incomplete Implementation
  • 题意
  • 解题思路
  • Code
• J.Jigsaw
  • 题意
  • 解题思路
  • Code
• 感想

比赛链接

传送门

C.Corrupted Contest

题意

输入一个n表示有n个人，然后输入一个p表示有p道题，接下来输入n行表示每个人昨晚最后一题的时间的排名，问你能否找到一种做题的排序方式使得满足这样的时间排序，如果存在不能确定的情况就输出"ambiguous"，否则输出每个人的做题数

解题思路

很明显这个题目是非递增的序列，并且如果后一个人的最后做出来的时间比前面一个人少的话，那么后一个人的做题的数量必然比前面那个人的做题数目少， 但是需要注意的是如果遇到时间为0的情况那么这个人做出来的题目数必然为0，我们通过差分处理一下，如果第一个时间为0的话后面都是0，直接输出就行，否则的话第一个人的做题数一定是p，然后我们按照之前的差分数组遇到-1就减少，我们最后再扫一遍结果数组，如果出现断层情况那么一定是不能确定的，那么找到了断层就直接输出"ambiguous"否则的话就直接输出我们处理的答案

Code

#include<bits/stdc++.h>
using namespace std;
const int N = 10005; 
int n,p,a[N],b[N],c[N];
 
 
int main()
{
	scanf("%d%d",&n,&p);
	for(int i = 0;i < n; ++i) {
		scanf("%d",&a[i]);
	}
	memset(c,-1,sizeof c);
	if(a[0]) {
		c[0] = p;
	}
	else {
		c[0] = 0;
	}
	c[n] = 0;
	for(int i = 1;i < n; ++i) {
		if(a[i] == 0) {
			c[i] = 0;
			continue;
		}
		if(a[i]-a[i-1] >= 0) {
			b[i] = 1;
		}
		else {
			b[i] = -1;
		}
	}
	for(int i = 1;i < n; ++i) {
		if(c[i] == 0) continue;
		if(b[i] == 1) {
			c[i] = c[i - 1];
		}
		else {
			c[i] = c[i - 1] - 1;
		}
	}
	for(int i = 1;i <= n; ++i) {
		if(c[i] - c[i-1] < -1) {
			puts("ambiguous");
			return 0;
		}
	}
	for(int i = 0;i < n; ++i) {
//		printf("c[%d] = %d\n",i + 1,c[i]);
		printf("%d\n",c[i]);	
	}
	
	return 0;
}

E.Efficiently Elevated

题意

给你一个$h \times w$ 的地图，然后给每个坐标点输入一个值，表示的是该点楼层的高度，高度为1的楼层不需要电梯，在一个楼层群中只需要建立一个最高的楼层的电梯即可，问你最少需要多少电梯

解题思路

很明显我们可以优先对楼层高的电梯周围的较低楼层进行染色，然后看染色几次就能全部满足，这个就是最少所需要的电梯数

Code

#include<bits/stdc++.h>
using namespace std;
 
const int N = 505;
int n,m;
int mp[N][N];
int A[N][N];
int dx[4] = {0,0,-1,1};
int dy[4] = {-1,1,0,0};
 
struct node {
	int x,y,h;
	node(int x,int y,int h) {
	this->x = x;
	this->y = y;
	this->h = h; 
	}
	bool operator< (const node &r) const { return (h < r.h); }
};
 
void dfs(int i,int j) {
	if(!mp[i][j]) return;
	mp[i][j] = 0;
	for(int k = 0;k < 4; ++k) {
		int nx = i + dx[k];
		int ny = j + dy[k];
		if(nx > 0 && nx <= n && ny > 0 && ny <= m && A[i][j] >= A[nx][ny]) {
			dfs(nx,ny);
		} 
	}
}
priority_queue<node> que;
 
int main()
{
	scanf("%d%d",&n,&m);
	for(int i = 1;i <= n; ++i) {
		for(int j = 1;j <= m; ++j) {
			scanf("%d",&mp[i][j]);
			A[i][j] = mp[i][j];
			if(mp[i][j] <= 1)
				mp[i][j] = 0;
			else 
				mp[i][j] = 1;
			que.push({i,j,A[i][j]});
		}
	}
	int ans = 0;
	while(que.size()) {
		node p = que.top();
		que.pop();
		if(mp[p.x][p.y]) {
			dfs(p.x,p.y);
			ans++;
		}
	}
	printf("%d",ans);
	
	return 0;
}

H.Hungry Henk

题意

输入一个n，表示有n组菜，然后对每一组菜输入一个d表示的是每一组菜有多少个菜，然后输入d个菜，问你能否找到一组菜，它的每一个菜的小写字母个数都小于等于20，然后输出这一组菜(可以输出任意满足题意的答案)

解题思路

直接暴力模拟就行，签到题

Code

#include<bits/stdc++.h>
using namespace std;
int n;
int main()
{
	int d;
	string ch,ans="";
	int ansd;
	cin>>n;
	
	for(int i = 0;i < n; ++i) {
		cin>>d;
		ansd = d;
		bool fg = true;
		for(int j = 0;j < d; ++j) {
			cin>>ch;
			if(ch.size() > 20) fg = false;
			ans += ch;
			ans += "\n";
		}
		if(fg == true) {
			while(++ i < n) {
				cin>>d;
				for(int j = 0;j < d; ++j) 
					cin>>ch;
			}
			cout<<ansd<<"\n";
			cout<<ans<<"\n";
			break;
		}
	}
	
	
	
	return 0;
 }

I.Incomplete Implementation

题意

输入长度为n的乱序数组(每个数都是不一样的，但是都是小于等于n的)，然后你可以每次任意选择n/2个不同的下标使得他们值排序，然后有序放回这几个位置，你最多有三次操作机请问你怎么操作，会使得这个乱序数组恢复有序。(可以输出仍以方式)

解题思路

我们第一步先让 [1,n/2] 的值恢复到原位，然后再让[n/4+1,n/2]恢复到原位，最后直接输出剩下的n/2个数，即可完成排序，值得注意的是，当我们再处理前两种的情况有可能会有这样的情况，那个数本来就在自己的位置，那么我们就需要找一些其他位置的数来凑成n/2个数，我们应该从1开始往后选择，因为我们是优先对前面处理，也就是前面的数字不会影响我们对排序的处理

Code

#include<bits/stdc++.h>
using namespace std;
 
const int N = 100005;
 
int n,a[N],b[N];
set<int> ans;
 
int main()
{
	scanf("%d",&n);
	for(int i = 1;i <= n; ++i) {
		scanf("%d",&a[i]);
		b[a[i]] = i;
	}
	printf("%d\n",3);
	ans.clear();
	for(int i = 1;i <= n/4; ++i) {
		int a1 = b[i];
		int a2 = i;
		if(a1 == a2) {
			a2 = n;
		}
		else {
			b[a[i]] = a1; 
			b[i] = i;
			
			int temp = a[a1];
			a[a1] = a[a2];
			a[a2] = temp;
		}
		ans.insert(a1);
		ans.insert(a2);
	}
	int i = 1;
	while(ans.size() < n / 2) {
		ans.insert(i++);
	}
	for(auto it : ans) {
		printf("%d ",it);
	}
	puts("");
	ans.clear();
//	for(int i = 1;i <= n; ++i) printf("%d%c",a[i],i==n?'\n':' ');
//	for(int i = 1;i <= n; ++i) printf("%d%c",b[i],i==n?'\n':' ');
//	for(int i = 1;i <= n; ++i) b[a[i]] = i;
	for(int i = n/4 + 1;i <= n/2; ++i) {
		int a1 = b[i];
		int a2 = i;
		if(a1 == a2) {
			a2 = n;
		}
		else {
			b[a[i]] = a1; 
			b[i] = i;
			
			int temp = a[a1];
			a[a1] = a[a2];
			a[a2] = temp;
		}
		ans.insert(a1);
		ans.insert(a2);
	}
	i = 1;
	while(ans.size() < n / 2) {
		ans.insert(i++);
	}
	for(auto it : ans) {
		printf("%d ",it);
	}
	puts("");
//	for(int i = 1;i <= n; ++i) b[a[i]] = i;
	for(int i = n/2+1;i <= n; ++i) {
		printf("%d%c",a[i],i==n?'\n':' ');
	}
//	for(int i = 1;i <= n; ++i) {
//		printf("%d ",a[i]);
//	}
	return 0;
}

J.Jigsaw

题意

给你拼图的一些碎片，角落的碎片数为c，边缘的碎片数为e，中间的碎片数为m，问你能否用尽这些碎片拼出一个图，如果可以的话就输出最后拼图的长和宽，否则输出“impossible”

解题思路

很明显如果角落的c不为4，那么一定不能满足条件，然后如果e不能被2整除那么一定不能满足条件，最后就是计算长和宽了，这里我们设内矩形的长和宽为a,b

$$(a + b)\times 2= e$$

$$a\times b = m$$

然后可以得到一个一元二次方程，注意的是，解可能有两种，所以我们两种都要考虑

Code

#include<bits/stdc++.h>
using namespace std;
#define int long long
int c,e,m;
signed main()
{
	cin>>c>>e>>m;
	if(c == 4) {
		if(e % 2 == 0) {
			int a1,a2,b1,b2;
			a1 = (e + sqrt((e*e-16.0*m)))/4.0;
			a2 = (e - sqrt((e*e-16.0*m)))/4.0;
			b1 = (e/2)-a1;
			b2 = (e/2)-a2;
			if(a1 * b1 == m) {
				printf("%lld %lld\n",a1+2,b1+2);
			}
			else if(a2 * b2 == m) {
				printf("%lld %lld\n",a2+2,b2+2);
			}
			else {
				puts("impossible");
			}
		}
		else {
			puts("impossible");
		}
	}
	else {
		puts("impossible");
	}
	return 0;
 }

感想

被各位大佬暴捶……这个绝望小学我可能一被子都忘不掉(

打下来除了E题一直读错题，rhr写了一发wa了，然后我按照他的理解写了一发然后又wa了，然后我又去读题，感觉还是没懂，结果比赛结束发现是真的读错题了，想起了yy在比赛的时候想了个反例我按照rhr的想法，就直接否定了……，然后最后半小时就一直挂机