专栏文章

AtCoder Beginner Contest 385 A~D

IIronMen
题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@miq07tb0
此快照首次捕获于
2025/12/03 20:49
3 个月前
此快照最后确认于
2025/12/03 20:49
3 个月前
查看原文

A - Equally

洛谷链接
AtCoder链接

题目

给你三个整数 A,B,CA,B,C。请判断能否将这三个整数分成两组或更多组，使这些组的和相等。

代码

CPP
#include <bits/stdc++.h>

using namespace std;

int a, b, c;

int main()
{
	scanf("%d %d %d", &a, &b, &c);
	if (a == b && b == c)
		puts("Yes");
	else if (a + b == c)
		puts("Yes");
	else if (b + c == a)
		puts("Yes");
	else if (a + c == b)
		puts("Yes");
	else
		puts("No");
	return 0;
}

B - Santa Claus 1

洛谷链接
AtCoder链接

题目

有一个网格，网格中有 HH 行和 WW 列。让 (i,j)(i,j) 表示从上往下数第 ii 行和从左往上数第 jj 列的单元格。
如果 Si,jS_{i,j} 是 #，则 (i,j)(i,j) 单元格无法通过；如果是 .，则该单元格可以通过且不包含房屋；如果是 @，则该单元格可以通过且包含房屋。
起初，圣诞老人在 (X,Y)(X,Y) 单元中。他将根据字符串 TT 采取以下行动。
  • 假设 ∣T∣|T| 是字符串 TT 的长度。对于 i=1,2,…,∣T∣i=1,2, \ldots ,|T|，他的移动步骤如下。
    • 假设 (x,y)(x,y) 是他目前所在的单元格。
      • 如果 TiT_i 是 U，且 (x−1,y)(x-1,y) 单元格可以通过，则移动到 (x−1,y)(x-1,y) 单元格。
      • 如果 TiT_i 是 D，且 (x+1,y)(x+1,y) 单元格可以通过，请移至 (x+1,y)(x+1,y) 单元格。
      • 如果 TiT_i 是 L，且 (x,y−1)(x,y-1) 单元格可以通过，请移动到 (x,y−1)(x,y-1) 单元格。
      • 如果 TiT_i 是 R，且 (x,y+1)(x,y+1) 单元格可以通过，则移动到 (x,y+1)(x,y+1) 单元格。
      • 否则，停留在 (x,y)(x,y) 格。
找出他完成所有行动后所在的单元格，以及他在行动过程中经过或到达的不同房子的数量。如果多次经过同一间房子，则只计算一次。

代码

CPP
#include <bits/stdc++.h>

using namespace std;

int h, w, x, y, c;
string s[110], t;
bool f[110][110];

int main()
{
	scanf("%d %d %d %d", &h, &w, &x, &y);
	for (int i = 0; i < h; i ++ )
		cin >> s[i];
	cin >> t;
	x --;
	y --;
	for (int i = 0; i < t.length(); i ++ )
	{
		if (t[i] == 'U' && s[x - 1][y] != '#' && x - 1 >= 0)
			x --;
		else if (t[i] == 'D' && s[x + 1][y] != '#' && x + 1 < h)
			x ++;
		else if (t[i] == 'L' && s[x][y - 1] != '#' && y - 1 >= 0)
			y --;
		else if (t[i] == 'R' && s[x][y + 1] != '#' && y + 1 < w)
			y ++;
		if (s[x][y] == '@')
			f[x][y] = 1;
	}
	for (int i = 0; i < h; i ++ )
	{
		for (int j = 0; j < w; j ++ )
		{
			if (f[i][j])
				c ++;
		}
	}
	cout << x + 1 << ' ' << y + 1 << ' ' << c << '\n';
	return 0;
}

C - Illuminate Buildings

洛谷链接
AtCoder链接

题目

有 NN 幢楼房等间距排成一行。第 ii 幢楼房从正面看的高度是 HiH_i。
你想给其中一些建筑物装上灯饰，要同时满足以下两个条件：
  • 所选建筑物的高度相同。
  • 所选建筑物的排列间隔相等。
您最多可以选择多少座建筑物？如果您选择的建筑物只有一幢，则认为它满足条件。

思路

我们设 dp[i][j]dp[i][j] 表示到第 ii 个数字时，数列间隔为 jj 的最长子序列个数。
设计完状态，我们来推方程：
我们分两类讨论：
  • 若 h[i]=h[i−j]h[i]=h[i−j] 则易得有 dp[i][j]=dp[i−j][j]+1dp[i][j]=dp[i−j][j]+1。
  • 若 h[i]=h[i−j]h[i]=h[i−j] 则因为 dp[i][j]dp[i][j] 不能从 dp[i−j][j]dp[i−j][j] 转移而来，所以 dp[i][j]=1dp[i][j]=1。
答案即为 dpdp 数组中的最大值。

代码

CPP
// LUOGU_RID: 207347596
#include <bits/stdc++.h>

using namespace std;

int n, ans, h[3010], dp[3010][3010];

int main()
{
	scanf("%d", &n);
	for (int i = 1; i <= n; i ++ )
		scanf("%d", &h[i]);
	for (int i = 1; i <= n; i ++)
	{
		for (int j = 1; j <= n; j ++ )
			dp[i][j] = 1;
		for (int j = 1; j <= i; j ++ )
		{
			dp[i][j] = 1;
			if (h[i] == h[i - j])
				dp[i][j] = dp[i - j][j] + 1;
			ans = max(ans, dp[i][j]);
		}
	}
	cout << ans << '\n';
	return 0;
}

D - Santa Claus 2

洛谷链接
AtCoder链接

题目

在二维平面上的点 (X1,Y1),…,(XN,YN)(X_1,Y_1), \ldots ,(X_N,Y_N) 上有 NN 座房子。
最初，圣诞老人位于点 (Sx,Sy)(S_x,S_y)。他将按照 (D1,C1),…,(DM,CM)(D_1,C_1), \ldots ,(D_M,C_M) 序列进行如下操作：
  • 对于 i=1,2,…,Mi=1,2, \ldots ,M 的顺序，他的移动如下：
    • 假设 (x,y)(x,y) 是他目前所在的点。
      • 如果 DiD_i 是 U，则从 (x,y)(x,y) 直线移动到 (x,y+Ci)(x,y+C_i)。
      • 如果 DiD_i 是 D，则从 (x,y)(x,y) 直线移动到 (x,y−Ci)(x,y-C_i)。
      • 如果 DiD_i 是 L，则从 (x,y)(x,y) 直线移动到 (x−Ci,y)(x-C_i,y)。
      • 如果 DiD_i 为 R，则从 (x,y)(x,y) 沿直线移动到 (x+Ci,y)(x+C_i,y)。
找出他完成所有行动后所在的点，以及他在行动过程中经过或到达的不同房子的数量。如果多次经过同一房屋，则只计算一次。

思路

我们分析一下算法的大致流程。我们考虑第一种行走方式，即 (x,y)→(x,y+Ci)(x,y) \to (x,y+C_i) 这种。你会发现 xx 不变，那么此时你固定 xx，找出所有满足 Xi=xX_i=x 的 YiY_i，并找出那些满足 y≤Yi≤y+Ciy \le Y_i \le y+C_i 的 YiY_i，并把这些 (Xi,Yi)(X_i,Y_i) 都删掉。其他情况同理。
这很好写，只需要开一个 map<int, set<int> >，同时完成了坐标的离散化和统计，删除的时候就在 set 上二分找出左边界和右边界直接暴力删就可以了，因为你会发现最多只有 MM 个点会被删掉。
时间复杂度 O((m+n)log⁡n)O((m+n) \log n)。
十年 OI 一场空，不开 long long 见祖宗。

代码

CPP
#include <bits/stdc++.h>

using namespace std;

long long n, m, x, y, c, ans;
char op;
vector <long long> temp;
map<long long, set<long long> > mpx, mpy;

void work (long long x, long long y, long long u, long long v, map<long long, set<long long> > &i, map<long long, set<long long> > &j)
{
	if (i[x].empty() || abs(x) > 1e9 || abs(y) > 1e9)
		return;
	temp.clear();
	auto bg = i[x].lower_bound(y + u), ed = i[x].upper_bound(y + v);
	for (auto it = bg; it != ed; it ++ )
	{
		ans ++;
		temp.push_back((*it));
	}
	for (auto p : temp)
	{
		j[p].erase(x);
		i[x].erase(p);
	}
}

int main()
{
	scanf("%lld %lld %lld %lld", &n, &m, &x, &y);
	for (long long i = 1, u, v; i <= n; i ++ )
	{
		scanf("%lld %lld", &u, &v);
		mpx[u].insert(v);
		mpy[v].insert(u);
	}
	for (long long i = 1; i <= m; i ++ )
	{
		cin >> op >> c;
		if (op == 'U')
		{
			work(x, y, 0, c, mpx, mpy);
			y = y + c;
		}
		if (op == 'D')
		{
			work(x, y, -c, 0, mpx, mpy);
			y = y - c;
		}
		if (op == 'L')
		{
			work(y, x, -c, 0, mpy, mpx);
			x = x - c;
		}
		if (op == 'R')
		{
			work(y, x, 0, c, mpy, mpx);
			x = x + c;
		}
	}
	cout << x << ' ' << y << ' ' << ans << '\n';
	return 0;
}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...