1.小Q爬塔
【题目描述】：小Q正在攀爬一座宝塔，这座宝塔很特别，塔共有n层，但是每两层之间的净高却不同，所以造成了小Q爬过每层的时间也不同。如果某一层的高度为x，所以爬过这一层的时间也为x。 小Q还会使用一种魔法，每用一次可以让他向上跳一层或者两层，但是每次跳跃之后小Q都将用完魔法力，必须爬过至少一层才能再次跳跃（你可以认为小Q需要跳两次一层才休息，最后也可以跳到塔外即超过塔高，跳是不花费时间的）。 小Q想用最短时间爬到塔顶，希望你告诉他最短时间是多少。 输入描述： 第一行一个数n（n<10000），表示塔的层数。 接下来的n行每行一个数h(1 <= h <= 100)表示从下往上每层的高度。 输出描述： 一个数，表示最短时间。 输入样例：
代码语言：javascript复制5
3
5
1
8
4输出样例：
代码语言：javascript复制1【解题思路】 p[i]表示到达第i层的最短时间，并且到达第i层的方式是爬。 t[i]表示到达第i层的最短时间，并且到达第i层的方式是跳。 到达第i层的方式采用爬还是采用跳。
- 情况1，到达第i层的方式是爬： 那么到达第i层的方式可以是爬也可以是跳，从两者中选择最小的 p[i]=min(p[i-1],t[i-1] a[i]);
- 情况2，到达第i层的方式是跳： 那么从第i-1层起跳，也可以从i-2层起跳。到达并且到达第i-1层和i-2层的方式只能是爬（到第i层是跳），所以在两者中选择最小的。 t[i]=min(p[i-1],p[i-1]);
最后在p[n]和t[n]中选最小者做结果。 【代码】
代码语言：javascript复制#include<iostream>
#include<algorithm>
using namespace std;
int p[1005], t[1005];
int main()
{
int n=0;
cin >> n;
int m = 0;
for (int i = 1; i <= n; i )
{
cin >> m;
p[i] = min(p[i - 1], t[i - 1]) m;
if (i == 1)
continue;
t[i] = min(p[i - 1], p[i - 2]);
}
cout << min(p[n], t[n]) << endl;
system("pause");
return 0;
}
2.妞妞的问题
【题目描述】妞妞公主新得到一块黑白棋盘。这块棋盘共有n行m列，任意相邻的两个格子都是不同的颜色（黑或白），坐标为（1,1）的格子是白色的。 这一天牛牛来看妞妞公主，妞妞公主正在望着这块棋盘发呆。牛牛看妞妞公主闷闷不乐的样子，便对妞妞公主说“只要你告诉我n和m，我能马上算出黑色方块和白色方块的数量。” “这太简单了”妞妞公主想了一会，“我会在这n行m列中选择一个左下角坐标为（x0,y0）。右上角为（x1,y1）的矩形，把这个矩形里的共（x1-x0 1,y1-y0 1）个方块全部涂白。你还能马上计算出黑色方块和白色方块的数量。” “这太简单了。”牛牛自信的一笑，“你可以在执行涂白操作后再选择一个左下坐标为（x2,y2），右上角坐标为（x3,y3）的矩形，把这个矩阵里面的方块全部涂黑，我依然能马上计算出黑色方块和白色方块的数量。” 妞妞公主张大眼睛，于是抛出了他的T次提问。 聪明的牛牛当然会做了，但是他想把这个问题交给你，请帮助牛牛算出每次提问棋盘的黑白方块数目吧。 输入描述： 第一行一个整数T，表示妞妞一共提问了T次。 接下来3T行， 第（1 3i）行两个整数n,m。表示第i次提问时棋盘的大小。 第（2 3i）行四个整数x0,y0,x1,y1。表示第i次提问时涂白操作选取的两个坐标。 第（3 3i）行四个整数x2,y2,x3,y3。表示第i次提问时涂黑操作选取的两个坐标。 i <= T <= 1000，1 <= x <= n <= 1000000000,1 <= y <= m <= 1000000000,x0<x1,y0<y1,x2<x3,y2<y3。 输出描述: 共T行，每行两个整数分别表示白色方块的数量和黑色方块的数量。 输入样例：
代码语言：javascript复制3
1 3
1 1 1 3
1 1 1 3
3 3
1 1 2 3
2 1 3 3
3 4
2 1 2 4
1 2 3 3输出样例：
代码语言：javascript复制0 3
3 6
4 8【解题思路】 格子的个数可以快速维护，然后对应维护出来即可。 【代码】
代码语言：javascript复制#include<iostream>
using namespace std;
long long x[8], y[8];
int main()
{
int T;//提问次数
long long n, m, black, white, a, b, c, d, e;
scanf("%d", &T);//输入提问次数
while (T--)
{
scanf("%lld%lld", &n, &m);//输入棋盘大小
black = n*m / 2;//黑色方块数量为总方块数的一半，如果总方块数为偶数，黑白方块数量一样，如果为奇数，黑素方块比白色少一块
white = n*m - black;//白色方块数量
for (int i = 0; i <= 3; i )
scanf("%lld%lld", &x[i], &y[i]);
if ((x[0] y[0]) & 1)//涂白起点决定黑白方块数量差
d = ((x[1] - x[0] 1)*(y[1] - y[0] 1) 1) / 2;//起点和为奇数，说明起点为黑色
else
{
d = ((x[1] - x[0] 1)*(y[1] - y[0] 1)) / 2;//起点为偶数，说明起点为白色
}
white = d;
black -= d;
if ((x[2] y[2]) & 1)
d = (x[3] - x[2] 1)*(y[3] - y[2] 1) / 2;
else
{
d = ((x[3] - x[2] 1)*(y[3] - y[2] 1) 1) / 2;
}
white -= d;
black = d;
a = max(x[0], x[2]);
b = max(y[0], y[2]);
c = min(x[1], x[3]);
d = min(y[1], y[3]);
if (c < a || d < b)e = 0ll;
else//涂白和涂黑区域有重叠
{
if ((a b) & 1)
e = ((c - a 1)*(d - b 1) 1) / 2;
else
{
e = (c - a 1)*(d - b 1) / 2;
}
}
white -= e;
black = e;
printf("%lld %lldn", white, black);
}
system("pause");
return 0;
}
3、小Q的最小值序列
小 Q 得到了一个长度为 n 的序列 A，A 中的数各不相同。对于 A 中的每一个数 Ai，求：min(1≤j<i)|Ai−Aj|
以及令上式取到最小值的 j（记为 P_i）。若最小值点不唯一，则选择使 Aj 较小的那个。
输入描述:
第一行一个整数 n，第二行 n 个数。
输出描述:
n-1 行，每行 2 个用空格隔开的整数。分别表示当 i 取 2~n 时，对应的 min(1≤j<i)|Ai−Aj|和 Pi的值
输入样例：
3
1 5 3输出样例：
代码语言：javascript复制4 1
2 1【解题思路】 维护一个单调的链表，边读边算边输出，这样每一个数进来时，都能保证链表里的数下标比他小，那么插入后用它两边的数计算答案即可。
【代码】
代码语言：javascript复制#include<iostream>
using namespace std;
const int N = 1e5 5;
const int inf = 1e9;
struct P
{
int value;
int pos;
};
P a[N];
int cmp(P x, P y)
{
return x.value < y.value;
}
int b[N], b2[N], cnt, head, tail, ans1[N], ans2[N];
struct node
{
int value;
int next, pre;
}e[N];
void init(){
cnt = 2;
head = 1, tail = 2;
e[head].next = tail;
e[head].pre = head;
}
void ins(int pos, int x){//在pos位置后边加一个数X
e[ cnt].value = x;
e[cnt].next = e[pos].next;
e[cnt].pre = pos;
e[e[pos].next].pre = cnt;
e[pos].next = cnt;
}
void del(int pos){
e[e[pos].next].pre = e[pos].pre;
e[e[pos].pre].next = e[pos].next;
}
int main()
{
int n;
scanf("%d", &n);
for (int i = 1; i <= n; i )
{
scanf("%d", &a[i].value);
a[i].pos = i;
}
sort(a 1, a 1 n,cmp);
init();
for (int i = 1; i <= n; i )
{
ins(e[tail].pre, a[i].value);
b[a[i].pos] = cnt;
b2[cnt] = a[i].pos;
}
for (int i = n; i >= 2; --i)
{
ans1[i] = inf;
if (e[b[i]].next != tail){
ans1[i] = min(ans1[i], abs(e[b[i]].value - e[e[b[i]].next].value));
ans2[i] = b2[e[b[i]].next];
}
if (e[b[i]].pre != head){
if (ans1[i] >= abs(e[b[i]].value - e[e[b[i]].pre].value)){
ans1[i] = abs(e[b[i]].value - e[e[b[i]].pre].value);
ans2[i] = b2[e[b[i]].pre];
}
}
del(b[i]);
}
for (int i = 2; i <= n; i )printf("%d %dn", ans1[i], ans2[i]);
system("pause");
return 0;
}
