2031. 折叠绳子
本文最后更新于 768 天前,其中的信息可能已经有所发展或是发生改变。

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;

}

暂无评论

发送评论 编辑评论


				
|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
(╯‵□′)╯︵┴─┴
 ̄﹃ ̄
(/ω\)
∠( ᐛ 」∠)_
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ`)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ( ̄∇ ̄o)
ヾ(´・ ・`。)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò。)
Σ(っ °Д °;)っ
( ,,´・ω・)ノ"(´っω・`。)
╮(╯▽╰)╭
o(*////▽////*)q
>﹏<
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
颜文字
Emoji
小恐龙
花!
上一篇
下一篇