2018-2019赛季多校联合新生训练赛第四场 18-12-09

这次的题目还是不错的,考察了比较多的细节处理。

Problem A:数一数

题目描述
星期天早上,小明开始做数学家庭作业。因为小明成绩很优异,觉得题目太简单了,思考出道难点的数学题去学校考考同学,他注意到:数学书的第10页和第11页在同一张纸上,但第11页和第12页不在同一张纸上。
哈哈,题目有了,请问数学书的第x页到第y页共有多少张纸呢?
例如:该书的第81页到第92页,共有7张纸。

输入
一行两个数x、y如题所述,用空格隔开。

输出
一个数,表示纸张数。

1
2
3
4
样例输入
81 92
样例输出
7

提示
50%:0<y-x<=15;
100%:1<=x,y<=longint;0<y-x<longint。

分析:这个题只要拿一本书稍微看一下就找到规律了,注意就是有多少张纸要包含那页自身的那一张纸,我是把输入的页数全部转化为左边偶数那一页。

1
2
3
4
5
6
7
8
9
10
11
12
13
#include<bits/stdc++.h>
using namespace std;
int main()
{
long long x,y;
cin>>x>>y;
if(x%2==1)
x--;
if(y%2==1)
y--;
cout<<((y-x)/2)+1;
return 0;
}

Problem B:博物馆

题目描述
从前,有一个偌大的博物馆,每天都会有数以万计的人们来参观,欣赏这里的艺术作品。这一天,博物馆来了N批人,第i批人有Ai个人以及一个导游组成,他们依次到达,但同时也有一些批次的人离开,由于人次太多,博物馆的管理人员递给你一些人数表,就请你来统计一下剩下多少人。

输入
第一行是个整数N,接下来N行。每行两个数,第一个数X,如果X=0则后面接一个数Ai,表示来了Ai个人;如果X=1,那么接下来就有一个数Y,表示来的人中的第Y批离开了。

输出
一个数,表示剩下多少人。

1
2
3
4
5
6
7
8
9
10
样例输入
6
0 5
0 6
1 1
0 7
0 8
1 3
样例输出
16

提示
有四批人,每批人要加上一位导游,分别是6,7,8,9人,离开的是第1和3批,即走了6+8=14人,剩7+9=16人。

对于30%的数据,1≤N≤100,1≤Ai≤1000;
对于100%的数据,1≤N≤1000000,1≤Ai≤1000000。
保证:X只为0或1,Y一定符合要求。

分析:这个题需要注意的地方是离开的那个Y,是第Y批,而不是离开Y个人(我眼瞎)我设置了一个数组存进入的批次人数,并累积总人数,注意输入的人数要加上一个导游。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include<bits/stdc++.h>
using namespace std;
long long aha[1000010];
int main()
{
int n;
cin>>n;
long long a,b;
long long sum=0;
long long k=1;
while(n)
{
cin>>a;
if(a==0)
{
cin>>b;
aha[k]=b+1;
k++;
sum+=b+1;
}
if(a==1)
{
cin>>b;
sum-=aha[b];
}
n--;
}
cout<<sum;
return 0;
}

Problem C:旅游

题目描述
Lanlan的好朋友Qiqi来到了东莞,她决定带Qiqi去东莞的名胜景区旅游,以此增进友谊。但Qiqi不喜欢去拥挤度大于k的景点,而且旅游的时间不能是断开的。Lanlan现在知道了明天n个连续时间景区的拥挤度,她想知道她最多能陪Qiqi旅游多久。

输入
第一行两个整数n,k。
第二行有n个整数表示每个时间的拥挤程度(数值小于1000)。

输出
一个整数表示Lanlan最多能陪Qiqi的时间。

1
2
3
4
5
样例输入
20 2
1 1 1 3 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
样例输出
16

提示
60%的数据 N<=1000
100%的数据 N<=100000
分析:用数组来存这些拥挤程度,遍历时小于等于k时计数器自增,遇到超过k的拥挤度时,记录k的最大值,并将k初始化。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
#include<bits/stdc++.h>
using namespace std;
int main()
{
int n,k;
cin>>n>>k;
int a[100010];
for(int i=0;i<n;i++)
{
cin>>a[i];
}
int t=0;
int Max=0;
for(int i=0;i<n;i++)
{
if(a[i]<=k)
{
t++;
}
if(a[i]>k||i==n-1)
{
Max=max(Max,t);
t=0;
}
}
cout<<Max;
return 0;
}

Problem D:17倍

题目描述
学习程序设计的Lanlan记得老师给她布置的第一个任务是:输入一个数N,然后输出17*N的值。当然这个任务非常简单,经过一段时间的学习,兰兰有了一些的进步,老师又布置了一个类似的任务,只是变更了一个条件,输入的N是一个二进制数,输出的值也要是二进制表示的。
现在请帮助Lanlan完成这个任务。

输入
一个二进制表示的数N。

输出
二进制表示的17*N。

1
2
3
4
样例输入
10110111
样例输出
110000100111

提示
10110111相当于十进制的183,于是183*17=3111,二进制形式是110000100111。

30%的数据N的位数小于25位
50%的数据N的位数小于50位
100%的数据N的位数小于1000位
这个题,搞了半天从2进制变成10进制,又从10进制变成2进制,终于调试完成了,样例能过了,然后发现好像10进制的溢出了,然后就疯狂wa了。(自闭ing)
先放上错误代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
/*#include<bits/stdc++.h>
using namespace std;
int main()
{
char n[1010];
cin>>n;
int len=strlen(n);
long long a=0;
int k=0;
while(1)
{
if(n[len-1]!='0')
{
a+=pow(2,k);
}
len--;
if(len==0)
break;
k++;
}
a*=17;
string shu;
k=0;
while(a!=0)
{
if(a%2==1)
{
shu+='1';
}
if(a%2==0)
{
shu+='0';
}
a/=2;
k++;
}
for(int i=k-1;i>=0;i--)
{
cout<<shu[i];
}
return 0;
}*/

其实可以不用转化成十进制的,还是脑子太死了,直接用二进制加上16次就可以了,两个二进制字符串先反转,然后从第一位开始一位对一位的相加,满二进一,用一个变量来保存下一位是否需要进位。
由于是在二进制数中,所以进位数只可能是1或0,当前位可以通过a[k]+b[k]-48-48+jw来判断,这个式子只有4种情况分别是3,2,1,0,四种对应的本位计算结果是1,0,1,0,需要注意的点是,如果最后一位还需要进位,那么只需要在最高为加上个字符1就可以了。并且要统一a和b的长度,a前最高位之前可以用字符0补齐。
感谢马鸿儒同学的博客:https://www.cnblogs.com/baccano-acmer/p/10092910.html

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
#include<bits/stdc++.h>
using namespace std;
int main()
{
string a;
cin>>a;
reverse(a.begin(),a.end());//逆转字符串
string b=a;
int lenb;
for(int i=1;i<=16;i++)
{
int lena=a.size();
for(int k=0;k<b.size()-lena;k++)//统一a,b的字符串长度,a的高位用‘0’补齐
a+='0';

lenb=b.size();
int jinwei=0;
for(int k=0;k<lenb;k++)
{
if(jinwei+a[k]+b[k]-48-48==3)//本位加进位数的和,只有下面四种情况
{
b[k]='1';
jinwei=1;
}
else if(jinwei+a[k]+b[k]-48-48==2)
{
b[k]='0';
jinwei=1;
}
else if(jinwei+a[k]+b[k]-48-48==1)
{
b[k]='1';
jinwei=0;
}
else if(jinwei+a[k]+b[k]-48-48==0)
{
b[k]='0';
jinwei=0;
}
}
if(jinwei==1)//最高为还要进位
b=b+'1';
}
reverse(b.begin(),b.end());
cout<<b;
return 0;
}

Problem F:移动石子

题目描述
期待已久的“清明”假期终于到了。清明节是中华民族几千年来留下的优良传统,它有利于弘扬孝道亲情,唤醒家庭共同记忆,促进家庭成员乃至民族的凝聚力和认同感。
小学生卡卡西非常高兴,因为清明前后正是踏青的好时光,他终于可以和小伙伴们一起出去踏青了!然而,天公不作美,假期的第一天就下起了雨,卡卡西只能放弃出游计划,待在家里。
期间,无聊的卡卡西和小伙伴玩了一个博弈游戏:
在一个给定的 n×n 的棋盘上,有一个石头被放在棋盘的左上角。他们轮流移动石头。每一回合,每个人只能把石头向上,下,左,右四个方向移动一格,并且要求移动到的格子之前不能被访问过。谁不能移动石头了就算输。假如小卡卡西先移动石头,而且两人都以最优策略走步,问最后谁能赢?

输入
输入有多组数据。
输入第一行包含一个整数n,表示棋盘的规模。
当输入n为0时,表示输入结束。

输出
对于每组数据,如果小卡卡西最后能赢,则输出“Kakashi”,否则输出“Lost”,每一组答案独占一行。

1
2
3
4
5
样例输入
2
0
样例输出
Kakashi

提示
对于20%的数据,保证1<=n<=10;
对于40%的数据,保证1<=n<=1000;
对于所有的数据,保证1<=n<=10000。
分析:这个题就比较搞笑了,什么叫以最有策略走步?难道还能给对手下套么?然后开始了dfs之旅,显然很痛苦,,炸了。
然后抱着豁出去,试一试,看不见(最后一句)的态度,计算各自总数,偶数胜,奇数输,然后就a了,,(疯狂嘲笑自己)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#include<bits/stdc++.h>
using namespace std;
int main()
{
int n;
while(scanf("%d",&n)&&n!=0)
{
long long sum;
sum=n*n;
if(sum%2==0)
cout<<"Kakashi"<<endl;
else
cout<<"Lost"<<endl;
}
return 0;
}

Problem I:幸运数字III

题目描述
小李非常喜欢数字4和7,看到一个数字他就想快速计算出因子里面分别有几个4和7,但是智商捉急的他总是要算很久,喜欢编程的你能够帮助他吗?

输入
第一行一个整数n(3<=n<=2^60),表示给定的数字。

输出
两个用空格隔开的数字,分别表示给定数字的因子中4和7的个数。

1
2
3
4
样例输入
112
样例输出
2 1

提示
112=447

看到题目第一眼竟然想到了新生热身赛的那个欧皇签到题2333.
分析:这个题目只需要将入的数字反复除以4,7直到不能被这两个数整除为止。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include<bits/stdc++.h>
using namespace std;
int main()
{
long long n;
cin>>n;
long long four=0,seven=0;
while(n!=0)
{
if(n%4!=0&&n%7!=0)
break;
if(n%4==0)
{
four++;
n/=4;
}
if(n%7==0)
{
seven++;
n/=7;
}
}cout<<four<<' '<<seven;
return 0;
}

Problem J:英雄卡

题目描述
小李非常迷恋收集各种干脆面里面的英雄卡,为此他曾经连续一个月都只吃干脆面这一种零食,但是有些稀有英雄卡真的是太难收集到了。后来某商场搞了一次英雄卡兑换活动,只要你有三张编号连续的英雄卡,你就可以换任意编号的英雄卡。小李想知道他最多可以换到几张英雄卡(新换来的英雄卡不可以再次兑换)。

输入
第一行,共一个整数n(1<=n<=10000),表示小李拥有的英雄卡数。
第二行,共n个空格隔开的数字ai(1<=ai<=100000),表示英雄卡的编号。

输出
输出仅有一行,共1个整数,表示小李最多可以换到的英雄卡。

1
2
3
4
5
6
样例输入
复制样例数据
6
3 1 2 4 4 5
样例输出
1

提示
1 2 3三张编号连续,可以换一张,换完后剩下4 4 5,不符合兑换规则,无法继续兑换。
第一次提交的时候,忘记可能会有重复的情况,所以就白给了一次。
后来想了一种方法,索性就用桶,这个数字出现一次对应的桶就加一,然后再对整个数组来找连续的三个进行兑换。
寻找的方法是,从第一个桶开始,往后找两个桶,取这三个桶的最小值,也就是这三个桶可以兑换数目的最大值,然后都减去这个值,继续从第二个桶开始……。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
#include<bits/stdc++.h>
using namespace std;
int main()
{
int n;
cin>>n;
int a[100010]={0};
for(int i=1;i<=n;i++)
{
int b;
cin>>b;
a[b]++;
}
int k=0;
int Min=0;
for(int i=1;i<=99997;i++)
{
Min=min(a[i],a[i+1]);
Min=min(Min,a[i+2]);
k+=Min;
a[i+1]-=Min;
a[i+2]-=Min;
}
cout<<k;
return 0;
}

Peoblem K:最强阵容

题目描述
拿着新换来的英雄卡,小李满心欢喜的准备和同学们PK一下。
他们的游戏规则非常简单,双方把自己的牌绕成一圈,然后指定一个起点,从该张牌开始顺时针方向往后取,谁取出的字符串字典序更小(从左到右开始比较,碰到第一个不一样的字符进行比较,比较规则为a<b<…<z)谁将获得胜利。具体规则可参考样例。虽然现在小李的牌已经很好了,但是你能不能帮他快速算出起始位置,使得他能够派出最强阵容。

输入
第一行n(1<=n<=30000),表示共有n张牌。
第二行共n个用一个空格隔开的小写字母,表示给定的一圈牌起始序列。

输出
仅一个整数,能获得最小字典序字符串的起点位置。如果有多个位置开始的字符串一样,则输出最小的那个位置,且第一个位置从1开始。

1
2
3
4
5
样例输入
4
b c a b
样例输出
3

提示
四个位置取出的字符串分别为bcab,cabb,abbc,bbca,显然最小位置是3。
分析:一开始直接是第一个字母开始试,每当遇到比前面都小的字符串再更新位置,于是超时了,不知道怎么优化。看了马鸿儒同学的优化程序,进行了改进,把输入时遇到的最小字符的位置进行一遍记录,存入数组,这样会极大地缩小时间复杂度。
ps:这是第一次使用string结构,真滴好用啊。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
#include<bits/stdc++.h>
using namespace std;
int main()
{
int n;
cin>>n;
char t,minc='z';
string b;
for(int i=0;i<n;i++)
{
cin>>t;
b+=t;
minc=min(minc,t);
}//输入字符,并找到最小字符。
n=b.size();
int weizhi[30000];
int weizhishu=0;
for(int i=0;i<n;i++)//记录最小字符的位置,只有从这里开始取,才能使整个串最小
{
if(b[i]==minc)
{
weizhi[weizhishu]=i;
weizhishu++;
}
}
b+=b;
string mins=b;
string s="";
int ans;
for(int i=0;i<weizhishu;i++)//从刚才记录的字符里面开始找。
{
s="";
for(int k=weizhi[i];k<weizhi[i]+n;k++)//最小字符往后找n个
{
s+=b[k];
}
if(mins>s)
{
mins=s;
ans=weizhi[i]+1;//注意是最小字符的位置加一。
}
}
cout<<ans;
return 0;
}

坚持原创技术分享,您的支持也将成为我的动力!
-------------本文结束感谢您的阅读-------------
undefined