比赛场次 615
比赛名称 2024暑假C班集训5
比赛状态 已结束比赛成绩
开始时间 2024-07-05 08:00:00
结束时间 2024-07-05 12:00:00
开放分组 全部用户
注释介绍 由于 COGS 特性,题目顺序完全乱序,请自行决策开题顺序。
组题人主观难度顺序:T2 < T1 < T4 < T3。
题目名称 充电宝
输入输出 charger.in/out
时间限制 1000 ms (1 s)
内存限制 256 MiB
测试点数 10 简单对比
用户 结果 时间 内存 得分
GravatardarkMoon AAAAAAAAAA 0.300 s 9.47 MiB 100
Gravatar┭┮﹏┭┮ AAAAAAAAAA 0.309 s 11.32 MiB 100
Gravatarwdsjl AAAWWWWWWW 0.117 s 6.60 MiB 30
Gravatarliuyiche AAATTTTTTT 7.041 s 7.36 MiB 30
Gravatar123 AAWWWWWWWW 0.265 s 94.09 MiB 20
Gravatar健康铀 AAEEEEEEEE 1.639 s 91.35 MiB 20
GravatarUntitled AAWTTTTTTT 7.174 s 6.71 MiB 20
Gravatar陆晨洗 AATTTTTTTT 8.012 s 6.53 MiB 20
GravatarAeeE5x AATTTTTTTT 8.018 s 7.22 MiB 20
Gravatar蜀山鸭梨大 AATTTTTTTT 8.019 s 8.17 MiB 20
Gravatarwzh0425 AATTTTTTTT 8.303 s 7.22 MiB 20
Gravatarflyfree EEAEEEEEEE 1.591 s 43.88 MiB 10
Gravatar彭欣越 AEEEEEEEEE 1.705 s 21.09 MiB 10
Gravatardream ATWTTTTTTT 8.030 s 7.22 MiB 10
Gravatardjyqjy WWWWWWWWWW 0.405 s 6.42 MiB 0
Gravatar李奇文 WWEEEEEEEE 1.823 s 5.85 MiB 0

充电宝

★★   输入文件:charger.in   输出文件:charger.out   简单对比
时间限制:1 s   内存限制:256 MiB

【题目背景】

我的一个机器人朋友 - dottle 

多头在 NOI 2022 晚会上的精彩演讲 

【题目描述】

作为机器人,波特日常生活中没法找到充电插座,就需要充电宝维持运转。

一天,波特早上出门时,突然发现自己的电量严重不足。

波特有 $n$ 个充电宝,依次排成一排,第 $i$ 个充电宝的种类编号为 $a_i$。

波特可以拿上第 $l$ 个到第 $r$ 个充电宝,并且第 $l$ 个和第 $r$ 个充电宝必须和 $[l,r]$ 中的其它充电宝种类都不同。

平常波特可以用自己强大的大脑快速算出答案,但现在他的电量趋近于零,已经无法计算。

所以,请你帮忙算出波特有多少种拿充电宝的方案。

形式化题面

给定 $n$ 个正整数 $a_1,a_2,a_3,\ldots,a_n$

求满足 $a_l \neq a_{l+1\sim r},a_r \neq a_{l\sim r-1}$ 的 $[l,r]$ 的数量。

【输入格式】

第一行一个整数 $n$。

第二行 $n$ 个正整数,第 $i$ 个数表示 $a_i$。

【输出格式】

一个整数,表示取充电宝的方案数。

【样例输入】

7
1 2 3 4 3 2 5

【样例输出】

13

【样例说明】

方案为:$[1,2],[1,3],[1,4],[1,7],[2,3],[2,4],[3,4],[4,5],[4,6],[4,7],[5,6],[5,7],[6,7]$

大样例

【数据规模与约定】

对于前 10% 的数据,$1\le n\le 100$。

对于前 20% 的数据,$1\le n\le 5\times 10^3$。

另有 10% 的数据,保证 $a$ 是 $1\sim n$ 的一个排列。

对于 100% 的数据,$1\le n\le 2\times 10^5,1\le a_i\le n$。

【来源】

hasy-lgc