2020暑期实训算法温故知新

2020暑期实训算法温故知新

这次接触算法应该是我学习代码以来最多的一次，而且写完这些算法的时间很短，根本来不及进行整理和归纳，因此，我认为进行这样一次温故知新是非常有必要的，一方面，我可以把一些我认为能够通过c++ 的STL优化的算法重写一遍（这次实训最坑的一点就是只能用C，什么都要自己造，而我造的东西移植性又不好，性能也不咋地，哭了~~)，另一方面，我可以对当时一些不是很清楚的算法做一些总结和归类，这也算是我的第一个小题库。

龙虎斗

枚举

轩轩和凯凯正在玩一款叫《龙虎斗》的游戏，游戏的棋盘是一条线段，线段上有 n个兵营(自左至右编号 1~ n)，相邻编号的兵营之间相隔 1 厘米，即棋盘为长度为 n - 1 厘米的线段。i 号兵营里有 ci 位工兵。

下面图 11 为 n = 6 的示例:

img

图 11. n = 6的示例

轩轩在左侧，代表 “龙”；凯凯在右侧，代表 “虎”。他们以 m号兵营作为分界，靠左的工兵属于龙势力，靠右的工兵属于虎势力，而 第 m 号兵营中的工兵很纠结，他们不属于任何一方。

一个兵营的气势为：该兵营中的工兵数 × 该兵营到 m 号兵营的距离；参与游戏一方的势力定义为：属于这一方所有兵营的气势之和。

下面图 22 为 n = 6, m = 4的示例，其中红色为龙方，黄色为虎方:

img

图 22. n = 6, m = 4 的示例

游戏过程中，某一刻天降神兵，共有 s1 位工兵突然出现在了 p1 号兵营。作为轩轩和凯凯的朋友，你知道如果龙虎双方气势差距太悬殊，轩轩和凯凯就不愿意继续玩下去了。为了让游戏继续，你需要选择一个兵营p2，并将你手里的s2 位工兵 全部 派往兵营 p2，使得双方气势差距尽可能小。

注意：你手中的工兵落在哪个兵营，就和该兵营中其他工兵有相同的势力归属(如果落在 m号兵营，则不属于任何势力)。

输入格式

输入文件的第一行包含一个正整数 n，代表兵营的数量。

接下来的一行包含 n 个正整数，相邻两数之间以一个空格分隔，第 i个正整数代表编号为 i的兵营中起始时的工兵数量 ci。

接下来的一行包含四个正整数，相邻两数间以一个空格分隔，分别代表 m,p1,s1,s2。

输出格式

输出文件有一行，包含一个正整数，即 p2，表示你选择的兵营编号。

如果存在多个编号同时满足最优，取最小的编号。

数据范围

1 < m < n, 1≤ p1 ≤n。

对于 20% 的数据，n*=3,m=2,*ci=1,s1,s2≤100。

另有 20% 的数据，n≤10,p1=m,ci=1,s1,s2≤100。

对于 60% 的数据，n≤100,ci=1,s1,s2≤100。

对于 80% 的数据，n≤100,ci,s1,s2≤100。

对于100% 的数据，n≤$10^5$,ci,s1,s2≤$10^9$。

样例说明

样例 1

双方以 m=4号兵营分界，有s1=5 位工兵突然出现在 p1=6 号兵营。

龙方的气势为：

2 x (4 - 1) + 3 x (4 - 2) + 2 x (4 - 3) = 14

虎方的气势为：

2 x (5 - 4) + (3 + 5) x (6 - 4) = 18

当你将手中的s2=2 位工兵派往p2=2 号兵营时，龙方的气势变为：

14 + 2 × ( 4 − 2 ) = 18

此时双方气势相等。

样例 2

双方以 m = 5 号兵营分界，有s1=1 位工兵突然出现在 p1=4 号兵营。

龙方的气势为:

1 × ( 5−1 ) + 1 × ( 5−2 ) + 1 × ( 5−3 ) + ( 1+1 ) × ( 5−4 ) = 11

虎方的气势为:

16 × ( 6 −5 ) = 16

当你将手中的 s2=1 位工兵派往 p2=1 号兵营时，龙方的气势变为:

11+1×(5−1)=15

此时可以使双方气势的差距最小。

解题思路

现在看来，当时做题可能是被题目的长度给吓到了，如果时间的限制不太严的话，直接枚举每一个值，分别计算气势差距就OK了，最后时间复杂度在O(n)，我估计当时应该是被时间给卡住了，但直接枚举比较不费脑子，所以也懒得想什么奇淫技巧了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
#include <bits/stdc++.h>
using namespace std;

//题目要求输入的数据：
int n;
int m;
int p1, s1;
int p2, s2;

//双方的气势
int lpower = 0, rpower = 0;

int main(){
    //记录当前的最小气势差
    int min = 0x3f3f3f3f;
    //记录当前气势差
    int gap;
    cin >> n;
    int i ,j;
    vector<int> build;
    build.push_back(0);
    //初始化所有数据
    for(i = 0;i < n;i++){
        cin >> m;
        build.push_back(m);
    }
    cin >> m >> p1 >> s1 >> s2;
    //天降神兵后双方的气势
    build[p1] += s1;
    for(i = 1;i < m ;i++){
        lpower += build[i] * (m - i);
    }
    for(i = m + 1;i <= n;i++){
        rpower += build[i] * (i - m);
    }
    //对每一个兵营进行遍历，然后计算气势差，记录下最小的那个p2
    for(i = 1;i <= n;i++){
        int tmp;
        if(i < m){
            tmp = lpower;
            lpower += s2 * (m - i);
            gap = abs(lpower - rpower);
            lpower = tmp;
        } else if(i > m){
            tmp = rpower;
            rpower += s2 * (i - m);
            gap = abs(lpower - rpower);
            rpower = tmp;
        } else {
            gap = abs(lpower - rpower);
        }
        if(gap < min){
            min = gap;
            p2 = i;
        }
    }
    cout << p2 << endl;
    return 0;
}

大整数加法

高精度

求两个不超过 200200 位的非负整数的和。

输入格式

有两行，每行是一个不超过 200200 位的非负整数，可能有多余的前导 00。

输出格式

一行，即相加后的结果。结果里不能有多余的前导 00，即如果结果是 342342，那么就不能输出为 03420342。


解题思路

使用dequeue能够快速头插元素对这题帮助极大！毫无疑问，如果只能使用C语言来解析这题，第一层麻烦就是静态数组，如果正向做加法，会把数组颠三倒四好多次，但如果逆向做加法，由于不清楚各个数组的长度和是否有最终进位，因此空间十分不好申请，还有一点就是，如果不让两个数组长度相同（其中一个用0补充），那么判断条件会增添许多麻烦，如果让其中一个填充0，那头插又会耗费数组大量时间。

而有了deque，这一切都不是问题，我们可以像做竖式加法一样去思考这个大整数加法。将两个字符串转化一下读到deque中，用头插补0，然后申请一个逆向的迭代器就可以愉快地做加法啦~

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
#include <bits/stdc++.h>
using namespace std;

int main(){
    string str1, str2;
    cin >> str1 >> str2;
    int len1 = str1.length();
    int len2 = str2.length();
    deque<int> qu1, qu2;
    string::reverse_iterator it;
    for(it = str1.rbegin(); it != str1.rend();it++){
        qu1.push_front(int((*it) - '0'));
    }
    for(it = str2.rbegin(); it != str2.rend();it++){
        qu2.push_front(int((*it) - '0'));
    }
    int gap;
    if(len1 > len2){
        gap = len1 - len2;
        while(gap){
            qu2.push_front(0);
            gap--;
        }
    } else {
        gap = len2 - len1;
        while(gap){
            qu1.push_front(0);
            gap--;
        }
    }
    int cf = 0;
    deque<int> ans;
    deque<int>::reverse_iterator it1, it2;
    //小学加法
    for(it1 = qu1.rbegin(), it2 = qu2.rbegin(); it1 != qu1.rend();it1++, it2++){
        int tmp = *it1 + *it2 + cf;
        ans.push_front(tmp % 10);
        if(tmp >= 10)cf = 1;
        else cf = 0;
    }
    if(cf == 1){
        ans.push_front(1);
    }
    for(auto x : ans)cout << x;
    cout << endl;
    return 0;
}

有木有很清晰的感觉~~


高精度运算

高精度

看了几个题，基本都是涉及到大数的加减乘除，因此在这里将其归纳总结起来，再遇到类似的题融会贯通就好。

解决思路

将大数用字符串读取进来以后，使用vector进行逐位运算（在不优化的情况下，使用小学竖式加减乘除的思想就OK），这里可能涉及到结构继承。

代码如下（转自百度百科）：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
#include <bits/stdc++.h>
using namespace std;

struct Wint:vector<int>
{
    Wint(int n=0)//默认初始化为0，但0的保存形式为空
    {
        push_back(n);
        check();
    }
    //每一种运算完成后，需要将数据整理成正常的十进制表达
    Wint& check()
    {
        while(!empty()&&!back())pop_back();//去除最高位可能存在的0
        if(empty())return *this;
        for(int i=1; i<size(); ++i)
        {
            (*this)[i]+=(*this)[i-1]/10;
            (*this)[i-1]%=10;
        }
        while(back()>=10)
        {
            push_back(back()/10);
            (*this)[size()-2]%=10;
        }
        return *this;//为使用方便，将进位后的自身返回引用
    }
};

istream& operator>>(istream &is,Wint &n)
{
    string s;
    is>>s;
    n.clear();
    for(int i=s.size()-1; i>=0; --i)n.push_back(s[i]-'0');
    return is;
}

//该算法只能接受正数输入
ostream& operator<<(ostream &os,const Wint &n)
{
    if(n.empty())os<<0;
    for(int i=n.size()-1; i>=0; --i)os<<n[i];
    return os;
}

//大数比较
bool operator!=(const Wint &a,const Wint &b)
{
    if(a.size()!=b.size())return 1;
    for(int i=a.size()-1; i>=0; --i)
        if(a[i]!=b[i])return 1;
    return 0;
}
bool operator==(const Wint &a,const Wint &b)
{
    return !(a!=b);
}
bool operator<(const Wint &a,const Wint &b)
{
    if(a.size()!=b.size())return a.size()<b.size();
    for(int i=a.size()-1; i>=0; --i)
        if(a[i]!=b[i])return a[i]<b[i];
    return 0;
}
bool operator>(const Wint &a,const Wint &b)
{
    return b<a;
}
bool operator<=(const Wint &a,const Wint &b)
{
    return !(a>b);
}
bool operator>=(const Wint &a,const Wint &b)
{
    return !(a<b);
}

//大数加法，逐位相加后整理格式
Wint& operator+=(Wint &a,const Wint &b)
{
    if(a.size()<b.size())a.resize(b.size());
    for(int i=0; i!=b.size(); ++i)a[i]+=b[i];
    return a.check();
}
Wint operator+(Wint a,const Wint &b)
{
    return a+=b;
}

//大数减法，重点在于连续借位
Wint& operator-=(Wint &a,Wint b)
{
    if(a<b)swap(a,b);
    for(int i=0; i!=b.size(); a[i]-=b[i],++i)
        if(a[i]<b[i])//需要借位
        {
            int j=i+1;
            while(!a[j])++j;
            while(j>i)
            {
                --a[j];
                a[--j]+=10;
            }
        }
    return a.check();
}
Wint operator-(Wint a,const Wint &b)
{
    return a-=b;
}

Wint operator*(const Wint &a,const Wint &b)
{
    Wint n;
    n.assign(a.size()+b.size()-1,0);
    for(int i=0; i!=a.size(); ++i)
        for(int j=0; j!=b.size(); ++j)
            n[i+j]+=a[i]*b[j];
    return n.check();
}
Wint& operator*=(Wint &a,const Wint &b)
{
    return a=a*b;
}
	
Wint divmod(Wint &a,const Wint &b)
{
    Wint ans;
    for(int t=a.size()-b.size(); a>=b; --t)
    {
        Wint d;
        d.assign(t+1,0);
        d.back()=1;
        Wint c=b*d;
        while(a>=c)
        {
            a-=c;
            ans+=d;
        }
    }
    return ans;
}
Wint operator/(Wint a,const Wint &b)
{
    return divmod(a,b);
}
Wint& operator/=(Wint &a,const Wint &b)
{
    return a=a/b;
}
Wint& operator%=(Wint &a,const Wint &b)
{
    divmod(a,b);
    return a;
}
Wint operator%(Wint a,const Wint &b)
{
    return a%=b;
}

Wint& operator !(Wint &a){
    if(a == Wint(0) || a == Wint(1)){
        a = Wint(1);
        return a;
    }
    else {
        Wint n = a;
        a = Wint(1);
        Wint i(1);
        for(;i <= n;i += Wint(1)){
            a *= i;
        }
        return a;
    }
}

引爆炸弹

DFS

在一个 n×m 的方格地图上，某些方格上放置着炸弹。手动引爆一个炸弹以后，炸弹会把炸弹所在的行和列上的所有炸弹引爆，被引爆的炸弹又能引爆其他炸弹，这样连锁下去。

img

现在为了引爆地图上的所有炸弹，需要手动引爆其中一些炸弹，为了把危险程度降到最低，请算出最少手动引爆多少个炸弹可以把地图上的所有炸弹引爆。

输入格式

第一行输两个整数 n,m，用空格隔开。

接下来 n 行，每行输入一个长度为 m 的字符串，表示地图信息。0表示没有炸弹，1表示炸弹。

数据约定：

对于 40% 的数据：1≤n,m≤100；

对于 100% 的数据：1≤n,m≤500；

输出格式

输出一个整数，表示最少需要手动引爆的炸弹数。

解题思路

​ 使用深度搜索，先引爆一个炸弹，获得一个全新的地图，然后再引爆剩下的炸弹，直到所有的炸弹都被引爆完，然后取较少的引爆次数，直到所有的情况都遍历完获得答案。（这题为什么没有首先考虑广度优先搜索，原因在于地图的面积是很小的，因此在炸弹稀疏的情况下能够较快被引爆完，而选择广度优先搜索的话会占用大量的队列空间）。

代码如下（具体实现步骤看代码注释）：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
#include <bits/stdc++.h>
using namespace std;

/**
 * 使用深度搜索，先引爆一个炸弹，获得一个全新的地图，然后再引爆剩下的炸弹，直到所有的炸弹都被引爆完，
 * 然后取较少的引爆次数，直到所有的情况都遍历完获得答案。
*/

struct Point{
    int x;
    int y;
    Point(int x, int y):x(x), y(y) {}
};

ostream& operator<< (ostream& os, const Point &pos){
    cout << "(" << pos.x << "," << pos.y << ")";
    return os;
}

//int min = 0x3f3f3f3f;

//查看zone中炸弹的位置,如果没有炸弹返回false
bool check(const vector<string> &zone,vector<Point> &bombs){
    int row, col;
    row = zone.size();
    col = zone[0].size();
    int i , j;
    for(i = 0;i < row;i++){
        for(j = 0;j < col;j++){
            if(zone[i][j] == '1'){
                bombs.push_back(Point(i, j));
            }
        }
    }
    if(bombs.size() == 0)return false;
    else return true;
}

//引爆其中一个炸弹，并且连锁引爆同一条线上的其他炸弹，获得一个新的地图
void fire_one(vector<string> &zone, Point fire_pos){
    int row = fire_pos.x;
    int col = fire_pos.y;
    for(int i = 0;i < zone.size();i++){
        if(zone[i][col] == '1'){
            zone[i][col] = '0';
        }
    }
    for(int j = 0;j < zone[0].size();j++){
        if(zone[row][j] == '1'){
            zone[row][j] = '0';
        }
    }
}

//深度搜索函数，参数：zone, 引爆位置，最少炸弹个数
void bfs(vector<string> zone, Point fire_pos, int cur_min, int &min){
    fire_one(zone, fire_pos);
    vector<Point> bombs;              //存放地图上剩余的所有炸弹
    if(check(zone, bombs)){
        while(bombs.size()){
            bfs(zone, bombs.back(), cur_min + 1, min);
            bombs.pop_back();
        }
    } else {
        if(cur_min < min){
            min = cur_min;
        }
    }
    return;
}

//找出地图上的所有炸弹，然后对每一种情况深度优先搜索，最后比较出最小的那个
int fire_bombs(vector<string> &zone){
    int min = 0x3f3f3f3f;
    vector<Point> bombs;
    if(check(zone, bombs)){
        while(bombs.size()){
            bfs(zone, bombs.back(), 0, min);
            bombs.pop_back();
        }
    }
    return min;
}

int main(){
    int n,m;
    cout << "please input row and col:\n";
    cin >> n >> m;

    //初始化地图zone
    vector<string> zone;
    string tmp;
    for(int i = 0;i < n;i++){
        cin >> tmp;
        zone.push_back(tmp);
    }
    int min = fire_bombs(zone);
    cout << "min:" << min << endl;
    return 0;
}

一维跳棋

BFS

一维跳棋是一种在 1×(2N+1) 的棋盘上玩的游戏。一共有 N 个棋子，其中 N 个是黑的，N个是白的。游戏开始前，N 个白棋子被放在一头，N 个黑棋子被放在另一头，中间的格子空着。在这个游戏里有两种移动方法是允许的：你可以把一个棋子移到与它相邻的空格；你可以把一个棋子跳过一个（仅一个）与它不同色的棋子到达空格。

对于N=3 的情况，棋盘状态依次为：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
WWW BBB
WW WBBB
WWBW BB
WWBWB B
WWB BWB
W BWBWB
 WBWBWB
BW WBWB
BWBW WB
BWBWBW
BWBWB W
BWB BWW
B BWBWW
BB WBWW
BBBW WW
BBB WWW

对应的空格所在的位置（从左数）为：3 5 6 4 2 1 3 5 7 6 4 2 3 5 4。

输入格式

输入仅一个整数，表示针对 N(1≤N≤8) 的取值。

输出格式

依次输出空格所在棋盘的位置，每个整数间用空格分隔，每行 5个数（每行结尾无空格，最后一行可以不满 5个数；如果有多组移动步数最小的解，输出第一个数最小的解）。

解题思路

求最小的解一般优先考虑广度优先搜索，本题就是这个例子。对于每一种棋况，考虑空格能够移动的情况，而最多的可能情况只有4种：空格往左移动，往右移动一格，当左边（右边）的相邻两个棋子不同时，可以往左（右）跳1格。因此，我们只用检查每一种情况，把符合情况的新棋况放入一格队列中，然后继续取出头部的元素进行搜索，直到遇到结果的情况。

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
#include <bits/stdc++.h>
using namespace std;

map<string, bool> visited;

//一种局势状态
struct stat{
    string board;
    int space_index;
    int parent;
    stat(string b, int index, int pa):board(b), space_index(index), parent(pa) {}
    
    //将当前局势状态下形成的所有合理新局势状态放入new_stat中
    void check(vector<stat> &new_stat, int pa) const{        
        //判断空格是否可以向左移动
        if(space_index != 0){
            string new_board = board;
            //最先判断空格是否可以向左跳一格，以保证结果序列中空格坐标小的值排在最前面
            if(space_index != 1){                
                if(new_board[space_index - 2] != new_board[space_index - 1]){
                    new_board[space_index] = new_board[space_index - 2];
                    new_board[space_index - 2] = ' ';
                    if(visited.find(new_board) == visited.end()){
                        new_stat.push_back(stat(new_board, space_index - 2, pa));
                    } 
                }
            }
            
            //再判断空格是否可以向左移动一格
            new_board = board;
            new_board[space_index] = new_board[space_index - 1];
            new_board[space_index - 1] = ' ';
            if(visited.find(new_board) == visited.end()){
                new_stat.push_back(stat(new_board, space_index - 1, pa));
            }
        }

        int size = board.size();
      	//判断空格是否可以向右移动
        if(space_index != size - 1){
            //先假设向右移动一格
            string new_board = board;
            new_board[space_index] = new_board[space_index + 1];
            new_board[space_index + 1] = ' ';
            if(visited.find(new_board) == visited.end()){
                new_stat.push_back(stat(new_board, space_index + 1, pa));
            }
            //判断空格是否可以向右跳一格
            if(space_index != size - 2){
                new_board = board;
                if(new_board[space_index + 1] != new_board[space_index + 2]){
                    new_board[space_index] = new_board[space_index + 2];
                    new_board[space_index + 2] = ' ';
                    if(visited.find(new_board) == visited.end()){
                        new_stat.push_back(stat(new_board, space_index + 2, pa));
                    }
                }
            }
        }
    }
};

//声明非循环队列，继承自vector(因为不需要删除首个元素)
struct myQueue:vector<stat>{
    int front;
    myQueue(){front = 0;}
    
    stat get_front(){
        return this->at(front);
    }
    //只是头指针移动，而不弹出结点，以回溯路径
    void qu_pop(){
        front++;
        return;
    }
};

int main(){
    //初始化
    int n;
    cout << "please input number of every side:";
    cin >> n;
    myQueue qu;
    string start, end;
    for(int i = 0;i < 2 * n + 1; i++){
        if(i < n){
            start.push_back('w');
        } else if(i == n){
            start.push_back(' ');
        } else {
            start.push_back('b');
        }
    }
    string::reverse_iterator r_it;
    for(r_it = start.rbegin(); r_it != start.rend(); r_it++){
        end.push_back(*r_it);
    }
    
    //将最初的局势状态放入队列中
    stat tmp(start, n, -1);
    qu.push_back(tmp);
    visited[tmp.board] = true;
    
    vector<stat> new_stat;  //用于存放生成的新状态
    
    //处理队列中的元素
    while(qu.size() != qu.front){
        tmp = qu.get_front();  //获取首个未处理的元素
        
        //如果该元素为目标，则回溯路径，输出结果
        if(tmp.board == end){
            vector<int> ans;
            while(tmp.parent != -1){
                ans.push_back(tmp.space_index);
                tmp = qu.at(tmp.parent);
            }
            vector<int>::reverse_iterator re_it;
            for(re_it = ans.rbegin(); re_it != ans.rend(); re_it++){
                cout << *re_it + 1 << " ";
            }cout << endl;
            return 0;
        }
        
        int pa = qu.front;   //记录每个新元素的父元素在队列中的位置，以回溯路径
        qu.qu_pop();
        new_stat.clear();
        tmp.check(new_stat, pa);
        vector<stat>::iterator it;
        for(it = new_stat.begin(); it != new_stat.end(); it++){
            visited[it->board] = true;
            qu.push_back(*it);
        }
    }
    return 0;
}

数独

DFS

蒜头君今天突然开始还念童年了，想回忆回忆童年。他记得自己小时候，有一个很火的游戏叫做数独。便开始来了一局紧张而又刺激的高阶数独。蒜头君做完发现没有正解，不知道对不对？ 不知道聪明的你能否给出一个标准答案？

标准数独是由一个给与了提示数字的 9×9 网格组成，我们只需将其空格填上数字，使得每一行，每一列以及每一个 3×3 宫都没有重复的数字出现。

img

输入格式

一个 9×9 的数独，数字之间用空格隔开。0表示需要填写的数字。

输出格式

输出一个 9×9 的数独，把出入中的0替换成需要填写的数字即可。

解题思路

由于只用求出一个解，所以使用深度优先搜索，由于在填数字的过程中需要频繁地查找地图中的元素以判断是否违反规则。如果直接查找，则每一次都需要消耗大约9+9+9个时间单位，但其实这是没有必要的，因为我们只需要知道和它相同的值是否在同一条线或者同一个九宫格内就行，因此这里可以使用哈希表来降低查找时间。

对于查找到的每一个空格，我们需要遍历数字1~9，如果填入该数字后不会违反规则，我们就填入它，然后查找下一个空格，直到这个查找的指针遍历到最后一个位置，算法结束。如果当前空格已经遍历完所有可能的数字，则将该位置重置为0，并且从哈希表中删除它，再回到前一个位置进行遍历。

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
/** 
 * ubuntu sukodu 秒杀算法
 * 使用vector存储board，数据类型为int,空余位置用0来替代
 * 规则:每行，每列和每个小方格里面都是数字1-9
 * 能够快速初始化界面
 * 
 * 解决办法：深度优先搜索
 * 对于每一个位置，找出它的所有可能数字，然后在此基础上处理下一个位置
 * 检查是否符合规则：用哈希表存储相同数字的位置，删除方法：遍历该vector
*/
#include <bits/stdc++.h>
using namespace std;

class Point{
public:
    int row;
    int col;
    Point(int r, int c){
        row = r;
        col = c;
    }
    bool equal(Point a){
        return a.row == row && a.col == col;
    }
};

unordered_map<int, vector<Point> > points;

vector<vector<int> > board(9, vector<int>(9, 0));

void init_board(){
    string input;
    //8 + 9
    cout << "format: " << "123456789\n";
    cout << "-----------------\n";
    for(int i = 0; i < 9;i++){
        cout << "line " << i + 1 << ": ";
        getline(cin, input);
        for(int j = 0; j < 9; j++){
            board[i][j] = (int)(input[j] - '0');
            if(board[i][j])points[board[i][j]].push_back(Point(i, j));
        }
    }

}

//检查该位置放置的数字是否符合条件
bool check(int val, Point pos){
    for(auto it = points[val].begin(); it != points[val].end(); it++){
        if(pos.row == it->row || pos.col == it->col)return false;
        if(pos.row/3 == it->row/3 && pos.col/3 == it->col/3)return false;
    }
    return true;
}

void del(int val, Point pos){
    for(auto it = points[val].begin(); it != points[val].end(); it++){
        if(it->equal(pos)){
            points[val].erase(it);
            return;
        }
    }
}

//获取第一个需要填写的位置坐标
Point init_pos(Point pos){
    while(board[pos.row][pos.col]){
        if(pos.equal(Point(8, 8))){
            cout << "it's full!\n";
            exit(1);
        }
        if(pos.col == 8){
            pos.row++;
            pos.col = 0;
        } else {
            pos.col++;
        }
    }
    return pos;
}

void disp_board(){
    for(int i = 0;i < 9;i++){
        for(int j = 0; j < 9;j++){
            printf(",%d" + !j, board[i][j]);
        }cout << endl;
    }
}

bool DFS(Point pos){
    for(int i = 1; i <= 9;i++){
        if(check(i, pos)){
            board[pos.row][pos.col] = i;
            points[i].push_back(pos);
            Point new_pos(pos);
            while(board[new_pos.row][new_pos.col]){
                if(new_pos.equal(Point(8, 8))){
                    disp_board();
                    return true;
                }
                if(new_pos.col == 8){
                    new_pos.row++;
                    new_pos.col = 0;
                } else {
                    new_pos.col++;
                }
            }
            //找到一个空位置
            if(DFS(new_pos))return true;
            board[pos.row][pos.col] = 0;
            del(i, pos);
        }
    }
    return false;
}

int main(){
    init_board();
    if(!DFS(init_pos(Point(0,0))))cout << "no solution!\n";
    return 0;
}

任务系统

优先队列

蒜头君设计了一个任务系统。这个系统是为了定时提醒蒜头君去完成一些事情。

系统大致如下，初始的时候，蒜头君可能会注册很多任务，每一个任务的注册如下:

Register $Q_{num}$ Period

表示从系统启动开始，每过 Period 秒提醒蒜头君完成编号为 $Q_{num}$的任务。

你能计算出蒜头君最先被提醒的 k个任务吗？

输入格式

第一行输入 n(0<n≤50000)，k(0<k≤10000)，其中 n表示蒜头君注册的任务数量。

接下来 n行，每行输入一条注册命令，其中0<$q_{num}$≤3000，0≤Period≤3000。

输出格式

顺序输出 k行，表示依次提醒的任务的编号。如果同一时间有多个任务，最先提醒编号小的任务。

解题思路

使用优先队列（堆结构），每次弹出时间最近的任务后，更新该任务的下一次触发时间放入队列中排序，直到前k次输出完。

eg: 堆结构经常是在插入和弹出之间交替进行的。

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
#include <bits/stdc++.h>
using namespace std;

map<int, int> single_time;

struct task{
    int num, time;
    task(int x, int y):num(x), time(y) {}
    bool operator < (const task &a) const{
        if(time > a.time)return true;
        if(time == a.time && num > a.num)return true;
        return false;
    }
};

//优先队列的排序规则：对于运算符 < , 如果返回true，就把前一个参数排在前面，而
//优先队列总是弹出最后一个元素
priority_queue<task> qu;

int main(){
    int n ,k;
    cin >> n >> k;
    string buff;
    int num, time;
    while(n--){
        cin >> buff >> num >> time;
        single_time[num] = time;
        qu.push(task(num, time));
    }
    while(k--){
        task tmp = qu.top();
        qu.pop();
        cout << tmp.num << endl;
        //更新下一次的触发时间，并放入优先队列中
        tmp.time += single_time[tmp.num];
        qu.push(tmp);
    }
    return 0;
}
数据结构与算法
#枚举 #高精度 #DFS #BFS #优先队列
2020暑期实训算法温故知新
http://example.com/2023/01/10/2020暑期实训算法温故知新/
作者
Chen Shuwen
发布于
2023年1月10日
许可协议