我们可以这么理解，你有两个杯子 a a a 和 b b b，两个杯子里都盛满了水，现在想把两个杯子里的水交换一下，那么第一个想到的方法是什么？
当然是再找来一个临时杯子：
1）先把 a a a 杯子的水倒进这个临时的杯子里；
2）再把 b b b 杯子的水倒进 a a a 杯子里；
3）最后把临时杯子里的水倒进 b b b 杯子；
这种就是临时变量法，那么当然，还有很多很多的方法，接下来就让我们来见识一下吧。
三、代码详解 1、正确解法1：引入临时变量
#include <stdio.h>
int main() {
int a, b, tmp;
while (scanf("%d %d", &a, &b) != EOF) {
tmp = a; // (1)
a = b; // (2)
b = tmp; // (3)
printf("%d %d\n", a, b);
}
return 0;
}
( 1 ) (1) (1)tmp = a;表示把 a a a 杯子的水倒进这个临时的杯子里；
( 2 ) (2) (2)a = b;表示把 b b b 杯子的水倒进 a a a 杯子里；
( 3 ) (3) (3)b = tmp;表示把临时杯子里的水倒进 b b b 杯子里；
这三步，就实现了变量 a a a 和 b b b 的交换。
2、正确解法2：引入算术运算
#include <stdio.h>
int main() {
int a, b;
while (scanf("%d %d", &a, &b) != EOF) {
a = a + b; // (1)
b = a - b; // (2)
a = a - b; // (3)
printf("%d %d\n", a, b);
}
return 0;
}
( 2 ) (2) (2)b = a - b;执行完毕后，相当于b的值变成了a + b - b，即原先a的值；
( 3 ) (3) (3)a = a - b;执行完毕后，相当于a的值变成了a + b - a，即原先b的值；
从而实现了变量a和b的交换。
3、正确解法3：引入异或运算
首先，介绍一下C语言中的^符号，代表的是异或。
二进制的异或，就是两个数转换成二进制表示后，按照位进行以下运算：
[tr]左操作数右操作数异或结果[/tr]
0
0
0
1
1
0
0
1
1
1
0
1
也就是对于 0 和 1，相同的数异或为 0，不同的数异或为 1。
这样就有了三个比较清晰的性质：
1）两个相同的十进制数异或的结果一定位零。
2）任何一个数和 0 的异或结果一定是它本身。
3）异或运算满足结合律和交换律。
#include <stdio.h>
int main() {
int a, b;
while (scanf("%d %d", &a, &b) != EOF) {
a = a ^ b; // (1)
b = a ^ b; // (2)
a = a ^ b; // (3)
printf("%d %d\n", a, b);
}
return 0;
}
#include <stdio.h>
int main() {
int a, b;
while (scanf("%d %d", &a, &b) != EOF) {
printf("%d %d\n", b, a);
}
return 0;
}
你学废了吗 ????？
2、例题2：整数溢出 一、题目描述
先输入一个 t ( t ≤ 100 ) t (t \le 100) t(t≤100)，然后输入 t t t 组数据。每组输入为 4 个正整数 a , b , c , d ( 0 ≤ a , b , c , d ≤ 2 62 ) a,b,c,d(0 \le a,b,c,d \le 2^{62}) a,b,c,d(0≤a,b,c,d≤262)，输出 a + b + c + d a+b+c+d a+b+c+d 的值。
#include <stdio.h>
typedef unsigned long long ull; // (1)
const ull MAX = (((ull)1)<<62); // (2)
int main() {
int t;
ull a, b, c, d;
scanf("%d", &t);
while (t--) {
scanf("%llu %llu %llu %llu", &a, &b, &c, &d); // (3)
if (a == MAX && b == MAX && c == MAX && d == MAX) // (4)
printf("18446744073709551616\n"); // (5)
else
printf("%llu\n", a + b + c + d); // (6)
}
return 0;
}
( 1 ) (1) (1) 由于这题数据量较大，所有数据都需要用64位无符号整型。ull作为unsigned long long的别名；
图 G G G 是一个有序二元组 ( V , E ) (V,E) (V,E)，其中 V V V 称为顶点集合， E E E 称为边集合， E E E 与 V V V 不相交。顶点集合的元素被称为顶点，边集合的元素被称为边。
对于无权图，边由二元组 ( u , v ) (u,v) (u,v) 表示，其中 u , v ∈ V u, v \in V u,v∈V。对于带权图，边由三元组 ( u , v , w ) (u,v, w) (u,v,w) 表示，其中 u , v ∈ V u, v \in V u,v∈V， w w w 为权值，可以是任意类型。
图分为有向图和无向图，对于有向图， ( u , v ) (u, v) (u,v) 表示的是 从顶点 u u u 到 顶点 v v v 的边，即 u → v u \to v u→v；对于无向图， ( u , v ) (u, v) (u,v) 可以理解成两条边，一条是 从顶点 u u u 到 顶点 v v v 的边，即 u → v u \to v u→v，另一条是从顶点 v v v 到 顶点 u u u 的边，即 v → u v \to u v→u；
如图所示， d a t a data data 即 ( v , w ) (v, w) (v,w) 二元组，代表和对应顶点 u u u 直接相连的顶点数据， w w w 代表 u → v u \to v u→v 的边权， n e x t next next 是一个指针，指向下一个 ( v , w ) (v, w) (v,w) 二元组。
如图所示，表示的是三元组 ( u , v , w ) (u, v, w) (u,v,w) 的数组， i d x idx idx 代表数组下标。
那么用哪种数据结构才能满足所有图的需求呢？
接下来介绍一种新的数据结构 —— 链式前向星。
4）链式前向星
链式前向星和邻接表类似，也是链式结构和数组结构的结合，每个结点 i i i 都有一个链表，链表的所有数据是从 i i i 出发的所有边的集合（对比邻接表存的是顶点集合），边的表示为一个四元组 ( u , v , w , n e x t ) (u, v, w, next) (u,v,w,next)，其中 ( u , v ) (u, v) (u,v) 代表该条边的有向顶点对 u → v u \to v u→v， w w w 代表边上的权值， n e x t next next 指向下一条边。
具体的，我们需要一个边的结构体数组 edge[maxm]，maxm表示边的总数，所有边都存储在这个结构体数组中，并且用head来指向 i i i 结点的第一条边。
边的结构体声明如下：
struct Edge {
int u, v, w, next;
Edge() {}
Edge(int _u, int _v, int _w, int _next) :
u(_u), v(_v), w(_w), next(_next)
{
}
}edge[maxm];
初始化所有的head = -1，当前边总数 edgeCount = 0；
每读入一条 u → v u \to v u→v 的边，调用 addEdge(u, v, w)，具体函数的实现如下：
void addEdge(int u, int v, int w) {
edge[edgeCount] = Edge(u, v, w, head[u]);
head[u] = edgeCount++;
}
这个函数的含义是每加入一条边 ( u , v , w ) (u, v, w) (u,v,w)，就在原有的链表结构的首部插入这条边，使得每次插入的时间复杂度为 O ( 1 ) O(1) O(1)，所以链表的边的顺序和读入顺序正好是逆序的。这种结构在无论是稠密的还是稀疏的图上都有非常好的表现，空间上没有浪费，时间上也是最小开销。
调用的时候只要通过head就能访问到由 i i i 出发的第一条边的编号，通过编号到edge数组进行索引可以得到边的具体信息，然后根据这条边的next域可以得到第二条边的编号，以此类推，直到 next域为 -1 为止。
for (int e = head[u]; ~e; e = edges[e].next) {
int v = edges[e].v;
ValueType w = edges[e].w;
...
}
文中的 ~e等价于 e != -1，是对e进行二进制取反的操作（-1 的的补码二进制全是 1，取反后变成全 0，这样就使得条件不满足跳出循环）。
1）令初始情况下，数组下标从 0 开始，且数组长度为 n n n，则定义一个区间，它的左端点是 l = 0 l=0 l=0，右端点是 r = n − 1 r = n-1 r=n−1；
2）生成一个区间中点 m i d = ( l + r ) / 2 mid = (l + r) / 2 mid=(l+r)/2，并且判断 m i d mid mid 对应的数组元素和给定的目标值的大小关系，主要有三种：
2.a）目标值 等于 数组元素，直接返回 m i d mid mid；
2.b）目标值 大于 数组元素，则代表目标值应该出现在区间 [ m i d + 1 , r ] [mid+1, r] [mid+1,r]，迭代左区间端点： l = m i d + 1 l = mid + 1 l=mid+1；
2.c）目标值 小于 数组元素，则代表目标值应该出现在区间 [ l , m i d − 1 ] [l, mid-1] [l,mid−1]，迭代右区间端点： r = m i d − 1 r = mid - 1 r=mid−1；
3）如果这时候 l > r l > r l>r，则说明没有找到目标值，返回 − 1 -1 −1；否则，回到 2）继续迭代。
5、双指针
双指针，主要是利用两个下标在一个数组上，根据问题的单调性，进行指针偏移，由于每个指针只往后偏移，所以时间复杂度可以达到 O ( n ) O(n) O(n)，由于思想非常简单，所以出题时，热度不低。
6、差分法
差分法一般配合前缀和。
对于区间 [ l , r ] [l, r] [l,r] 内求满足数量的数，可以利用差分法分解问题；
假设 [ 0 , x ] [0, x] [0,x] 内的 g o o d n u m b e r good \ number good number 数量为 g x g_x gx，那么区间 [ l , r ] [l, r] [l,r] 内的数量就是 g r − g l − 1 g_r - g_{l-1} gr−gl−1；分别用同样的方法求出 g r g_r gr 和 g l − 1 g_{l-1} gl−1，再相减即可；
如果子问题的数目为 O ( n t ) O(n^t) O(nt)，每个子问题需要用到 O ( n e ) O(n^e) O(ne) 个子问题的结果，那么我们称它为 tD/eD 的问题，于是可以总结出四类常用的动态规划方程：（下面会把opt作为取最优值的函数（一般取 m i n min min 或 m a x max max ）, w ( j , i ) w(j, i) w(j,i)为一个实函数，其它变量都可以在常数时间计算出来）。
1、1D/1D
d [ i ] = o p t ( d [ j ] + w ( j , i ) ∣ 0 < = i < j ) d = opt( d[j] + w(j, i) | 0 <= i < j ) d=opt(d[j]+w(j,i)∣0<=i<j)
状态转移如图四所示（黄色块代表 d [ i ] d d，绿色块代表 d [ j ] d[j] d[j]）：
这类状态转移方程一般出现在线性模型中。
2、2D/0D
d [ i ] [ j ] = o p t ( d [ i − 1 ] [ j ] + x i , d [ i ] [ j − 1 ] + y j , d [ i − 1 ] [ j − 1 ] + z i j ) d[j] = opt( d[i-1][j] + x_i, d[j-1] + y_j, d[i-1][j-1] + z_{ij} ) d[j]=opt(d[i−1][j]+xi,d[j−1]+yj,d[i−1][j−1]+zij)
状态转移如图四所示：
比较经典的问题是最长公共子序列、最小编辑距离。
有关最长公共子序列的问题，可以参考以下文章：夜深人静写算法（二十一）- 最长公共子序列
有关最小编辑距离的问题，可以参考以下文章：夜深人静写算法（二十二）- 最小编辑距离
3、2D/1D
d [ i ] [ j ] = w ( i , j ) + o p t ( d [ i ] [ k − 1 ] + d [ k ] [ j ] ) d[j] = w(i, j) + opt( d[k-1] + d[k][j] ) d[j]=w(i,j)+opt(d[k−1]+d[k][j])
区间模型常用方程，如图所示：
另外一种常用的 2D/1D 的方程为：
d [ i ] [ j ] = o p t ( d [ i − 1 ] [ k ] + w ( i , j , k ) ∣ k < j ) d[j] = opt( d[i-1][k] + w(i, j, k) | k < j ) d[j]=opt(d[i−1][k]+w(i,j,k)∣k<j)
区间模型的详细内容可以参考以下这篇文章：夜深人静写算法（二十七）- 区间DP
4、2D/2D
d [ i ] [ j ] = o p t ( d [ i ′ ] [ j ′ ] + w ( i ′ , j ′ , i , j ) ∣ 0 < = i ′ < i , 0 < = j ′ < j ) d[j] = opt( d[i'][j'] + w(i', j', i, j) | 0 <= i' < i, 0 <= j' < j) d[j]=opt(d[i′][j′]+w(i′,j′,i,j)∣0<=i′<i,0<=j′<j)
如图所示：
常见于二维的迷宫问题，由于复杂度比较大，所以一般配合数据结构优化，如线段树、树状数组等。
对于一个tD/eD 的动态规划问题，在不经过任何优化的情况下，可以粗略得到一个时间复杂度是 O ( n t + e ) O(n^ {t+e}) O(nt+e)，空间复杂度是 O ( n t ) O(n^t) O(nt) 的算法，大多数情况下空间复杂度是很容易优化的，难点在于时间复杂度，后续章节将详细讲解各种情况下的动态规划优化算法。
编程语言
发布于：2021-07-08 11:15
|
阅读数：683
|
评论：0
QQ好友和群
QQ空间
