ACM实训冲刺第二十一天

2024-05-28 21:12
文章标签 实训 acm 冲刺 第二十一

本文主要是介绍ACM实训冲刺第二十一天,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

寒冰王座(数据处理与逻辑判断)

这段C语言代码实现了一个根据特定条件计算整数输入值变换的程序,它并不直接对应于经典的算法题类型,但可以视为一个“数据处理与逻辑判断”练习题。代码的主要逻辑如下:

  1. 读取测试数据数量 (T):首先读取一个整数T,表示有多少组测试数据。如果T不在1到100的范围内,则结束输入。

  2. 循环处理每组测试数据:对于每组数据,执行以下操作:

    • 初始化变量sum为0。
    • 读取一个正整数n,如果n不在1到10000的范围内,结束当前循环。
    • 根据n的值应用不同的计算规则:
      • 如果n >= 300,则sum = n % 50(取模运算)。
      • 如果150 <= n < 200,则sum = n - 150
      • 如果200 <= n < 300,则sum = n - 200
      • 如果n < 150,则sum = n
    • 输出计算结果sum
  3. 错误的边界检查位置:代码中有一处逻辑错误,在外层循环结束后再次检查了n的范围,但这实际上在循环结束后已经失去了意义,因为此时n的值未被重新定义,且这一检查并不能终止程序或改变程序流程,应视为冗余或错误代码。

#include <stdio.h> 
int main(){int T,i,n,sum;while(scanf("%d",&T)!=EOF){ //T代表的是测试数据的数量 if(T<1||T>100) break;for(i=0;i<T;i++){int sum=0;//初始化置0scanf("%d",&n) ;//正整数Nif(n<1||n>10000) break;if(n>=300) sum=n%50;else if(n<200&&n>=150) sum=n-150;else if(n<300&&n>=200) sum=n-200;else if(n<150) sum=n;printf("%d\n",sum);}}return 0;
}

Charm Bracelet(0-1背包问题

这段代码实现的是一个经典的动态规划问题——0-1背包问题。0-1背包问题是一种组合优化问题,问题描述为:给定一组物品,每种物品都有自己的重量W和价值V,以及一个背包所能承载的最大重量M,要求在不超过背包最大重量的前提下,挑选物品装入背包,使得背包中物品的总价值最大。

代码解析如下:

  1. 输入: 首先读取两个整数nm,分别代表物品的总数和背包的最大容量。
  2. 初始化: 定义一个数组dp,长度为12881(这里的长度选择是基于题目的实际情况,确保能覆盖到背包最大容量的情况),并初始化所有dp[i]为0。dp[i]表示当背包容量为i时,能够装入物品的最大价值。
  3. 动态规划转移: 遍历每一件物品(编号为1到n),对于每件物品,读取其重量w和价值d,然后从当前背包容量m反向遍历到这件物品的重量w,更新dp[j]的值。如果将当前物品装入背包(即考虑之前容量为j-w的情况,并加上当前物品的价值d)能得到更大的价值,就更新dp[j]的值为这个更大的价值。这是动态规划中典型的“状态转移”过程。
  4. 输出结果: 最终,dp[m]存储的就是在背包容量为m时能装入物品的最大总价值,将其输出即为答案。
#include<stdio.h> 
int main() {int n,m;scanf("%d %d",&n,&m);int dp[12881];for(int i=0;i<m;i++){dp[i]=0;}for(int i=0;i<n;i++){int d,w;scanf("%d %d",&w,&d);for(int j=m;j>=w;j--){//注意条件 if(dp[j-w]+d>dp[j]){dp[j]=dp[j-w]+d;}}}printf("%d\n",dp[m]);return 0;
}

Vanya and Lanterns(最大覆盖半径)

实现的算法主要是基于排序和扫描的方式来解决一个具体问题,即找出能够使得所有路段上的点都被路灯覆盖所需的最小最大半径。具体步骤如下:

  1. 输入读取:首先读取路灯数量(n)和路的总长度(l),然后读取每个路灯所在的位置。

  2. 排序:使用std::sort函数对路灯位置数组进行排序,这样可以确保位置按升序排列,便于后续处理。

  3. 最大间距计算:通过遍历排序后的路灯位置数组,计算相邻路灯之间的距离并取其中的最大值的一半作为可能的最大覆盖半径的一个候选值。这是因为任何位置上的点到相邻两个路灯的最远距离不会超过这两个路灯间距的一半。

  4. 处理边界情况:检查第一个和最后一个路灯位置与路的两端点的关系,以确定是否存在路的两端没有直接被路灯覆盖的情况。如果路的开始位置或结束位置没有路灯,则需要将这些未覆盖的路段长度与之前计算的最大间距的一半比较,取其中的最大值作为实际的最大覆盖半径。

  5. 输出结果:最后输出计算得到的最大覆盖半径,保留10位小数。

 

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<algorithm>
using namespace std;
double ans=0;
int n;
int l; 
double loc[1001]; 
int main(){scanf("%d %d",&n,&l);for(int i=0;i<n;i++)scanf("%lf",&loc[i]);sort(loc,loc+n) ;for(int i=0;i<n;i++)ans=max(ans,(loc[i]-loc[i-1])/2.0) ;if(loc[0]!=0)ans=max(ans,loc[0]) ;if(loc[n-1]!=l)ans=max(ans,l-loc[n-1]) ;printf("%.010lf\n",ans);return 0;
}

Anton and Danik(数值运算与字符串处理)

这段代码运用的是计数/统计算法思路来解决问题。具体步骤如下:

  1. 输入处理:首先,程序读取一个整数n,表示字符串s的长度。随后,读取一个长度为n的字符串s,该字符串只包含字符'A'和'D'。

  2. 统计字符:通过遍历字符串s,使用两个计数器cntAcntD分别记录字符'A'和'D'出现的次数。这是通过一个简单的循环实现的,每次遇到字符'A'就增加cntA的值,遇到'D'就增加cntD的值。

  3. 结果判断:遍历结束后,根据cntAcntD的值来判断并输出结果:

    • 如果cntA大于cntD,则输出"Anton",表示字符'A'(代表Anton)出现次数更多。
    • 如果cntD大于cntA,则输出"Danik",表示字符'D'(代表Danik)出现次数更多。
    • 代码中存在一处逻辑错误,应使用==而非=, 正确的判断条件应该是else if(cntA == cntD),此时输出"Friendship",表示两者出现次数相等,象征友谊。
#include<stdio.h>
#include<string.h>
#define MAX_N 100000
int main() {int n;scanf("%d",&n);char s[MAX_N];scanf("%s",s);int cntA=0,cntD=0;for(int i=0;i<n;i++){if(s[i]=='A')cntA++;else if(s[i]=='D')cntD++;}if(cntA>cntD)printf("Anton\n");		else if(cntD>cntA)printf("Danik\n");		else if(cntA=cntD)printf("Friendship\n");return 0;
}

题型统计

练习题名称数学计算与序列求和数值运算与字符串处理频率统计题数据处理与逻辑判断0-1背包问题最大覆盖半径
SUM Problem
A+B problem
Anton and letters
Sum of digits
寒冰王座
Charm Bracelet
Vanya and Lanterns
Anton and Danik

这篇关于ACM实训冲刺第二十一天的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1011701

相关文章

认识、理解、分类——acm之搜索

普通搜索方法有两种:1、广度优先搜索;2、深度优先搜索; 更多搜索方法: 3、双向广度优先搜索; 4、启发式搜索(包括A*算法等); 搜索通常会用到的知识点:状态压缩(位压缩,利用hash思想压缩)。

两个月冲刺软考——访问位与修改位的题型(淘汰哪一页);内聚的类型;关于码制的知识点;地址映射的相关内容

1.访问位与修改位的题型(淘汰哪一页) 访问位:为1时表示在内存期间被访问过,为0时表示未被访问;修改位:为1时表示该页面自从被装入内存后被修改过,为0时表示未修改过。 置换页面时,最先置换访问位和修改位为00的,其次是01(没被访问但被修改过)的,之后是10(被访问了但没被修改过),最后是11。 2.内聚的类型 功能内聚:完成一个单一功能,各个部分协同工作,缺一不可。 顺序内聚:

研一实训总结

说长不长说短不短的一个月,从最开始的激动到期间,要中期要兼顾找实习准备笔试面试的焦虑,再到最后一周的加班加点和总结,收获和感触还是蛮多的。 首先,这一个月让我更加全面的认知了完成一个从无到有项目的过程,激发了我对自己工程师职业生涯的向往和对自己有了更广的除了编码以外的要求。 我一直是一个结果导向和追求效率的人,所以在团队合作过程中我们也经历了最开始的不知所措,到争执,再到主动配合和贡献,这个过

【转载】ACM感悟

今天看了一篇我们学校前辈的ACM的感悟,觉得写的十分有道理,这里转载,文章还会不断的改进和更新。 原文链接:http://www.cnblogs.com/Chierush/p/3760870.html?ADUIN=1339764596&ADSESSION=1401536826&ADTAG=CLIENT.QQ.5329_.0&ADPUBNO=26349 声明:本文是写给弱校ACM新手的一点

我们依旧在追梦的路上-山东省第六届ACM比赛总结

这场比赛从结果而言达到了预期(金牌),从过程而言和我的预期相差甚远(打的太乱,个人发挥很差),还好关键时刻队友抗住压力,负责后果真的不堪设想。 热身赛 热身赛纯粹测机器的,先把A,B,C草草水过(A题小写x打成大写的也是醉了),我和老高开始各种测机器,long long不出所料是lld的,试了一下除0和数组越界的re问题,发现没有re,只有wa(甚至数组越界还AC了),至于栈深的话也没过多追

2024国赛论文拿奖快对照这几点及评阅要点,勿踩雷区!(国赛最后冲刺,提高获奖概率)

↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑ 2024“高教社杯”全国大学生数学建模竞赛已过去第三个夜晚,小伙伴们都累了没有,如果感到思维滞涩,别忘了稍作休息,放松一下自己,准备迎接国赛非常重要的收尾阶段——论文。 国赛这几天的努力最后都

ACM东北地区程序设计大赛

不得不说随着参赛级别的提高,题目真的是越来越难啊,不过队长真是给力啊,在我们三个共同努力之下拿下了地区赛三等奖,哈哈我们可是大一唯一一只获奖队,终于在这次比赛打败了田大神。。。大神是失手了,俺和他差距还是挺大的。。。队友陈彤马上要去服兵役了,他说这是我们送给他最好的离别礼物,希望那家伙在部队好好干,以后谁干揍我!!!东北地区赛结束后,今年已经估计没机会参加亚洲区比赛了,赶紧补高数和线数啊!!别挂了

ACM比赛中如何加速c++的输入输出?如何使cin速度与scanf速度相当?什么是最快的输入输出方法?

在竞赛中,遇到大数据时,往往读文件成了程序运行速度的瓶颈,需要更快的读取方式。相信几乎所有的C++学习者都在cin机器缓慢的速度上栽过跟头,于是从此以后发誓不用cin读数据。还有人说Pascal的read语句的速度是C/C++中scanf比不上的,C++选手只能干着急。难道C++真的低Pascal一等吗?答案是不言而喻的。一个进阶的方法是把数据一下子读进来,然后再转化字符串,这种方法传说中

2014年ACM/ICPC亚洲区现场赛广州赛区总结

本来不想提这件事的,后来学姐找我谈心时提到这件事,我突然意识到在这件事情上我错了一次,明明答应的去参加这场比赛,最后临时决定不去......其实中间有很多很多原因 1:我和tyh,sxk临时不去主要是广州太远,我们身上money不够,呵呵。。。别笑我们,你以为我们是高富帅啊,去一趟广州消费要2个月的生活费,奖学金又没发,你让我找我妈要她辛辛苦苦挣来的工资吗?!从哈尔滨到广州单来回的火车票每个人就

两个月冲刺软考——逻辑地址与物理地址的转换(例题+讲解);文件类型的考点

1.已知计算机系统页面大小和进程的逻辑地址,根据页面变换表(页号-物理块号),求变换后的物理地址。 首先介绍几个公式: 逻辑地址 = 页号 + 页内地址 (默认为32机位) 物理地址 = 物理块号 + 物理地址的页内地址 其中:页内地址 = 物理地址的页内地址 解题:由于页面大小为4K,即4K=2的12次方,占0~11位;也就是页内地址有12位,故十六进制数中的C28是页内地址,那