A - Rearranging ABC

题目

给你一个长度为

3

的字符串

S

，由大写英文字母组成。

请判断是否有可能重新排列

S

中的字符，使其与字符串 ABC 匹配。

代码

CPP

#include <bits/stdc++.h>

using namespace std;

string s;

int main()
{
	cin >> s;
	sort(s.begin(), s.end());
	if (s == "ABC")
		puts("Yes");
	else
		puts("No");
	return 0;
}

B - Avoid Rook Attack

洛谷链接

AtCoder链接

题目

有一个由

64

个正方形组成的网格，网格中有

8

行和

8

列。

(i,j)

表示从上面

(1 \le i \le 8)

起第

i

行，从左边

(1 \le j \le 8)

起第

j

列的正方形。

每个方格要么是空的，要么有棋子放在上面。方格的状态由长度为

8

的

8

字符串序列

(S_1,S_2,S_3, \ldots ,S_8)

表示。如果

S_i

的第

j

的字符是 .，则

(1 \le i \le 8,1 \le j \le 8)

为空；如果是 #，则有棋子。

您要将棋子放在空方格上，使它不能被任何现有棋子吃掉。

放置在方格

(i,j)

上的棋子可以吃掉满足以下任一条件的棋子：

放置在第 $i$ 行的一个位置上。
放置在 $j$ 列的一个位置上。

例如，位于

(4,4)

位置上的棋子可以吃掉位于下图中蓝色所示位置上的棋子：

您可以将棋子放在几个位置上？

代码

CPP

#include <bits/stdc++.h>

using namespace std;

string ip;
int rt, pi[10], pj[10];

int main()
{
	for (int i = 1; i <= 8; i ++ )
	{
		cin >> ip;
		for (int j = 0; j < 8; j ++ )
		{
			if (ip[j] == '#')
			{
				pi[i] = 1;
				pj[j + 1] = 1;
			}
		}
	}
	for (int i = 1; i <= 8; i ++ )
	{
		for (int j = 1; j <= 8; j ++ )
		{
			if (pi[i] + pj[j] == 0)
				rt += 1;
		}
	}
	cout << rt << '\n';
	return 0;
}

C - Avoid Knight Attack

洛谷链接

AtCoder链接

题目

有一个由

N^2

个正方形组成的网格，网格中有

N

行和

N

列。让

(i,j)

表示从上面

(1 \le i \le N)

起第

i

行，从左边

(1 \le j \le N)

起第

j

列的正方形。

每个方格要么是空的，要么放了一颗棋子。网格上有

M

个棋子，而第

k(1 \le k \le M)

个棋子被放置在

(a_k,b_k)

个方格上。

您想要将棋子放在空方格上，使其不能被任何现有棋子吃掉。

放置在位置

(i,j)

上的棋子可以吃掉满足以下任何条件的棋子：

置于方格 $(i+2,j+1)$ 上。
置于方格 $(i+1,j+2)$ 上。
置于方格 $(i-1,j+2)$ 上。
置于方格 $(i-2,j+1)$ 上。
置于方格 $(i-2,j-1)$ 上。
置于方格 $(i-1,j-2)$ 上。
置于方格 $(i+1,j-2)$ 上。
置于方格 $(i+2,j-1)$ 上。

在这里，涉及不存在的正方形的条件被认为是不满足的。

例如，放在

(4,4)

位置上的棋子可以吃掉下图中蓝色所示位置上的棋子：

您可以将棋子放在几个位置上？

思路

可用方格的数量可达

10^{18}-3

，数量庞大；而不可用方格的数量不超过

9M

，完全可以维持。

通过在类似哈希集的数据结构中对不可用方格进行重复管理，可以找到所需的方格数。

时间复杂度约为

O(M)

或

O(M \log M)

。

代码

CPP

#include <bits/stdc++.h>

using namespace std;

int n, m, x, y;
set<pair<int, int> > bad_cell;
vector<pair<int, int> > knight_move{{2, 1}, {1, 2}, {-1, 2}, {-2, 1}, {-2, -1}, {-1, -2}, {1, -2}, {2, -1}};

int main()
{
	scanf("%d %d", &n, &m);
	for (int i = 0; i < m; i ++ )
	{
		scanf("%d %d", &x, &y);
		bad_cell.emplace(x, y);
		for (const auto& [dx, dy] : knight_move)
		{
			if (1 <= x + dx && x + dx <= n && 1 <= y + dy && y + dy <= n)
				bad_cell.emplace(x + dx, y + dy);
		}
	}
	cout << static_cast<long>(n) * n - size(bad_cell) << '\n';
	return 0;
}

D - Many Segments 2

洛谷链接

AtCoder链接

题目

给你两个长度分别为

N

、

L=(L_1,L_2, \ldots ,L_N)

和

R=(R_1,R_2, \ldots ,R_N)

的正整数序列，以及一个整数

M

。

求满足以下两个条件的整数对

(l,r)

的个数：

$1 \le l \le r \le M$ 。
对于每一个 $1 \le i \le N$ ，区间 $\lbrack l,r \rbrack$ 并不完全包含区间 $\lbrack L_i,R_i \rbrack$ 。

思路

这个题要倒着做，我们先统计出有多少个是不符合要求的，再用总数减去。（总数怎么算就不说了，从所有的选两个点做为左右端点，再加上一个的）。

不符合要求，即包含了某一个区间，如果只有一个区间是好做的，我们只要把左端点及左边点的个数和右端点及右边点的个数匹配（乘起来）即可，那么如果有多个区间，就有重复问题（其实和一个区间没什么关系）。

那么如何解决重复问题呢？那么我们要定住一个端点，右端点，那么对于每个右端点，我们该如何统计有多少个以这个点结尾的区间是不合法的呢？

那就是有几个左端点是不合法的。而我们知道如果一个区间

\lbrack l,r \rbrack

是不合法的那么区间

\lbrack l-1,r \rbrack

一定也是不合法的，因为区间

\lbrack l-1,r \rbrack

包含区间

\lbrack l,r \rbrack

，那么它一定包含区间

\lbrack l,r \rbrack

包含的那个给出区间，即可得出它也不合法。

那么有了这个性质，我们就只需要对于每个右端点把最靠后（最大）的使得它不合法的左端点存下来，前面的就都不合法了，即可求出前面的问题。

那么这个问题怎么做呢？如果个右端点和某些给出区间的右端点重合，那么就是要包含这些区间中的一个，肯定包含那个左端点最靠后的合适，那么对这些所有的取个最大值即可。

但是给出区间的右端点不一定非要恰好在这个点上，给出区间的右端点在当前点的前面即可，那么如果把这种也算上，其实也就是对第一种情况的数做一个从

1

到当前的取最大值（最靠后）即可，因为到前面已经不合法了，到当前这个一定更不合法，而我们又想让

l

更靠后，所以是这样。

最后统计一下答案即可。

代码

CPP

#include <bits/stdc++.h>

using namespace std;

long long n, m, f[200010], l[200010], r[200010], ans;

int main()
{
	scanf("%lld %lld", &n, &m);
	ans = m * (m - 1) / 2 + m;
	for (long long i = 1; i <= n; i ++ )
	{
		scanf("%lld %lld", &l[i], &r[i]);
		f[r[i]] = max(f[r[i]], l[i]);
	}
	for (long long i = 1; i <= m; i ++ )
	{
		f[i] = max(f[i - 1], f[i]);
		ans -= f[i];
	}
	cout << ans << '\n';
	return 0;
}

AtCoder Begginer Contest 377 A~D

文章操作

A - Rearranging ABC

题目

代码

B - Avoid Rook Attack

题目

代码

C - Avoid Knight Attack

题目

思路

代码

D - Many Segments 2

题目

思路

代码

相关推荐

评论

AtCoder Begginer Contest 377 A~D