7-1 高精度数加法
原题呈现：
解题思路 ： 1.毫无疑问板子是两个数的高精度加法，用到倒序写入、模拟竖式加法等技巧，不再赘述。2.由两个数扩展到N个数只要加一重循环，且在循环体最后把每次加和的结果作为下一次的一个加数即可。
以下是根据这一思路写出的代码：
#include<bits/stdc++.h>
using namespace std;
const int maxn = 1000010;
char s1[maxn], s2[maxn];
int a[maxn], b[maxn], c[maxn];
int main() {
int num, len;
scanf("%d\n", &num);
scanf("%s\n", s1);
num--;
while (num--) {
if (num == 1)
break;
scanf("%s\n",s2);//读入字符串b
//将字符串s1写入到数组a中
int len1 = strlen(s1);
for (int i = 0; i < len1; i++) {
//倒序写入
a[i] = s1[len1 - i - 1] - '0';
}
//将字符串s2写入到数组b中
int len2 = strlen(s2);
for (int i = 0; i < len2; i++) {
//倒序写入
b[i] = s2[len2 - i - 1] - '0';
}
//模拟竖式加法
int jw = 0;//进位
len = max(len1, len2) + 1;//注意因为最高位可能出现进位
for (int i = 0; i < len; i++) {
c[i] = a[i] + b[i] + jw;//当前加数A位数据+加数B位位数据+上一位的进位
jw = c[i] / 10;//本次加法是否存在进位
c[i] %= 10;//只能保存 0 ~ 9 的数据
}
//删除前导零
for (int i = len - 1; i >= 0; i--) {
//因为我们是从索引 0 开始，所以最高位是保存在 len-1
if (0 == c[i] && len > 1) {
//注意要有 len>1 这个条件。考虑特殊情况，加法结果为 00，我们实际要输出 0。
len--;
}
else {
//第一个不是零的最高位，结束删除
break;
}
}
//把s1更新为之前所有数的和，用char[]储存
for (int i = 0; i < len; i++) {
s1[len-1-i] = c[i] + '0';
}
//清空数组a、b
for (int i = 0; i < len; i++) {
a[i] = 0;
b[i] = 0;
}
}
//特判：只有一个加数
if (num == -1) {
int i = 0;
while (s1[i] == '0')
i++;
printf("%s\n", s1 + i);
}
//逆序打印输出
else {
for (int i = len - 1; i >= 0; i--) {
printf("%d", c[i]);
}
printf("\n");
}
}
解后反思： 1.注意特判N=1时的情形。2.注意每次循环后清空数组，以免发生奇奇怪怪的错误。
7-2 二叉树加权距离
原题呈现：
解题思路 ： 一开始使用了LCA的板子，结果空间超了。再读题发现该题只要查询一次，套用LCA的板子时空开销太大。故直接建树，并保存每个节点的父亲节点和深度，最后找出两个节点的公共父亲，再进行一系列简单操作即可。
以下是根据这一思路写出的代码：
#include<bits/stdc++.h>
using namespace std;
struct tree {
int num;
int depth;
struct tree* father;
struct tree* left;
struct tree* right;
};
tree t[100005];
int main()
{
int num;
scanf("%d", &num);
for (int i = 1; i < num; i++)
{
int f, s;
scanf("%d %d", &f, &s);
if (t[f].left == NULL)
t[f].left = &t[s];
else
t[f].right = &t[s];
t[s].father = &t[f];
t[s].depth = t[f].depth + 1;
}
int u, v;
scanf("%d %d", &u, &v);
tree* f1 = &t[u], * f2 = &t[v];
while (f1 != f2)
{
if (f1->depth > f2->depth)
f1 = f1->father;
else
f2 = f2->father;
}
int res = (t[u].depth - f1->depth) * 3 + (t[v].depth - f1->depth) * 2;
printf("%d", res);
}
也可以用静态形式储存树，代码如下：
#include<bits/stdc++.h>
using namespace std;
int depth[100005],father[100005], l[100005], r[100005];
int main()
{
int num;
scanf("%d", &num);
for (int i = 1; i < num; i++)
{
int f, s;
scanf("%d %d", &f, &s);
if (l[f] == 0)
l[f] = s;
else
r[f] = s;
father[s] = f;
depth[s] = depth[f] + 1;
}
int u, v;
scanf("%d %d", &u, &v);
int f1 = u, f2 = v;
while (f1 != f2)
{
if (depth[f1] > depth[f2])
f1 = father[f1];
else
f2 = father[f2];
}
int res = (depth[u] - depth[f1]) * 3 + (depth[v] - depth[f1]) * 2;
printf("%d", res);
}
解后反思： 一般有多组查询时可以用打表或者具有类似思想的算法；如果只有一次查询，则直接模拟/暴力可能就能达到题目要求，且能节省时空开销。
7-3 修轻轨
原题呈现：
解题思路：
1.因为题目要求最小施工天数，自然想到先取施工天数少的，可以利用sort对节点排序；又因为一共只有n段路，又有n支队伍可同时施工，故一支队伍只要修一段其他队伍不修的，就可以完成任务，故不用考虑n的限制（此处比较抽象，只可意会）。
2.首先考虑用flag数组标记每一段路是否打通，并用一个变量标记已经打通的路的段数，当该变量的值等于n时，终止循环。但是，这种方法时间复杂度过高，因而考虑用并查集优化：当find(n) = find(1)时，表示从1~n均被打通。
以下是根据这一思路写出的代码：
#include<bits/stdc++.h>
using namespace std;
const int maxn = 100010;
struct edge
{
int f, t, c;
}e[100010];
bool cmp(const edge& a, const edge& b) {
return a.c < b.c;
}
int f[maxn];//并查集
int find(int x)
{
if (f[x] == x)
return x;
return f[x] = find(f[x]);
}
void merge(int m, int n)
{
int x = find(m), y = find(n);
if (x != y){
f[x] = y;
}
}
int main()
{
int n, m, ans=0;
scanf("%d %d", &n, &m);
for (int i = 1; i <= n; ++i)
f[i] = i;
for (int i = 1, u, v, w; i <= m; ++i)
scanf("%d %d %d", &e[i].f, &e[i].t, &e[i].c);
sort(e + 1, e + m + 1, cmp);
int count = 0;
for (int i = 1; i <= m && count != n - 1; ++i)
{
if (find(e[i].f) != find(e[i].t)){
count++;
ans = e[i].c;
merge(e[i].f, e[i].t);
}
if (find(1) == find(n))
break;
}
printf("%d\n", ans);
}
解后反思： 注意并查集适用情景的多样化。
7-4 数据结构设计I
原题呈现：
解题思路： 因为可以从表的一端插入，另一端删除，故考虑用双端队列；因为有取反操作，故同时维护maxn，minn两个双端队列，并用flag记录取反的次数；此外，题目中还要维护一个区间，故用cnt标明队尾（插入位置），del标明队首（删除位置）。
以下是根据这一思路写出的代码：
#include<bits/stdc++.h>
using namespace std;
const int mmax = 1000010;
deque<int> maxn, minn;
int m, n, flag, a[mmax], cnt, del;
int main()
{
scanf("%d", &m);
char op;
while (m--)
{
scanf("\n%c", &op);
if (op == 'I') {
cnt++;
scanf("%d", &a[cnt]);
if (pow(-1, flag) == -1)
a[cnt] = -a[cnt];
int tmp = a[cnt];
while (!maxn.empty() && a[maxn.back()] >= tmp)
maxn.pop_back();
maxn.push_back(cnt);
while (!minn.empty() && a[minn.back()] <= tmp)
minn.pop_back();
minn.push_back(cnt);
}
else if (op == 'D') {
if (del < cnt) {
del++;
while (!maxn.empty() && maxn.front() <= del)
maxn.pop_front();
while (!minn.empty() && minn.front() <= del)
minn.pop_front();
}
}
else if (op == 'R') {
flag++;
}
else if (op == 'M') {
if (del < cnt) {
if (pow(-1, flag) == -1) {
printf("%d\n", -a[maxn.front()]);
}
else {
printf("%d\n", a[minn.front()]);
}
}
}
}
}