Codeforces Round #578 (Div. 2)

A、Hotelier

暴力

#include<bits/stdc++.h>
#define sc scanf
#define pr printf
using namespace std;
int a[15];
int main()
{
	int n;
	sc("%d", &n);
	getchar();
	for (int i = 1; i <= n; i++)
	{
		char s = getchar();
		if (s == 'L')
		{
			for (int i = 0; i <= 9; i++)
			{
				if (a[i] == 0)
				{
					a[i] = 1;
					break;
				}
			}
		}
		else if (s == 'R')
		{
			for (int i = 9; i >= 0; i--)
			{
				if (a[i] == 0)
				{
					a[i] = 1;
					break;
				}
			}
		}
		else
		{
			a[s - '0'] = 0;
		}
	}
		for (int i = 0; i <= 9; i++)
			printf("%d", a[i]);
}

B、Block Adventure

让左边尽量等于右边减 k ，注意判断小于0的情况

#include<bits/stdc++.h>
#define sc scanf
#define pr printf
using namespace std;
int a[105];
int main()
{
	int T;
	sc("%d", &T);
	while (T--)
	{
		int n, m, k;
		sc("%d%d%d", &n, &m, &k);
		for (int i = 1; i <= n; i++)
			sc("%d", &a[i]);
		for (int i = 1; i < n; i++)
		{
			if (a[i] > a[i + 1] - k)
			{
				int qq = a[i + 1] - k;
				qq = max(qq, 0);
				m += a[i] - qq;
			}
			else
			{
				int qq = a[i + 1] - k;
				qq = max(qq, 0);
				int cha = qq - a[i];
				if (m < cha)
				{
					printf("NO\n");
					goto qwe;
				}
				else
					m -= cha;
			}
		}
		printf("YES\n");
		qwe:;
	}
}

C、Round Corridor

找找规律，这两块一共被分为了gcd(n,m) 块，求一下每块的个数，然后算一下在第几块里面，判一下相等就可以。

#include<bits/stdc++.h>
#define ll long long
#define sc scanf
#define pr printf
using namespace std;
ll gcd(ll a, ll b)
{
	return b == 0 ? a : gcd(b, a % b);
}
int main()
{
	ll n, m, k;
	scanf("%lld%lld%lld", &n, &m, &k);
	ll g = gcd(n, m);
	ll a, b, c, d;
	ll q = n / g;
	ll w = m / g;
	while (k--)
	{
		scanf("%lld%lld%lld%lld", &a, &b, &c, &d);
		b--; d--;
		if (a == 1)
			b /= q;
		else
			b /= w;
		if (c == 1)
			d /= q;
		else
			d /= w;
		if (b == d)
			printf("YES\n");
		else
			printf("NO\n");
	}
}

D、White Lines

求出可以使当前这一行/列变成白线的左上顶点( i, j )的取值范围，然后用更新四个点来代替更新面积，然后扫一遍前缀和就可以

#include <bits/stdc++.h>
#define ll long long
#define sc scanf
#define pr printf
using namespace std;
char s[2005][2005];
int ans[2005][2005];
void update(int a, int b, int c, int d)//x1 y1 x2 y2
{
	ans[a][b]++;
	ans[c][d]++;
	ans[a][d]--;
	ans[c][b]--;
}
int main()
{
	int n, k;
	sc("%d%d", &n, &k);
	for (int i = 1; i <= n; i++)
		scanf("%s", s[i] + 1);
	int res = 0, yes = 0;
	for (int i = 1; i <= n; i++)
	{
		int minn = 0, maxn = 0;
		for (int j = 1; j <= n; j++)
		{
			if (s[i][j] == 'B')
			{
				maxn = j;
				if (minn == 0)
					minn = j;
			}
		}
		if (minn == 0)
			yes++;
		else if (maxn - minn + 1 <= k)
			update(max(0, i - k + 1), max(0, maxn - k + 1), i + 1, minn + 1);
	}
	for (int j = 1; j <= n; j++)
	{
		int minn = 0, maxn = 0;
		for (int i = 1; i <= n; i++)
		{
			if (s[i][j] == 'B')
			{
				maxn = i;
				if (minn == 0)
					minn = i;
			}
		}
		if (minn == 0)
			yes++;
		else if (maxn - minn + 1 <= k)
			update(max(0, maxn - k + 1), max(0, j - k + 1), minn + 1, j + 1);
	}
	for (int i = 1; i <= n; i++)
	{
		ans[0][i] += ans[0][i - 1];
		ans[i][0] += ans[i - 1][0];
	}
	for (int i = 1; i <= n; i++)
	{
		for (int j = 1; j <= n; j++)
		{
			ans[i][j] = ans[i - 1][j] + ans[i][j - 1] - ans[i - 1][j - 1] + ans[i][j];
			res = max(res, ans[i][j]);
		}
	}
	printf("%d\n", res + yes);
}