文章目录
- 题目背景
- 题目描述
- 输入格式
- 输出格式
- 样例
- 样例输入
- 样例输出
- 数据范围与提示
- 思路及部分实现
- 完整代码
- 文章小结
题目背景
在洛谷中,打卡不只是一个简单的鼠标点击动作,通过每天在洛谷打卡,可以清晰地记录下自己在洛谷学习的足迹。通过每天打卡,来不断地暗示自己:我又在洛谷学习了一天,进而帮助自己培养恒心、耐心、细心。此外,通过打卡,还可以获取经验值奖励,经验值的多少在一定程度上反映了你在洛谷的资历和成就。通过打卡累积活跃值,渐渐升级,会让你感觉“离神犇越来越近了”。
题目描述
洛谷的打卡系统与其他网站的打卡系统一样,连续”打卡天数越多,每次打卡获得的奖励也就越多,同时连续天数加上一天。然而,于其他网站只要一天不打卡,连续天数就要清零。与其他网站不同的是,洛谷的打卡更具有人性化,如果多天不打卡,连续天数仅仅只是减少,当遗漏天数越少,减少的天数也就越少。规则是减少 2 n − 1 2^{n-1} 2n−1 天, n n n 为连续遗漏天数。连续天数在下一次打卡时清算,打卡连续天数不会小于 0 0 0。也就是说,如果每隔一天打卡,那么连续天数就不会变了。
当连续天数达到以下天数时,给予不同的活跃值奖励:
1 1 1 天:奖励 1 1 1(千里之行,始于足下)
3 3 3 天:奖励 2 2 2(坚持 3 3 3 天了,加油!)
7 7 7 天:奖励 3 3 3(曜日轮回)
30 30 30 天:奖励 4 4 4(月圆月缺,习惯养成)
120 120 120 天:奖励 5 5 5(坚持四个月了!)
365 365 365 天:奖励 6 6 6(一年四季都坚持下来了!真不容易!)
小 a N N N 天前在洛谷注册了一个账号,虽然当时立志每天都要打卡,但发现这不太容易做到。现在知道他 N N N 天的的打卡记录,小 a 希望得知他通过打卡,在 N N N 天能获得多少活跃值?
输入格式
第 1 1 1 行一个整数 N N N。
接下来 N N N 行,每行一个整数 1 1 1 或 0 0 0,代表当天是否打过卡。
输出格式
一个整数,表示获得的活跃值!
样例
样例输入
12
1
1
1
1
1
0
0
0
1
0
1
1
样例输出
12
数据范围与提示
样例说明:
第 1 1 1 天: 1 1 1 :开始打卡!获得 1 1 1 点经验,共 1 1 1 点,连续 1 1 1 天。
第 2 2 2 天: 1 1 1 :获得 1 1 1 点经验,共 2 2 2 点,连续 2 2 2 天。
第 3 3 3 天: 1 1 1 :获得 2 2 2 点经验,共 4 4 4 点,连续 3 3 3 天。
第 4 4 4 天: 1 1 1 :获得 2 2 2 点经验,共 6 6 6 点,连续 4 4 4 天
第 5 5 5 天: 1 1 1 :获得 2 2 2 点经验,共 8 8 8 点,连续 5 5 5 天
第 6 6 6 天: 0 0 0 :由于要去趟火星,没有网络不得已而断签
第 7 7 7 天: 0 0 0
第 8 8 8 天: 0 0 0
第 9 9 9 天: 1 1 1 :我回来了,可惜连续天数变成 5 − 4 = 1 5-4=1 5−4=1 天了 TQT……获得 1 1 1 点经验,共 9 9 9 点,连续 2 2 2 天
第 10 10 10 天: 0 0 0 :啊,事情太多给忘了
第 11 11 11 天: 1 1 1 :连续天数变成 2 − 1 = 1 2-1=1 2−1=1 天。获得 1 1 1 点经验,共 10 10 10 点,连续 2 2 2 天。
第 12 12 12 天: 1 1 1 :获得 2 2 2 点经验,共 12 12 12 点,连续 3 3 3 天。
小 a:弄个自动打卡机,怎么样?
kkksc03:这不符合洛谷的规则的!
对于 100 % 100\% 100% 的数据, 1 ≤ N ≤ 1 0 3 1\leq N\leq 10^3 1≤N≤103。
题目传送门(题目源自洛谷)
思路及部分实现
简单的模拟题,可以在输入的过程中完成计算,最后输出答案。
考虑用四个 i n t int int 类型的变量分别储存当前连续打卡天数( c n t cnt cnt )、当前连续没打卡天数( c c c )、当前获得的活跃值( a n s ans ans )、当前打卡情况(即是否打卡, x x x)。
- 如果 x = 1 x=1 x=1,即表示当前天已打卡,将 c n t cnt cnt 加一,这时又要分为两种情况:
- 如果 c > 0 c>0 c>0,说明前一天没有打卡,需将 c n t cnt cnt 减去 2 c − 1 2_{c-1} 2c−1 作为没有签到的惩罚,由于 c c c 已经被使用过了,所以要将 c c c 清零。
这时 c n t cnt cnt 可能小于 0 0 0,所以用一个特判保证 c n t cnt cnt 最少为 0 0 0。
if(c>0) cnt-=pow(2,c-1),c=0; if(cnt<0) cnt=0;
- 如果 c = 0 c=0 c=0,说明前一天打卡了,无需做出特殊处理。
- 如果 c > 0 c>0 c>0,说明前一天没有打卡,需将 c n t cnt cnt 减去 2 c − 1 2_{c-1} 2c−1 作为没有签到的惩罚,由于 c c c 已经被使用过了,所以要将 c c c 清零。
- 如果 x = 1 x=1 x=1,即表示当前天没有打卡,将 c c c 加一。
再添加上 x = 1 x=1 x=1 时对获得活跃值的统一处理:
- 如果 1 ≤ c n t ≤ 2 1 \leq cnt \leq 2 1≤cnt≤2,活跃值加 1 1 1。
- 如果 3 ≤ c n t ≤ 6 3 \leq cnt \leq 6 3≤cnt≤6,活跃值加 2 2 2。
- 如果 7 ≤ c n t ≤ 29 7 \leq cnt \leq 29 7≤cnt≤29,活跃值加 3 3 3。
- 如果 30 ≤ c n t ≤ 119 30 \leq cnt \leq 119 30≤cnt≤119,活跃值加 4 4 4。
- 如果 120 ≤ c n t ≤ 364 120 \leq cnt \leq 364 120≤cnt≤364,活跃值加 5 5 5。
- 如果 c n t ≥ 365 cnt \geq 365 cnt≥365,活跃值加 6 6 6。
不过笔者由于实在不想打那么多代码,于是又想出来一个更为绝妙的办法:
- 如果 c n t ≥ 1 cnt \geq 1 cnt≥1,活跃值加 1 1 1。
- 如果 c n t ≥ 3 cnt \geq 3 cnt≥3,活跃值加 1 1 1。
- 如果 c n t ≥ 7 cnt \geq 7 cnt≥7,活跃值加 1 1 1。
- 如果 c n t ≥ 30 cnt \geq 30 cnt≥30,活跃值加 1 1 1。
- 如果 c n t ≥ 120 cnt \geq 120 cnt≥120,活跃值加 1 1 1。
- 如果 c n t ≥ 365 cnt \geq 365 cnt≥365,活跃值加 1 1 1。
注意,上方的判断语句是并列的! 代码实现如下:
if(cnt>=1) ans++;
if(cnt>=3) ans++;
if(cnt>=7) ans++;
if(cnt>=30) ans++;
if(cnt>=120) ans++;
if(cnt>=365) ans++;
完整代码
#include<iostream>
#include<cmath>
using namespace std;
int main()
{int n,x,c=0,cnt=0,ans=0;scanf("%d",&n);for(int i=1;i<=n;i++){scanf("%d",&x);if(x==1){cnt++;if(c>0) cnt-=pow(2,c-1),c=0;if(cnt<0) cnt=0;if(cnt>=1) ans++;if(cnt>=3) ans++;if(cnt>=7) ans++;if(cnt>=30) ans++;if(cnt>=120) ans++;if(cnt>=365) ans++;}else c++;}printf("%d",ans);return 0;
}
文章小结
动脑思考是解决手上劳累的不唯一途径 … \dots … … \dots …