17级算法分析与设计上机考试

http://192.168.173.163/JudgeOnline/contest.php?cid=1262

问题 A: 进制转换

给定一个十进制正整数N,请将其转换为十六进制并输出。

输入

一个十进制正整数N。( 1 <= N <= 2×109 )

输出

输出N对应的十六进制,用数字 0~9 以及大写字母 A~F 来表示。

样例输入

1
2019

样例输出

1
7E3

思路:进制转化

问题 B: 背包问题

题目描述

在N件物品取出若干件放在容量为W的背包里,每件物品的体积为W1,W2……Wn(Wi为整数),与之相对应的价值为P1,P2……Pn(Pi为整数)。求背包能够容纳的最大价值。

输入

第1行,2个整数,N和W中间用空格隔开。N为物品的数量,W为背包的容量。(1 <= N <= 1000,1 <= W <= 105)
第2 ~ N+1行,每行2个整数,Wi和Pi,分别是物品的体积和物品的价值。(1 <= Wi <= 105,1 <= Pi <= 2×109)

输出

输出可以容纳的最大价值。

样例输入

1
2
3
4
3 6
2 5
3 8
4 9

样例输出

1
14

思路:01背包问题

问题 C: 迷宫问题

题目描述

给定一个N行M列的迷宫,其中’.’代表空地,可以通行;’#’代表障碍物,无法通行;’S’代表起点;’T’代表终点;’’S’和’T’这两个位置也是空地,可以通行。在迷宫中可以向上、下、左、右四个不同的方向行走,请你判断从起点出发是否可以走到终点?如果可以,请你计算到达终点最少需要走几步。

输入

第1行,2个整数,N和M,中间用空格隔开。N为迷宫的行,M为迷宫的列。(2 <= N,M <= 1000)
第2 ~ N+1行,每行M个字符,对应整个迷宫的布局,输入数据中保证只有’.’,’#’,’S’,’T’这四种字符,并且只有一个’S’,只有一个’T’。

输出

如果可以到达终点,输出两行,第一行输出”YES”,第二行输出一个整数代表最少需要走几步。如果无法到达终点,输出”NO”

样例输入

1
2
3
4
5
4 9
#S#.#.#T#
#....##.#
#.##....#
#....####

样例输出

1
2
YES
10

思路:dfs

问题 D: 素数问题

题目描述

葬爱家族的Halobin近在研究素数,他想知道对于两个整数x和y(x>y),能否找到若干个素数p1,p2,…pk,使得x=y+p1+p2+…+pk。注意素数可以无限重复使用,例如x=9,y=1,那么只需要用4个2就可以了,即9=1+2+2+2+2. 请你帮他解决这个问题。

输入

第一行输入数据组数T(T<100)

接下来T行每行输入两个整数x和y(0<y<x<109)

输出

如果能找到若干个素数满足条件,输出“YES”,否则输出“NO”

样例输入

1
2
3
4
5
4
100 98
42 36
100000000 1
41 40

样例输出

1
2
3
4
YES
YES
YES
NO

思路:贪心算法

问题 E: 锯木棒

题目描述

xiaok大佬最近再雇佣工人给他掰木棒。把一根长为L的木棒锯成两段,他需要支付给工人L元钱。xiaok大佬一开始只有长为L的一根木棒,他想把它锯成n段,每段长度分别为L1,L2,…,Ln,问xiaok大佬最少要付给工人多少钱?

输入

第一行两个整数n,L(1<n<103,n<L<109)

第二行n个整数L1,L2,…,Ln(0<Li<L,且保证L1+L2+…+Ln=L)

输出

输出一个整数,表示最小花费

样例输入

1
2
3 21
8 5 8

样例输出

1
34

提示

先把木棒锯成13和8两段,花费21,再把13那段锯成5和8,花费13,总花费13+21=34

思路:动态规划合并问题

!@#¥^%@$#>#…

至于为什么只有思路没有代码…

连做得最多的人也只做了三道…

不是不会做,是时间超限令人窒息

01背包和堆沙这样的问题连规整的代码也时间超限我也是佛啦

为什么考迷宫问题咱也不敢问

考试时间要是再多点我可能会考虑看看题面

image.png

-------------end ♥-------------