3月5日定位赛题解

  • 内容
  • 评论
  • 相关

}32A1XWXFD~VQ07(~FX4A58

题目名称:第几天?

题目来源:平顶山学院ACM算法攻关部

给定一个年月日的日期,来算这是这一年的第几天。

输入

输入数据有多组,每组占一行,数据格式为YYYY.MM.DD组成,具体参见sample input ,另外,可以向你确保所有的输入数据是合法的。

输出

对于每组输入数据,输出一行,表示该日期是该年的第几天。

样例输入

1985.1.20

2006.3.12

样例输出

20

71

  • 考核知识点

数学思维

  • 常见误区

这道题没有什么误区,简单数学题

  • 解题思路

我的解题思路是把一年当成13个月,然后日的数字就是第13个月的几天,到最后再把本来这个月份有几天减去,就是第几天。然后这个时候我们是把所有都当成平年来算的,最后在判断是否是闰年,并且月份大于2的时候再加1就可以了。

  • 参考答案(附关键注释)
    • 整理者

    学号姓名 :151210104  郭旭东

    院系 :计算机学院(软件学院)

    专业班级: 15计科1班

 

  • 题目描述

题目名称:括号匹配

题目来源:平顶山学院ACM算法攻关部

现在有一行括号让你来判断是否匹配,多组输入数据,每组输入数据都是一个字符串S(S的长度小于10000,且S不是空串),数据保证S中只含有"[","]","(",")"四种字符。每组输入数据的输出占一行,如果该字符串中所含的括号是配对的,则输出Yes,如果不配对则输出No。

输入

多组输入数据,每组输入数据都是一个字符串S(S的长度小于10000,且S不是空串),数据保证S中只含有"[","]","(",")"四种字符。

输出

每组输入数据的输出占一行,如果该字符串中所含的括号是配对的,则输出Yes,如果不配对则输出No。

样例输入

[(])

(])

([[]()])

样例输出

No

No

Yes

  • 考核知识点

关于栈的基本操作

  • 常见误区

栈的基本操作的用法

  • 解题思路

本题主要考察的对栈的用法,括号一个一个进栈并进行与下一个元素的匹配,最后判断栈内元素是否为空即可解出此题

特别提示

[[[[][]]()]()][([(][)])]这种括号匹配是错误的

  • 参考答案(附关键注释)
    • 整理者

    学号姓名 :151210118  黄峥

    院系 :计算机学院(软件学院)

    专业班级: 15计科1班

 

 

 

  • 题目描述

题目名称:ip

题目来源:平顶山学院ACM算法攻关部

判断字符串是不是一个合法的ip地址.为简单考虑,仅考虑ipv4的情况,即合法ip为形同"a1.a2.a3.a4",且0<=ai<=255。

输入

多组测试数据,每组一个字符串,其中不包括空格,Tab以及回车。

输出

若合法,输出"Yes",否则输出"No"。

样例输入

110.1.2.51

f.a.t.e

样例输出

Yes

No

提示

我们认为110.001.002.051是合法的。

  • 考核知识点

逻辑思维能力

  • 常见误区

这道题误区在于对于ip的一个要求,ip不仅要求当前的数字在0~255之间,“0000”这种情况虽然

满足要求,但是也是不合法的ip。

  • 解题思路

我的解题思路是吧当前给出的字符串进行处理,逐步谈论ip需要满足的条件,一旦当前的ip不满足所给定的条件的话,就认为当前的ip不合法,没有不要再往下进行判断。否则的话就要一步一步进行判断直到满足所有的条件,才能认为当前的ip是合法的。

    • 整理者

    学号姓名 :151210114  崔梦梦

    院系 :计算机学院(软件学院)

    专业班级: 15计科1班

 

 

 

  • 题目描述

题目名称:斐波那契字符串

题目来源:平顶山学院ACM算法攻关部

相信大家对斐波那契数列都非常熟悉,现在我们对斐波那契数列做一个变形,我们定义:str[n] = str[n-1] + str[n-2](n > 1)。例如:如果str[0] = "ab"; str[1] = "bc";那么得到的结果是str[2]="abbc", str[3]="bcabbc" , str[4]="abbcbcabbc" …………;

输入

多组测试数据,每组测试数据包括两个字符串和一个整数K(0<=K<=50),字符串都是小写,且长度小于30。

输出

对于每一个测试数据,要求你求出第K个斐波那契数列字符串的字母的个数。

样例输入

ab bc 3

样例输出

a:1

b:3

c:2

d:0

e:0

f:0

g:0

h:0

i:0

j:0

k:0

l:0

m:0

n:0

o:0

p:0

q:0

r:0

s:0

t:0

u:0

v:0

w:0

x:0

y:0

z:0

 

  • 考核知识点

数组模拟。

  • 常见误区

可能直接用C++的string去做,简单的字符串相加,最后在测长度,统计字母个数。

  • 解题思路

此题看起来并不难,但是一般一看到就是直接用C++的string类型去解题,然后向求普通的斐波那契数去求解,最后测字符串的长度,并统计各个字符的个数,但是这样是不行的,内存会爆掉,为什么会这样呢?测试数据中明确说了给的初始的两个字符串最长长度为30,斐波那契数最多让求到50,那么我们就考虑最极端的情况,假如第一个字符串给30个’a’,第二个字符串也给30个’a’,则第三个字符串就有60个’a’,第四个字符串就有90个’a’,第五个字符串就有150个’a’……可以看出字符串的长度增加的是非常快的,如果用string可以想象求第五十个斐波那契数字符串是多么的长啊!会造成内存超限。因此我想到用数组去存各个字符的个数。对于输入的两个字符串,先统计字符串中各个字符的个数,然后第三个字符串中各个字符的个数等于这两个数组对应位置的数相加,然后用数组2刷新数组1,在用数组3刷新数组2,然后重复该过程。因为就如所举的非常极限的例子,最后整个字符串都只由一个字符组成,且让求第50个斐波那契数,则整型数组里面的数会非常大,那么用int类型的就会造成溢出,因此设置的数组的长度应该是long long int类型。这也是这道题目的易错点之一。

  • 参考答案(附关键注释)
    • 整理者

    学号姓名 :151210107  温雅新

    院系 :计算机学院(软件学院)

    专业班级: 15计科1班

 

 

 

  • 题目描述

题目名称:买糖果

题目来源:平顶山学院ACM算法攻关部

现在你有M块钱,准备去买糖果,在商店里有着各式各样的糖果,现在要求你把你的钱用光去尽量买更多的糖果。其中J[i]代表一种糖果的重量,F[i]代表买完这种糖果的价格。为了获得最大重量的糖果,你可以选取其中一部分。

输入

多组测试数据,每组测试数据包括两个整数M,N其中M代表你身上的钱,N代表N中粮食。接下来N行,每行两个数J[i],F[i],代表每种糖果的重量和价格。

输出

输出获取糖果的最大重量,结果保留3位小数。

样例输入

5 3

7 2

4 3

5 2

20 3

25 18

24 15

15 10

样例输出

13.333

31.500

  • 考核知识点

贪心算法

  • 常见误区

排序要排单价的水果,同时水果的重量和价格要跟着单价的水果一起排序。

  • 解题思路

本题是一个简单的贪心算法的题目,根据贪心算法的思想,算出单价能买到的水果,根据单价水果量多的排序,我用的是结构体排序,整体排序。

  • 参考答案(附关键注释)
    • 整理者

    学号姓名 :151210132 许娜

    院系 :计算机学院(软件学院)

    专业班级: 15计科1班

 

 

 

 

现在有一个迷宫,'a'代表起点位置,'.'代表可以通行的路,'#'代表不能通过的墙,'x'代表迷宫的守卫,'r'代表终点位置,现在要求你算出起点位置到终点位置的最短时间,其中通过'.'时,消耗1个单位时间,通过'x'消耗两个单位时间。

  • 考核知识点

常见的广搜题,不同的是要运用优先队列。

  • 常见误区

忽略了当碰到迷宫守卫时花费的时间为2,而其他情况是1。

  • 解题思路

首先要考虑它到达一个位置,路上会碰到三种情况,一是’#’,此时不能通过,二是’.’,此时可以通过,消耗一个单位时间,三是’X’,表示碰到守卫,要花费2个单位时间,虽然同一时间到达,但是通过此位置所消耗的时间不一样,题目要求输出到终点位置的最短时间,采用优先队列,可以使时间短的先出队,刚好解决了普通队列解决不了的此问题。

  • 参考答案(附关键注释)

 

 

 

 

  • 整理者

学号姓名 :151060145  陈杨

院系 :计算机学院(软件学院)

专业班级: 15计科2班

评论

0条评论

发表评论

电子邮件地址不会被公开。 必填项已用*标注