文档介绍：CCF模拟练****试题(下)
一、最大的矩形
:
在横轴上放了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
:
import .*;
public class Main {
public static void main(String[] args) {
new Main().run();
}
public void run() {
Scanner fin = new Scanner();int N = ();
int[] height = new int[N];
for (int i = 0; i < N; ++i) height[i] = ();
int result = 0;
for (int i = 0; i < N; ++i) {
int width = 1;
for (int j = i - 1; j >= 0; --j) {
if (height[j] < height[i]) break;
++width;
}
for (int j = i + 1; j < N; ++j) {
if (height[j] < height[i]) break;
++width;
}
int area = width * height[i];
result = (result, area);
}
(result);
}
}
二、有趣的数
:
我们把一个数称为有趣的,当且仅当:
它的数字只包含0, 1, 2, 3,且这四个数字都出现过至少一次。
所有的0都出现在所有的1之前,而所有的2都出现在所有的3之前。
最高位数字不为0。
因此,符合我们定义的最小的有趣的数是2013。除此以外,4位的有趣的数还有两个:2031和2301。
请计算恰好有n位的有趣的数的个数。由于答案可能非常大,只需要输出答案除以1000000007的余数。
输入只有一行,包括恰好一个正整数n (4 ≤ n ≤ 1000)。
输出只有一行,包括恰好n 位的整数中有趣的数的个数除以1000000007的余数。
样例输入
4
样例输出
3
:
import .*;
public class Main {
public static void main(String[] args) {
new Main().run();
}
public void run() {
Scanner fin = new Scanner();
int N = ();
long[] count = new long[8];
count[6] = 0;
count[7] = 1;
long mod = 1000000007;for (int i = 2; i <= N; ++i) {
long[] newCount = new long[8];
newCount[0] = (count[0] * 2 + count[1] + count[3]) % mod;
newCount[1] = (count[1] * 2 + count[2] + count[5]) % mod;
newCount[2] = (count[2] + count[6]) % mod;
newCount[3] = (count[3] * 2 + count[4] + count[5]) % mod;
newCount[4] = (count[4] + count[7]) % mod;
newCount[5] = (count[5] * 2 + count[6] + count[7]) % mo