本文最后更新于 815 天前,其中的信息可能已经有所发展或是发生改变。
2031. 折叠绳子
描述
农夫约翰有一条长度为 L 的绳子,可用于农场周围的各种任务。
绳子在不同的位置有 N 个绳结,包括两个端点处各有一个。
约翰注意到,在某些位置,他可以将绳子对折,这样,相对的绳索上的绳结就可以彼此完全对齐:
请帮助约翰统计具有此属性的折叠点数。
允许在某个绳结处折叠,但不允许在端点绳结处折叠。
折叠后,较长的一侧可以有多余节点。
输入格式
第一行包含两个整数 N 和 L。
接下来 N 行,每行包含一个 0∼L 范围内的整数,表示一个绳结的位置。其中两行包含的数字分别是 0 和 L。
输出格式
输出有效折叠位置的数量。
数据范围
1≤L≤10000,
1≤N≤100
输入样例:
输出样例:
4
5 10
0
10
6
2
4
样例解释
有效折叠位置为 1,2,3,8。
分析
- 对于样例:
- 可知,枚举
j
问绳子上的折叠点,若j
点之前所有的点a[j]
与a[i+i-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;
}
}
ans+=flag;
}
cout<<ans-2<<endl; //ans-2去除作为端点的两个结点
return 0;
}