集训题解-Day1
A.喜欢素数的gg
题目描述
描述
GG是一个特别特别喜欢素数的好孩子，有一天他发现了一个有意思的现象，任意一个大于1的整数n都可以被拆分成k个素数的和。他想知道怎么拆能让这个k最大。
GG比较懒，所以他想让你来帮他解决这个问题。
输入
多组输入数据
每组输入数据给出一个整数n（1 < n < 1e6）
输出
对于每组输入
第一行给出一个k
第二行给出k个素数，即n拆分出来k个素数，要求按照升序排列，用空格隔开。
样例输入1
2
5
样例输出1
1
2
2
2 3
解答
本题的描述不够明确，事实上拆成的素数是可以相等的。
只有两种情况：n偶数则拆成若干个2，n奇数则拆成若干个2加1个3
int main()
{
int n;
while(scanf("%d", &n) == 1){
if (n % 2 == 0){
int cnt = n / 2;
printf("%d\n", cnt);
printf("2"); rep(i, cnt-1) printf(" 2");
pn;
}else{
int cnt = n / 2 - 1;
printf("%d\n", cnt + 1);
rep(i, cnt) printf("2 ");
printf("3\n");
}
}
return 0;
}
B.平庸的GG
题目描述
描述
GG是一个平庸的人，准确的说他的成绩一直处于中游水平
但GG是一个很特别的人，他总是讨厌学习最好的学生和学习最差的学生
所以给出n个学生的成绩，他想让你找出有多少学生是他不讨厌的。
输入
多组测试数据
对于每组测试数据
第一行给出一个整数n(0 < n < 1e6)
第二行给出n个数ai（0<=ai<1e9）
输出
对于每组测试数据数出一个整数k，表示他不讨厌的人数。
样例输入1
2
1 5
5
1 1 2 5 5
样例输出1
0
1
解答
由题意，将学生的成绩排序后，去掉最高分和最低分即可。
如果为了追求极限复杂度，直接扫描并维护最高分的值和出现次数会更快一点，最低分同理。
int main()
{
int n;
while(scanf("%d", &n) == 1){
int lmin = -1, lmax = -1, cnt_min = 0, cnt_max = 0;
rep(i, n){
int x; scanf("%d", &x);
if (x < lmin || lmin == -1){
lmin = x;
cnt_min = 1;
}else if (x == lmin) cnt_min++;
if (x > lmax || lmax == -1){
lmax = x;
cnt_max = 1;
}else if (x == lmax) cnt_max++;
}
printf("%d\n", n - cnt_min - cnt_max);
}
return 0;
}
C.迷恋lz小姐姐的GG
题目描述
描述
GG今天在玩一个有趣的游戏
有三个箱子，分别放在标号0，1，2的地方
他让lz小姐姐藏到期中一个箱子里
然后经过若干次op后lz小姐姐从箱子里走出来
对于op：
奇数次的op：交换0，1位置的箱子
偶数次的op：交换1，2位置的箱子
已知lz小姐姐从箱子里走出来的位置和op的次数
迷恋lz小姐姐的GG想知道一开始lz小姐姐藏在了哪个位置箱子内
输入
多组输入数据
对于每组输入数据
第一行给出一个整数n（0
解答
根据题意，直接进行逆推，根据op的奇偶性即可一步推出初始位置。
int main()
{
int n, p;
while(scanf("%d%d", &n, &p)== 2){
if (n % 2 == 0) printf("%d\n", 3 - p);
else printf("%d\n", 1 - p);
}
return 0;
}
D.GG拼果盘
题目描述
描述
GG收到了迷妹送来的一堆水果，其中有a个苹果，b个橘子和c个草莓
GG要用这些水果拼出苹果：橘子：草莓=1：2：4的果盘
因为GG有强迫症，所以每个果盘里的水果的量都是整个的，也就是果盘的份数是整个的
懒惰的GG想让你帮他算出最多可以使用多少
输入
多组测试数据
每组测试数据给出a,b,c(a, b, c <= 1000)
输出
对于每组输入输出一个整数ans。
样例输入1
2
5
7
4
7
13
2
3
2
样例输出1
7
21
0
解答
由题意，答案即min(a,b/2,c/4)
E.智障的GG
题目描述
描述
给一个n*m的只含有0和1的矩阵，有两个操作给一个n*m的只含有0和1的矩阵，有两个操作
1：某一列的所有0变成1，所有1变成0；
2：某一行的所有0变成1，所有1变成0；
问，该矩阵是否可以经过若干次操作变成全为1的矩阵，若可以输出Yes，不可以输出No。
智障的GG做不出这道题，只能求助你
输入
多个测试数据，
对于每个测试数据
第一行两个数n,m（0 < n,m <= 1000）
接下来n行，每行m个0或1
输出
对于每个测试样例输出Yes or No
样例输入1
3 3
1 0 1
0 1 0
1 0 1
3 3
1 1 1
0 1 0
1 0 1
样例输出1
Yes
No
解答
结论：答案为Yes的一个充要条件：任意的两行数字，比如满足相同或恰好相反。
易知操作顺序不会影响操作结果，不妨让行操作先做，则行操作结束后，所有行必须完全相同，再将所有的”0列”进行列操作，即可拼出全1。
const int maxn = 1010;
int a[maxn][maxn];
int main()
{
int n, m;
while(scanf("%d%d", &n, &m) == 2){
rep(i, n) rep(j, m) scanf("%d", &a[i][j]);
rep(i, n)
if (a[i][0] == 0)
rep(j, m) a[i][j] = 1 - a[i][j];
int flag = 1;
rep(i, n) rep(j, m) if (a[i][j] != a[0][j])
flag = 0;
if (flag) printf("Yes\n");
else printf("No\n");
}
return 0;
}
F.fff团的GG
题目描述
描述
fff团是一个神秘的组织
GG花费了巨大的努力终于加了进去
fff团团长Fire看他如此上进就赐予了他一个神秘的力量
GG现在可以花费寿命去烧情侣
烧第x(x > 3)对情侣的花费
f(x) = a * f(x – 1) + b * f(x – 2) + c * f(x – 3)
f(1) = f(2) = f(3) = t;
GG想知道烧死第n队情侣的花费是多少
由于答案可能很大，请输出 花费 % (1e9 + 7)之后的结果
输入
多组输入数据
每组给出个数a，b，c（0<=a,b,c<10）,t(0 < t<1e6),n(0 < n<=1e11)
输出
对于每组输入数据输出一个数字ans表示第n个
样例输入1
1 1 1 1 1
1 1 1 1 2
1 1 1 1 3
1 1 1 1 4
1 1 1 1 5
样例输出1
1
1
1
3
5
解答
标准的递推式问题，系数矩阵为
a
1
0
b
0
1
c
0
0
使用矩阵快速幂即可