UESTC 547 Rope Folding [水坑题]

点击打开题目

题意:在一个长度为L的绳子上打了N个节点,然后让你折叠这个绳子(可以在非整数处),使得这些节点对起来,超出部分忽略。

大水题,个人赛坑死我了,换了两种姿势写都没过,后来才知道可以不再整数位置处折叠。这样枚举两种情况的相邻节点就可以了。

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

const int maxn = 105;
int n, l, v[maxn];


int main() {
    while(~scanf("%d%d", &n, &l)) {
        for (int i = 0; i < n; ++i)
            scanf("%d", v + i);
        sort(v, v + n);
        int cnt = 0;
        for(int i = 0; i < n-1; ++i) {
            int j = i + 1, ok = true;
            double mid = (v[i] + v[j]) / 2.0;
            for(int k = 1; i - k >= 0 && j + k < n; ++k) {
                if(mid - v[i-k] != v[j+k] - mid) {
                    ok = false;
                    break;
                }
            }
            if(ok) ++cnt;
        }
        for(int i = 1; i < n-1; ++i) {
            int ok = true;
            for(int k = 1; i - k >= 0 && i + k < n; ++k) {
                if(v[i] - v[i-k] != v[i+k] - v[i]) {
                    ok = false;
                    break;
                }
            }
            if(ok) ++cnt;
        }
        printf("%d\n", cnt);
    }
    return 0;
}

欢迎留言