CF653C Bear and Up-Down 题解
Zzzzzzzm
2021-02-01 11:27:07
## 题目分析
首先找到错误的部分，如$123$中$23$之间有一个错误。**因为只能换一次，所以最多有四个错误，这里我们分类讨论。**
四个时以上：
**绝对没有可能。**
四个时：
1.两两相邻：只能交换两个错误的之间点点才有可能改正所有错误，即$2123343$中$21$，$12$，$34$，$43$中都有错误，只有交换$1$与$4$才有可能。
2.其他都不可能
三个时：1.有一对两两相邻:两个连续错误处只能中间那个交换才有可能，另一处前后皆可。2.其他不可能
两个时：1.错误不相临错误前后调整都有可能。2.错误相邻：搜索整个数组与中间点交换
一个时：错误前后搜索整个数组与之替换
没有时：$O$($n^2$)，无法处理，~~思考了半天没有想到，发现根本无此类测试点~~。
# Code
```cpp
#include<bits/stdc++.h>
using namespace std;
int a[1500010], n;
bool ok(int i){
if(i < 1 || i >= n) return 1;
if((i&1) && a[i] >= a[i+1]) return 0;
if(!(i&1) && a[i] <= a[i+1]) return 0;
return 1;
}
vector<int> w;
bool check(int x, int y){
bool flag = 1;
swap(a[x], a[y]);
for(int i = 0; i < w.size(); i++) if(!ok(w[i])) flag = 0;
if(!ok(x) || !ok(x-1) || !ok(y) || !ok(y-1)) flag = 0;
swap(a[x], a[y]);
return flag;
}
int main(){
scanf("%d", &n);
for(int i = 1; i <= n; i++) scanf("%d", &a[i]);
for(int i = 1; i < n; i++) if(!ok(i)) w.push_back(i);
if(w.size() > 4){
printf("0\n");
return 0;
}
int x = w[0];
int ans = 0;
for(int i = 1; i <= n; i++) if(check(i, x)) ans++;
for(int i = 1; i <= n; i++) if(check(i, x+1)) ans++;
if(check(x, x+1)) ans--;
printf("%d\n", ans);
return 0;
}
```