题解 P1881 【绳子对折】

yagyagyag · 2019-07-21 18:02:09 · 题解

这题本身很水，但有一个很坑的地方，就是非整数点也要考虑

扫了一下题解，好像神犇都是用 +0.5 两个check()函数 之类的方法解决，这里我提供另外一个算法

*2

把位置，长度都*2,这样原来如果是小数(当然小数部分一定是0.5)，现在的答案就会变为整数，处理的时候就会方便

首先标记节点位置

for (int i=1;i<=n;i++){
        int x;
        cin>>x;
        x*=2;//注意这里要*2 
        used[x]=1;
    }

只要一个check()

bool check(int l,int r,int mid)
{
    while (l>=0 && r<=L){
        while (!used[l]) l--;
        while (!used[r]) r++;
        if (l>=0 && r<=L){
            if (abs(l-mid)!=abs(r-mid)) return 0;
            l--;r++;
        }
    }
    return 1;
}

类似于快排，固定好边界，往左找节点，往右找节点，最后再判断一下边界，计算与mid的距离。如果不相等直接return 0，最后函数结尾return 1，表示该位置可行

然后是穷举

    for (int i=1;i<L;i++){
        int l=i-1,r=i+1;
        if (check(l,r,i) && i/2<L/2/*这里要注意，因为答案*2，所以还要判断这个点在原来的轴上是否存在*/){
            ans++;
        } 
    }

最后就是输出答案

CODE

#include<bits/stdc++.h>
using namespace std;
int n,L;
bool used[20005];
bool check(int l,int r,int mid)
{
    while (l>=0 && r<=L){
        while (!used[l]) l--;
        while (!used[r]) r++;
        if (l>=0 && r<=L){
            if (abs(l-mid)!=abs(r-mid)) return 0;
            l--;r++;
        }
    }
    return 1;
}
int main()
{
    cin>>n>>L;
    L*=2;
    for (int i=1;i<=n;i++){
        int x;
        cin>>x;
        x*=2;//注意这里要*2 
        used[x]=1;
    }

    int ans=0;
    for (int i=1;i<L;i++){
        int l=i-1,r=i+1;
        if (check(l,r,i) && i/2<L/2/*这里要注意，因为答案*2，所以还要判断这个点再原来的轴上是否存在*/){
            ans++;
        } 
    }
    cout<<ans<<endl;
    return 0;
 }