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