Codeforces Round #699 (Div. 2)

A Space Navigation

#include <bits/stdc++.h>
using namespace std;

typedef long long LL;
#define IOS ios::sync_with_stdio(false); cin.tie(0); cout.tie(0)
#define RI register int

const int MOD = 1e9 + 7;
const double PI = acos(-1.0);
const int INF = 0x3f3f3f3f;
const int N = 2e5 + 20;

int n, m;
char s[N];

int main()
{
	int __;
	scanf("%d", &__);
	while(__ -- )
	{
		scanf("%d%d", &n, &m);
		scanf("%s", s);
		int r = 0, u = 0, l = 0, d = 0;
		int len = strlen(s);
		for(int i = 0; i < len; ++ i)
		{
			if(s[i] == ‘R‘) r ++;
			if(s[i] == ‘U‘) u ++;
			if(s[i] == ‘D‘) d ++;
			if(s[i] == ‘L‘) l ++;
		}
		int flag = 0;
		if(n >= 0 && r < n) flag = 1;
		if(n < 0 && l < abs(n)) flag = 1;
		if(m >= 0 && u < m) flag = 1;
		if(m < 0 && d < abs(m)) flag = 1;
		if(flag) puts("NO");
		else puts("YES"); 
	}
	return 0;
}

B New Colony

最多也就填充 \(10000\) 块，直接模拟即可，当滑出边界时 \(break\) 掉

#include <bits/stdc++.h>
using namespace std;

const int N = 100 + 10;

int n, k;
int h[N];

int main()
{
	int __;
	scanf("%d", &__);
	while(__ -- )
	{
		scanf("%d%d", &n, &k);
		for(int i = 1; i <= n; ++ i) scanf("%d", &h[i]);
		int res;
	 	bool flag = 0;
		for(int i = 1; i <= k; ++ i)
		{
			flag = 1;
			for(int j = 1; j < n; ++ j)
				if(h[j] < h[j + 1]) 
				{
					flag = 0;
					h[j] ++;
					res = j;
					break;
				}
			if(flag == 1) break;
		}
		if(flag) puts("-1");
		else printf("%d\n", res);
	}
	return 0;
}

C Fence Painting

需要的颜色可以直接利用，不需要的颜色染到当前就是该颜色的位置或者接下来就要被染掉的位置
可以用队列暂存当前不需要的颜色，下次染色之前用掉

#include <bits/stdc++.h>
using namespace std;

const int N = 1e5 + 20;

int n, m;
int a[N], b[N], c[N];
int res[N];
map<int, vector<int>> mp;
map<int, vector<int>> hav;

bool check()
{
	mp.clear(); hav.clear();
	for(int i = 1; i <= n; ++ i)
		if(a[i] != b[i]) mp[b[i]].push_back(i); 
		else hav[b[i]].push_back(i);
	queue<int> q;
	for(int i = 1; i <= m; ++ i)
	{
		if(!mp[c[i]].size())
		{ 
			if(!hav[c[i]].size()) q.push(i);
			else
			{
				q.push(i);
				while(!q.empty()) 
				{
					res[q.front()] = hav[c[i]].back();
					q.pop();
				}	
			}
		}
		else 
		{
			while(!q.empty())
			{
				res[q.front()] = mp[c[i]].back();
				q.pop();
			}
			res[i] = mp[c[i]].back();
			a[res[i]] = c[i]; 
			hav[c[i]].push_back(res[i]);
			mp[c[i]].pop_back();
		}
	}
	if(!q.empty()) return 0; 
	for(int i = 1; i <= n; ++ i)
		if(a[i] != b[i]) return 0;
	return 1;
}

int main()
{
	int __;
	scanf("%d", &__);
	while(__ -- )
	{
		scanf("%d%d", &n, &m);
		for(int i = 1; i <= n; ++ i) scanf("%d", &a[i]);
		for(int i = 1; i <= n; ++ i) scanf("%d", &b[i]);
		for(int i = 1; i <= m; ++ i) scanf("%d", &c[i]);
		if(check())
		{
			puts("YES");
			for(int i = 1; i <= m; ++ i) printf("%d ", res[i]);
			puts("");
		}
		else puts("NO");
	}
	return 0;
}

D AB Graph

如果存在两个点之间的两条边上字母相同，一直在这两个点之间走即可
如果不存在上述情况，即任意两个点之间的两条边上字母不相同，则分奇偶讨论：
对于奇数的情况，任选两个点，在这两点之间一直走即可
对于偶数的情况，需要找到一个点 \(u\) 既有到 \(x\) 的字母 \(a\) 的出边， 也有到 \(y\) 的字母 \(b\) 的出边，在 \(u\) 和 \(x\) 之间走一半， 在 \(u\) 和 \(y\) 之间走一半即可

#include <bits/stdc++.h>
using namespace std;

typedef long long LL;
#define IOS ios::sync_with_stdio(false); cin.tie(0); cout.tie(0)
#define RI register int

const int MOD = 1e9 + 7;
const double PI = acos(-1.0);
const int INF = 0x3f3f3f3f;
const int N = 1e3 + 20;

int n, m;
char g[N][N];

void init()
{
	for(int i = 1; i <= n; ++ i)
		for(int j = i + 1; j <= n; ++ j)
			if(g[i][j] == g[j][i]) 
			{ 
				puts("YES");
				for(int k = 1; k <= m + 1; ++ k) printf("%d ", k % 2 ? i : j);
				puts(""); return;
			}
	if(m % 2) 
	{
		puts("YES");
		for(int i = 1; i <= m + 1; ++ i) printf("%d ", i % 2 ? 1 : 2);
		puts(""); return;
	}
	for(int i = 1; i <= n; ++ i)
	{
		int hav_a = 0, hav_b = 0;
		for(int j = 1; j <= n; ++ j)
		{
			if(i == j) continue;
			if(g[i][j] == ‘a‘) hav_a = j;
			if(g[i][j] == ‘b‘) hav_b = j;
			if(hav_a && hav_b) break;
		}
		if(!hav_a || !hav_b) continue;
		puts("YES");
		if(m % 4) 
		{
			for(int j = 1; j <= m / 2 + 1; ++ j) printf("%d ", j % 2 ? hav_a : i);
			for(int j = 1; j <= m / 2; ++ j) printf("%d ", j % 2 ? hav_b : i);
		}  
		else 
		{
			for(int j = 1; j <= m / 2 + 1; ++ j) printf("%d ", j % 2 ? i : hav_a);
			for(int j = 1; j <= m / 2; ++ j) printf("%d ", j % 2 ? hav_b : i);
		}
		puts(""); return;
	}
	puts("NO");
	return;
}

int main()
{
	int __;
	scanf("%d", &__);
	while(__ -- )
	{
		scanf("%d%d", &n, &m); getchar();
		for(int i = 1; i <= n; ++ i) scanf("%s", g[i] + 1);
		init();
	}
	return 0;
}

E Sorting Books

Codeforces Round #699 (Div. 2)

原文：https://www.cnblogs.com/ooctober/p/14482608.html