第一题 宇宙总统

题目描述

地球历公元 6036 年，全宇宙准备竞选一个最贤能的人当总统，共有 $n$ 个非凡拔尖的人竞选总统，现在票数已经统计完毕，请你算出谁能够当上总统。

输入格式

第一行为一个整数 $n$，代表竞选总统的人数。

接下来有 $n$ 行，分别为第一个候选人到第 $n$ 个候选人的票数。

输出格式

共两行，第一行是一个整数 $m$，为当上总统的人的号数。

第二行是当上总统的人的选票。

样例 #1

样例输入 #1

5
98765
12365
87954
1022356
985678
1
2
3
4
5
6

样例输出 #1

4
1022356
1
2

提示

票数可能会很大，可能会到 $100$ 位数字。

$1\le n\le 20$

解题思路

• 1）数字可以用字符串存储。
• 2）可以直接比较字符串的位数，记录大的一方。若相等，直接比较大小，记录大的一方。
• 3）进行输出。

参考代码

#include
using namespace std;    
int main()    
{
    string a,b;
    int n;
    int x=1;
    cin>>n;
    cin>>a;
    for(int i=2;i<=n;i++)
    {
        cin>>b;
        if(a.length()<b.length())
        {
            a=b;
            x=i;
           
        }
        else if(a<b&&a.length()==b.length())
        {
            a=b;
            x=i;
        }
    }
     cout<<x<<endl<<a;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

第二题 [HAOI2012] 音量调节

题目描述

一个吉他手准备参加一场演出。他不喜欢在演出时始终使用同一个音量，所以他决定每一首歌之前他都需要改变一次音量。在演出开始之前，他已经做好一个列表，里面写着每首歌开始之前他想要改变的音量是多少。每一次改变音量，他可以选择调高也可以调低。

音量用一个整数描述。输入文件中整数 $beginLevel$，代表吉他刚开始的音量，整数 $maxLevel$，代表吉他的最大音量。音量不能小于 $0$ 也不能大于 $maxLevel$。输入中还给定了 $n$ 个整数 $c_1,c_2,c_3,\cdots ,c_n$，表示在第 $i$ 首歌开始之前吉他手想要改变的音量是多少。

吉他手想以最大的音量演奏最后一首歌，你的任务是找到这个最大音量是多少。

输入格式

第一行依次为三个整数 $n$，$beginLevel$ 和 $maxLevel$。

第二行依次为 $n$ 个整数 $c_1,c_2,c_3,\cdots ,c_n$。

输出格式

输出演奏最后一首歌的最大音量。如果吉他手无法避免音量低于 $0$ 或者高于 $maxLevel$，输出 -1。

样例 #1

样例输入 #1

3 5 10
5 3 7
1
2

样例输出 #1

10
1

提示

$1\le n\le 50$，$1\le c_i\le maxLevel$，$1\le maxLevel\le 1000$，$0\le beginLevel\le maxLevel$。

解题思路

• 1）01背包问题。
• 2）背包之后倒序找最大能达到的音量。
• 2）找到了进行输出。

参考代码

#include
using namespace std;
long long dp[10500][10200];
int main()
{
	int n,b,m;
	cin>>n>>b>>m;
	dp[0][b]=1;
	for(int i=1;i<=n;i++)
	{
		int c;
		cin>>c;
		for(int j=m;j>0;j--)
		{
                dp[i][j]=(dp[i][j]||dp[i-1][j+c]||dp[i-1][j-c]);
		}
	}
	
	for(int j=m;j>0;j--)
	{
		if(dp[n][j]==1)
		{
			cout<<j;
			return 0;
		}
	}
	cout<<-1;
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

第三题 高低位交换

题目描述

给出一个小于$2^{32}$的正整数。这个数可以用一个$32$位的二进制数表示（不足$32$位用$0$补足）。我们称这个二进制数的前$16$位为“高位”，后$16$位为“低位”。将它的高低位交换，我们可以得到一个新的数。试问这个新的数是多少（用十进制表示）。

例如，数$1314520$用二进制表示为$00000000000101000000111011011000$（添加了$11$个前导$0$补足为$32$位），其中前$16$位为高位，即$0000000000010100$；后$16$位为低位，即$0000111011011000$。将它的高低位进行交换，我们得到了一个新的二进制数$00001110110110000000000000010100$。它即是十进制的$249036820$。

输入格式

一个小于$2^{32}$的正整数

输出格式

将新的数输出

样例 #1

样例输入 #1

1314520
1

样例输出 #1

249036820
1

解题思路

• 1）位运算问题，可以看看这个文章了解一下 点这里！！！
• 2）将原数的后16位前移至新数的前16位。
• 3）将原数的前16位前移至新数的后16位。

参考代码

#include
using namespace std;
int main()
{
    unsigned long long n;
    cin>>n;
    cout<<((n&0x0000ffff)<<16|(n&0xffff0000)>>16);
}
1
2
3
4
5
6
7
8

第四题 【深基16.例1】淘汰赛

题目描述

有 $2^n(n\le 7)$ 个国家参加世界杯决赛圈且进入淘汰赛环节。已经知道各个国家的能力值，且都不相等。能力值高的国家和能力值低的国家踢比赛时高者获胜。1 号国家和 2 号国家踢一场比赛，胜者晋级。3 号国家和 4 号国家也踢一场，胜者晋级……晋级后的国家用相同的方法继续完成赛程，直到决出冠军。给出各个国家的能力值，请问亚军是哪个国家？

输入格式

第一行一个整数 $n$，表示一共 $2^n$ 个国家参赛。

第二行 $2^n$ 个整数，第 $i$ 个整数表示编号为 $i$ 的国家的能力值（$1\le i\le 2^n$）。

数据保证不存在平局。

输出格式

仅一个整数，表示亚军国家的编号。

样例 #1

样例输入 #1

3
4 2 3 1 10 5 9 7
1
2

样例输出 #1

1
1

解题思路

• 1）冠亚军应该从左半部分的最强者和右半部分的最强者中产生。
• 2）找到左半部分的最强者。
• 3）找到右半部分的最强者。
• 4）比较，输出答案。

参考代码

#include 
using namespace std;
struct gj {
    int hm;
    int nl=0;
};

int main() 
{
    int n;
    gj maxl, maxr;
    gj a;
    cin >> n;
    for (int i=0;i<pow(2,n-1);i++) 
    {
        cin >>a.nl;
        if (a.nl>maxl.nl) 
        {
            maxl.nl=a.nl;
            maxl.hm=i+1;
        }
    }

    for (int i=pow(2,n-1);i<pow(2,n);i++) 
    {
        cin>>a.nl;
        if (a.nl>maxr.nl)
        {
            maxr.nl=a.nl;
            maxr.hm=i+1;
        }
    }
    if (maxl.nl>maxr.nl)cout << maxr.hm;
    else cout << maxl.hm;
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36