ACM第三次考核题解

ACM第三次考核题解

题目序号难度题目编号题目考察知识点
1签到题A这是一道很难的题！！！输出
2迷之难度F神说要有光，于是有了手电筒贪心
3简单BThis 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 1 1 11地消耗，始终能够把所有的电池电量和 ÷ 2 ÷2 ÷2（向下取整）消耗完，比如样例中 222 2 2 2 222 共 3 3 3个电池，可以用第一个电池和第二个电池消耗 1 1 1的电量，然后再和第三个电池消耗1的电量，最后第二个和第三个一起消耗 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 n n，输出一个最小的质数 m m m使得 n + m n+m n+m是合数。

这是一个很简单的题目，可以证明答案不是 2 2 2就是 3 3 3。因为如果是奇数+3之后一定为偶数，一定为合数，但需要考虑 + 2 +2 +2后是不是合数，因为此题找的是最小的 m m m，偶数 + 2 +2 +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 ) O(n^3) O(n3)给过了，气死了！！！

请添加图片描述

#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+10 5+10，如果没有再考虑 5 + 5 + 5 5+5+5 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 简单截断

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

#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;
}

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：http://www.mfbz.cn/a/885077.html

如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈qq邮箱809451989@qq.com，一经查实，立即删除！

相关文章

速通数据结构与算法第六站 树堆

速通数据结构与算法第六站 树堆

系列文章目录 速通数据结构与算法系列 1 速通数据结构与算法第一站 复杂度 http://t.csdnimg.cn/sxEGF 2 速通数据结构与算法第二站 顺序表 http://t.csdnimg.cn/WVyDb 3 速通数据结构与算法第三站 单链表 http://t.csdnimg.cn/cDpcC 4 速通…
阅读更多...
一文上手SpringSecurity【九】

一文上手SpringSecurity【九】

在校验token的过滤器当中, 由于需要根据用户名称, 去查询出要认证的对象,然后再去数据库当中查询出角色列表、权限列表.频繁的操作数据库,可能会带来性能瓶颈, 那么我们该如何解决呢? 我们可以引入Redis, 将认证的对象,存储到Redis当中,在校验token的过滤器当中,可以直接从Red…
阅读更多...
9.29 LeetCode 3304、3300、3301

9.29 LeetCode 3304、3300、3301

思路&#xff1a; ⭐进行无限次操作&#xff0c;但是 k 的取值小于 500 &#xff0c;所以当 word 的长度大于 500 时就可以停止操作进行取值了 如果字符为 ‘z’ &#xff0c;单独处理使其变为 ‘a’ 得到得到操作后的新字符串&#xff0c;和原字符串拼接 class Solution { …
阅读更多...
ServletContainerInitializer接口详解

ServletContainerInitializer接口详解

版权声明 本文原创作者：谷哥的小弟作者博客地址：http://blog.csdn.net/lfdfhlServletContainerInitializer概述 ServletContainerInitializer是Servlet 3.0规范中引入的一个接口，它的主要目的是允许开发者在Servlet容器（如Tomcat、Jetty等）启动时执行一些自定义的初始化代…
阅读更多...
synchronized相关知识

synchronized相关知识

1、对象头Markword 2、锁升级过程 无锁 偏向锁&#xff1a;只有一个线程过来加锁&#xff0c;Markword对应变化&#xff1a;偏向线程ID存储当前线程ID&#xff0c;偏向锁标志位置成1&#xff0c;锁标志位置为01&#xff1b;此后如果当前线程再次获取锁&#xff0c;只需对比偏…
阅读更多...
《十年国庆游，洞察中国旅游新趋势》

《十年国庆游，洞察中国旅游新趋势》

作者&#xff1a;侯炯 一、十年国庆旅游数据总览 过去十年&#xff0c;中国国庆旅游市场呈现出丰富的变化和强劲的发展态势。从接待游客人次来看&#xff0c;2014 年接待国内游客 4.75 亿人次&#xff0c;到 2019 年已增长至 7.82 亿人次&#xff0c;2023 年国内旅游出游人数更…
阅读更多...
【预备理论知识——1】深度学习：概率论概述

【预备理论知识——1】深度学习：概率论概述

简单地说&#xff0c;机器学习就是做出预测。 概率论 掷骰子 假设我们掷骰子&#xff0c;想知道看到1的几率有多大&#xff0c;而不是看到另一个数字。 如果骰子是公平的&#xff0c;那么所有六个结果{1,…, 6}都有相同的可能发生&#xff0c; 因此我们可以说 1 发生的概率为1…
阅读更多...
【数据结构】图的最小生成树

【数据结构】图的最小生成树

快乐的流畅&#xff1a;个人主页 个人专栏&#xff1a;《C游记》《进击的C》《Linux迷航》 远方有一堆篝火&#xff0c;在为久候之人燃烧&#xff01; 文章目录 引言一、最小生成树的概念二、Kruskal算法2.1 思想2.2 实现 三、Prim算法3.1 思想3.2 实现 四、Kruskal和Prim的对比…
阅读更多...
container_of 函数的分析

container_of 函数的分析

这个函数的目的是&#xff0c; 通过结构体里面的内容 找到 大结构体的 基地址。 函数的原型是&#xff1a;　 &#xff30;&#xff34;&#xff32;是指针 &#xff54;&#xff59;&#xff50;&#xff45;　&#xff0c;　&#xff4d;&#xff45;&#xff4d;&#xff…
阅读更多...
新手上路：Anaconda虚拟环境创建和配置以使用PyTorch和DGL

新手上路：Anaconda虚拟环境创建和配置以使用PyTorch和DGL

文章目录 前言步骤 1: 安装 Anaconda步骤 2: 创建新的 Anaconda 环境步骤 3: 安装最新版本的 PyTorch步骤 4: 安装特定版本的 PyTorch步骤 5: 安装最新版本的 DGL步骤 6: 安装特定版本的 DGL步骤 7: Pycharm中使用虚拟环境解释器第一种情况&#xff1a;创建新项目第二种情况&am…
阅读更多...
Word办公自动化的一些方法

Word办公自动化的一些方法

1.Word部分内容介绍 word本身是带有格式的一种文档&#xff0c;有人说它本质是XML&#xff0c;所以一定要充分利用标记了【样式】的特性来迅速调整【格式】&#xff0c;从而专心编辑文档内容本身。 样式&#xff08;集&#xff09; 编号&#xff08;多级关联样式编号&#xff…
阅读更多...
Tomcat系列漏洞复现

Tomcat系列漏洞复现

CVE-2017-12615——Tomcat put⽅法任意⽂件写⼊漏洞 漏洞描述 当 Tomcat运⾏在Windows操作系统时&#xff0c;且启⽤了HTTP PUT请求⽅法&#xff08;例如&#xff0c;将 readonly初始化参数由默认值设置为false&#xff09;&#xff0c;攻击者将有可能可通过精⼼构造的攻击请求…
阅读更多...
探索 Snowflake 与 Databend 的云原生数仓技术与应用实践 | Data Infra NO.21 回顾

探索 Snowflake 与 Databend 的云原生数仓技术与应用实践 | Data Infra NO.21 回顾

上周六&#xff0c;第二十一期「Data Infra 研究社」在线上与大家相见。活动邀请到了西门子数据分析师陈砚林与 Databend 联合创始人王吟&#xff0c;为我们带来了一场关于 Snowflake 和 Databend 的技术探索。Snowflake&#xff0c;这个市值曾超过 700 亿美元的云原生数据仓库…
阅读更多...
Android 安卓内存安全漏洞数量大幅下降的原因

Android 安卓内存安全漏洞数量大幅下降的原因

谷歌决定使用内存安全的编程语言 Rust 向 Android 代码库中写入新代码&#xff0c;尽管旧代码&#xff08;用 C/C 编写&#xff09;没有被重写&#xff0c;但内存安全漏洞却大幅减少。 Android 代码库中每年发现的内存安全漏洞数量&#xff08;来源&#xff1a;谷歌&#xff09…
阅读更多...
资质申请中常见的错误有哪些？

资质申请中常见的错误有哪些？

在申请建筑资质的过程中&#xff0c;企业可能会犯一些常见的错误&#xff0c;以下是一些需要避免的错误&#xff1a; 1. 资料准备不充分&#xff1a; 申请资质需要提交大量的资料&#xff0c;包括企业法人资料、财务报表、业绩证明等。资料不齐全或不准确都可能导致申请失败。…
阅读更多...
汽车线束之故障诊断方案-TDR测试

汽车线束之故障诊断方案-TDR测试

当前&#xff0c;在汽车布局中的线束的性能要求越来越高。无法通过简单的通断测试就能满足性能传输要求。早起对智能化要求不高&#xff0c;比如没有激动雷达、高清摄像、中央CPU等。 近几年的智能驾驶对网络传输要求越来越高&#xff0c;不但是高速率&#xff0c;还需要高稳定…
阅读更多...
【C++题目】7.双指针_和为 s 的两个数字

【C++题目】7.双指针_和为 s 的两个数字

文章目录 题目链接&#xff1a;题目描述&#xff1a;解法C 算法代码&#xff1a;图解 题目链接&#xff1a; LCR 179.查找总价格为目标值的两个商品 题目描述&#xff1a; 解法 解法一&#xff08;暴力解法&#xff0c;会超时&#xff09; 两层 for 循环列出所有两个数字的组合…
阅读更多...
一种使用 SUMO + Python 联合仿真平台

一种使用 SUMO + Python 联合仿真平台

一种使用 SUMO Python 联合仿真平台&#xff08;一&#xff09; 本文适用人群包括但不仅限于【交通运输】【车辆工程】【自动化控制】【计算机科学与技术】等专业本科生、研究生、博士生。本文通过在Pycharm平台&#xff0c;使用Python语言 Traci工具包&#xff0c;调用SUMO客…
阅读更多...
【步联科技身份证】 身份证读取与解析———未来之窗行业应用跨平台架构

【步联科技身份证】 身份证读取与解析———未来之窗行业应用跨平台架构

一、身份证解析代码 C# function 身份证数据解析_湖南步联科技(wzxx) {var result {};result[xm] wzxx.substr(0, 15);result[xbdm] wzxx.substr(15, 1);result[mzdm] wzxx.substr(16, 2);result[csrq] wzxx.substr(18, 8);result[dzmc] wzxx.substr(26, 35);result[gms…
阅读更多...
Ansible-template模块动态生成特定文件

Ansible-template模块动态生成特定文件

文章目录 一、Jinja2介绍什么是主要特性安装基本用法进阶特性总结 Jinja2与Ansible关系1. 模板引擎2. Ansible 的依赖3. 变量和模板4. 动态生成配置5. 社区和生态系统总结 二、Ansible如何使用Jinja2使用template模块Jinja2文件中使用判断和循环Jinja2文件中使用判断语法 Jinja…
阅读更多...
最新文章

Copyright @ 2022~2023