算法实验上机考试
问题 A: 进制转换
题目描述
给定一个十进制正整数N，请将其转换为十六进制并输出。
输入
一个十进制正整数N。( 1 <= N <= 2×109 )
输出
输出N对应的十六进制，用数字 0~9 以及大写字母 A~F 来表示。
样例输入
2019
样例输出
7E3
提示
递归
代码
#include<bits/stdc++.h>
using namespace std;
char *t="0123456789ABCDEF";
void f(int n)
{
if(n>0)
{
f(n/16);
cout<<t[n%16];
}
}
int main()
{
int m;
cin>>m;
f(m);
cout<<endl;
}
问题 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)
输出
输出可以容纳的最大价值。
样例输入
3 6
2 5
3 8
4 9
样例输出
14
提示
肯定是递归做，但是dp数组用二维的不知道为什么总是数组超限，考完和同学交流了一下，发现不是个例，考试的时候我还提交了一维的写法，但是时间又超限了，时间卡在1040，差40就可以过了，但是我交了30多遍也没用，代码就不贴出来了（我还是太弱了）。
问题 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”。
样例输入
4 9
#S#.#.#T#
#....##.#
#.##....#
#....####
样例输出
YES
10
提示
回溯，但是考试前觉得不会考，也没怎么看，拿到手有思路，就是没写出来（话说好像和数据结构实验的最后一题差不多）
问题 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
输出
如果能找到若干个素数满足条件，输出“YES”，否则输出“NO”
样例输入
4
100 98
42 36
100000000 1
41 40
样例输出
YES
YES
YES
NO
提示
这题本是签到题，但是老师中途说了思路（两数之差是1就不可能，不是就可以），我感觉是实在看不下去我们做的题了，所以才来告诉我们答案，感觉智商被按在地上摩擦。
代码
#include<bits/stdc++.h>
using namespace std;
int main()
{
int t,x,y;
cin>>t;
for(int i=0;i<t;i++)
{
cin>>x>>y;
if((x-y)>1)
{
cout<<"YES"<<endl;
}
else
cout<<"NO"<<endl;
}
}
问题 E: 锯木棒
题目描述
xiaok大佬最近再雇佣工人给他掰木棒。把一根长为L的木棒锯成两段，他需要支付给工人L元钱。xiaok大佬一开始只有长为L的一根木棒，他想把它锯成n段，每段长度分别为L1,L2,…,Ln，问xiaok大佬最少要付给工人多少钱？
输入
第一行两个整数n,L(1
第二行n个整数L1,L2,…,Ln（0<Li<L,且保证L1+L2+…+Ln=L）
输出
输出一个整数，表示最小花费
样例输入
3 21
8 5 8
样例输出
34
提示
先把木棒锯成13和8两段，花费21，再把13那段锯成5和8，花费13，总花费13+21=34
很明显，贪心，设个优先级队列，（参考哈夫曼树）
代码
#include<bits/stdc++.h>
using namespace std;
struct cmp1
{
bool operator()(int& a,int& b)
{
return a>b;
}
};
int main()
{
priority_queue<int,vector<int>,cmp1> pq;
int n,l,s;
cin>>n>>l;
for(int i=0;i<n;i++)
{
cin>>s;
pq.push(s);
}
int sum=0;
while(pq.size()>1)
{
int a=pq.top();
pq.pop();
int b=pq.top();
pq.pop();
sum=sum+a+b;
pq.push(a+b);
}
cout<<sum<<endl;
}
