当前位置: 代码迷 >> 综合 >> Rope Folding
  详细解决方案

Rope Folding

热度:65   发布时间:2024-01-11 14:53:47.0

Contest2892 - 2021个人训练赛第39场

Rope Folding

时间限制: 1 Sec 内存限制: 64 MB

题目描述
Farmer John has a long rope of length L (1 <= L <= 10,000) that he uses for various tasks around his farm. The rope has N knots tied into it at various distinct locations (1 <= N <= 100), including one knot at each of its two endpoints.

FJ notices that there are certain locations at which he can fold the rope back on itself such that the knots on opposite strands all line up exactly with each-other:
在这里插入图片描述

Please help FJ count the number of folding points having this property. Folding exactly at a knot is allowed, except folding at one of the endpoints is not allowed, and extra knots on the longer side of a fold are not a problem (that is, knots only need to line up in the areas where there are two strands opposite each-other). FJ only considers making a single fold at a time; he fortunately never makes multiple folds.

输入

  • Line 1: Two space-separated integers, N and L.
  • Lines 2…1+N: Each line contains an integer in the range 0…L specifying the location of a single knot. Two of these lines will always be 0 and L.
    输出
  • Line 1: The number of valid folding positions.
    样例输入
5 10
0
10
6
2
4

样例输出

4

**题意:**有个线段,上面有结点,求在几个位置可以让俩边结点重合,一段超出部分的结点不算。允许完全在一个结处折叠,但不允许在一个端点折叠,求有效折叠位置的数量。
**思路:**枚举。因为不是每个折叠位置都是整数位置,可能有0-1之间0.5的情况。
代码:

#include<iostream>
using namespace std;
int n,len,s=0;
int a[11000];
int fun2(int x)
{
    int l=x,r=x+1;//两点之间,eg:0.5 while(l>=0&&r<=len){
    if(a[l]!=a[r]) return 0;//如果两边结点没有重回,停止,该点不能折叠 l--;r++;}return 1;//可以,加一 
}
int fun1(int x)
{
    int l=x,r=x;while(l>=0&&r<=len){
    if(a[l]!=a[r]) return fun2(x);l--;r++;}if(fun2(x)==1) return 2;//如果在两点间的中点也可以,共两个 return 1;//该点可以,加一 
}
int main()
{
    cin>>n>>len;for(int i=1;i<=n;i++){
    int x;cin>>x;a[x]=1;//如果该位置有结点,a[x]=1,标记一下,与没有节点的区分 }s+=fun2(0);for(int i=1;i<len;i++){
    s+=fun1(i);}cout<<s;return 0;
}