专栏文章

AtCoder Beginner Contest 380 A~E

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

文章操作

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

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

A - 123233

洛谷链接
AtCoder链接

题目

给你一个 66（位）正整数 NN。
请判断 NN 是否满足以下所有条件。
  • 在 NN 的数字中，数字 11 恰好出现一次。
  • 在 NN 的数字中，数字 22 恰好出现两次。
  • 在 NN 的数字中，数字 33 恰好出现三次。

代码

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

using namespace std;

string s;
int a[3];

int main()
{
	cin >> s;
	for (int i = 0; i < s.length(); i ++ )
	{
		if (s[i] == '1')
			a[0] ++;
		else if (s[i] == '2')
			a[1] ++;
		else if (s[i] == '3')
			a[2] ++;
	}
	if (a[0] == 1 && a[1] == 2 && a[2] == 3)
		puts("Yes");
	else
		puts("No");
	return 0;
}

B - Hurdle Parsing

洛谷链接
AtCoder链接

题目

伊洛哈有一个长度为 N (N≥1)N\ (N \ge 1) 的正整数序列 A=(A1,A2,…,AN)A=(A_1,A_2, \ldots ,A_N)。
她用 AA 生成了如下字符串 SS：
  • 以 | 开始。
  • 对于 i=1,2,…,Ni=1,2, \ldots ,N，依次执行以下操作：
    • 将 AiA_i 个 - 加到 SS 的末尾。
    • 然后，在 SS 的末尾添加一份 |。
在生成的字符串 SS 中，重建序列 AA。

代码

题意就是求每对 | 中 - 的个数。
CPP
#include <bits/stdc++.h>

using namespace std;

string s;
int cnt;

int main()
{
	cin >> s;
	for (int i = 1; i < s.length(); i ++ )
	{
		if (s[i] == '-')
			cnt ++;
		else
		{
			cout << cnt << ' ';
			cnt = 0;
		}
	}
	return 0;
}

C - Move Segment

洛谷链接
AtCoder链接

题目

给你一个长度为 NN 的字符串 SS，它由 0 和 1 组成。
将 SS 中开头的第 KK 个 1 字块移动到第 (K−1)(K-1) 个 1 字块的后面，并输出得到的字符串。
保证 SS 至少包含 KK 个 1 字块。
下面是更精确的描述。
  • 让 Sl…rS_{l \ldots r} 表示 SS 从 ll（第 3 个字符）到 rr（第 3 个字符）的子串。
  • 如果 SS 的子串 Sl…rS_{l \ldots r} 满足以下所有条件，我们就定义它为 1 字块：
    • Sl=Sl+1=⋯=Sr=S_l=S_{l+1}=\cdots=S_r=1
    • l=1l=1 或 Sl−1=S_{l-1}=0
    • r=Nr=N 或 Sr+1=S_{r+1}=0
  • 假设 SS 中所有的 1 块都是 Sl1…r1,…,Slm…rmS_{l_1 \ldots r_1}, \ldots ,S_{l_m \ldots r_m}，其中 l1<l2<⋯<lml_1<l_2< \cdots <l_m。
    然后，我们定义长度为 NN 的字符串 TT，将第 KK 个 1 字块移动到紧接着的第 (K−1)(K-1) 个 1 字块的位置，如下所示：
    • 当 1≤i≤rK−11 \le i \le r_{K-1} 时，Ti=SiT_i=S_i。
    • 当 rK−1+1≤i≤rK−1+(rK−lK)+1r_{K-1}+1 \le i \le r_{K-1}+(r_K-l_K)+1 时，Ti=T_i=1。
    • 当 rK−1+(rK−lK)+2≤i≤rKr_{K-1}+(r_K-l_K)+2 \le i \le r_K 时，Ti=T_i=0。
    • 当 rK+1≤i≤Nr_K+1 \le i \le N 时，Ti=SiT_i=S_i。

思路

我们找到第 k−1k-1 个段的结尾和第 kk 个段的开头和结尾，当输出到第 k−1k-1 个段的结尾时，输出第 kk 个段，也就是第 kk 个段的开头到结尾的 11，当输出到第 kk 个段的开头时，直接跳到第 kk 个段的结尾。
那么怎么找第 k−1k-1 个段的结尾和第 kk 个段的开头和结尾呢？遍历一遍字符串，当找到一个前面不是 11 的 11 时，当前段编号加 11；当找到一个 11 时，当前这段的结尾往后挪一个；当找到一个 00 的时候，把开头移到当前加 11，结尾移到当前，解释一下，因为当前是 00，所以只有当前加 11 有可能是 11，而到后面的 11 时会把结尾往后移动一个，所以结尾要提前往前一个，要不然已经是 l=rl=r，即 ll 到 ll，有一个了，如果再在第一个往后移动一个就会多 11 个。

代码

可能会因无法输入 s + 1 而 CE，换一下 C++ 版本就好了。
CPP
#include <bits/stdc++.h>

using namespace std;

int n, k, qr, dl, dr, lx = 1, rx, op;
char s[500010];

int main()
{
	cin >> n >> k >> s + 1;
	for (int i = 1; i <= n && op <= k; i ++ )
	{
		if (s[i] == '1')
		{
			if (s[i-1] != '1')
				op ++;
			rx ++;
			if (op == k - 1)
				qr = rx;
			if (op == k)
			{
				dl = lx;
				dr = rx;
			}
		}
		else if (s[i] == '0')
		{
			lx = i + 1;
			rx = i;
		}
	}
	for (int i = 1; i <= n; i ++ )
	{
		if (i == dl)
		{
			i = dr;
			continue;
		}
		cout << s[i];
		if (i == qr)
		{
			for (int j = dl; j <= dr; j ++ )
				cout << 1;
		}
	}
	return 0;
}

D - Strange Mirroring

洛谷链接
AtCoder链接

题目

有一个由大写和小写英文字母组成的字符串 SS。
我们对 SS 进行以下运算 1010010^{100} 次：
  • 首先，将 SS 中的大写字母改为小写，将小写字母改为大写，从而创建一个字符串 TT。
  • 然后，依次连接 SS 和 TT 形成新的 SS。
回答 QQ 查询。第 ii 次查询如下：
  • 在完成所有运算后，找出 SS 开头的第三个字符 KiK_i。

思路

我们可以发现，每次长度都会变成原来的两倍，那么如果我们对半砍，如果在一半的后面就给它对应到前一半的对应位置，记一次翻转，直到对应到 11 或 22 的位置。好像不是很好理解是不是，但其实就是这样了，那么我们看一个图，重讲一遍。
我们知道，这一个序列是同时变动的，所以我们可以把序列认为是一个字符，把 kk 对 nn 取余，就是序列的第几个位置，把 kk 除以 nn 上取整就是在第几个序列，那么图片中每一个 00 就是代表了一个序列，红色代表原序列，绿色代表翻转了的序列。
假设我们要找的位置时在四号三角形的那个序列里的，那么它一定三号三角形那个序列翻转后得到的，那么三号序列就是二号三角形那个序列翻转后得到的，直到第二个（一号）序列。这样是翻转了三次，加上它是第二个本来就翻转了一次，一共是四次，但是翻转四次和没翻转没有区别，所以就是原序列的那个位置，如果是奇数次翻转，那么就是原序列的那个位置转换一下大小写即可。
这时已经对上面的简洁的描述有了一定的理解，我们继续理解一下为什么是在一半的后面。如果是在五号序列的话，那么我们会直接到二号序列，在第二次对半砍的时候并不会有变化，那么如果我们仍然记了一次翻转，就会多翻转一次。 那么大部分需要理解的内容就结束了，那么怎么实现对半砍呢？我们可以发现每次对半砍完长度都是除以 22 了，那么我们只需要找到这个数（假设为 xx ）满足条件的 yy：2y≤x≤2y+12^y \le x \le 2^{y+1}，那么我们就可以从 2y2^y 开始砍（这里对砍的定义是把这个位置化成小于这个长度的一个位置）。
那么我们现在解决了从多长开始砍，那么具体怎么砍呢？我们只要判断当前位置是否大于当前要砍的长度，如果不大于就行了，如果大于就减去这个长度，翻转次数加 11 即可。再将长度除以 22，再继续砍。
最后判断一下翻转次数的奇偶性，翻一下即可。

代码

可能会因无法输入 s + 1 而 CE，换一下 C++ 版本就好了。
CPP
#include <bits/stdc++.h>

using namespace std;

char s[200010];
long long q, n, w[200010], cn, k, g, gk, t, a, c;

char bian(long long x)
{
	if (x >= 'a' && x <= 'z')
		return x - 'a' + 'A';
	else
		return x - 'A' + 'a';
}

int main()
{
	cin >> s + 1 >> q;
	n = strlen(s + 1);
	while (q -- )
	{
		cn = 0;
		scanf("%lld", &k);
		g = (k + n - 1) / n;
		gk = k % n;
		if (gk == 0)
			gk = n;
		t = g;
		a = 1;
		while (t)
		{
			w[++ cn] = a;
			t >>= 1;
			a *= 2;
		}
		c = 0;
		for (long long i = cn; i > 1; i -- )
		{
			if (g > w[i])
			{
				g -= w[i];
				c ++;
			}
		}
		if (g == 2)
			c ++;
		c %= 2;
		if (c == 1)
			cout << bian(s[gk]) << ' ';
		else
			cout << s[gk] << ' ';
	}
	return 0;
}

E - 1D Bucket Tool

洛谷链接
AtCoder链接

题目

一行中有 NN 个单元格，编号为 11 至 NN。
在每个 1≤i<N1 \le i < N 单元格中，ii 和 i+1i+1 单元格相邻。
最初，ii 单元格被涂上了颜色 ii。
给您 QQ 个查询。请按顺序处理它们。每个查询属于以下两种类型之一。
  • 1 x c：将以下单元格重新涂成颜色 cc：通过重复移动到与当前单元格相同颜色的相邻单元格，从单元格 xx 到达的所有可到达单元格。
  • 2 c:打印涂上颜色 cc 的单元格数量。

思路

用并查集维护几个信息：fif_i，代表 ii 的父亲；lil_i，代表 ii 所在颜色块的左端点；rir_i，代表 ii 所在颜色块的右端点。
其他再记录几个信息：colicol_i，代表 ii 的颜色；cnticnt_i，代表颜色 ii 的个数。
那么初始化都是很好做的。
为了方便，我们使一个点的正确左右端点存储在它的终极祖先（也就是 find(x)find(x) 的结果）中，也就是说，这个点本身的左右端点（lil_i 和 rir_i），不一定是正确的，可能会比原来的小（补充一下：不会比原来的大，因为我们如果要改变颜色，是这个点左右的一个颜色块一起改变，不会说一个颜色块内的一部分颜色改变，颜色块缩小，只会和这个颜色块的外部一样颜色合并起来，颜色块变大），而这个点的终极祖先的左右端点（lfind(i)l_{find(i)} 和 rfind(i)r_{find(i)}）一定是正确的。
对于操作 22，直接输出 cntccnt_c 即可。
操作 11 稍微有点复杂，但也比较好理解。首先，我们让 xx 成为 xx 的终极祖先（因为各种信息 xx 的终极祖先都有）。
其次，我们把原来颜色的个数减少颜色块长度个，要改变到的颜色的个数加上颜色块长度个，把 xx 的颜色改变一下。
然后我们判断一下这个颜色块和左右颜色是否变得相同了，如果颜色一样了，就合并到一起。
那么如何合并呢？首先，肯定要把一个的父亲赋成另一个，然后我们把那个在上面那个（终极祖先）的左右端点改变一下（左端点赋成两个左端点靠前的那个，右端点赋成两个右端点靠后的那个）。

代码

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

using namespace std;

int n, q, op, x, c, f[500010], cnt[500010], col[500010], l[500010], r[500010];

int find(int x)
{
	if (x == f[x])
		return x;
	else
		return f[x] = find(f[x]);
}

void merge(int x, int y)
{
	x = find(x);
	y = find(y);
	f[x] = y;
	l[y] = min(l[y], l[x]);
	r[y] = max(r[y], r[x]);
}

int main()
{
	scanf("%d %d", &n, &q);
	for (int i = 1; i <= n; i ++ )
	{
		f[i] = col[i] = l[i] = r[i]= i;
		cnt[i] = 1;
	}
	while (q -- )
	{
		scanf("%d", &op);
		if (op == 1)
		{
			scanf("%d %d", &x, &c);
			x = find(x);
			cnt[c] += r[x] - l[x] + 1;
			cnt[col[x]] -= r[x] - l[x] + 1;
			col[x] = c;
			if (l[x] > 1 && c == col[find(l[x] - 1)])
				merge(l[x]-1,x);
			if (r[x] < n && c == col[find(r[x] + 1)])
				merge(r[x] + 1, x);
		}
		else
		{
			scanf("%d", &c);
			cout << cnt[c] << '\n';
		}
	}
	return 0;
}

评论

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

正在加载评论...