Java代码题m个小朋友分糖果,王道论坛研究生机试练习赛(二)

2023-10-15 13:10

本文主要是介绍Java代码题m个小朋友分糖果,王道论坛研究生机试练习赛(二),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

昨天在微博上看到王道论坛说晚上有机试练习赛(http://ac.jobdu.com/contest.php?cid=1053),想来反正也没什么事,何不参加一下。于是晚上吃完饭回到实验室,等着七点开始做题。练习赛结束了,虽然自己全部AC,但感觉时间花的有点长,主要卡在第三道求公约数个数上。看来自己的数论真的弱爆了。现将自己对这四道解题的看法归纳一下,总的来说题目不算很难,前两道超级水,第三道考素数筛选以及因式分解,第四道动态规划。

一、调整方阵

对应题目1470:http://ac.jobdu.com/problem.php?pid=1470

题目描述:

输入一个N(N<=10)阶方阵,按照如下方式调整方阵:

1.将第一列中最大数所在的行与第一行对调。

2.将第二列中从第二行到第N行最大数所在的行与第二行对调。

依此类推...

N-1.将第N-1列中从第N-1行到第N行最大数所在的行与第N-1行对调。

N.输出这个方阵

输入:

包含多组测试数据,每组测试数据第一行为一个整数N,表示方阵的阶数.

接下来输入这个N阶方阵.

输出:

调整后的方阵

样例输入:

4

3 6 8 7

6 7 5 3

8 6 5 3

9 8 7 2

样例输出:

9 8 7 2

6 7 5 3

3 6 8 7

8 6 5 3

水题,就不多说了。代码

69c5a8ac3fa60e0848d784a6dd461da6.png1 #include

2

3 int data[10][10];4

5 void adjustment(int i,intn);6 intmain()7 {8 intN;9 inti,j;10 while(scanf("%d",&N) !=EOF){11 for(i=0;i

27 void adjustment(int i,intn)28 {29 int max_i =i;30 int j = i+1;31 int temp[10];32 for(;jdata[max_i][i])34 max_i =j;35 if(max_i !=i){36 for(j=0;j

69c5a8ac3fa60e0848d784a6dd461da6.png

二、货币问题

对应题目1549:http://ac.jobdu.com/problem.php?pid=1549

题目描述:

已知有面值为1元,2元,5元,10元,20元,50元,100元的货币若干(可认为无穷多),需支付价格为x的物品,并需要恰好支付,即没有找零产生。

求,至少需要几张货币才能完成支付。

如,若支付价格为12元的物品,最少需要一张10元和一张2元,即两张货币就可完成支付。

输入:

输入包含多组测试数据,每组仅包含一个整数p(1<=p<=100000000),为需支付的物品价格。

输出:

对于每组输入数据,输出仅一个整数,代表最少需要的货币张数。

样例输入:

10

11

13

样例输出:

1

2

3

也是水题吧,有点贪心的思想吧。先尽可能用最大面值,然后依次考虑较小面值。这题如果限制货币的数量的话,应该就是0-1背包问题吧。

代码

69c5a8ac3fa60e0848d784a6dd461da6.png1 #include

2

3 intmain()4 {5 intp;6 inti;7 intsum;8 int money[7] = {1,2,5,10,20,50,100};9 while(scanf("%d",&p) !=EOF){10 sum = 0;11 for(i=6;i>=0;--i){12 sum += (p/money[i]);13 p %=money[i];14 }15 printf("%d\n",sum);16 }17 return 0;18 }

69c5a8ac3fa60e0848d784a6dd461da6.png

三、公约数

对应题目1493:http://ac.jobdu.com/problem.php?pid=1493

题目描述:

给定两个正整数a,b(1<=a,b<=100000000),计算他们公约数的个数。

如给定正整数8和16,他们的公约数有:1、2、4、8,所以输出为4。

输入:

输入包含多组测试数据,每组测试数据一行,包含两个整数a,b。

输出:

对于每组测试数据,输出为一个整数,表示a和b的公约数个数。

样例输入:

8 16

22 16

样例输出:

4

2

一直被卡在这道题的超时上。我的做法:采用素数筛选法通过函数computePrime(int n,int

maxC)返回第n个素数,其中只需要判断maxC之前的数,注意为了减少空间,我把所有的偶数(当然除了2)都去掉了,所以flag数组只有总数M的一半。在主函数里,首先求出最大公约数,则公约数的个数就等于这个最大公约数的所有约数个数,然后对这个公约数进行因式分解。即假设最大公约数为maxC,则其因式分解为:

\begin{equation*}maxC=p_1^{x_1}\times p_2^{x_2}\times\cdots\times

p_m^{x_m}\end{equation*}

所以其公约数个数为: $(x_1+1)\times(x_2+1)\times\cdots\times(x_m+1)$,这个好像叫约数个数定理吧。

代码:

69c5a8ac3fa60e0848d784a6dd461da6.png1 #include

2 #include

3

4 #define M 100000000

5 bool flag[M/2];6 int prime[6000000];7 intprimeNum;8

9 int computePrime(int n,intmaxC)10 {11 if(n == 1){12 prime[primeNum++] = 2;13 return 2;14 }15 if(n == 2){16 prime[primeNum++] = 3;17 return 3;18 }19 inti,j;20 intpos;21 i = prime[primeNum-1]+2;22 while(primeNum >1);24 if(!flag[pos]){25 prime[primeNum++] =i;26 j = 3*i;27 while(j<=maxC){28 flag[(j-3)>>1] = 1;29 j += (i<<1);30 }31 }32 i += 2;33 }34 return prime[n-1];35 }36 intmain()37 {38 inta,b;39 intsum;40 intmaxC,i,j;41 primeNum = 0;42 while(scanf("%d%d",&a,&b) !=EOF){43 intt;44 while(a%b != 0){45 t =a;46 a =b;47 b = t%b;48 }49 maxC =b;50 sum = 1;51 i = 0;52 intprime_i;53 while(maxC != 1){54 prime_i = computePrime(i+1,maxC);55 if(maxC %prime_i)56 ++i;57 else{58 t=0;59 while(maxC%prime_i == 0){60 ++t;61 maxC /=prime_i;62 }63 sum *= (t+1);64 ++i;65 }66 }67 printf("%d\n",sum);68 }69 return 0;70 }

69c5a8ac3fa60e0848d784a6dd461da6.png

四、分糖果

对应题目1550:http://ac.jobdu.com/problem.php?pid=1550

题目描述:

给从左至右排好队的小朋友们分糖果,

要求:

1.每个小朋友都有一个得分,任意两个相邻的小朋友,得分较高的所得的糖果必须大于得分较低的,相等则不作要求。

2.每个小朋友至少获得一个糖果。

求,至少需要的糖果数。

输入:

输入包含多组测试数据,每组测试数据由一个整数n(1<=n<=100000)开头,接下去一行包含n个整数,代表每个小朋友的分数Si(1<=Si<=10000)。

输出:

对于每组测试数据,输出一个整数,代表至少需要的糖果数。

样例输入:

3

1 10 1

3

6 2 3

2

1 1

样例输出:

4

5

2

看完题目,第一反应是要用动态规划解决。其最优子结构为:假如我们已经解决了(s,mid)以及(mid+1,e)这两个子问题,那么我们现在要按如下方法解决子问题(s,e)。首先分三种情况:1)score[mid]=score[mid+1];2)score[mid]

> score[mid+1];3)score[mid] < score[mid+1]。

1)由于分数相等的话对糖果的分配不做要求,所以最小的糖果数是两个子问题的和。

2)左边的分数大。此时若左边的糖果多的话,则最小糖果数也是两个子问题的和;否则调整左边的糖果分配,先将[mid]位置的糖果数分配为比[mid+1]位置多一个,然后从mid到s进行调整。

3)右边的分数大。此时若右边的糖果多的话,则最小糖果数也是两个子问题的和;否则调整右边的糖果分配,先将[mid+1]位置的糖果数分配为比[mid]位置多一个,然后从mid+1到e进行调整。

代码

69c5a8ac3fa60e0848d784a6dd461da6.png1 #include

2

3 int candyNum[100000];4 int score[100000];5

6 int distributeCandy(int,int);7 intmain()8 {9 intn,i;10 while(scanf("%d",&n)!=EOF){11 for(i=0;i

19 int distributeCandy(int s,inte)20 {21 if(s ==e){22 candyNum[s] = 1;23 return 1;24 }else if(s+1 ==e){25 if(score[s] ==score[e]){26 candyNum[s] = candyNum[e] = 1;27 return 2;28 }else if(score[s] >score[e]){29 candyNum[s] = 2;30 candyNum[e] = 1;31 return 3;32 }else{33 candyNum[s] = 1;34 candyNum[e] = 2;35 return 3;36 }37 }else{38 int total = 0;39 int mid = (s+e)/2;40 int left =distributeCandy(s,mid);41 int right = distributeCandy(mid+1,e);42 if(score[mid] == score[mid+1]){43 return left +right;44 }else if(score[mid] > score[mid+1]){45 if(candyNum[mid] > candyNum[mid+1])46 return left+right;47 else{48 total += (candyNum[mid+1]+1-candyNum[mid]);49 candyNum[mid] = candyNum[mid+1] + 1;50 int i = mid - 1;51 int totalAdd = 0;52 for(;i>=s;--i){53 if(score[i] <= score[i+1] || (score[i] > score[i+1] && candyNum[i] > candyNum[i+1]))54 break;55 else{56 total += (candyNum[i+1]+1-candyNum[i]);57 candyNum[i] = candyNum[i+1] +1;58 }59 }60 return left+right+total;61 }62 }else{63 if(candyNum[mid] < candyNum[mid+1])64 return left+right;65 else{66 total += (candyNum[mid]+1-candyNum[mid+1]);67 candyNum[mid+1] = candyNum[mid]+1;68 int i = mid+2;69 for(;i<=e;++i){70 if(score[i] <= score[i-1] || (score[i] > score[i-1] && candyNum[i] > candyNum[i-1]))71 break;72 else{73 total += (candyNum[i-1]+1-candyNum[i]);74 candyNum[i] = candyNum[i-1]+1;75 }76 }77 return left+right+total;78 }79 }80 }81 }

69c5a8ac3fa60e0848d784a6dd461da6.png

PS:此次第一名竟然在十四分钟内四道题全部AC,真是不可思议,估计有些题之前做过,直接拷贝过去或者稍微改一下。

原文:http://www.cnblogs.com/boostable/p/online_judge_1470_1549_1493_1550.html

这篇关于Java代码题m个小朋友分糖果,王道论坛研究生机试练习赛(二)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



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

相关文章

Python Transformers库(NLP处理库)案例代码讲解

《PythonTransformers库(NLP处理库)案例代码讲解》本文介绍transformers库的全面讲解,包含基础知识、高级用法、案例代码及学习路径,内容经过组织,适合不同阶段的学习者,对... 目录一、基础知识1. Transformers 库简介2. 安装与环境配置3. 快速上手示例二、核心模

Spring Boot 整合 SSE的高级实践(Server-Sent Events)

《SpringBoot整合SSE的高级实践(Server-SentEvents)》SSE(Server-SentEvents)是一种基于HTTP协议的单向通信机制,允许服务器向浏览器持续发送实... 目录1、简述2、Spring Boot 中的SSE实现2.1 添加依赖2.2 实现后端接口2.3 配置超时时

Spring Boot读取配置文件的五种方式小结

《SpringBoot读取配置文件的五种方式小结》SpringBoot提供了灵活多样的方式来读取配置文件,这篇文章为大家介绍了5种常见的读取方式,文中的示例代码简洁易懂,大家可以根据自己的需要进... 目录1. 配置文件位置与加载顺序2. 读取配置文件的方式汇总方式一:使用 @Value 注解读取配置方式二

一文详解Java异常处理你都了解哪些知识

《一文详解Java异常处理你都了解哪些知识》:本文主要介绍Java异常处理的相关资料,包括异常的分类、捕获和处理异常的语法、常见的异常类型以及自定义异常的实现,文中通过代码介绍的非常详细,需要的朋... 目录前言一、什么是异常二、异常的分类2.1 受检异常2.2 非受检异常三、异常处理的语法3.1 try-

Java中的@SneakyThrows注解用法详解

《Java中的@SneakyThrows注解用法详解》:本文主要介绍Java中的@SneakyThrows注解用法的相关资料,Lombok的@SneakyThrows注解简化了Java方法中的异常... 目录前言一、@SneakyThrows 简介1.1 什么是 Lombok?二、@SneakyThrows

Java中字符串转时间与时间转字符串的操作详解

《Java中字符串转时间与时间转字符串的操作详解》Java的java.time包提供了强大的日期和时间处理功能,通过DateTimeFormatter可以轻松地在日期时间对象和字符串之间进行转换,下面... 目录一、字符串转时间(一)使用预定义格式(二)自定义格式二、时间转字符串(一)使用预定义格式(二)自

Spring 请求之传递 JSON 数据的操作方法

《Spring请求之传递JSON数据的操作方法》JSON就是一种数据格式,有自己的格式和语法,使用文本表示一个对象或数组的信息,因此JSON本质是字符串,主要负责在不同的语言中数据传递和交换,这... 目录jsON 概念JSON 语法JSON 的语法JSON 的两种结构JSON 字符串和 Java 对象互转

JAVA保证HashMap线程安全的几种方式

《JAVA保证HashMap线程安全的几种方式》HashMap是线程不安全的,这意味着如果多个线程并发地访问和修改同一个HashMap实例,可能会导致数据不一致和其他线程安全问题,本文主要介绍了JAV... 目录1. 使用 Collections.synchronizedMap2. 使用 Concurren

Java Response返回值的最佳处理方案

《JavaResponse返回值的最佳处理方案》在开发Web应用程序时,我们经常需要通过HTTP请求从服务器获取响应数据,这些数据可以是JSON、XML、甚至是文件,本篇文章将详细解析Java中处理... 目录摘要概述核心问题:关键技术点:源码解析示例 1:使用HttpURLConnection获取Resp

Java的栈与队列实现代码解析

《Java的栈与队列实现代码解析》栈是常见的线性数据结构,栈的特点是以先进后出的形式,后进先出,先进后出,分为栈底和栈顶,栈应用于内存的分配,表达式求值,存储临时的数据和方法的调用等,本文给大家介绍J... 目录栈的概念(Stack)栈的实现代码队列(Queue)模拟实现队列(双链表实现)循环队列(循环数组