You can not select more than 25 topics
Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.
|
|
|
|
|
# [第一题](https://www.jisuanke.com/problem/T3698)
|
|
|
|
|
|
|
|
|
|
|
|
### 题目描述
|
|
|
|
|
|
给定一个长度为 $n$ 的 $01$ 序列 $a$，你可以对其进行若干次操作。
|
|
|
|
|
|
|
|
|
|
|
|
对于一次操作，选择 $1\leq l\leq r\leq n$，将 $a_l,…,a_r$ 中的 $01$ 翻转。
|
|
|
|
|
|
|
|
|
|
|
|
例如，将 `1010010` 翻转为 `0101101`。
|
|
|
|
|
|
|
|
|
|
|
|
请你构造一个序列 $b$，使得序列 $a$ 变为序列 $b$ 的最少操作次数最多。
|
|
|
|
|
|
|
|
|
|
|
|
### 输入格式
|
|
|
|
|
|
|
|
|
|
|
|
输入共两行。
|
|
|
|
|
|
|
|
|
|
|
|
第一行输入一个正整数 $n$。
|
|
|
|
|
|
|
|
|
|
|
|
第二行输入长度为 $n$ 的 $01$ 序列 $a$。
|
|
|
|
|
|
|
|
|
|
|
|
### 输出格式
|
|
|
|
|
|
|
|
|
|
|
|
输出共一行，输出长度为 $n$ 的 $01$ 序列 $b$。
|
|
|
|
|
|
|
|
|
|
|
|
### 数据范围
|
|
|
|
|
|
|
|
|
|
|
|
对于 $30%$ 的数据，有 $1\leq n\leq 5$。
|
|
|
|
|
|
|
|
|
|
|
|
对于另外 $20%$ 的数据，有 $1\leq n\leq 10$。
|
|
|
|
|
|
|
|
|
|
|
|
对于另外 $20%$ 的数据，有 $1\leq n\leq 20$。
|
|
|
|
|
|
|
|
|
|
|
|
对于 $100%$ 的数据，有 $1\leq n\leq 10^5$，$n$ 为奇数。
|
|
|
|
|
|
|
|
|
|
|
|
<div style="page-break-after: always"></div>
|
|
|
|
|
|
|
|
|
|
|
|
### 题解
|
|
|
|
|
|
|
|
|
|
|
|
通过观察发现，偶数位(下标从$0$开始)的,需要翻成相反的，奇数位需要不动。
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
#### 参考代码
|
|
|
|
|
|
|
|
|
|
|
|
```c++{.line-numbers}
|
|
|
|
|
|
#include <bits/stdc++.h>
|
|
|
|
|
|
|
|
|
|
|
|
using namespace std;
|
|
|
|
|
|
const int N = 1e5 + 10;
|
|
|
|
|
|
char a[N];
|
|
|
|
|
|
|
|
|
|
|
|
int main() {
|
|
|
|
|
|
freopen("reverse.in", "r", stdin);
|
|
|
|
|
|
freopen("reverse.out", "w", stdout);
|
|
|
|
|
|
|
|
|
|
|
|
int n;
|
|
|
|
|
|
cin >> n;
|
|
|
|
|
|
for (int i = 0; i < n; i++) cin >> a[i];
|
|
|
|
|
|
|
|
|
|
|
|
for (int i = 0; i < n; i++)
|
|
|
|
|
|
if (i % 2 == 0)
|
|
|
|
|
|
cout << !(a[i] - '0');
|
|
|
|
|
|
else
|
|
|
|
|
|
cout << a[i];
|
|
|
|
|
|
|
|
|
|
|
|
return 0;
|
|
|
|
|
|
}
|
|
|
|
|
|
```
|
|
|
|
|
|
|
|
|
|
|
|
<div style="page-break-after: always"></div>
|
