#GC4049. GC.2017---. GC.2016.六年级

这套题包含了历年真题，包含了前面我写的博客中的题目，十分重要！！！！要考试的同学可以参考一下！！

此套题限时3小时。

#GC4049. GC.2017.六年级.01.更多闰年

题目描述
在 smoj 网站上，有很多针对小学信息学入门的课程，把这些入门课程的题都刷一遍并理解之后，你就算正式的信息学选手啦。例如课程 9 的某一道题是这样的：
输入两个正整数 a 和 b，表示开始的年份和结束的年份，问从 a 年到 b 年有多少闰年？闰年只需要满足如下两个条件之一：
1.能整除 400
2.能整除 4，但不能整除 100

输入格式
第一行 2 个整数 a 和 b，范围在[1, 1000000000]。

输出格式
一个整数。

样例

输入数据 1

1 10000

Copy

输出数据 1

Copy

提示
对于 80%的数据，b<=100000000。

代码：

#include <bits/stdc++.h>
using namespace std;
int main()
{long long a,b;scanf("%lld%lld",&a,&b);printf("%lld\n",(b/4-(a-1)/4)-(b/100-(a-1)/100)+(b/400-(a-1)/400));return 0;
}

#GC4050. GC.2017.六年级.02.吃萝卜

题目描述
兔子有 N 盒胡萝卜，编号 0 到 N-1，第 i 盒包含 a[i]根胡萝卜。她决定从这些盒子里总共吃 K 根胡萝卜。她一次只吃一根胡萝卜，每次从胡萝卜最多的盒子里选一个胡萝卜吃。如果有多个满足条件的盒子，她将选择其中编号最小的盒子。输出最后一次吃胡萝卜的盒子编号。

输入格式
第 1 行，两个正整数，N 和 K。1 <= N <= 50。
第 2 行，N 个整数，第 i 个整数是 a[i]。1 <= a[i] <= 100。数据保证所有的胡萝卜总和大于等于 K。

输出格式
一个整数，表示最后一次吃胡萝卜的盒子编号.

样例

输入数据 1

2 3
5 8

Copy

输出数据 1

Copy

输入数据 2

2 4
5 8

Copy

输出数据 2

代码：

#include<bits/stdc++.h>
using namespace std;
int main()
{int n,k;cin>>n>>k;vector<int> c(n);for(int i=0;i<n;i++){cin>>c[i];}int s=0;while (k>0) {int t=c[0];int a=0;for(int i=1;i<n;i++) {if(c[i]>t) {t=c[i];a=i;}}c[a]--;k--;s=a;}cout<<s<<endl;return 0;
}

#GC4051. GC.2017.六年级.03.倍数

题目描述
给定一个整数 X，能不能通过调换 X 数字的位置，使得调换之后得到的数是 X 的倍数？
注意：交换数字位置之后得到的数不能有前导 0。如果可以输出"Possible"，否则输出"Impossible"。其中双引号不用输出。

输入格式
多组测试数据。
第一行，一个整数 G,表示有 G 组测试数据。 1 <=G<=11。
每组测试数据格式：

一个正整数 X， X 的范围是[1,1000000]。

输出格式
如果可以输出"Possible"，否则输出"Impossible"。

样例

输入数据 1

Copy

输出数据 1

Possible
Impossible
Possible
Impossible
Impossible

Copy

样例解释

第一组测试数据：
- 可以通过把 142857 交换数字的位置，得到 285714。
- 因为 285714=2*142857,所以满足要求，输出 Possible
第二组测试数据：
- 只能变成 41，但不能整除 14。
第三组测试数据：
- 可以变成 3105, 3105 = 3 * 1035。、
第四组测试数据：
- 不能变化，因为不能出现前导 0。
第五组测试数据：
- 没得变化。

代码：

#include<bits/stdc++.h>
using namespace std;
int main() {int n,m,t,c,i,k,j,s;long long int a[1000],b[11],d[10000];scanf("%d",&t);while(t--) {c=0;scanf("%d",&n);for(i=2;i<10;i++){b[i]=n*i;            }while(n!=0) {a[++c]=n%10;n=n/10;}for(i=2;i<10;i++) {s=0;while(b[i]!=0) {d[++s]=b[i]%10;b[i]=b[i]/10;}m=0;if(s==c){for(j=1;j<=s;j++)for(k=1;k<=s;k++) {if(a[j]==d[k]) {d[k]=-1;m++;break;}}if(m==c) {printf("Possible\n");break;} }if(m!=c&&i==9) {printf("Impossible\n");}}}return 0;
}

#GC4052. GC.2017.六年级.04.猫和兔子

题目描述

一只猫和一只兔子玩简单的猜谜游戏。猫选择了两个不同的正整数 xx 和 yy ，然后他告诉兔子 nn 个正整数，这 nn 个正整数当中，有一个是 x+yx+y ，还有一个是 x−yx−y ，剩余的 n−2n−2 个是任意给的。兔子喜欢大整数，输出 x∗yx∗y 的最大可能值。

输入格式

多组测试数据。

第一行，一个整数 GG ，表示有 GG 组测试数据 ( 1≤G≤51≤G≤5 )。

每组测试数据格式如下：

第 1 行，一个正整数 nn 。( 2≤N≤502≤N≤50 )。

第 2 行， nn 个正整数，空格分开，就是猫给出的那 nn 个正整数，范围都是 [1,100], 数据保证这 nn 个正整数都是不同的，而且一定有解。

输出格式

共 G 行，每行一个正整数。

样例

输入数据 1

5
3
1 4 5
4
1 4 5 8
9
9 8 7 6 5 4 3 2 1
2
2 100
5
50 58 47 57 40

Copy

输出数据 1

Copy

样例解释

对于第 2 组测试数据的解释：

当 x=3x=3 且 y=2y=2 是可行的，此时 x∗yx∗y = 6。

但 x=6x=6 且 y=2y=2 也是可行，此时 x∗y=12x∗y=12。

可以发现，后者更优

代码：

#include <bits/stdc++.h>
#pragma GCC optimize(2)
using namespace std;
int main() {long long n,m,t,x,i,j,s,a[1000],b;scanf("%d",&t);while(t--){scanf("%d",&n);for(i=1;i<=n;i++){scanf("%d",&a[i]);}m=-1;sort(a+1,a+1+n);for(j=1;j<=n;j++){for(i=1;i<=n;i++){x=a[i]*a[i];s=a[j]*a[j];if((x-s)%4==0&&i!=j){b=(x-s)/4;m=max(b,m);}}}printf("%d\n",m);}return 0;   
}

#GC4053. GC.2017.六年级.05.积木

题目描述
乔治喜欢玩积木。目前他有 N 块积木，编号为 1 到 N。所有积木的高度都是正整数，第 i 块积木高度是 H[i]。乔治喜欢用积木堆起尽可能高的塔。他堆积木的过程中，只需要同时满足如下三个规则：

积木必须堆放在同一个列中，一个搭在另一个上面。最终的塔的高度就是构成塔的所有积木的高度总和。
塔中使用的积木的编号从底部到顶部必须是递增的。换句话说，每当乔治把积木 x 放在积木 y 的上面，必须要满足编号 x 大于编号 y。
乔治永远不会把高度是偶数的积木放置在高度是奇数的积木上面。

在满足上面的前提下，塔最高是多高？

输入格式
多组测试数据。
第一行，一个整数 G，表示有 G 组测试数据。1 <= G <= 5。
每组测试数据格式如下：

第 1 行，一个正整数 N。 2 <= N <= 50。
第 2 行，N 个正整数，空格分开，第 i 个整数就是编号为 i 的积木的高度 H[i]， 1 <= H[i] <= 50。

输出格式
共 G 行，每行一个正整数。

样例

输入数据 1

5
2
4 7
2
7 4
1
7
1
4
7
48 1 50 1 50 1 48

Copy

输出数据 1

Copy

样例解释
对于第 5 组测试数据的解释：
从底部往顶部，依次选择第 1、第 3、第 5、第 7 块积木，这样塔的高度是：48+50+50+48=196。

代码：

#include<bits/stdc++.h>
using namespace std;
int k,n,a[100000],b[100000],c[100000],x,s;
int main(){cin>>k;for(int i=1;i<=k;i++){cin>>n;for(int j=1;j<=n;j++){cin>>a[j];b[j]=b[j-1];if(a[j]%2==0){b[j]+=a[j];}}for(int j=n;j>=1;j--){c[j]=c[j+1];if(a[j]%2==1){c[j]+=a[j];}}for(int j=1;j<=n;j++){x=b[j]+c[j];s=max(s,x);}cout<<s<<endl;s=0;for(int j=1;j<=n;j++){b[j]=0;c[j]=0;}}return 0;
}

#GC4054. GC.2017.六年级.06.幸存者

题目描述
有 n 个人，现在他们从左往右站成一列。第 i 个人的位置为 i，且第 i 个人手里握着一把长度为 LiLi 的大刀。指挥者统一指令，n 个人一齐往左边砍去。

对于位置为 i，j 的两个人（i＜j），如果满足 i ≥ j - LjLj，那么位置为 i 的人就会被位置为 j 的人砍死。问：最后有几个人生存下来？

输入格式
第一行输入一个整数 n（1 ≤ n ≤ 1000000），表示有 n 个人。
第二行输入 n 个整数,第 i 个整数是 LiLi（0 ≤ LiLi ≤ 1000000000），LiLi 表示第 i 个人的大刀长度。

输出格式
输出一个整数，表示最后生存下来的人数。

样例

输入数据 1

4
0 1 0 10

Copy

输出数据 1

Copy

输入数据 2

2
0 0

Copy

输出数据 2

Copy

输入数据 3

10
1 1 3 0 0 0 2 1 0 3

Copy

输出数据 3

Copy

提示
有 30% 的数据，n <= 15，另有 20% 的数据，n <= 20000。

代码：

#include<bits/stdc++.h>
using namespace std;
int a[1000010];
int main()
{int n,c,t=0,b;cin>>n;for(int i=1;i<=n;i++){cin>>b;if(b==0) {  continue;}c=max(1,i-b);a[c]++;a[i]--;}c=0;for(int i=1;i<=n;i++){c+=a[i];if(c==0) {t++;}}cout<<t;return 0;
}

#GC4055. GC.2016.六年级.01.工资

题目描述
三只奶牛在农夫FJ的农场辛劳工作了一年，马上到圣诞节了，FJ准备给这3只奶牛发工资。
第一只奶牛的工资固定是a元，第二只奶牛的工资固定是b元。第三只奶牛特别善良，它对工资没什么特别要求，它反而对数学比较感兴趣，它的要求是：三只奶牛的工资加起来的结果必须是2016的倍数。
农夫FJ是比较吝啬的，他必须要满足奶牛的要求，但同时他又想支付的工资最少，那么FJ会支付多少工资给第三只奶牛呢？

输入格式
一行，两个正整数：a和b。 1 <= a,b <= 10000。

输出格式
一个正整数，表示FJ支付多少工资给第三只奶牛。

样例

输入数据 1

1000 800

Copy

输出数据 1

Copy

输入数据 2

2000 3000

Copy

输出数据 2

代码：

#include<bits/stdc++.h>
using namespace std;
int main(){int a,b,c;cin>>a>>b;c=(a+b)/2016+1;c=c*2016;cout<<c-a-b;return 0;
}

#GC4056. GC.2016.六年级.02.数字塔

题目描述

FJ 农场里每一只奶牛的脖子上挂着一个胸牌，胸牌上面印着一个倒三角数字塔，例如奶牛 Bessie 脖子上的胸牌印着：

Copy

你发现什么规律了吗？除了第一行的数字外，其他行的数字都等于其正上方的数字 + 其右上方数字的和，再除以 10 之后的余数。看不懂？除了第一行之外，我们用 a[i][j] 表示第i行第j列的数字，那么 a[i][j] = (a[i-1][j]+a[i-1][j+1])%10 。我们规定 i 从上到下是递增的，j 从左往右是递增的。

所有奶牛的胸牌都符合这个规律！！除了第一行之外，a[i][j] = (a[i-1][j]+a[i-1][j+1])%10。
奶牛 John 是个粗心的家伙，它在玩耍的过程中，胸牌上面的数字大部分都弄丢了，John 胸牌的每一行都只剩下一个数字！其他数字都丢失了。假如我们用 ‘?’ 来表示一个丢失的数字，那么 John 的胸牌可能变成这样了：

4??
?2
1

Copy

农夫知道后非常生气，打算不给 John 发圣诞礼物，除非 John 可以还原胸牌。John 希望你能帮助它还原胸牌，你能做到呢？

输入格式

第一行，一个整数 nn ，表示数字塔共有 nn 行:

第 1 行有 nn 个数字

第 2 行有 n−1n−1 个数字

第 3 行有 n−2n−2 个数字,

......

第 i 行有 n−i+1n−i+1 个数字

最后一行只有一个数字。这些数字都是 0 至 9 的数字。丢失的数字用 ? 来代替。

数据范围

对于 100 %的数据， 1≤n≤501≤n≤50。

输出格式

输出 John 的胸牌，也就是你要输出一个倒三角数字塔。请放心，答案肯定唯一。

样例

输入数据 1

3
4??
?2
1

Copy

输出数据 1

457
92
1

Copy

输入数据 2

4
???2
??2
?2
2

Copy

输出数据 2

代码：

#include<bits/stdc++.h>
using namespace std;
int n;
int a[52][52],ans[52];
char t;
int main(){cin>>n;for(int i=0;i<n;i++){for(int j=0;j<n-i;j++){cin>>t;if(t>='0'&&t<='9'){a[i][j]=t-'0';ans[i]=j;}else {a[i][j]=-1;}}}for(int i=n;i>=0;i--){for(int j=ans[i]+1;j<=n-i+1;j++){a[i][j]=a[i+1][j-1]-a[i][j-1];if(a[i][j]<0)	a[i][j]+=10;}for(int j=ans[i]-1;j>=0;j--){a[i][j]=a[i+1][j]-a[i][j+1];if(a[i][j]<0)	a[i][j]+=10;}}for(int i=0;i<n;i++){for(int j=0;j<n-i;j++){cout<<a[i][j];}cout<<"\n";}return 0;
}

#GC4057. GC.2016.六年级.03.路程

题目描述
奶牛Bessie要从家里出发，去超市购买一些圣诞礼物，但是Bessie之前没去过超市，怎么办呢？农夫FJ给出了M条指令，指令的格式是：X Y，指令的意义是沿着X方向走Y米。上面指令的X是一个字符，'N'表示向北、'S'表示向南、'W'表示向西、'E'表示向东。
当Bessie执行完FJ给出的M条指令后，就到达超市了。Bessie是个聪明的奶牛，知道两点之间走直线的距离最短，所以在返程时，Bessie从超市走直线回到家。
那么Bessie总共走过的路程总和是多少？

输入格式
第一行，一个整数M。
接下来有M行，每行的格式是：X和Y，其中X是‘N’、‘S’、‘W’、‘E’四种字符之一。 Y是一个正整数。

数据范围
1<=M<=50， 1<=Y<=50。

输出格式
一个实数。答案四舍五入保留6位小数。

样例

输入数据 1

3
N 1
E 3
S 3

Copy

输出数据 1

10.605551

Copy

输入数据 2

Copy

输出数据 2

60.000000

Copy

帮助说明

C++语言保留6位小数的做法：
- 要包含头文件: #include
- cout<<fixed<<setprecision(6)<<a<<endl; //变量a四舍五入保留6位小数
  例如：下面的代码运行后，输出123.456789

#include <iostream>
#include <iomanip>
int main()
{double a = 123.4567885;cout<<fixed<<setprecision(6)<<a<<endl;return 0;
}

Copy

C++开平方根可以用sqrt函数，记得包含头文件#include 。
例如：已知直角三角形的两条直角边长分别是：a=3.0, b=4.0，那么直角三角形的斜边c的长度= sqrt(aa+bb);

#include <iostream>
#include <iomanip>
#include <cmath>
int main()
{double a = 3.0, b=4.0;double c = sqrt(a*a+b*b);cout<<fixed<<setprecision(6)<<c<<endl;return 0;
}

Copy

上面的程序将会输出5.000000。

代码：

#include<bits/stdc++.h>
using namespace std;
int n,yy,x,y,s;
char xx;
double sum;
int main(){cin>>n;for(int i=1;i<=n;i++){cin>>xx;cin>>yy;s+=yy;if(xx=='N') {y+=yy;}if(xx=='S') {y-=yy;}if(xx=='W') {x+=yy;}if(xx=='E') {x-=yy;}}sum=sqrt(x*x+y*y)+s;cout<<fixed<<setprecision(6)<<sum<<endl;return 0;
}

#GC4058. GC.2016.六年级.04.整点

题目描述
在石门中学的oj网站上有一条题目是这样的：
在一条数轴上，从0至N共有N+1个整点，分别是：0,1,2,3,4,...N。有K头奶牛，每头奶牛选择一个整点作为它们的家，但它们不能选择相同的整点。为了方便联络，住得最远的那两头奶牛的距离必须等于D。问有多少种不同的方案？
出题人觉得这题不错，于是把这题给大家做，但为了降低难度，于是把上面的题目做了一个改变：K=3，即只有3头奶牛。

输入格式
一行，两个正整数，N 和 D。

数据范围

对于50%的数据， 1<=N<=100，2<=D<=N。
对于100%的数据，1<=N<=500000，2<=D<=N。

输出格式
一个整数。

样例

输入数据 1

2 2

Copy

输出数据 1

Copy

输入数据 2

5 3

Copy

输出数据 2

Copy

输入数据 3

500000 20000

Copy

输出数据 3

57597239994

Copy

样例解释
样例 1 说明：

方案1：奶牛A选择整点0，奶牛B选择整点1，奶牛C选择整点2。
方案2：奶牛A选择整点0，奶牛C选择整点1，奶牛B选择整点2。
方案3：奶牛B选择整点0，奶牛A选择整点1，奶牛C选择整点2。
方案4：奶牛B选择整点0，奶牛C选择整点1，奶牛A选择整点2。
方案5：奶牛C选择整点0，奶牛A选择整点1，奶牛B选择整点2。
方案6：奶牛C选择整点0，奶牛B选择整点1，奶牛A选择整点2。

温馨提示
答案可能较大，建议读入的变量N、D以及程序中你用到的其他变量，都定义为long long类型。

代码：

#include<bits/stdc++.h>
using namespace std;
int main(){long long n,m;cin>>n>>m;cout<<6*(n+1-m)*(m-1);return 0;
}

#GC4059. GC.2016.六年级.05.排序

题目描述
有N×M只奶牛，每只奶牛的头上都印有一个唯一的标识ID，第i头奶牛的ID是正整数i。农夫FJ有一块大农田，FJ把农田划分成N行M列的格子，每个格子都必须有且仅有一头奶牛在里面工作。由于奶牛是无序动物，所以它们随机的各自选取了一个格子就开始工作了。但FJ希望他的奶牛是有序的，FJ希望:
1.第1行的奶牛从左往右的ID依次是：1,2,3，......M
2.第二行的奶牛从左往右的ID依次是：M+1,M+2,M+3,....2*M；...
3.最后一行的奶牛从左往右的ID一次是：(N-1)×M+1,(n-1)×M+2,.....N×M

所以农夫FJ决定对奶牛进行排序。FJ只能对奶牛使用两种指令：

任意交换两行奶牛。
任意交换两列奶牛。

上述的两种指令，FJ可以任用无限次。
那么FJ可以达到目标吗？如果可以，输出"Possible"，否则输出"Impossible"。

输入格式
多组测试数据。
第一行，一个整数R，表示总共有R组测试数据。 1<=R<=10。
每组测试数据格式如下：

第一行，两个整数：N和M。 1<=N,M<=50。
接下来是N行M列的格子，第i行第j列是一个正整数，表示一开始在该格子工作的奶牛的ID。

输出格式
共R行，每行输出"Possible"，或者输出"Impossible"，双引号不用输出。

样例

输入数据 1

5
2 2
1 2 
3 4 
2 2
3 4 
1 2 
2 2
4 3 
1 2 
1 10
4 5 1 2 9 8 3 10 7 6 
3 5
10 6 8 9 7 
5 1 3 4 2 
15 11 13 14 12

Copy

输出数据 1

Possible
Possible
Impossible
Possible
Possible

代码：

#include<bits/stdc++.h>
using namespace std;
long long n,m,s,t,a[105][105],b[105][105],c[105][105];
int main(){cin>>s;while(s--){t=1;int d=1;cin>>n>>m;for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){cin>>a[i][j];b[i][j]=a[i][j]%m;c[i][j]=(a[i][j]-1)/m;}}for(int i=1;i<=n;i++){for(int j=i+1;j<=n;j++){for(int k=1;k<=m;k++){if(b[i][k]!=b[j][k]){t=0;break;}}if(t==0)break;}if(t==0)break;}for(int i=1;i<=m;i++){for(int j=i+1;j<=m;j++){for(int k=1;k<=n;k++){if(c[k][i]!=c[k][j]){t=0;break;}}if(t==0)break;}if(t==0)break;}if(t==0)cout<<"Impossible";else cout<<"Possible";cout<<endl;}return 0;
}

#GC4060. GC.2016.六年级.06.累加和

题目描述

老师在黑板上写下一个正整数，记为 X1X1 。
删除 X1X1 的最后一位数字后，得到的正整数记为 X2X2 。
删除 X2X2 的最后一位数字后，得到的正整数记为 X3X3 。

......

进行若干次操作后，剩下的正整数只有1位数字了，记为 XnXn 。

令 YY = X1+X2+X3+....+XnX1+X2+X3+....+Xn 。

例如：老师刚开始在黑板写下的正整数是 509 ，那么:

X1X1 = 509

X2X2 = 50

X3X3 = 5

那么此时的 YY = 509+50+9 = 564 。

现在给出 YY，你的任务是求出 X1X1 。数据能保证对于 YY，X1X1 不会有多个解，如果找不到 X1X1 ，那么输出 -1 。

输入格式

一行，一个正整数 YY 。

数据范围

对于 20% 的数据，1 <= YY <= 1000000。

对于 100% 的数据，1 <= YY <= 1000000000000000000。

输出格式

一行，一个整数 X1X1，或者输出 -1 。

样例

输入数据 1

Copy

输出数据 1

Copy

输入数据 2

Copy

输出数据 2

-1

Copy

输入数据 3

137174210616796

Copy

输出数据 3

123456789555123

Copy

样例解释

样例 1 ：509+50+9=564

代码：

#include<bits/stdc++.h> 
using namespace std; 
typedef long long ll; 
ll sum; 
int main() { ll tmp,ans,res; cin>>sum; ans=sum-sum/10; res=ans; while(1) { tmp=res; while(tmp) { tmp/=10; ans+=tmp; } if(ans==sum) { cout<<res<<endl; break; } else if(ans<sum) { res++; ans=res; } else { cout<<-1<<endl; break; } } return 0; 
}

谢谢观看！！！！！