第一题 宇宙总统
题目描述
地球历公元 6036 年，全宇宙准备竞选一个最贤能的人当总统，共有 n个非凡拔尖的人竞选总统，现在票数已经统计完毕，请你算出谁能够当上总统。
输入格式
第一行为一个整数 n，代表竞选总统的人数。
接下来有 n 行，分别为第一个候选人到第 n 个候选人的票数。
输出格式
共两行，第一行是一个整数 m，为当上总统的人的号数。
第二行是当上总统的人的选票。
样例 #1
样例输入 #1
5 98765 12365 87954 1022356 985678
样例输出 #1
4 1022356
提示
票数可能会很大，可能会到 100 100100 位数字。
1 ≤ n ≤ 20
解题思路
1）数字可以用字符串存储。
2）可以直接比较字符串的位数，记录大的一方。若相等，直接比较大小，记录大的一方。
3）进行输出。
参考代码
#include<bits/stdc++.h> 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; }
第二题 [HAOI2012] 音量调节
题目描述
一个吉他手准备参加一场演出。他不喜欢在演出时始终使用同一个音量，所以他决定每一首歌之前他都需要改变一次音量。在演出开始之前，他已经做好一个列表，里面写着每首歌开始之前他想要改变的音量是多少。每一次改变音量，他可以选择调高也可以调低。
音量用一个整数描述。输入文件中整数 b e g i n L e v e l ，代表吉他刚开始的音量，整数 maxLevel，代表吉他的最大音量。音量不能小于 0 也不能大于maxLevel。输入中还给定了 n 个整数 c 1 , c 2 , c 3 , ⋯ , c n ，表示在第 i首歌开始之前吉他手想要改变的音量是多少。
吉他手想以最大的音量演奏最后一首歌，你的任务是找到这个最大音量是多少。
输入格式
第一行依次为三个整数 n，beginLevel 和maxLevel。
第二行依次为 n 个整数 c 1 , c 2 , c 3 , ⋯ , c n 。
输出格式
输出演奏最后一首歌的最大音量。如果吉他手无法避免音量低于 0 或者高于maxLevel，输出 -1。
样例 #1
样例输入 #1
3 5 10 5 3 7
样例输出 #1
10
提示
解题思路
1）01背包问题。
2）背包之后倒序找最大能达到的音量。
2）找到了进行输出。
参考代码
#include<bits/stdc++.h> 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; }
第三题 高低位交换
题目描述
给出一个小于
的正整数。这个数可以用一个32位的二进制数表示（不足32位用0补足）。我们称这个二进制数的前16 位为“高位”，后16位为“低位”。将它的高低位交换，我们可以得到一个新的数。试问这个新的数是多少（用十进制表示）。
例如，数1314520用二进制表示为00000000000101000000111011011000（添加了11个前导0 补足为32位），其中前16位为高位，即0000000000010100；后16 位为低位，即0000111011011000。将它的高低位进行交换，我们得到了一个新的二进制数00001110110110000000000000010100。它即是十进制的249036820。
输入格式
一个小于
的正整数
输出格式
将新的数输出
样例 #1
样例输入 #1
1314520
样例输出 #1
249036820
解题思路
1）位运算问题，可以看看这个文章了解一下 点这里！！！
2）将原数的后16位前移至新数的前16位。
3）将原数的前16位前移至新数的后16位。
参考代码
#include<iostream> using namespace std; int main() { unsigned long long n; cin>>n; cout<<((n&0x0000ffff)<<16|(n&0xffff0000)>>16); }
第四题 【深基16.例1】淘汰赛
题目描述
有 
个国家参加世界杯决赛圈且进入淘汰赛环节。已经知道各个国家的能力值，且都不相等。能力值高的国家和能力值低的国家踢比赛时高者获胜。1 号国家和 2 号国家踢一场比赛，胜者晋级。3 号国家和 4 号国家也踢一场，胜者晋级……晋级后的国家用相同的方法继续完成赛程，直到决出冠军。给出各个国家的能力值，请问亚军是哪个国家？
输入格式
第一行一个整数 n，表示一共
个国家参赛。
第二行 
个整数，第 i个整数表示编号为 i 的国家的能力值（1 ≤ i ≤ 
）。
数据保证不存在平局。
输出格式
仅一个整数，表示亚军国家的编号。
样例 #1
样例输入 #1
3 4 2 3 1 10 5 9 7
样例输出 #1
1
解题思路
1）冠亚军应该从左半部分的最强者和右半部分的最强者中产生。
2）找到左半部分的最强者。
3）找到右半部分的最强者。
4）比较，输出答案。
参考代码
#include <bits/stdc++.h> 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; }
