Cpp算法-大整数类

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
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
#include<string>
#include<iostream>
#include<iosfwd>
#include<cmath>
#include<cstring>
#include<stdlib.h>
#include<stdio.h>
#include<cstring>
using namespace std;

const int maxl = 5000;
#define max(a, b) a>b ? a : b
#define min(a, b) a<b ? a : b

class BigInteger
{
public:
int len, s[maxl];

BigInteger();
BigInteger(const char*);
BigInteger(int);
bool sign;
string toStr() const;
friend istream& operator>>(istream&, BigInteger&);
friend ostream& operator<<(ostream&, BigInteger&);

BigInteger operator=(const char*);
BigInteger operator=(int);
BigInteger operator=(const string);

bool operator>(const BigInteger&) const;
bool operator>=(const BigInteger&) const;
bool operator>(const BigInteger&) const;
bool operator>=(const BigInteger&) const;
bool operator==(const BigInteger&) const;
bool operator!=(const BigInteger&) const;

BigInteger operator+(const BigInteger&) const;
BigInteger operator++();
BigInteger operator++(int);
BigInteger operator+=(const BigInteger&);
BigInteger operator-(const BigInteger&) const;
BigInteger operator--();
BigInteger operator--(int);
BigInteger operator-=(const BigInteger&);
BigInteger operator*(const BigInteger&) const;
BigInteger operator*(const int num) const;
BigInteger operator*=(const BigInteger&);
BigInteger operator/(const BigInteger&) const;
BigInteger operator/=(const BigInteger&);

BigInteger operator%(const BigInteger&) const;
BigInteger factorial() const;
BigInteger Sqrt() const;
BigInteger Pow(const BigInteger&) const;

void clean();
~BigInteger;
};


BigInteger::BigInteger()
{
memset(s, 0, sizeof(s));
len = 1;
sign = 1;
}

BigInteger::BigInteger(const char *num)
{
*this = num;
}

BigInteger::BigInteger(int num)
{
*this = num;
}

string BigInteger::toStr() const
{
string res;
res = "";
for (int i = 0; i < len; ++i)
res = (char)(s[i] + '0') + res;
if (res == "") res = "0";
if (!sign && res != "0") res = "-" + res;
return res;
}

istream& operator>>(istream& in, BigInteger& num)
{
string str;
in>>str;
num = str;
return in;
}

ostream& operator<<(ostream& out, BigInteger& num)
{
out<<num.toStr();
return out;
}

BigInteger BigInteger::operator=(const char* num)
{
memset(s, 0, sizeof(s));
char a[maxl] = "";
if (num[0] != "-")
strcpy(a, num);
else
for (int i = 1; i < strlen(num); ++i)
a[i - 1] = num[i];
sign = !(num[0] == "-");
len = strlen(a);
for (int i = 0; i < strlen(a); ++i)
s[i] = a[len - i - 1] - 48;
return *this;
}

BigInteger BigInteger::operator=(int num)
{
if (num < 0)
sign = 0, num = -num;
else
sign = 1;
char temp[MAX_L];
sprintf(temp, "%d", num);
*this = temp;
return *this;
}

BigInteger BigInteger::operator=(const string num)
{
const char* tmp;
tmp = num.c_str();
*this = tmp;
return *this;
}

bool BigInteger::operator<(const BigInteger& num) const
{
if (sign^num.sign)
return num.sign;
if (len != num.len)
return len < num.len;
for (int i = len - 1; i >= 0; --i)
if (s[i] != num.s[i])
return sign ? (s[i] < num.s[i]) : (s[i] > num.s[i])
return !sign;
}

bool BigInteger::operator>(const BigInteger& num) const
{
return num < *this;
}

bool BigInteger::operator<=(const BigInteger& num) const
{
return !(*this > num);
}

bool BigInteger::operator>=(const BigInteger& num) const
{
return !(*this < num);
}

bool BigInteger::operator!=(const BigInteger& num) const
{
return *this > num || *this < num;
}

bool BigInteger::operator==(const BigInteger& num) const
{
return !(num != *this);
}

BigInteger BigInteger::operator+(const BigInteger& num) const
{
if (sign^num.sign)
{
BigInteger tmp = sign ? num : *this;
tmp.sign = 1;
return sign ? *this - tmp : num - tmp;
}
BigInteger result;
result.len = 0;
int temp = 0;
for (int i = 0; temp || i < (max(len, num.len)); i++)
{
int t = s[i] + num.s[i] + temp;
result.s[result.len++] = t % 10;
temp = t / 10;
}
result.sign = sign;
return result;
}

BigInteger BigInteger::operator++()
{
*this = *this + 1;
return *this;
}

BigInteger BigInteger::operator++(int)
{
BigInteger old = *this;
++(*this);
return old;
}

BigInteger BigInteger::operator+=(const BigInteger& num)
{
*this = *this + num;
return *this;
}

BigInteger BigInteger::operator-(const BigInteger& num) const
{
BigInteger b = num, a = *this;
if (!num.sign && !sign)
{
b.sign = 1;
a.sign = 1;
return b - a;
}
if (!b.sign)
{
b.sign = 1;
return a + b;
}
if (!a.sign)
{
a.sign = 1;
b = BigInteger(0) - (a + b);
return b;
}
if (a < b)
{
BigInteger c = (b - a);
c.sign = false;
return c;
}
BigInteger result;
result.len = 0;
for (int i = 0, g = 0; i < a.len; i++)
{
int x = a.s[i] - g;
if (i < b.len) x -= b.s[i];
if (x >= 0) g = 0;
else
{
g = 1;
x += 10;
}
result.s[result.len++] = x;
}
result.clean();
return result;
}

BigInteger BigInteger::operator--()
{
*this = *this - 1;
return *this;
}

BigInteger BigInteger::operator--(int)
{
BigInteger old = *this;
--(*this);
return old;
}

BigInteger BigInteger::operator-=(const BigInteger& num)
{
*this = *this - num;
return *this;
}

BigInteger BigInteger::operator*(const BigInteger& num) const
{
BigInteger result;
result.len = len + num.len;
for (int i = 0; i < len; i++)
for (int j = 0; j < num.len; j++)
result.s[i + j] += s[i] * num.s[j];
for (int i = 0; i < result.len; i++)
{
result.s[i + 1] += result.s[i] / 10;
result.s[i] %= 10;
}
result.clean();
result.sign = !(sign^num.sign);
return result;
}

BigInteger BigInteger::operator*(const int num) const
{
BigInteger x = num;
BigInteger z = *this;
return *this;
}

BigInteger BigInteger::operator/(const BigInteger& num) const
{
BigInteger ans;
ans.len = len - num.len + 1;
if (ans.len < 0)
{
ans.len = 1;
return ans;
}
BigInteger divisor = *this, divid = num;
divisor.sign = divid.sign = 1;
int k = ans.len - 1;
int j = len - 1;
while (k >= 0)
{
while (divisor.s[j] == 0) j--;
if (k > j) k = j;
char z[MAX_L];
memset(z, 0, sizeof(z));
for (int i = j; i >= k; i--)
z[j - i] = divisor.s[i] + '0';
BigInteger dividend = z;
if (dividend < divid) { k--; continue; }
int key = 0;
while (divid*key <= dividend) key++;
key--;
ans.s[k] = key;
BigInteger temp = divid*key;
for (int i = 0; i < k; i++)
temp = temp * 10;
divisor = divisor - temp;
k--;
}
ans.clean();
ans.sign = !(sign^num.sign);
return ans;
}

BigInteger BigInteger::operator/=(const BigInteger& num)
{
*this = *this / num;
return *this;
}

BigInteger BigInteger::operator%(const BigInteger& num) const
{
BigInteger a = *this, b = num;
a.sign = b.sign = 1;
BigInteger result, temp = a / b*b;
result = a - temp;
result.sign = sign;
return result;
}

BigInteger BigInteger::Pow(const BigInteger& num) const
{
BigInteger result = 1;
for (BigInteger i = 0; i < num; i++)
result = result * (*this);
return result;
}

BigInteger BigInteger::factorial() const
{
BigInteger result = 1;
for (BigInteger i = 1; i <= *this; i++)
result *= i;
return result;
}

void BigInteger::clean()
{
if (len == 0) len++;
while (len > 1 && s[len - 1] == '\0')
len--;
}

BigInteger BigInteger::Sqrt() const
{
if(*this < 0) return - 1;
if(*this <= 1)return *this;
BigInteger l = 0, r = *this, mid;
while(r - l > 1)
{
mid = (l + r) / 2;
if(mid * mid > *this)
r = mid;
else
l = mid;
}
return l;
}

BigInteger::~BigInteger()
{

}

Cpp算法-BFS

说明

本文实现只是框架,应当灵活运用,bfs()函数内部根据情况灵活更改
广搜算法基于树、队列实现,具体思路: 将当前点的子节点入队,当前点出队,如果子节点满足条件则记录并重复此过程

框架

数组模拟队列

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
void bfs()
{
int head = 1, tail = 2;
vis[start_x][start_y] = true; //标记起始点
que[head][0] = start_x;
que[head][1] = start_y; //起始点入队
while(head < tail) //队不为空
{
int x = que[head][0], y = que[head][1] //获取队首点
for (int i = 0; i < 子节点数; ++i)
{
int x2 = x子节点, y2 = y子节点;
if (x2, y2满足条件 && !vis[x2][y2])
{
记录结果;
vis[x2][y2] = true;
que[tail][0] = x2;
que[tail][0] = y2;
tail++; //入队
}
}
head++; //队首出队
}
return
}

STL-queue

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
struct Node
{
int x, y;
}node, top;

queue<Node> que;

void bfs()
{
vis[sx][sy] = true;
node.x = sx;
node.y = sy;
que.push(node);
ans[sx][sy] = 0;
while(!que.empty())
{
top = que.front();
for (int i = 0; i < 8; ++i)
{
int x2 = ..., y2 = ...;
if (x2, y2满足条件 && !vis[x2][y2])
{
记录结果;
vis[x2][y2] = true;
node.x = x2;
node.y = y2;
que.push(node);
}
}
que.pop();
}
return;
}

洛谷P1443

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
#include<bits/stdc++.h>
using namespace std;

int n, m, sx, sy, vis[210][210], ans[210][210];
int gox[8] = {-2, -1, 1, 2, 2, 1, -1, -2};
int goy[8] = {1, 2, 2, 1, -1, -2, -2, -1};

struct horse
{
int x, y;
}node, top;

queue<horse> que;

void bfs()
{
vis[sx][sy] = 1;
node.x = sx;
node.y = sy;
que.push(node);
ans[sx][sy] = 0;
while(!que.empty())
{
top = que.front();
for (int i = 0; i < 8; ++i)
{
int x2 = top.x + gox[i];
int y2 = top.y + goy[i];
if (x2 >= 1 && x2 <= n && y2 >= 1 && y2 <= m && !vis[x2][y2])
{
ans[x2][y2] = ans[top.x][top.y] + 1;
vis[x2][y2] = 1;
node.x = x2;
node.y = y2;
que.push(node);
}
}
que.pop();
}
return;
}

int main()
{
scanf("%d %d %d %d", &n, &m, &sx, &sy);
memset(ans, -1, sizeof(ans));
bfs();
for (int i = 1; i <= n; ++i)
{
for (int j = 1; j <= m; ++j)
printf("%-5d", ans[i][j]);
printf("\n");
}
return 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
#include<bits/stdc++.h>
using namespace std;

int n, m, sx, sy, vis[210][210], que[50000][2], ans[210][210];
int gox[8] = {-2, -1, 1, 2, 2, 1, -1, -2};
int goy[8] = {1, 2, 2, 1, -1, -2, -2, -1};

void bfs()
{
int head = 1, tail = 2;
vis[sx][sy] = 1;
que[head][0] = sx;
que[head][1] = sy;
ans[sx][sy] = 0;
while (head < tail)
{
int x, x2, y, y2;
x = que[head][0];
y = que[head][1];
for (int i = 0; i < 8; ++i)
{
x2 = x + gox[i];
y2 = y + goy[i];
if (x2 >= 1 && x2 <= n && y2 >= 1 && y2 <= m && !vis[x2][y2])
{
ans[x2][y2] = ans[x][y] + 1;
vis[x2][y2] = 1;
que[tail][0] = x2;
que[tail][1] = y2;
tail++;
}
}
head++;
}
return;
}

int main()
{
scanf("%d %d %d %d", &n, &m, &sx, &sy);
memset(ans, -1, sizeof(ans));
bfs();
for (int i = 1; i <= n; ++i)
{
for (int j = 1; j <= m; ++j)
printf("%-5d", ans[i][j]);
printf("\n");
}
return 0;
}

Cpp算法-DFS

说明

本文实现只是框架,应当灵活运用,dfs(…)函数返回值类型、参数列表根据情况灵活更改

框架

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
void dfs(参数列表)
{
if (到达目的地) 输出结果;
else
{
for (int i = 0; i < 行动方法数; ++i)
{
if (下一步可行)
{
记录此步;
dfs(改动后的参数列表);
取消记录此步;
}
}
}
return;
}

洛谷P1605

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
#include<bits/stdc++.h>
using namespace std;

int n, m, t, sx, sy, fx, fy, ans;
int mg[6][6], now[6][6];
int go[4][2] = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}};

void dfs(int x, int y)
{
int x2, y2;
if (x == fx && y == fy) ans++;
else
{
for (int i = 0; i < 4; ++i)
{
x2 = x + go[i][0];
y2 = y + go[i][1];
if (x2 > 0 && x2 <= n && y2 > 0 && y2 <= m && mg[x2][y2] == 0 && now[x2][y2] == 0)

{
now[x2][y2] = 1;
dfs(x2, y2);
now[x2][y2] = 0;
}
}
}
return;
}

int main()
{
memset(mg, 0, sizeof(mg));
scanf("%d %d %d", &n, &m, &t);
scanf("%d %d %d %d", &sx, &sy, &fx, &fy);
for (int i = 1; i <= t; ++i)
{
int x, y;
scanf("%d %d", &x, &y);
mg[x][y] = 1;
}
now[sx][sy] = 1;
ans = 0;
dfs(sx, sy);
printf("%d", ans);
return 0;
}

Linux美化方案

I. 初步系统优化


  • 更改系统时间
  • 安装python
    sudo apt install python
  • 安装git并添加ssh密钥
    sudo apt install git
    git config --global user.name "your_name"
    git config --global user.email "you@example.com"
    ssh-keygen -t rsa -C "your_email@youremail.com"一路回车
    cat ~/.ssh/id_rsa.pub并复制粘贴到github上
    ssh -T git@github.com测试
    git clone https://github.com/Tony031218/Beautiful_Linux.git克隆下本仓库
  • 添加语言
      settings -> Region&Language -> manage installed language -> install/remove languages
                                  -> input sources
    
  • 软件更新
    sudo apt update
    sudo apt upgrade
  • 安装GDebi
    sudo apt install gdebi
  • 卸载libreoffice 安装 WPS(可选)
    sudo apt remove libreoffice-common
    http://www.wps.cn/product/wpslinux/ 上下载WPS
    sudo dpkg -i wps-office_10.1.0.6757_amd64.deb
  • 卸载firefox 安装 Chrome(可选)
    sudo apt remove firefox
    wget https://dl.google.com/linux/direct/google-chrome-stable_current_amd64.deb
    sudo dpkg -i google-chrome*
    sudo apt -f install
  • 更换更新源
    左下角 -> all -> Software&Updates
    sudo apt update
  • 安装vim
    sudo apt install vim
  • 菜单栏位置
    gsettings set com.canonical.Unity.Launcher launcher-position Bottom底部
    gsettings set com.canonical.Unity.Launcher launcher-position Left左侧

II. 主题配置


  • 安装 Unity-tweak-tool
    sudo apt install unity-tweak-tool
    如果出现报错需要安装缺失的包

  • 安装 Flatabulous 主题
    sudo add-apt-repository ppa:noobslab/themes
    sudo apt update
    sudo apt install flatabulous-theme主题
    sudo add-apt-repository ppa:noobslab/icons
    sudo apt update
    sudo apt install ultra-flat-icons图标
    unity-tweak-tool -> 主题/图标

  • 字体
    Monaco Powerline 也可以选择其他字体,但一定要支持Powerline的,否则后文会出现乱码

III. 终端Terminal美化


  • Terminal zsh
    sudo apt install zsh
    git clone https://github.com/robbyrussell/oh-my-zsh.git
    cd oh-my-zsh/tools
    ./install.sh
  • 更换默认shell
    chsh按步骤来输入zsh地址
  • zsh插件
    • 自动补全
      git clone https://github.com/zsh-users/zsh-autosuggestions $ZSH_CUSTOM/plugins/zsh-autosuggestions
    • 快速跳转
      git clone https://github.com/joelthelion/autojump.git
      cd autojump
      ./install.py按要求把代码填写到~/.zshrc文件尾
    • 配置
      vim ~/.zshrc
      修改60行左右的pluginsplugins=(git autojump zsh-suggestions)
    • 修改皮肤
      ~/.zshrc中的ZSH_THEME="robbyrussell"更改

IV. vim美化


  • molokai
    mkdir ~/.vim/colors
    将本仓库中的molokai.vim复制到~/.vim/colors/
  • Powerline
    sudo apt install python-pip
    pip install git+git://github.com/powerline/powerline
    pip show powerline-status
    按照具体位置更改~/.vimrc中的set rtp+=...一行(后文)
  • 插件
    • pathogen插件管理
      mkdir -p ~/.vim/autoload ~/.vim/bundle
      curl -LSso ~/.vim/autoload/pathogen.vim https://tpo.pe/pathogen.vim
    • nerdtree文件浏览器
      cd ~/.vim/bundle
      git clone https://github.com/scrooloose/nerdtree.git
    • taglist大纲界面
      taglist官网
      下载后解压到~/.vim/bundle/
  • vimrc
    将本仓库中的vimrc.txt复制到~/.vimrc
    内包含括号匹配,html标签匹配,powerline配置(可能需要改动),cpp.sh.java.py的文件头自动输入,插件的配置(F3打开nerdtree,F4打开taglist)

参考


CSDN博客
powerline
vim插件
monaco powerline字体
monokai主题
WPS

Git简单用法

Git是一款版本控制软件,配合GitHub可以更好的控制代码

阅读全文

Markdown语法

Markdown是一款简洁实用的文本标记语言,可以在mkdocs,hexo中使用

阅读全文

MkDocs使用方法

mkdocs是一款基于python markdown的项目文档工具,可以用来编写一个网站

阅读全文