这次题目真的衡水

文章拖了好久忘记发了
明天初赛祝各位考试顺利有一个好的心态（我也要考/(ㄒoㄒ)/~~）

矩形的周长与面积

内存限制: 256 Mb时间限制: 1000 ms
题目描述
给定一个矩形的长为 a，宽为 b，请输出这个矩形的周长和面积。

输入格式
两个整数表示 a 与 b。

输出格式
第一行：单个整数表示矩形的周长
第二行：单个整数表示矩形的面积

数据范围
1≤a,b≤10000

样例数据
输入:
3 2
输出:
10
6
输入:
12 3
输出:
30
36
分析：
不分析

#include <bits/stdc++.h>
using namespace std;
long long a, b;
int main() {
	cin >> a >> b;
	cout << 2 * (a + b) << endl << a*b;
	return 0;
}

机会成本

内存限制: 256 Mb时间限制: 1000 ms
题目描述
每个人的一生只能做好一件事。给定一个正整数 nn，表示人生中的 nn 件事。若认真对待某件事，可以获得的分数为 $a_1,a_2,\dots ,a_n$，若不认真对待，则获得的分数为 $b_1,b_2,\dots ,b_n$。请计算应该认真对待哪一件事，才能让分数的总和达到最大。

输入格式
第一行：单个整数表示 n
第二行到第 n+1 行：每行两个整数表示 $a_i$ 与 $b_i$

输出格式
单个整数：表示最大的分数之和

数据范围
对于 30% 的数据，1≤n≤5,000；
对于 60% 的数据，1≤n≤20,000；
对于 100% 的数据，1≤n≤500,000；
$0\le b_i\le a_i\le 4000$；
样例数据
输入:
3
1 1
2 0
3 2
输出:
5
说明:
选择做好第二件事
分析：
不要想复杂，就是所有的分数加起来再加上分差最大的一门。

#include <iostream>
using namespace std;
int a, b, n, cnt[500001], sum, maxn;
int main() {
	cin >> n;
	for (int i = 1; i <= n; i++) {
		cin >> a >> b;
		cnt[i] = a - b;
		maxn = max(maxn, cnt[i]);
		sum += b;
	}
	cout << sum + maxn << endl;
	return 0;
}

三色排序

内存限制: 256 Mb时间限制: 1000 ms
题目描述
给定 n 个整数 $a_1,a_2,\dots ,a_n$ ，每个数字都是 0,1,2 中的一个，请将其中的一部分数字两两交换，使得结果是升序的，请问最少需要几次交换？

输入格式
第一行：单个整数表示 n
第二行：n 个整数表示 $a_1,a_2,\dots ,a_n$

输出格式
单个整数：表示最少交换次数。

数据范围
对于 30% 的数据，1≤n≤5,000；
对于 60% 的数据，1≤n≤100,000；
对于 100% 的数据，1≤n≤1,000,000；
$0\le a_i\le 2$
样例数据
输入:
5
2 0 1 2 0
输出:
1
说明:
将第一个2与最后一个0交换即可
分析：
看一下有多少个2和0的位置错了就换过来，因为1永远要是在中间的

#include <bits/stdc++.h>
using namespace std;
const int MAXN=1e6+1;
int n, c[MAXN], num[3], x1, x2, e0, e1;
int main() {
	cin >> n;
	for (int i = 1; i <= n; ++i) {
		cin >> c[i];
		++num[c[i]];
	}
	for (int i = 1; i <= num[0]; ++i)
		if (c[i] == 1)
			x1++;
		else if (c[i] == 2)
			x2++;
	for (int i = num[0] + num[1] + 1; i <= n; ++i)
		if (c[i] == 1) 
			e1++;
		else if (c[i] == 0)	
			e0++;
	cout << x1 + x2 + e1 + e0 - min(e0, x2) << endl;
	return 0;
}

阶乘尾数

内存限制: 256 Mb时间限制: 1000 ms
题目描述
给定一个整数 n，n 的阶乘定义为

$n!=1\times 2\times \cdots \times n$

请计算在 n! 的十进制表示中，末尾有多少个连续的 0？

例如 n=5，则 n!=120，末尾有 1 个 0，又12!=479001600，末尾有 2 个 0。

输入格式
单个整数表示 n。

输出格式
单个整数表示 n! 中末尾零的个数。

数据范围
对于 30% 的数据，1≤n≤1000；
对于 60% 的数据，1≤n≤1,000,000；
对于 100% 的数据，1≤n≤2,000,000,000；
样例数据
输入:
5
输出:
1
输入:
12
输出:
2
说明:
12的阶乘为479001600
分析：
简单数学题，看一下n的阶乘中有多少个5（在5的倍数里找）

#include <bits/stdc++.h>
using namespace std;
long long n;
long long f(long long n) {
	long long num = 0, i, j;
	for (i = 5; i <= n; i += 5) {
		j = i;
		while (j % 5 == 0) {
			++num;
			j /= 5;
		}
	}
	return num;
}
int main() {
	cin >> n;
	cout << f(n);
	return 0;
}

前序中序转后序

内存限制: 256 Mb时间限制: 1000 ms
题目描述
有一棵二叉树，结点数量不超过 26，树上的每个结点都可以用一个唯一的大写英文字母区分，给定这棵二叉树的前序遍历与中序遍历，请输出它的后序遍历。

输入格式
第一行：一个字符串，表示二叉树的前序遍历；
第二行：一个字符串，表示二叉树的中序遍历。

输出格式
单独一行：一个字符串，表示二叉树的后序遍历。

数据范围
设二叉树的结点数量为 n，

对于 50% 的数据，1≤n≤10
对于 100% 的数据，1≤n≤26
样例数据
输入:
ACE
CAE
输出:
CEA
分析：
按照前中序的原理，前序判根中序判位置。

#include <bits/stdc++.h>
using namespace std;
int cnt = 0;
string n1, n2;
void tree(int l, int r, char ch) {
	for (int i = l; i < r; ++i) {
		if (n2[i] == ch) {
			if (l < i)
				tree(l, i, n1[cnt++]);
			if (i + 1 < r)
				tree(i + 1, r, n1[cnt++]);
			cout << ch;
			break;
		}
	}
}
int main() {
	cin >> n1 >> n2;
	tree(0, n1.size(), n1[cnt++]);
	return 0;
}