2021年北京理工大学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
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 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  0 && ny = A[nx][ny]) {
			dfs(nx,ny);
		} 
	}
}
priority_queue que;

int main()
{
	scanf("%d%d",&n,&m);
	for(int i = 1;i >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