A - 11/22 String

题目

本问题中 11/22 字符串的定义与问题 C 和 E 中的定义相同。

满足以下所有条件的字符串

T

称为 11/22 字符串：

$|T|$ 是奇数。这里， $|T|$ 表示 $T$ 的长度。
从 $1$ 到 $(\frac{|T|+1}{2}-1)$ 的字符都是 1。
第 $(\frac{|T|+1}{2})$ 个字符是 /。
从 $(\frac{|T|+1}{2}+1)$ 到 $|T|$ 的字符都是 2。

例如，11/22、111/222 和 / 是 11/22 字符串，但 1122、1/222、11/222、22/11 和 /2/2/211 则不是。

给定长度为

N

的字符串

S

由 1、2 和 / 组成，请判断

S

是否是 11/22 字符串。

代码

CPP

#include <bits/stdc++.h>

using namespace std;

int t;
string s;

int main()
{
	scanf("%d", &t);
	cin >> s;
	if (t % 2 == 0 || s[(t + 1) / 2 - 1] != '/')
		goto it;
	for (int i = 0; i < (t + 1) / 2 - 1; i ++ )
	{
		if (s[i] != '1')
			goto  it;
	}
	for (int i = (t + 1) / 2; i < (int)s.length(); i ++ )
	{
		if (s[i] != '2')
			goto it;
	}
	puts("Yes");
	return 0;
it:
	puts("No");
	return 0;
}

B - 1122 String

洛谷链接

AtCoder链接

题目

当且仅当字符串

T

满足以下三个条件时，它才被称为 1122 字符串：

$\lvert T \rvert$ 是偶数。这里， $\lvert T \rvert$ 表示 $T$ 的长度。
对于满足 $1 \le i \le \frac{|T|}{2}$ 的每个整数 $i$ ， $T$ 的第 $(2i-1)$ 个和第 $2i$ 个字符都相等。
每个字符在 $T$ 中出现的次数正好是 0 或 2。也就是说， $T$ 中包含的每个字符在 $T$ 中恰好出现两次。

给定一个由小写英文字母组成的字符串

S

，如果

S

是一个 1122 字符串，则打印 Yes，否则打印 No。

思路

只需检查给定字符串是否满足 1122 字符串的三个条件即可。

第三个条件可以以任何方式重新表述，例如，只要满足第一个和第二个条件，我们就可以使用这种重新表述的条件。这里，

S_i

表示

S

的第

i

个字符。

$S_1,S_3, \ldots ,S_{|S|-1}$ 都是不同的。
对于 $S$ 的每个字符 $S_i$ ， $S$ 中恰好有两个元素与之重合。也就是说，对于介于 $1$ 和 $|S|$ 之间的所有整数 $i$ ，恰好有两个索引 $j$ 与之重合。 $(1 \le j \le |S|)$ 与 $S_i=S_j$ 重合。

原解的复杂度为

O(\lvert S \rvert+C)

。这里，

C

是

S

中可能使用的不同字符数；这次是

C=26

。在重新表述的条件中，天真的实现可能会花费

O(\lvert S \rvert^2)

时间，但在我们的例子中是

\lvert S \rvert \le 100

，这是可以接受的。因此，可以用任何方法检查该条件，问题也就迎刃而解了。

代码

CPP

#include <bits/stdc++.h>

using namespace std;

int n, cnt[26];
string s;

int main()
{
	cin >> s;
	n = s.length();
	if (s.length() % 2 == 1)
	{
		puts("No");
		return 0;
	}
	for (int i = 0; i < (n / 2); i ++ )
	{
		if (s[2 * i] != s[2 * i + 1])
		{
			puts("No");
			return 0;
		}
	}
	for (int i = 0; i < n; i ++ )
		cnt[s[i] - 'a'] ++;
	for (int i = 0; i < 26; i ++ )
	{
		if ((cnt[i] != 0) && (cnt[i] != 2))
		{
			puts("No");
			return 0;
		}
	}
	puts("Yes");
	return 0;
}

C - 11/22 Substring

洛谷链接

AtCoder链接

题目

满足以下所有条件的字符串

T

称为 11/22 字符串：

$|T|$ 是奇数。这里， $|T|$ 表示 $T$ 的长度。
从 $1$ 到 $(\frac{|T|+1}{2}-1)$ 的字符都是 1。
第 $(\frac{|T|+1}{2})$ 个字符是 /。
第 $(\frac{|T|+1}{2}+1)$ 个到第 $|T|$ 个字符都是 2。

例如，11/22、111/222 和 / 是 11/22 字符串，但 1122、1/222、11/222、22/11 和 /2/2/211 则不是。

给定长度为

N

的字符串

S

由 1、2 和 / 组成，其中

S

包含至少一个 /。

请找出长度为 11/22 的

S

的连续子串的最大长度。

思路

模拟。先枚举找到 /，再向两边枚举，判断此时的字串是不是 11/22 字符串。如果是，就更新答案。

代码

CPP

#include <bits/stdc++.h>

using namespace std;

int n, ans, sum;
char a[200010];

int main()
{
	scanf("%d", &n);
	for (int i = 1; i <= n; i ++ )
		cin >> a[i];
	for (int i = 1; i <= n; i ++ )
	{
		if (a[i] == '/')
		{
			sum = 1;
			for (int j = i - 1, k = i + 1; j >= 1 && k <= n; j --, k ++ )
			{
				if (a[j] == '1' && a[k] == '2')
					sum += 2;
				else
					break;
			}
			ans = max(ans, sum);
		}
	}
	cout << ans << '\n';
	return 0;
}

AtCoder Beginner Contest 381 A~C

文章操作

A - 11/22 String

题目

代码

B - 1122 String

题目

思路

代码

C - 11/22 Substring

题目

思路

代码

相关推荐

评论

AtCoder Beginner Contest 381 A~C