当前位置：首页 > article >正文

ACM第三次考核题解

article 2024/11/20 2:37:40

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 1010

int 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;
	}
	// 辗转相除的过程，终止条件是余数为0
	while (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 分母den
	int 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);	
		else
			num = a * (den / b) - c * (den / d);
		
		// 以下是分数化到最简过程
		// 避免输出0/n
		
		if (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;
}