ACM第三次考核题解

题目序号	难度	题目编号	题目	考察知识点
1	签到题	A	这是一道很难的题！！！	输出
2	迷之难度	F	神说要有光，于是有了手电筒	贪心
3	简单	B	This is a real English problem！	思维英语
4	简单	C	玩具	简单排序
5	简单	I	“近义词”	字符数组
6	一般	G	一起来运动！！	二分搜索
7	一般	E	这糖保甜吗？	GCD 模拟
8	一般	K	卖教材	模拟
9	一般	D	简单切割小游戏	结构体运用
10	一般	J	简单截断	前缀和
11	困难	M	马学长的小游戏	博弈
12	困难	H	分提拉米苏	二分答案
13	困难	L	算两次	数学

A 这是一道很难的题！！！

print("想看马学长跳舞")

F 神说要有光，于是有了手电筒

需要推出一个结论：当最大的电池电量高于其他所有电池电量，则可以把其他电池给消耗完；如果不能，其他电池可以相互搭配， $11$ 地消耗，始终能够把所有的电池电量和 $\div 2$ （向下取整）消耗完，比如样例中 $222$ 共 $3$ 个电池，可以用第一个电池和第二个电池消耗 $1$ 的电量，然后再和第三个电池消耗1的电量，最后第二个和第三个一起消耗 $1$ 的电量。

#include <iostream>
using namespace std;
#define ll long long
int main() {ll sum = 0, ans = 0, n = 0, a = 0;cin >> n;for (int i = 0; i < n; i++) {cin >> a;ans = max(a, ans);sum += a;}if (ans > sum / 2) cout << sum - ans;else cout << sum / 2;return 0;
}

B This is a real English problem！

题意：对于给定一个质数 $n$ ，输出一个最小的质数 $m$ 使得 $n + m$ 是合数。

这是一个很简单的题目，可以证明答案不是 $2$ 就是 $3$ 。因为如果是奇数+3之后一定为偶数，一定为合数，但需要考虑 $+ 2$ 后是不是合数，因为此题找的是最小的 $m$ ，偶数 $+ 2$ 仍然为偶数，一定是合数。

#include<bits/stdc++.h>
using namespace std;
int n;
bool check(int x){for(int i = 2 ; i <= n ; i++)if(x%i==0) return true;return false;
}
int main()
{cin >> n;if(check(n+2)) cout << 2;else cout << 3;return 0;
}

C 玩具

/*
* 本题思路较为简单就是先排序然后从后往前取最大的那个就可以了
* 如果你觉得的冒泡太麻烦，可以去学一下 C++ 用 C++ 的 algorithm 头文件里的 sort 函数进行排序 
*/
#include <stdio.h>
#define N 1010int a[N];int main()
{int n, sum = 0;scanf("%d", &n);for (long long int i = 1; i <= n; i ++ )scanf("%d", &a[i]);// 对数组进行排序for (int i = 1; i < n; i ++ ) for (int j = 1; j <= n - i; j ++ ) if (a[j] > a[j + 1]) {int temp = a[j];a[j] = a[j + 1];a[j + 1] = temp;}// 从后往前取，两个两个取，只把大的那个算入结果内for (long long int j = n; j >= 1; j -- ) {sum += a[j];j --; // 略过下一个}printf("%d\n", sum);return 0;
}
//-------------- 我是一个分割线 -----------------------
/*
* 如果你用 c++ 并使用 algorithm 这个头文件
* 第18行至第24行的排序算法可以替换成下面这行代码 sort(a + 1, a + 1 + n); 
*/

I “近义词”

看了题目大家应该都知道是直接遍历比较就可以，最主要的是怎么存多个字母，因为比较的字符串是在最后给出，这里提供四个思路：

1.用二维字符数组

2.用一维字符数组(但计算位置时需要退一下坐标)

3.用c++的vector容器

4.用c++的string数组

下面给出两种解法1和3的代码

#include <stdio.h>
int main()
{int n,m;int num=0;int tem=0;char a[1100][1100];scanf("%d%d",&n,&m);for(int i=0;i<=n;i++){scanf("%s",a[i]);}for(int i=0;i<n;i++){for(int j=0;j<m;j++){if(a[i][j]!=a[n][j])tem++;if(tem>2)break;}if(tem<=2)num++;tem=0;}printf("%d",num);return 0;
}

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 2e5 + 10;
int n,m;
vector<string> v;
string s;
int ans;
int main()
{cin >> n >> m ;for(int i = 1 ; i <= n ; i ++){string s;cin >> s;v.push_back(s);}cin >> s;for(int i = 0 ; i < v.size() ; i ++){int t = 0;string ss = v[i];for(int i = 0 ; i < ss.size() ; i++){if(ss[i] != s[i]) t++;}if( t <= 2) ans ++;//cout << t << endl;}cout << ans;
}

G 一起来运动！！

这题本意是靠二分，但由于出题人疏忽，数据没有捏好，让你们 $O(n^3)$ 给过了，气死了！！！

请添加图片描述

#include <iostream>
#include <cstring>
#include <algorithm>using namespace std;const int N = 1100;
int a[N];
int n;int main() {cin >> n;for(int i = 0; i < n; i ++) cin >> a[i];sort(a, a + n);int ans = 0;for(int i = 0; i < n; i ++) {for(int j = i + 1; j < n; j ++) {int l = lower_bound(a , a + n, 2 * a[j] - a[i]) - a;int r = upper_bound(a , a + n, 3 * a[j] - 2 * a[i]) - a;ans += r - l;}}cout << ans << endl;return 0;
}

E 这糖保甜吗？

#include<stdio.h>
#include<math.h>int GCD(int m, int n)
{int tmp;m = abs(m);n = abs(n);// 保证后续m%n为较大数除以较小数if (m<n){tmp = m;m = n;n = tmp;}// 辗转相除的过程，终止条件是余数为0while (m % n != 0){tmp = m;m = n;n = tmp % n;}// 返回除数（较小数）return n;
}int main() {int a, b, c, d;int gcd; // 最大公约数int den, num; // 分子num 分母denint op; // 操作数scanf("%d",&op);scanf("%d %d %d %d",&a,&b,&c,&d);gcd = GCD(b, d);// 以下是分数运算过程// 通分——分母最大den = b * d / gcd;// den/b 为分母扩大了多少倍 分子也要相应扩大倍数if (op == 1)num = a * (den / b) + c * (den / d);	elsenum = a * (den / b) - c * (den / d);// 以下是分数化到最简过程// 避免输出0/nif (num == 0) {printf("0\n");} else if (num == den) {printf("1\n");}else {gcd = GCD(num, den); num = num / gcd;den = den / gcd;printf("%d/%d",num,den);}return 0;
}

K 卖教材

根据题意模拟即可，但需要注意的是当给20元找零的时候需要先使用 $5 + 10$ ，如果没有再考虑 $5 + 5 + 5$

#include <bits/stdc++.h>
using namespace std;
int num5,num10,num20;
int ans=0;
int main()
{int n;scanf("%d",&n);for(int i=1;i<=n;i++){int x;scanf("%d",&x);if(x==5) {num5++;ans++;}else if(x==10){if(num5>0){num5--;num10++;ans++;}else {break;}}else {if(num5>0&&num10>0){num5--;num10--;num20++;ans++;}else if(num5>=3){num5-=3;num20++;ans++;}else {break;}}}printf("%d",ans*5);return 0;
}

D 简单切割小游戏

使用结构体存每一段，排序之后贪心地从最后一个位置切割(这也是怎么排序的依据)

#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 1e5+5;
struct node{int a, b;
}s[N];
bool cmp(node x, node y){if(x.b == y.b){return x.a < y.a;}return x.b < y.b;
}
void solve()
{int n, m;scanf("%d%d",&n,&m);for(int i = 0;i < m;i++){scanf("%d%d",&s[i].a,&s[i].b);if(s[i].a > s[i].b)swap(s[i].a,s[i].b);}sort(s,s+m,cmp);int flag = 0, ans = 0;for(int i = 0;i < m;i++){if(flag <= s[i].a){flag = s[i].b;ans++;}}printf("%d",ans);
}
int main()
{solve();return 0;
}

J 简单截断

巧妙地运用了前缀和，第一个切割点一定在所有数和的 $\frac{1}{3}$ 处，而第二个切割点一定在所有数和的 $\frac{2}{3}$ 处

#include<bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
int sum[N];
int n;
int main(){cin >> n;for(int i = 1 ; i <= n ; i++){int x;cin >> x;sum[i] = sum[i-1] + x;}if(sum[n]%3!=0){cout << 0;return 0;}long long cnt = 0,ans = 0;for(int i = 1 ; i <= n - 2; i ++){if(sum[i] == sum[n]/3) cnt ++;if(sum[i+1] == sum[n]/3*2) ans += cnt;}cout << ans;return 0;
}

M 马学长的小游戏

#include <iostream>
using namespace std;
int main()
{int n = 1;while(1) {cin >> n; if (n == 0) break;if (n % 2 == 1) printf("maxuezhang win\n");else printf("xiaoJtongxue win\n");}return 0;
}

H 分提拉米苏

#include <bits/stdc++.h>
using namespace std;const int N = 1e5 + 10;
int l[N], r[N];
int n, k;
bool check(int mid){int res = 0;for(int i = 0 ; i < n ; i ++){res += (l[i]/mid)*(r[i]/mid);if(res >= k) return true;}return false;
}
int main()
{cin >> n >> k;for(int i = 0 ; i < n ; i ++) cin >> l[i] >> r[i];int l = 1 , r = 10000;while(l < r){int mid = (l + r + 1) / 2;if(check(mid)) l = mid;else r = mid - 1;}cout << l << endl;return 0;
}

L 算两次

#include <bits/stdc++.h>
#define ll long long
#define N 100005
int f[N],p[N],nu1[N],nu2[N];
int num1=0,num2=0;
int ma=0;
using namespace std;
int num=0;
void init_p()
{f[1]=1;num=0;for(int i=2;i<=N;i++){if(f[N]==0){p[++num]=i;}for(int j=1;j<=num;j++){if(i*p[j]<N) f[i*p[j]]=1;if(i%p[j]==0||i*p[j]>N) break;}}
}
int main()
{init_p();int m;scanf("%d",&m);for(int i=1;i<=m;i++){int op,x;scanf("%d%d",&op,&x);if(x<0){num1++;x=-1*x;}ma=max(ma,x);if(op==1){for(int i=1;p[i]<=x;i++){if(f[x]==0){nu1[x]++;break;}while(1){if(x%p[i]==0){nu1[p[i]]++;x/=p[i];}else break;}}}else {for(int i=1;p[i]<=x;i++){if(f[x]==0){nu1[x]--;break;}while(1){if(x%p[i]==0){nu1[p[i]]--;x/=p[i];}else break;}}}}scanf("%d",&m);for(int i=1;i<=m;i++){int op,x;scanf("%d%d",&op,&x);if(x<0){num2++;x=-1*x;}ma=max(ma,x);if(op==1){for(int i=1;p[i]<=x;i++){if(f[x]==0){nu2[x]++;break;}while(1){if(x%p[i]==0){nu2[p[i]]++;x/=p[i];}else break;}}}else {for(int i=1;p[i]<=x;i++){if(f[x]==0){nu2[x]--;break;}while(1){if(x%p[i]==0){nu2[p[i]]--;x/=p[i];}else break;}}}}if(num1%2!=num2%2){printf("NO");return 0;}for(int i=1;p[i]<=ma;i++){if(nu1[p[i]]!=nu2[p[i]]){printf("NO");return 0;}}printf("YES");return 0;
}