201312-1 出现次数最多的数

题目：

问题描述
试题编号： 201312-1
试题名称： 出现次数最多的数
时间限制： 1.0s
内存限制： 256.0MB
问题描述
　　给定n个正整数，找出它们中出现次数最多的数。如果这样的数有多个，请输出其中最小的一个。
输入格式
　　输入的第一行只有一个正整数n(1 ≤ n ≤ 1000)，表示数字的个数。
　　输入的第二行有n个整数s1, s2, …, sn (1 ≤ si ≤ 10000, 1 ≤ i ≤ n)。相邻的数用空格分隔。
输出格式
　　输出这n个次数中出现次数最多的数。如果这样的数有多个，输出其中最小的一个。
样例输入
6
10 1 10 20 30 20
样例输出
10

解题思路：

使用pair类型的数组 A 来存储数字 x 以及 x 出现的次数，利用sort对数字出现次数进行排序后，再对最大的出现次数值范围内的数字大小进行排序，最后输出A[0]即可。

代码：

#include<bits/stdc++.h>
using namespace std;
pair<int, int > A[10010];
int n;

bool cmp1(pair<int, int> a, pair<int, int> b) {
	return a.first < b.first;
}

bool cmp2(pair<int, int> a, pair<int, int> b) {
	return a.second > b.second;
}

int main() {
	cin >> n;
	for (int i = 0; i < n; i++) {
		int tmp;
		cin >> tmp;
		A[tmp].first = tmp;
		A[tmp].second++;
	}
	sort(A, A + 10010, cmp2);
	int cnt = 0, tmp = A[0].second;
	while (tmp == A[cnt++].second);
	sort(A, A + cnt - 1, cmp1);
	cout << A[0].first << endl;

	return 0;
}

201312-2 ISBN号码

题目:

试题编号： 201312-2
试题名称： ISBN号码
时间限制： 1.0s
内存限制： 256.0MB
问题描述
　　每一本正式出版的图书都有一个ISBN号码与之对应，ISBN码包括9位数字、1位识别码和3位分隔符，其规定格式如“x-xxx-xxxxx-x”，其中符号“-”是分隔符（键盘上的减号），最后一位是识别码，例如0-670-82162-4就是一个标准的ISBN码。ISBN码的首位数字表示书籍的出版语言，例如0代表英语；第一个分隔符“-”之后的三位数字代表出版社，例如670代表维京出版社；第二个分隔之后的五位数字代表该书在出版社的编号；最后一位为识别码。
　　识别码的计算方法如下：
　　首位数字乘以1加上次位数字乘以2……以此类推，用所得的结果mod 11，所得的余数即为识别码，如果余数为10，则识别码为大写字母X。例如ISBN号码0-670-82162-4中的识别码4是这样得到的：对067082162这9个数字，从左至右，分别乘以1，2，…，9，再求和，即0×1+6×2+……+2×9=158，然后取158 mod 11的结果4作为识别码。
　　编写程序判断输入的ISBN号码中识别码是否正确，如果正确，则仅输出“Right”；如果错误，则输出是正确的ISBN号码。
输入格式
　　输入只有一行，是一个字符序列，表示一本书的ISBN号码（保证输入符合ISBN号码的格式要求）。
输出格式
　　输出一行，假如输入的ISBN号码的识别码正确，那么输出“Right”，否则，按照规定的格式，输出正确的ISBN号码（包括分隔符“-”）。
样例输入
0-670-82162-4
样例输出
Right
样例输入
0-670-82162-0
样例输出
0-670-82162-4

解题思路：

对输入字符串的前9位数字进行相应的运算得到正确的识别码，再与最后一位数字比较即可。

代码：

#include<bits/stdc++.h>
using namespace std;

string a;

int main() {
	cin >> a;
	int ans = 0, b[20];
	int j = 0;

	for (int i = 0; i < 13; i++) {
		if (a[i] != '-') {
			b[j++] = a[i] - '0';
		}
	}
	for (int i = 0; i < 9; i++) {
		ans += (i + 1) * b[i];
	}
	ans %= 11;

	//获得识别码对应的字符
	if (ans == 10) ans = 'X';
	else ans += '0';

	//做比较 输出
	if (ans == a[12]) cout << "Right" << endl;
	else {
		a[12] = ans;
		cout << a << endl;
	}

	return 0;
}

201312-3 最大的矩形

题目：

试题编号： 201312-3
试题名称： 最大的矩形
时间限制： 1.0s
内存限制： 256.0MB
问题描述：
问题描述
　　在横轴上放了n个相邻的矩形，每个矩形的宽度是1，而第i（1 ≤ i ≤ n）个矩形的高度是hi。这n个矩形构成了一个直方图。例如，下图中六个矩形的高度就分别是3, 1, 6, 5, 2, 3。

请找出能放在给定直方图里面积最大的矩形，它的边要与坐标轴平行。对于上面给出的例子，最大矩形如下图所示的阴影部分，面积是10。

输入格式
　　第一行包含一个整数n，即矩形的数量(1 ≤ n ≤ 1000)。
　　第二行包含n 个整数h1, h2, … , hn，相邻的数之间由空格分隔。(1 ≤ hi ≤ 10000)。hi是第i个矩形的高度。
输出格式
　　输出一行，包含一个整数，即给定直方图内的最大矩形的面积。
样例输入
6
3 1 6 5 2 3
样例输出
10

解题思路

方法一：（暴力破解） O(n^2)
对每一个矩形从此矩形开始分别向左和向右扫描识别有多少个连续的矩形的高度大于或等于该矩形，而后得到以该矩形为高度得到的最大面积，用该面积与最大值进行比较。完成一遍扫描后得到整个直方图中的最大面积。

**方法二：单调栈 ** O(n)
对于直方图中的一个矩形，求以它为高的最大面积，必然是碰到一个高度小于它自身的就碰到了一个边界。那么可以考虑对直方图从左向右扫描，构造出一个高度递增的单调栈。操作过程如下：
如果栈为空，那么直接将当前扫描的矩形 Cur 压入栈中；
如果当前扫描的矩形 Cur 得到高度大于栈顶 Top 的高度，那么直接将 Cur 压入栈中；
如果 Cur 小于 Top ，那么将 Top 弹出，Cur 再与新的 Top 进行比较，直到 Cur >= Top 。
形成得到的单调栈的一些特点：

1. 单调栈中任意两个连续的矩形A、B(B>=A)之间的矩形高度均大于B，因为如果存在A<C<B那么C一定在A、B之间；
2. 如果单调栈只剩一个矩形，那么这个矩形的高度是至此最小的，否则其前面应该还会有矩形，不会以该矩形为最后一个栈元素；
   根据以上特点可以进行如下操作来求得最大的矩形面积，每次从栈中弹出一个矩形，那么对这个矩形求以它为高的最大面积。由于 特点1 ，假设当前与栈顶比较的矩形下标为 i ，未弹出栈时栈顶表示矩形下标 top_Pre ，由于H[top_Pre] > H[i] ，所以将top_Pre弹出栈，新的栈顶下标为 top_Cur 。由于top_Pre和top_Cur之间的矩形高度都大于 H[top_Pre]，所以以top_Pre为高度的最大矩形面积为：
   (i - top_Cur - 1)H[top_Pre]
   当弹出栈顶后栈为空，那么由于特点2* ，以 top_Pre 为高度的矩形面积为：
   ** H[top_Pre] * i **

代码：

暴力破解：

#include<bits/stdc++.h>

using namespace std;
int H[2010];
int n;
/*暴力破解
：因为n<=1000，所以O(n^2)的计算次数为 1e6 < 1e8
暴力破解是可行的
*/
int main() {
	cin >> n;
	for (int i = 0; i < n; i++)
		cin >> H[i];
	int Max = 0;
	int S = 0;
	for (int i = 0; i < n; i++) {
		int L = 0, R = 0;
		for (int j = i; j >= 0; j--) {  //从i开始向左扫描寻找 左部宽度
			if (H[j] >= H[i]) L++;
			else break;
		}
		for (int j = i; j < n; j++) {
			if (H[j] >= H[i]) R++;
			else break;
		}
		int W = L + R - 1;
		S = H[i] * W;
		if (S > Max) Max = S;
	}
	cout << Max << endl;

	return 0;
}

单调栈

#include<bits/stdc++.h>

using namespace std;
int H[2010];
int n;
//   单调栈方法
int main() {
	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> H[i];
	}
	H[n] = 0;
	stack<int> S;  //用一个栈来存储
	long long Max = 0;
	for (int i = 0; i <= n; i++) {  //一定要添加 i=n时候的情况 因为最后还需要对剩余的单调栈进行判断
		if (S.empty() || H[i] >= H[S.top()]) {   //如果新来的值大于栈顶值 或者 栈为空 直接压入即可
			S.push(i);
		}
		else {
			while (H[i] < H[S.top()]) {  //如果栈不空 且 栈顶值大于H[i]
				int top = S.top();
				S.pop();  //将栈顶弹出是因为需要知道下一个栈顶的值
				if (!S.empty()) {
					Max = max(Max, (long long)H[top] * (i - S.top() - 1));   //在第一个栈顶和第二个栈顶之间的所有值一定大于第一个栈顶 否则两栈顶之间要添加其他的值
				}
				else{
					Max = max(Max, (long long)H[top] * i);  //栈空说明从H[0] 到 H[i-1]中最小的值就是弹出的栈顶
					break;
				}
			}
			S.push(i);
		}
	}
	
	cout << Max << endl;

	return 0;
}

201312-4 有趣的数

题目：

试题编号： 201312-4
试题名称： 有趣的数
时间限制： 1.0s
内存限制： 256.0MB
问题描述
　　我们把一个数称为有趣的，当且仅当：
　　1. 它的数字只包含0, 1, 2, 3，且这四个数字都出现过至少一次。
　　2. 所有的0都出现在所有的1之前，而所有的2都出现在所有的3之前。
　　3. 最高位数字不为0。
　　因此，符合我们定义的最小的有趣的数是2013。除此以外，4位的有趣的数还有两个：2031和2301。
　　请计算恰好有n位的有趣的数的个数。由于答案可能非常大，只需要输出答案除以1000000007的余数。
输入格式
　　输入只有一行，包括恰好一个正整数n (4 ≤ n ≤ 1000)。
输出格式
　　输出只有一行，包括恰好n 位的整数中有趣的数的个数除以1000000007的余数。
样例输入
4
样例输出
3

解题思路：

一共四种数字 0必须在1前 2必须在3前
仅有以下几种情况：
（1） 只填写了2 只有数字 2
（2） 在（1）的基础上填写了0 只有数字 2 和 0
在自己的基础上填写2或者0
（3） 在（1）的基础上填写了3 只有数字 2 和 3
在自己的基础上填写3
（4） 在（2）的基础上填写了1 只有数字 2 、 0 、1
在自己的基础上填写1或者2
（5） 在（2）的基础上填写了3 只有数字 2 、 0 、3
在（3）的基础上填写了0
在自己的基础上填写3或者0
（6） 在（4）的基础上填写了3 1 、2 、 3、 0全部都有
在（5）的基础上填写了1
在自己的基础上填写1或者3

代码：

#include<bits/stdc++.h>

using namespace std;
#define ll long long
ll dp[1010][7];
#define Mod 1000000007 

int main() {
	ll n;
	cin >> n;

	for (ll i = 1; i <= n; i++) {
		dp[i][1] = 1;
		dp[i][2] = (dp[i - 1][1] + dp[i - 1][2] * 2) % Mod;
		dp[i][3] = (dp[i - 1][1] + dp[i - 1][3]) % Mod;
		dp[i][4] = (dp[i - 1][2] + dp[i - 1][4] * 2) % Mod;
		dp[i][5] = (dp[i - 1][2] + dp[i - 1][3] + dp[i - 1][5] * 2) % Mod;
		dp[i][6] = (dp[i - 1][4] + dp[i - 1][5] + dp[i - 1][6] * 2) % Mod;
	}
	cout << dp[n][6] << endl;

	return 0;
}