吴凡精选题库：快快编程第151到200题

182. Hanoi双塔

题目描述
给定A、B、C三根足够长的细柱，在A柱上放有2n个中间有孔的圆盘，共有n个不同的尺寸，每个尺寸都有两个相同的圆盘，注意这两个圆 盘是不加区分的（下图为n=3的情形）。现要将这些圆盘移到C柱上，在移动过程中可放在B柱上暂存。要求：
（1）每次只能移动一个圆盘；
（2）A、B、C三根细柱上的圆盘都要保持上小下大的顺序；
任务：设An为2n个圆盘完成上述任务所需的最少移动次数，对于输入的n，输出An。

hanoi双塔.bmp

输入输出格式
输入格式
输入文件 hanoi.in 一个正整数n，表示在A柱上放有2n个圆盘。
对于50%的数据，1<=n<=25
对于100%的数据，1<=n<=200
输出格式
输出文件 hanoi.out 一个正整数, 为完成上述任务所需的最少移动次数

输入输出样例
输入样例#1:
2
输出样例#1:
6
输入样例#2:
无
输出样例#2:
无
输入样例#3:
无
输出样例#3:
无

#include<bits/stdc++.h>
using namespace std;
int main(){
	freopen("hanoi.in","r",stdin);
	freopen("hanoi.out","w",stdout);
    int n;
    cin>>n;
    stringstream s;
    s.precision(0);
    s<<fixed<<pow(2.0L,n+1);
    string a=s.str();
    a[a.length()-1]--;
    a[a.length()-1]--;
    cout<<a<<endl;
    return 0;
}

184. 逃难

题目描述
僵尸大战爆发后，爷爷需要带上值钱的财宝去逃难 ，他的每个宝物都有各自的价钱和重量。爷爷请你 帮他对所有宝物进行排序。越值钱的排在越靠前， 如果价钱一样重量越小越靠前。如果价钱和重量都 一样，那么编号越小越靠前。

输入输出格式
输入格式
输入文件escape.in 输入第一行为n，之后n行每行 有三个整数，代表每件宝物的编号，价格和重量， 编号依次为1到n。n<=10000
输出格式
输出文件escape.out 输出共n行，为排序后的编号 。

输入输出样例
输入样例#1:
4
1 10000 5
2 888 2
3 666666 10
4 888 1
输出样例#1:
3
1
4
2
输入样例#2:

输出样例#2:

输入样例#3:

输出样例#3:

#include<bits/stdc++.h>
using namespace std;
const int N=100001;
struct escape{
	int id, value, weight;
};
bool cmp(const escape&a, const escape&b){
	if(a.value>b.value)	return true;
	if(a.value<b.value)	return false;
	if(a.weight<b.weight)	return true;
	if(a.weight>b.weight)	return false;
	if(a.id<b.id)	return true;
	if(a.id>b.id)	return false;
}
int main(){
	freopen("escape.in", "r", stdin);
	freopen("escape.out", "w", stdout);
	int n;
	escape s[N];
	cin>>n;
	for(int i=0;i<n;i++){
		cin>>s[i].id;
		cin>>s[i].value;
		cin>>s[i].weight;
	}
	sort(s, s+n, cmp);
	for(int i=0;i<n;i++){
		cout<<s[i].id<<endl;
	}
	return 0;
}

185. 英雄榜

题目描述
人们在评选世界上的超级英雄们哪个更厉害，通过 投票对英雄的攻击力，防御力，人品这三个方面进 行了打分。现在请你将投票结果进行排序：三项总 分越高排名越靠前；总分相同时，人品越高排名越 靠前；若总分和人品都相同，攻击力越高排名越高 ；若总分，人品，攻击力和防御力都相同，按照英 雄名称的字典序排列。

输入输出格式
输入格式
输入第一行为n，代表有n个英雄，1<=n<=100，每项得分都是整数，范围是[0,100]。保证英雄名称都是连续的大写字母。以下每行为英雄名称，攻击力， 防御力，人品。
输出格式
输出排序结果，每行一位英雄

输入输出样例
输入样例#1:
10
MONKEYKING 90 90 80
CAPTAINAMERICA 60 60 70
MAGNETO 85 30 10
ULTRAMAN 80 90 80
HIPPOPMAN 0 0 80
WOLVERINE 70 80 20
DORAEMON 50 20 100
IRONMAN 80 60 30
BATMAN 80 60 50
SUPERMAN 80 70 70
输出样例#1:
MONKEYKING
ULTRAMAN
SUPERMAN
CAPTAINAMERICA
BATMAN
DORAEMON
IRONMAN
WOLVERINE
MAGNETO
HIPPOPMAN
输入样例#2:

输出样例#2:

输入样例#3:

输出样例#3:

#include<bits/stdc++.h>
using namespace std;
const int N=101;
struct hero{
	string name;
	int a, b, rp, sum; 
};
bool cmp(const hero&a, const hero&b){
	if(a.sum>b.sum)	return true;
	if(a.sum<b.sum)	return false;
	if(a.rp>b.rp)	return true;
	if(a.rp<b.rp)	return false;
	if(a.a>b.a)	return true;
	if(a.a<b.a)	return false;
	if(a.name<b.name) return true;
	return false;
}
int main(){
	int n;
	hero h[N];
	cin>>n;
	for(int i=0;i<n;i++){
		cin>>h[i].name;
		cin>>h[i].a;
		cin>>h[i].b;
		cin>>h[i].rp;
		h[i].sum = h[i].a+h[i].b+h[i].rp;
	}
	sort(h, h+n, cmp);
	for(int i=0;i<n;i++){
		cout<<h[i].name<<endl;
	}
	return 0;
}

190. 最长上升子序列之简单版

题目描述
由n个整数组成的数列，记为b[1], b[2], …, b[n]。若存在i1<i2<i3< … < ie 且有b[i1]< b[i2]< … <b[ie]则称为长度为e的上升子序列。求最长上升 。求最长上升子序列(Longest increasing subsequence, LIS)

输入输出格式
输入格式
输入文件lis.in 输入一行整数序列，由空格隔开。说明:序列长度<=100, 每个整数绝对值<=10000。
说明：输入可以用以下代码：
int n=0;
while( cin>>x[n+1] ) n++ ;
输出格式
输出文件lis.out 输出一个整数。

输入输出样例
输入样例#1:
2 1 1 2 3
输出样例#1:
3
输入样例#2:
1 2 3 4 5 6 5
输出样例#2:
6
输入样例#3:
无
输出样例#3:
无

#include<bits/stdc++.h>
using namespace std;
const int N=109;
int n=0,x[N],f[N];
int main(){
    freopen("lis.in", "r", stdin);
    freopen("lis.out", "w", stdout);
	while(cin>>x[n+1])n++;
	f[0]=0;
	for(int i=1;i<=n;i++){
		f[i]=1;
		for(int j=1;j<i;j++)
		    if(x[j]<x[i])
		        f[i]=max(f[i],f[j]+1);
	}
	int ans=*max_element(f+1,f+1+n);
	cout<<ans;
	return 0;
}

197. 命运卡牌

题目描述
小明最近运气不好想找大师求教，大师拿出一副卡 牌，共100张牌，每张正面有一个数字分别为1到100的整数，背面写有一些人生哲理。 大师问，“小明 你的幸运数字是哪个？” 小明说，“当然是6666。” 大师心算很快，“如果要用卡牌里两个数字的乘积凑出6666，最接近的方法是68乘以98。所以这两张牌 就是你的命运卡牌，牌背后的人生哲理送给你。”  但是大师马上就要变老脑子变慢，请帮大师写一个 程序能为客人计算两张命运卡牌，输入一个数字n代表客人的幸运数字，输出两个不同数字乘法形式， 两数乘积是所有可能中最接近n的。先输出较小的数。如果有多种可能，输出两数里较小数最小的方案 。

输入输出格式
输入格式
输入文件destiny.in 输入一个数字n，n<=10000
输出格式
输出文件destiny.out 输出一行字符串。

输入输出样例
输入样例#1:
6666
输出样例#1:
68*98=6664
输入样例#2:

输出样例#2:

输入样例#3:

输出样例#3:

#include<bits/stdc++.h>
using namespace std;
int main(){
	freopen("destiny.in", "r", stdin);
	freopen("destiny.out", "w", stdout);
	int n,x,y;
	cin>>n;
	int bst=10000;
	for(int i=1;i<=99;i++)
	    for(int j=i+1;j<=100;j++){
	    	int d=abs(i*j-n);
	    	if(d<bst){
	    		bst=d;
	    		x=i;y=j;	    		
			}
		}
	cout<<x<<"*"<<y<<"="<<x*y;
	return 0;
}

198. 比例简化

题目描述
在社交媒体上，经常会看到针对某一个观点同意与 否的民意调查以及结果。例如，对某一观点表示支 持的有1498 人，反对的有 902人，那么赞同与反对的比例可以简单的记为1498:902。 不过，如果把调查结果就以这种方式呈现出来，大多数人肯定不会 满意。因为这个比例的数值太大，难以一眼看出它 们的关系。对于上面这个例子，如果把比例记为5:3，虽然与真实结果有一定的误差，但依然能够较为 准确地反映调查结果，同时也显得比较直观。 现给出支持人数A，反对人数B，以及一个上限L，请你将A比B化简为A’比B’，要求在A’和B’均不大于L且A’和B’互质（两个整数的最大公约数是1）的前提下，A’/B’≥ A/B且A’/B’- A/B的值尽可能小。 (本题目为2014NOIP普及T2)

输入输出格式
输入格式
输入文件ratio.in 输入共一行，包含三个整数A，B，L，每两个整数之间用一个空格隔开，分别表示支持人数、反对人数以及上限。
说明 1 ≤ A ≤ 1,000,000，1 ≤ B ≤ 1,000,000，1 ≤ L ≤ 100，A/B ≤ L。
输出格式
输出文件ratio.out 输出共一行，包含两个整数A’ ，B’，中间用一个空格隔开，表示化简后的比例。

输入输出样例
输入样例#1:
1498 902 10
输出样例#1:
5 3
输入样例#2:
无
输出样例#2:
无
输入样例#3:
无
输出样例#3:
无

#include<bits/stdc++.h>
using namespace std;
int main(){
	freopen("ratio.in", "r", stdin);
	freopen("ratio.out", "w", stdout);
	int L,x,y;
	double a,b;
	cin>>a>>b>>L;
	double ratio=a/b;
	double bst=L;
	for(int i=1;i<=L;i++)
	    for(int j=1;j<=L;j++){
	    	double d=i*1.0/j-ratio;
			if(d>=0&&d<bst){
				bst=d;
				x=i;y=j;
			}
		}
	cout<<x<<" "<<y;
	
	return 0;
}

原文地址：https://www.cnblogs.com/WindowsRegedit/p/16133855.html