P16112 「o.OI R-1」青蛙平衡树

ooliver 发布于 1 天前 55 次阅读 OI

AI 摘要

想在一维上解决问题？青蛙平衡树告诉你：不对称的直线上连续点，中心对称才是王道！补空或者延长，总共就两条路，怎么走都能搞定。

P16112 「o.OI R-1」青蛙平衡树

一个或两个点是一定中心对称的，所以先特判掉这种情况。

对于一般情况，先尝试能不能只在一维上做。

不难发现直线上连续的点一定是中心对称的，所以第一个点直接输出 $(1,1)$，后面要是保持中心对称，就继续向右把线延长就行了。

对于不对称的点，直接空一个输出。接下来要是要保证中心对称，就返回来把这个空补上；要是接下来还要保证不对称，就向左延长之前那个线段。

代码：

C++
#include<bits/stdc++.h>
using namespace std;

#define int long long
const int N=2e5+5;
int n,x=0,l=1,r=1;
int a[N];

signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    cin>>n;
    for(int i=1;i<=n;i++) cin>>a[i];
    if(a[1]==0||(n>1&&a[2]==0)) {cout<<"No";return 0;}
    cout<<"Yes\n1 0\n";
    for(int i=2;i<=n;i++){
        if(a[i]&&x) cout<<x<<" 0\n",x=0;
        else if(a[i]&&!x) cout<<++r<<" 0\n";
        else if(!a[i]&&x) cout<<--l<<" 0\n";
        else if(!a[i]&&!x) cout<<(r+=2)<<" 0\n",x=r-1;
    }
    return 0;
}