算法实验上机考试

问题 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(09</sup>)

输出

如果能找到若干个素数满足条件,输出“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(13</sup>,n9</sup>)

第二行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;
}