2031-折叠绳子

2031. 折叠绳子

原题链接

描述

农夫约翰有一条长度为 L 的绳子，可用于农场周围的各种任务。

绳子在不同的位置有 N 个绳结，包括两个端点处各有一个。

约翰注意到，在某些位置，他可以将绳子对折，这样，相对的绳索上的绳结就可以彼此完全对齐：

请帮助约翰统计具有此属性的折叠点数。

允许在某个绳结处折叠，但不允许在端点绳结处折叠。

折叠后，较长的一侧可以有多余节点。

输入格式 第一行包含两个整数 N 和 L。

接下来 N 行，每行包含一个 0∼L 范围内的整数，表示一个绳结的位置。其中两行包含的数字分别是 0 和 L。

输出格式 输出有效折叠位置的数量。

数据范围 1≤L≤10000, 1≤N≤100

输入样例：

5 10
0
10
6
2
4

输出样例：

4

样例解释 有效折叠位置为 1, 2, 3, 8。

分析

• 对于样例：
  • 
  • 可知，枚举 j 作为折叠点，若 j 点之前所有的点 a[j] 与 a[2i-j] 的状态相同，则说明该折叠点是有效的。
  • 注意绳子的折叠点可能为 0.5、1.5，故将绳子长度变为原来的 2 倍处理。

代码

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

const int N = 1e6 + 3;

int a[N];

int main() {
    int n, l;
    cin >> n >> l;  // 读入

    for (int i = 0; i < n; i++) {
        int p;
        cin >> p;
        a[p * 2]++;  // 在 2*p 的位置记录节点
    }

    int ans = 0;

    for (int i = 0; i <= l * 2; i++) {  // l*2 使得绳子长度变为原来的2倍
        int flag = 1;
        for (int j = 0; j < i; j++) {  // 枚举第 i 个节点作为折点
            if (i + i - j <= l * 2 && a[i + i - j] != a[j]) {  // 当 i+i-j 在 2*l 范围内且 a[j] 与 a[i+i-j] 的状态不相同，说明 i 不是有效折点
                flag = 0;
                break;
            }
        }
        if (flag) {
            ans++;
        }
    }

    cout << ans << endl;  // 输出答案

    return 0;
}