GC.2017.六年级.01.更多闰年
题目描述
在 smoj 网站上，有很多针对小学信息学入门的课程，把这些入门课程的题都刷一遍并理解之后，你就算正式的信息学选手啦。例如课程 9 的某一道题是这样的：
输入两个正整数 a 和 b，表示开始的年份和结束的年份，问从 a 年到 b 年有多少闰年？闰年只需要满足如下两个条件之一：
1.能整除 400
2.能整除 4，但不能整除 100
输入格式
第一行 2 个整数 a 和 b，范围在[1, 1000000000]。
输出格式
一个整数。
样例
输入数据 1
1 10000
Copy
输出数据 1
2425
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;
}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
1
Copy
输入数据 2
2 4
5 8
Copy
输出数据 2
0代码：
#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;
}GC.2017.六年级.03.倍数
题目描述
给定一个整数 X，能不能通过调换 X 数字的位置，使得调换之后得到的数是 X 的倍数？
注意：交换数字位置之后得到的数不能有前导 0。如果可以输出"Possible"，否则输出"Impossible"。其中双引号不用输出。
输入格式
多组测试数据。
第一行，一个整数 G,表示有 G 组测试数据。 1 <=G<=11。
每组测试数据格式：
- 一个正整数 X， X 的范围是[1,1000000]。
输出格式
如果可以输出"Possible"，否则输出"Impossible"。
样例
输入数据 1
5
142857
14
1035
1000000
4
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;
}#D. GC.2017.六年级.04.猫和兔子
- 传统题1000ms256MiB
题目描述
一只猫和一只兔子玩简单的猜谜游戏。猫选择了两个不同的正整数 xx 和 yy ，然后他告诉兔子 nn 个正整数，这 nn 个正整数当中，有一个是 x+yx+y ，还有一个是 x-yx−y ，剩余的 n-2n−2 个是任意给的。兔子喜欢大整数，输出 x*yx∗y 的最大可能值。
输入格式
多组测试数据。
第一行，一个整数 GG ，表示有 GG 组测试数据 ( 1 \le G \le 51≤G≤5 )。
每组测试数据格式如下：
第 1 行，一个正整数 nn 。( 2 \le N \le 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
6
12
20
2499
441
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;
}#E. GC.2017.六年级.05.积木
- 传统题1000ms256MiB
题目描述
乔治喜欢玩积木。目前他有 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
11
7
7
4
196
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;
}#F. GC.2017.六年级.06.幸存者
- 传统题1000ms256MiB
题目描述
有 n 个人，现在他们从左往右站成一列。第 i 个人的位置为 i，且第 i 个人手里握着一把长度为 L_iLi 的大刀。指挥者统一指令，n 个人一齐往左边砍去。
对于位置为 i，j 的两个人（i＜j），如果满足 i ≥ j - L_jLj，那么位置为 i 的人就会被位置为 j 的人砍死。问：最后有几个人生存下来？
输入格式
第一行输入一个整数 n（1 ≤ n ≤ 1000000），表示有 n 个人。
第二行输入 n 个整数,第 i 个整数是 L_iLi（0 ≤ L_iLi ≤ 1000000000），L_iLi 表示第 i 个人的大刀长度。
输出格式
输出一个整数，表示最后生存下来的人数。
样例
输入数据 1
4
0 1 0 10
Copy
输出数据 1
1
Copy
输入数据 2
2
0 0
Copy
输出数据 2
2
Copy
输入数据 3
10
1 1 3 0 0 0 2 1 0 3
Copy
输出数据 3
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;
}谢谢观看！！