首页 > 其他分享 >ARC138 B - 01 Generation 题解

ARC138 B - 01 Generation 题解

时间:2024-09-08 21:15:29浏览次数:10  
标签:01 No Generation 题解 序列 操作 Yes 倒推

ARC138 B - 01 Generation

思路

考虑逆向思维,很容易想到可以优先从后面删掉0(操作B的逆向操作),然后如果前面是0则删掉它并将序列翻转(操作A的逆向操作),一直重复这两个步骤直到字符串为空。如果中途无法操作,输出No,否则输出Yes

下面我们来证明这个方法的正确性:

  • 首先,假设有一个序列\(A\)按照上述方法输出No,但正确答案为Yes
  • 则一定在某一步(可能是第一步)只能先倒推操作A,而不是操作B,设这一步执行前的序列为\(S\);
  • 此时,令\(N=|S|\),则\(S_1=S_N=0\);
  • 如果先倒推操作A,得到\((S_2,S_3,\dots,S_{N-1},1)\)
  • 如果先倒推操作B,得到\((S_1,S_2,\dots,S_{N-1})\)
  • 对比两个序列,发现先倒推操作B不会影响后续倒推A的结果,因此,序列\(S\)不存在
  • 结论:做法正确。

代码

代码实现时,没有必要真正翻转序列,只需记录当前翻转的状态(\(0\)或\(1\)),记为\(\text{flipped}\),则实际的\(A_i=A_i'\oplus\text{flipped}\)(其中\(A_i'\)为输入的\(A\),\(\oplus\)表示异或/XOR操作)。

删除时可以使用deque或者数组\(l,r\)端点记录。

#include <cstdio>
#define maxn 200005
using namespace std;

bool a[maxn];

int main()
{
	int n = 0;
	char c;
	while((c = getchar()) != '\n')
		n = (n << 3) + (n << 1) + (c ^ 48);
	for(int i=0; i<n; i++, getchar())
		a[i] = getchar() ^ 48;
	bool flipped = false;
	for(int l=0, r=n-1; a[l]==flipped; flipped^=1, l++)
		while(!a[r] ^ flipped)
			if(l > --r)
				return puts("Yes"), 0;
	puts("No");
	return 0;
}

标签:01,No,Generation,题解,序列,操作,Yes,倒推
From: https://www.cnblogs.com/stanleys/p/18403490/arc138_b

相关文章

  • AtCoder题解集锦
    注:本文原发表于CSDN,现已停止更新。原文如下:AtCoder题解集锦自己从全网整理的一些优质AtCoder题解,目前只有ABC(AtCoderBeginnerContest)的C~F。不定期更新。如您有更多需求,欢迎私信我或在评论区留言!\(\rarr\)题解列表传送门用法表格查找找到对应比赛的行找到对应......
  • AtCoder Beginner Contest 250 C~E 题解
    C-AdjacentSwaps题目大意\(N\)个球从左到右排成一列。开始时,从左往右的第\(i\)个球上写着数字\(i\)。请执行\(Q\)个操作,第\(i\)个操作如下:令\(j=~N\)个球中写着数字\(x_i\)的球的位置如果\(j=N\),将其与第\(j-1\)个球交换;否则,与第\(j+1\)个球交换。求所有操作后的球上分......
  • UNIQUE VISION Programming Contest 2022(AtCoder Beginner Contest 248)C~D 题解
    C-DiceSum题目大意有多少个整数序列\(A=(A_1,\dots,A_N)\)符合如下条件:\(1\leA_i\leM\)\(\sum\limits_{i=1}^NA_i\leK\)输出答案,对\(998244353\)取模。\(1\leN,M\le50\)\(N\leK\leNM\)输入格式\(N~M~K\)输出格式输出答案,对\(998244353\)取模。分析艹C题......
  • AtCoder Beginner Contest 252 A~G 题解
    前言这是我第一次写7题(A~G)的ABC题解,若有写得不好或者不到位的地方请多多指教,我将万分感激,感谢大家的支持!A-ASCIIcode题目大意给定正整数\(N\),输出ASCII码是\(N\)的字母。\(97\leN\le122\)输入格式\(N\)输出格式输出ASCII码是\(N\)的字母。分析注意a对应\(97\)......
  • AtCoder Beginner Contest 192 A~D 题解
    A-Star题目大意下一个大于\(X\)的\(100\)的倍数与\(X\)的差是多少?\(1\leX\le10^5\)输入格式\(X\)输出格式输出答案。样例\(X\)输出\(140\)\(60\)\(1000\)\(100\)分析下一个大于\(X\)的\(100\)的倍数是\((\lfloorX/100\rfloor+1)\times100\)。所......
  • AtCoder Beginner Contest 191 A~D 题解
    A-VanishingPitch题目大意一个球的速度是\(V~\text{m/s}\),它飞了\(T\)秒后会隐形,飞了\(S\)秒时会接触隐形。球在飞了\(D\)米后,人能看见它吗?输出Yes或者No。\(1\leV\le1000\)\(1\leT<S\le1000\)\(1\leD\le1000\)输入格式\(V~T~S~D\)输出格式输出答案。样例......
  • AtCoder Beginner Contest 190 A~D 题解
    A-VeryVeryPrimitiveGame题目大意Takahashi和Aoki在玩一个游戏。游戏规则是这样的:最开始,Takahashi和Aoki分别有\(A\)和\(B\)颗糖。他们将轮流吃一颗糖,第一个无法吃糖的人算输。如果\(C=0\),那么Takahashi先吃;如果\(C=1\),那么Aoki先吃。请输出最终胜者的名字。\(0\le......
  • AtCoder Beginner Contest 194 A~E 题解
    A-IScream题目大意在日本,有如下四种冰淇淋产品:至少有\(15\%\)的milksolids和\(8\%\)的milkfat的产品称为“冰淇淋”;至少有\(10\%\)的milksolids和\(3\%\)的milkfat且不是冰淇淋的产品称为“冰奶”;至少有\(3\%\)的milksolids且不是冰淇淋或冰奶的产品称为“乳冰**”;......
  • AtCoder Beginner Contest 198 A~E 题解
    A-Div题目大意两个男孩要分\(N\)颗糖。问一共有几种分法(每个男孩都必须分到糖)?\(1\leN\le15\)输入格式\(N\)输出格式将答案输出为一个整数。样例\(N\)输出\(2\)\(1\)\(1\)\(0\)\(3\)\(2\)分析这题说白了就是将\(N\)分成\(A\)和\(B\)两个正整数......
  • AtCoder Beginner Contest 196 A~E 题解
    A-DifferenceMax题目大意给定四个整数\(a,b,c\)和\(d\)。我们要选择两个整数\(x\)和\(y\)(\(a\lex\leb\);\(c\ley\led\))。输出最大的\(x-y\)。\(-100\lea\leb\le100\)\(-100\lec\led\le100\)输入格式\(a~~b\)\(c~~d\)输出格式输出最大的\(x-y\)。样例\(......