0%

邻接

树与图的存储
树是一种特殊的图,与图的存储方式相同。
对于无向图中的边ab,存储两条有向边a->b, b->a。
因此我们可以只考虑有向图的存储。

(1) 邻接矩阵:g[a][b] 存储边a->b

(2) 邻接表:

1
2
3
4
5
6
7
8
9
10
11
12
// 对于每个点k,开一个单链表,存储k所有可以走到的点。h[k]存储这个单链表的头结点
int h[N], e[N], ne[N], idx;

// 添加一条边a->b
void add(int a, int b)
{
e[idx] = b, ne[idx] = h[a], h[a] = idx ++ ;
}

// 初始化
idx = 0;
memset(h, -1, sizeof h);

树与图的遍历

时间复杂度 O(n+m) n表示点数,m表示边数
树和图的遍历:遍历不用像搜索解空间一样递归后恢复,只用遍历一次即可

深度优先遍历

1
2
3
4
5
6
7
8
9
10
int dfs(int u)
{
st[u] = true; // st[u] 表示点u已经被遍历过

for (int i = h[u]; i != -1; i = ne[i])
{
int j = e[i];
if (!st[j]) dfs(j);
}
}

宽度优先遍历

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
queue<int> q;
st[1] = true; // 表示1号点已经被遍历过
q.push(1);

while (q.size())
{
int t = q.front();
q.pop();

for (int i = h[t]; i != -1; i = ne[i])
{
int j = e[i];
if (!st[j])
{
st[j] = true; // 表示点j已经被遍历过
q.push(j);
}
}
}

拓扑排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
bool topsort()
{
int hh = 0, tt = -1;

// d[i] 存储点i的入度
for (int i = 1; i <= n; i ++ )
if (!d[i])
q[ ++ tt] = i;

while (hh <= tt)
{
int t = q[hh ++ ];

for (int i = h[t]; i != -1; i = ne[i])
{
int j = e[i];
if (-- d[j] == 0)
q[ ++ tt] = j;
}
}

// 如果所有点都入队了,说明存在拓扑序列;否则不存在拓扑序列。
return tt == n - 1;
}

朴素dijkstra

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
int g[N][N];  // 存储每条边
int dist[N]; // 存储1号点到每个点的最短距离
bool st[N]; // 存储每个点的最短路是否已经确定

// 求1号点到n号点的最短路,如果不存在则返回-1
int dijkstra()
{
memset(dist, 0x3f, sizeof dist);
dist[1] = 0;

for (int i = 0; i < n - 1; i ++ )
{
int t = -1; // 在还未确定最短路的点中,寻找距离最小的点
for (int j = 1; j <= n; j ++ )
if (!st[j] && (t == -1 || dist[t] > dist[j]))
t = j;

// 用t更新其他点的距离
for (int j = 1; j <= n; j ++ )
dist[j] = min(dist[j], dist[t] + g[t][j]);

st[t] = true;
}

if (dist[n] == 0x3f3f3f3f) return -1;
return dist[n];
}

堆优化dijkstra

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
typedef pair<int, int> PII;

int n; // 点的数量
int h[N], w[N], e[N], ne[N], idx; // 邻接表存储所有边
int dist[N]; // 存储所有点到1号点的距离
bool st[N]; // 存储每个点的最短距离是否已确定

// 求1号点到n号点的最短距离,如果不存在,则返回-1
int dijkstra()
{
memset(dist, 0x3f, sizeof dist);
dist[1] = 0;
priority_queue<PII, vector<PII>, greater<PII>> heap;
heap.push({0, 1}); // first存储距离,second存储节点编号

while (heap.size())
{
auto t = heap.top();
heap.pop();

int ver = t.second, distance = t.first;

if (st[ver]) continue;
st[ver] = true;

for (int i = h[ver]; i != -1; i = ne[i])
{
int j = e[i];
if (dist[j] > distance + w[i])
{
dist[j] = distance + w[i];
heap.push({dist[j], j});
}
}
}

if (dist[n] == 0x3f3f3f3f) return -1;
return dist[n];
}

bellman-ford

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
int n, m;       // n表示点数,m表示边数
int dist[N],backup[N]; // dist[x]存储1到x的最短路距离

struct Edge // 边,a表示出点,b表示入点,w表示边的权重
{
int a, b, w;
}edges[M];

// 求1到n的最短路距离,如果无法从1走到n,则返回-1。
int bellman_ford()
{
memset(dist, 0x3f, sizeof dist);
dist[1] = 0;

// 如果第n次迭代仍然会松弛三角不等式,就说明存在一条长度是n+1的最短路径,由抽屉原理,路径中至少存在两个相同的点,说明图中存在负权回路。
for (int i = 0; i < n; i ++ )
{
memcpy(backup,dist,sizeof dist);
for (int j = 0; j < m; j ++ )
{
int a = edges[j].a, b = edges[j].b, w = edges[j].w;
if (dist[b] > backup[a] + w)
dist[b] = backup[a] + w;
}
}

if (dist[n] > 0x3f3f3f3f / 2) return -1;
return dist[n];
}

spfa(队列优化bellman-ford)

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
int n;      // 总点数
int h[N], w[N], e[N], ne[N], idx; // 邻接表存储所有边
int dist[N]; // 存储每个点到1号点的最短距离
bool st[N]; // 存储每个点是否在队列中

// 求1号点到n号点的最短路距离,如果从1号点无法走到n号点则返回-1
int spfa()
{
memset(dist, 0x3f, sizeof dist);
dist[1] = 0;

queue<int> q;
q.push(1);
st[1] = true;

while (q.size())
{
auto t = q.front();
q.pop();

st[t] = false;

for (int i = h[t]; i != -1; i = ne[i])
{
int j = e[i];
if (dist[j] > dist[t] + w[i])
{
dist[j] = dist[t] + w[i];
if (!st[j]) // 如果队列中已存在j,则不需要将j重复插入
{
q.push(j);
st[j] = true;
}
}
}
}

if (dist[n] == 0x3f3f3f3f) return -1;
return dist[n];
}

floyd

1
2
3
4
5
6
7
8
9
10
11
12
13
14
初始化:
for (int i = 1; i <= n; i ++ )
for (int j = 1; j <= n; j ++ )
if (i == j) d[i][j] = 0;
else d[i][j] = INF;

// 算法结束后,d[a][b]表示a到b的最短距离
void floyd()
{
for (int k = 1; k <= n; k ++ )
for (int i = 1; i <= n; i ++ )
for (int j = 1; j <= n; j ++ )
d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
}

朴素版prim 稀疏图

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
int n;      // n表示点数
int g[N][N]; // 邻接矩阵,存储所有边
int dist[N]; // 存储其他点到当前最小生成树的距离
bool st[N]; // 存储每个点是否已经在生成树中


// 如果图不连通,则返回INF(值是0x3f3f3f3f), 否则返回最小生成树的树边权重之和
int prim()
{
memset(dist, 0x3f, sizeof dist);

int res = 0;
for (int i = 0; i < n; i ++ )
{
int t = -1;
for (int j = 1; j <= n; j ++ )
if (!st[j] && (t == -1 || dist[t] > dist[j]))
t = j;

if (i && dist[t] == INF) return INF;

if (i) res += dist[t];
st[t] = true;

for (int j = 1; j <= n; j ++ ) dist[j] = min(dist[j], g[t][j]);
}

return res;
}

Kruskal算法 稠密图

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
int n, m;       // n是点数,m是边数
int p[N]; // 并查集的父节点数组

struct Edge // 存储边
{
int a, b, w;

bool operator< (const Edge &W)const
{
return w < W.w;
}
}edges[M];

int find(int x) // 并查集核心操作
{
if (p[x] != x) p[x] = find(p[x]);
return p[x];
}

int kruskal()
{
sort(edges, edges + m);

for (int i = 1; i <= n; i ++ ) p[i] = i; // 初始化并查集

int res = 0, cnt = 0;
for (int i = 0; i < m; i ++ )
{
int a = edges[i].a, b = edges[i].b, w = edges[i].w;

a = find(a), b = find(b);
if (a != b) // 如果两个连通块不连通,则将这两个连通块合并
{
p[a] = b;
res += w;
cnt ++ ;
}
}

if (cnt < n - 1) return INF;
return res;
}

染色法判别二分图

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
int n;      // n表示点数
int h[N], e[M], ne[M], idx; // 邻接表存储图
int color[N]; // 表示每个点的颜色,-1表示未染色,0表示白色,1表示黑色

// 参数:u表示当前节点,c表示当前点的颜色
bool dfs(int u, int c)
{
color[u] = c;
for (int i = h[u]; i != -1; i = ne[i])
{
int j = e[i];
if (color[j] == -1)
{
if (!dfs(j, !c)) return false;
}
else if (color[j] == c) return false;
}

return true;
}

bool check()
{
memset(color, -1, sizeof color);
bool flag = true;
for (int i = 1; i <= n; i ++ )
if (color[i] == -1)
if (!dfs(i, 0))
{
flag = false;
break;
}
return flag;
}

匈牙利算法

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
int n1, n2;     // n1表示第一个集合中的点数,n2表示第二个集合中的点数
int h[N], e[M], ne[M], idx; // 邻接表存储所有边,匈牙利算法中只会用到从第一个集合指向第二个集合的边,所以这里只用存一个方向的边
int match[N]; // 存储第二个集合中的每个点当前匹配的第一个集合中的点是哪个
bool st[N]; // 表示第二个集合中的每个点是否已经被遍历过

bool find(int x)
{
for (int i = h[x]; i != -1; i = ne[i])
{
int j = e[i];
if (!st[j])
{
st[j] = true;
if (match[j] == 0 || find(match[j]))
{
match[j] = x;
return true;
}
}
}

return false;
}

// 求最大匹配数,依次枚举第一个集合中的每个点能否匹配第二个集合中的点
int res = 0;
for (int i = 1; i <= n1; i ++ )
{
memset(st, false, sizeof st);
if (find(i)) res ++ ;
}

快速排序算法模板

1
2
3
4
5
6
7
8
9
10
11
12
13
void quick_sort(int q[], int l, int r)
{
if (l >= r) return;

int i = l - 1, j = r + 1, x = q[l + r >> 1];
while (i < j)
{
do i ++ ; while (q[i] < x);
do j -- ; while (q[j] > x);
if (i < j) swap(q[i], q[j]);
}
quick_sort(q, l, j), quick_sort(q, j + 1, r);
}

归并排序算法模板

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
void merge_sort(int q[], int l, int r)
{
if (l >= r) return;

int mid = l + r >> 1;
merge_sort(q, l, mid);
merge_sort(q, mid + 1, r);

int k = 0, i = l, j = mid + 1;
while (i <= mid && j <= r)
if (q[i] <= q[j]) tmp[k ++ ] = q[i ++ ];
else tmp[k ++ ] = q[j ++ ];

while (i <= mid) tmp[k ++ ] = q[i ++ ];
while (j <= r) tmp[k ++ ] = q[j ++ ];

for (i = l, j = 0; i <= r; i ++, j ++ ) q[i] = tmp[j];
}

整数二分算法模板 (找左边界不需要+ 1 右边界需要 并且check(mid) 里必须包含 相等的情况)

bool check(int x) {/* … */} // 检查x是否满足某种性质

// 区间[l, r]被划分成[l, mid]和[mid + 1, r]时使用:
int bsearch_1(int l, int r)
{
while (l < r)
{
int mid = l + r >> 1;
if (check(mid)) r = mid; // check()判断mid是否满足性质
else l = mid + 1;
}
return l;
}
// 区间[l, r]被划分成[l, mid - 1]和[mid, r]时使用:
int bsearch_2(int l, int r)
{
while (l < r)
{
int mid = l + r + 1 >> 1;
if (check(mid)) l = mid;
else r = mid - 1;
}
return l;
}

1
### 浮点数二分模板

bool check(double x) {/* … */} // 检查x是否满足某种性质

double bsearch_3(double l, double r)
{
const double eps = 1e-6; // eps 表示精度,取决于题目对精度的要求
while (r - l > eps)
{
double mid = (l + r) / 2;
if (check(mid)) r = mid;
else l = mid;
}
return l;
}

1
###  一维前缀和

S[i] = a[1] + a[2] + … a[i]
a[l] + … + a[r] = S[r] - S[l - 1]

1
### 二维前缀和

S[i, j] = 第i行j列格子左上部分所有元素的和
以(x1, y1)为左上角,(x2, y2)为右下角的子矩阵的和为:
S[x2, y2] - S[x1 - 1, y2] - S[x2, y1 - 1] + S[x1 - 1, y1 - 1]

````

一维差分

1
给区间[l, r]中的每个数加上c:B[l] += c, B[r + 1] -= c

二维差分

1
2
给以(x1, y1)为左上角,(x2, y2)为右下角的子矩阵中的所有元素加上c:
S[x1, y1] += c, S[x2 + 1, y1] -= c, S[x1, y2 + 1] -= c, S[x2 + 1, y2 + 1] += c

位运算

1
2
求n的第k位数字: n >> k & 1
返回n的最后一位1:lowbit(n) = n & -n

双指针

1
2
3
4
5
6
7
8
9
for (int i = 0, j = 0; i < n; i ++ )
{
while (j < i && check(i, j)) j ++ ;

// 具体问题的逻辑
}
常见问题分类:
(1) 对于一个序列,用两个指针维护一段区间
(2) 对于两个序列,维护某种次序,比如归并排序中合并两个有序序列的操作

离散化

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
vector<int> alls; // 存储所有待离散化的值
sort(alls.begin(), alls.end()); // 将所有值排序
alls.erase(unique(alls.begin(), alls.end()), alls.end()); // 去掉重复元素

// 二分求出x对应的离散化的值
int find(int x) // 找到第一个大于等于x的位置
{
int l = 0, r = alls.size() - 1;
while (l < r)
{
int mid = l + r >> 1;
if (alls[mid] >= x) r = mid;
else l = mid + 1;
}
return r + 1; // 映射到1, 2, ...n
}

区间合并

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
// 将所有存在交集的区间合并
void merge(vector<PII> &segs)
{
vector<PII> res;

sort(segs.begin(), segs.end());

int st = -2e9, ed = -2e9;
for (auto seg : segs)
if (ed < seg.first)
{
if (st != -2e9) res.push_back({st, ed});
st = seg.first, ed = seg.second;
}
else ed = max(ed, seg.second);

if (st != -2e9) res.push_back({st, ed});

segs = res;
}

单链表(数组)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
// head存储链表头,e[]存储节点的值,ne[]存储节点的next指针,idx表示当前用到了哪个节点
int head, e[N], ne[N], idx;

// 初始化
void init()
{
head = -1;
idx = 0;
}

// 在链表头插入一个数a
void insert(int a)
{
e[idx] = a, ne[idx] = head, head = idx ++ ;
}

// 将头结点删除,需要保证头结点存在
void remove()
{
head = ne[head];
}

双链表(数组)

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
// e[]表示节点的值,l[]表示节点的左指针,r[]表示节点的右指针,idx表示当前用到了哪个节点
int e[N], l[N], r[N], idx;

// 初始化
void init()
{
//0是左端点,1是右端点
r[0] = 1, l[1] = 0;
idx = 2;
}

// 在节点a的右边插入一个数x
void insert(int a, int x)
{
e[idx] = x;
l[idx] = a, r[idx] = r[a];
l[r[a]] = idx, r[a] = idx ++ ;
}

// 删除节点a
void remove(int a)
{
l[r[a]] = l[a];
r[l[a]] = r[a];
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
// tt表示栈顶
int stk[N], tt = 0;

// 向栈顶插入一个数
stk[ ++ tt] = x;

// 从栈顶弹出一个数
tt -- ;

// 栈顶的值
stk[tt];

// 判断栈是否为空
if (tt > 0)
{

}

普通队列

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
// hh 表示队头,tt表示队尾
int q[N], hh = 0, tt = -1;

// 向队尾插入一个数
q[ ++ tt] = x;

// 从队头弹出一个数
hh ++ ;

// 队头的值
q[hh];

// 判断队列是否为空
if (hh <= tt)
{

}

循环队列

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
// hh 表示队头,tt表示队尾的后一个位置
int q[N], hh = 0, tt = 0;

// 向队尾插入一个数
q[tt ++ ] = x;
if (tt == N) tt = 0;

// 从队头弹出一个数
hh ++ ;
if (hh == N) hh = 0;

// 队头的值
q[hh];

// 判断队列是否为空
if (hh != tt)
{

}

单调栈 (数组)

1
2
3
4
5
6
7
常见模型:找出每个数左边离它最近的比它大/小的数
int tt = 0;
for (int i = 1; i <= n; i ++ )
{
while (tt && check(stk[tt], i)) tt -- ;
stk[ ++ tt] = i;
}

单调队列 (数组)

1
2
3
4
5
6
7
8
常见模型:找出滑动窗口中的最大值/最小值
int hh = 0, tt = -1;
for (int i = 0; i < n; i ++ )
{
while (hh <= tt && check_out(q[hh])) hh ++ ; // 判断队头是否滑出窗口
while (hh <= tt && check(q[tt], i)) tt -- ;
q[ ++ tt] = i;
}

kmp(数组)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
// s[]是长文本,p[]是模式串,n是s的长度,m是p的长度
求模式串的Next数组:
for (int i = 2, j = 0; i <= m; i ++ )
{
while (j && p[i] != p[j + 1]) j = ne[j];
if (p[i] == p[j + 1]) j ++ ;
ne[i] = j;
}

// 匹配
for (int i = 1, j = 0; i <= n; i ++ )
{
while (j && s[i] != p[j + 1]) j = ne[j];
if (s[i] == p[j + 1]) j ++ ;
if (j == m)
{
j = ne[j];
// 匹配成功后的逻辑
}
}

Trie树

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
int son[N][26], cnt[N], idx;
// 0号点既是根节点,又是空节点
// son[][]存储树中每个节点的子节点
// cnt[]存储以每个节点结尾的单词数量

// 插入一个字符串
void insert(char *str)
{
int p = 0;
for (int i = 0; str[i]; i ++ )
{
int u = str[i] - 'a';
if (!son[p][u]) son[p][u] = ++ idx;
p = son[p][u];
}
cnt[p] ++ ;
}

// 查询字符串出现的次数
int query(char *str)
{
int p = 0;
for (int i = 0; str[i]; i ++ )
{
int u = str[i] - 'a';
if (!son[p][u]) return 0;
p = son[p][u];
}
return cnt[p];
}

并查集 (数组)

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
(1)朴素并查集:

int p[N]; //存储每个点的祖宗节点

// 返回x的祖宗节点
int find(int x)
{
if (p[x] != x) p[x] = find(p[x]);
return p[x];
}

// 初始化,假定节点编号是1~n
for (int i = 1; i <= n; i ++ ) p[i] = i;

// 合并a和b所在的两个集合:
p[find(a)] = find(b);


(2)维护size的并查集:

int p[N], size[N];
//p[]存储每个点的祖宗节点, size[]只有祖宗节点的有意义,表示祖宗节点所在集合中的点的数量

// 返回x的祖宗节点
int find(int x)
{
if (p[x] != x) p[x] = find(p[x]);
return p[x];
}

// 初始化,假定节点编号是1~n
for (int i = 1; i <= n; i ++ )
{
p[i] = i;
size[i] = 1;
}

// 合并a和b所在的两个集合:
size[find(b)] += size[find(a)];
p[find(a)] = find(b);


(3)维护到祖宗节点距离的并查集:

int p[N], d[N];
//p[]存储每个点的祖宗节点, d[x]存储x到p[x]的距离

// 返回x的祖宗节点
int find(int x)
{
if (p[x] != x)
{
int u = find(p[x]);
d[x] += d[p[x]];
p[x] = u;
}
return p[x];
}

// 初始化,假定节点编号是1~n
for (int i = 1; i <= n; i ++ )
{
p[i] = i;
d[i] = 0;
}

// 合并a和b所在的两个集合:
p[find(a)] = find(b);
d[find(a)] = distance; // 根据具体问题,初始化find(a)的偏移量

堆 (数组)

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
// h[N]存储堆中的值, h[1]是堆顶,x的左儿子是2x, 右儿子是2x + 1
// ph[k]存储第k个插入的点在堆中的位置
// hp[k]存储堆中下标是k的点是第几个插入的
int h[N], ph[N], hp[N], size;

// 交换两个点,及其映射关系
void heap_swap(int a, int b)
{
swap(ph[hp[a]],ph[hp[b]]);
swap(hp[a], hp[b]);
swap(h[a], h[b]);
}

void down(int u)
{
int t = u;
if (u * 2 <= size && h[u * 2] < h[t]) t = u * 2;
if (u * 2 + 1 <= size && h[u * 2 + 1] < h[t]) t = u * 2 + 1;
if (u != t)
{
heap_swap(u, t);
down(t);
}
}

void up(int u)
{
while (u / 2 && h[u] < h[u / 2])
{
heap_swap(u, u / 2);
u >>= 1;
}
}

// O(n)建堆
for (int i = n / 2; i; i -- ) down(i);

一般哈希 (数组)

  1. 拉链法
    int h[N], e[N], ne[N], idx;

    // 向哈希表中插入一个数
    void insert(int x)
    {

     int k = (x % N + N) % N;
     e[idx] = x;
     ne[idx] = h[k];
     h[k] = idx ++ ;
    

    }

    // 在哈希表中查询某个数是否存在
    bool find(int x)
    {

     int k = (x % N + N) % N;
     for (int i = h[k]; i != -1; i = ne[i])
         if (e[i] == x)
             return true;
    
     return false;
    

    }

(2) 开放寻址法 (数组)
int h[N];

// 如果x在哈希表中,返回x的下标;如果x不在哈希表中,返回x应该插入的位置
int find(int x)
{
    int t = (x % N + N) % N;
    while (h[t] != null && h[t] != x)
    {
        t ++ ;
        if (t == N) t = 0;
    }
    return t;
}
1
### 字符串哈希

核心思想:将字符串看成P进制数,P的经验值是131或13331,取这两个值的冲突概率低
小技巧:取模的数用2^64,这样直接用unsigned long long存储,溢出的结果就是取模的结果

typedef unsigned long long ULL;
ULL h[N], p[N]; // h[k]存储字符串前k个字母的哈希值, p[k]存储 P^k mod 2^64

// 初始化
p[0] = 1;
for (int i = 1; i <= n; i ++ )
{
h[i] = h[i - 1] * P + str[i];
p[i] = p[i - 1] * P;
}

// 计算子串 str[l ~ r] 的哈希值
ULL get(int l, int r)
{
return h[r] - h[l - 1] * p[r - l + 1];
}

1
2

### C艹 STL简介

vector, 变长数组,倍增的思想
size() 返回元素个数
empty() 返回是否为空
clear() 清空
front()/back()
push_back()/pop_back()
begin()/end()
[]
支持比较运算,按字典序

pair<int, int>
first, 第一个元素
second, 第二个元素
支持比较运算,以first为第一关键字,以second为第二关键字(字典序)

string,字符串
size()/length() 返回字符串长度
empty()
clear()
substr(起始下标,(子串长度)) 返回子串
c_str() 返回字符串所在字符数组的起始地址

queue, 队列
size()
empty()
push() 向队尾插入一个元素
front() 返回队头元素
back() 返回队尾元素
pop() 弹出队头元素

priority_queue, 优先队列,默认是大根堆
size()
empty()
push() 插入一个元素
top() 返回堆顶元素
pop() 弹出堆顶元素
定义成小根堆的方式:priority_queue<int, vector, greater> q;

stack, 栈
size()
empty()
push() 向栈顶插入一个元素
top() 返回栈顶元素
pop() 弹出栈顶元素

deque, 双端队列
size()
empty()
clear()
front()/back()
push_back()/pop_back()
push_front()/pop_front()
begin()/end()
[]

set, map, multiset, multimap, 基于平衡二叉树(红黑树),动态维护有序序列
size()
empty()
clear()
begin()/end()
++, – 返回前驱和后继,时间复杂度 O(logn)

set/multiset
    insert()  插入一个数
    find()  查找一个数
    count()  返回某一个数的个数
    erase()
        (1) 输入是一个数x,删除所有x   O(k + logn)
        (2) 输入一个迭代器,删除这个迭代器
    lower_bound()/upper_bound()
        lower_bound(x)  返回大于等于x的最小的数的迭代器
        upper_bound(x)  返回大于x的最小的数的迭代器
map/multimap
    insert()  插入的数是一个pair
    erase()  输入的参数是pair或者迭代器
    find()
    []  注意multimap不支持此操作。 时间复杂度是 O(logn)
    lower_bound()/upper_bound()

unordered_set, unordered_map, unordered_multiset, unordered_multimap, 哈希表
和上面类似,增删改查的时间复杂度是 O(1)
不支持 lower_bound()/upper_bound(), 迭代器的++,–

bitset, 圧位
bitset<10000> s;
~, &, |, ^
>>, <<
==, !=
[]

count()  返回有多少个1

any()  判断是否至少有一个1
none()  判断是否全为0

set()  把所有位置成1
set(k, v)  将第k位变成v
reset()  把所有位变成0
flip()  等价于~
flip(k) 把第k位取反

```

高精度加法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
// C = A + B, A >= 0, B >= 0
vector<int> add(vector<int> &A, vector<int> &B)
{
if (A.size() < B.size()) return add(B, A);

vector<int> C;
int t = 0;
for (int i = 0; i < A.size(); i ++ )
{
t += A[i];
if (i < B.size()) t += B[i];
C.push_back(t % 10);
t /= 10;
}

if (t) C.push_back(t);
return C;
}

高精度减法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
// C = A - B, 满足A >= B, A >= 0, B >= 0
vector<int> sub(vector<int> &A, vector<int> &B)
{
vector<int> C;
for (int i = 0, t = 0; i < A.size(); i ++ )
{
t = A[i] - t;
if (i < B.size()) t -= B[i];
C.push_back((t + 10) % 10);
if (t < 0) t = 1;
else t = 0;
}

while (C.size() > 1 && C.back() == 0) C.pop_back();
return C;
}

高精度乘法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
vector<int> mul(vector<int> &A, int b)
{
vector<int> C;

int t = 0;
for (int i = 0; i < A.size() || t; i ++ )
{
if (i < A.size()) t += A[i] * b;
C.push_back(t % 10);
t /= 10;
}

while (C.size() > 1 && C.back() == 0) C.pop_back();

return C;
}

高精度除法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
vector<int> div(vector<int> &A, int b, int &r)
{
vector<int> C;
r = 0;
for (int i = A.size() - 1; i >= 0; i -- )
{
r = r * 10 + A[i];
C.push_back(r / b);
r %= b;
}
reverse(C.begin(), C.end());
while (C.size() > 1 && C.back() == 0) C.pop_back();
return C;
}

快速排序模板

1
2
3
4
5
6
7
8
9
10
11
12
13
void quick_sort(int q[], int l, int r)
{
if (l >= r) return;

int i = l - 1, j = r + 1, x = q[l + r >> 1];
while (i < j)
{
do i ++ ; while (q[i] < x);
do j -- ; while (q[j] > x);
if (i < j) swap(q[i], q[j]);
}
quick_sort(q, l, j), quick_sort(q, j + 1, r);
} // 先排再递归

归并排序算法模板

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
void merge_sort(int q[], int l, int r)
{
if (l >= r) return;

int mid = l + r >> 1;
merge_sort(q, l, mid);
merge_sort(q, mid + 1, r);

int k = 0, i = l, j = mid + 1;
while (i <= mid && j <= r)
if (q[i] <= q[j]) tmp[k ++ ] = q[i ++ ];
else tmp[k ++ ] = q[j ++ ];

while (i <= mid) tmp[k ++ ] = q[i ++ ];
while (j <= r) tmp[k ++ ] = q[j ++ ];

for (i = l, j = 0; i <= r; i ++, j ++ ) q[i] = tmp[j];
} //先递归再排序

整数二分算法模板

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
bool check(int x) {/* ... */} // 检查x是否满足某种性质

// 区间[l, r]被划分成[l, mid]和[mid + 1, r]时使用:
// 找右边界
int bsearch_1(int l, int r)
{
while (l < r)
{
int mid = l + r >> 1;
if (check(mid)) r = mid; // check()判断mid是否满足性质
else l = mid + 1;
}
return l;
}
// 区间[l, r]被划分成[l, mid - 1]和[mid, r]时使用:
//找左边界
int bsearch_2(int l, int r)
{
while (l < r)
{
int mid = l + r + 1 >> 1;
if (check(mid)) l = mid;
else r = mid - 1;
}
return l;
}

浮点数二分算法模板

1
2
3
4
5
6
7
8
9
10
11
12
13
bool check(double x) {/* ... */} // 检查x是否满足某种性质

double bsearch_3(double l, double r)
{
const double eps = 1e-6; // eps 表示精度,取决于题目对精度的要求 一般精确到题目要求后两位
while (r - l > eps)
{
double mid = (l + r) / 2;
if (check(mid)) r = mid;
else l = mid;
}
return l;
}

位运算与常用库函数(C ++)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
                                       
位运算


符号 运算
& 与
| 或
~ 非
^ 异或
>> 右移 /2^k
<< 左移 * 2^k
常用操作:

求x的第k位数字 x >> k & 1
lowbit(x) = x & -x(~ a +1),返回x的最后一位1

2. 常用库函数

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
2.1 reverse翻转
翻转一个vector:

reverse(a.begin(), a.end());
翻转一个数组,元素存放在下标1 ~ n:

reverse(a + 1, a + n + 1);
2.2 unique去重
返回去重(只去掉相邻的相同元素)之后的尾迭代器(或指针),仍然为前闭后开,即这个迭代器是去重之后末尾元素的下一个位置。该函数常用于离散化,利用迭代器(或指针)的减法,可计算出去重后的元素个数。

把一个vector去重:

int m = unique(a.begin(), a.end()) – a.begin();
a.erase(unique(a.begin(), a.end()),a.end())
把一个数组去重,元素存放在下标0 ~ m:

int m = unique(a + 1, a + n + 1) – (a + 1);
2.3 random_shuffle随机打乱
用法与reverse相同。
Srand (time(0)); 随机种子 <ctime>头文件
2.4 sort
对两个迭代器(或指针)指定的部分进行快速排序(从小到大)。可以在第三个参数传入定义大小比较的函数,或者重载“小于号”运算符。

把一个int数组(元素存放在下标1 ~ n)从大到小排序,传入比较函数:

int a[MAX_SIZE];
bool cmp(int a, int b)
{
return a > b;
}
sort(a + 1, a + n + 1, cmp);

sort(a.begin(),a.end(),greater<int>())

把自定义的结构体vector排序,重载“小于号”运算符:

struct Rec
{
int x, y;
bool operator <(const Rec &t) const
{
return x < a.x;
}

};

vector<Rec> a;

bool operator <(const Rec &a, const Rec &b)
{
return a.x < b.x || a.x == b.x && a.y < b.y;
}

sort(a.begin(), a.end());
2.5 lower_bound/upper_bound 二分
lower_bound的第三个参数传入一个元素x,在两个迭代器(指针)指定的部分上执行二分查找,返回指向第一个大于等于x的元素的位置的迭代器(指针)。

upper_bound的用法和lower_bound大致相同,唯一的区别是查找第一个大于x的元素。当然,两个迭代器(指针)指定的部分应该是提前排好序的。

在有序int数组(元素存放在下标1 ~ n)中查找大于等于x的最小整数的下标:

int i = lower_bound(a + 1, a + 1 + n, x) - a;
在有序vector<int>中查找小于等于x的最大整数(假设一定存在):

int y = *--upper_bound(a.begin(), a.end(), x);

next_permutation(begin(),end()); (排序输出数组)

1. #include 倍增思想

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
vector是变长数组,支持随机访问,不支持在任意位置 O(1)O(1) 插入。为了保证效率,元素的增删一般应该在末尾进行。

1.1 声明
#include <vector> // 头文件
vector<int> a; // 相当于一个长度动态变化的int数组
vector<int> b[233]; // 相当于第一维长233,第二位长度动态变化的int数组
struct rec{…};
vector<rec> c; // 自定义的结构体类型也可以保存在vector中
1.2 size/empty
size函数返回vector的实际长度(包含的元素个数),empty函数返回一个bool类型,表明vector是否为空。二者的时间复杂度都是 O(1)O(1)。
所有的STL容器都支持这两个方法,含义也相同,之后我们就不再重复给出。

1.3 clear
clear函数把vector清空。

1.4 迭代器
迭代器就像STL容器的“指针”,可以用星号*操作符解除引用。

一个保存int的vector的迭代器声明方法为:

vector<int>::iterator it; //可以用auto
vector的迭代器是“随机访问迭代器”,可以把vector的迭代器与一个整数相加减,其行为和指针的移动类似。可以把vector的两个迭代器相减,其结果也和指针相减类似,得到两个迭代器对应下标之间的距离。

1.5 begin/end
begin函数返回指向vector中第一个元素的迭代器。例如a是一个非空的vector,则*a.begin()与a[0]的作用相同。

所有的容器都可以视作一个“前闭后开”的结构,end函数返回vector的尾部,即第n 个元素再往后的“边界”。*a.end()与a[n]都是越界访问,其中n = a.size()。

下面三份代码都遍历了vector<int> a,并输出它的所有元素。

for (int i = 0; i < a.size(); i ++)
cout << a[i] << endl;

for (vector<int>::iterator it = a.begin(); it != a.end(); it ++)
cout << *it << endl;

for (auto c : a) cout <<c <<” ”;

1.6 front/back
front函数返回vector的第一个元素,等价于*a.begin()和a[0]。
back函数返回vector的最后一个元素,等价于*--a.end()和a[a.size() – 1]。

1.7 push_back()和pop_back()
a.push_back(x)把元素x插入到vector a的尾部。
a.pop_back()删除vector a的最后一个元素。

2. #include

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
头文件queue主要包括循环队列queue和优先队列priority_queue两个容器。

2.1 声明
queue<int> q;
struct rec{…}; queue<rec> q; //结构体rec中必须定义符号
重载:
Struct rec{
Int a,b;
Bool operator < (const rec& t) const
{
Return a < t.a;
}
}
priority_queue<int> q; // 大根堆结构体重载小于号
priority_queue<int, vector<int>, greater<int>> q; // 小根堆结构体重载大于号
priority_queue<pair<int, int>>q;
2.2 循环队列queue
push // 从队尾插入
pop // 从队头弹出
front // 返回队头元素
back // 返回队尾元素
2.3 优先队列priority_queue
push // 把元素插入堆
pop // 删除堆顶元素(删除)
top // 查询堆顶元素(最大值)

要想清空 重新初始化 q =queue<int> ();

3. #include

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
头文件stack包含栈。声明和前面的容器类似。

push // 向栈顶插入
pop // 弹出栈顶元素
top / /最大(栈顶)
4. #include <deque>
双端队列deque是一个支持在两端高效插入或删除元素的连续线性存储空间。它就像是vector和queue的结合。与vector相比,deque在头部增删元素仅需要 O(1)O(1) 的时间;与queue相比,deque像数组一样支持随机访问。

[] // 随机访问
begin/end // 返回deque的头/尾迭代器
front/back // 队头/队尾元素
push_back // 从队尾入队
push_front // 从队头入队
pop_back // 从队尾出队
pop_front // 从队头出队
clear // 清空队列

5. #include

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
头文件set主要包括set和multiset两个容器,分别是“有序集合”和“有序多重集合”,即前者的元素不能重复,而后者可以包含若干个相等的元素。set和multiset的内部实现是一棵红黑树,它们支持的函数基本相同。

5.1 声明
set<int> s; //元素不能重复
struct rec{…}; set<rec> s; // 结构体rec中必重载小于号
multiset<double> s; // 元素可以重复
5.2 size/empty/clear
与vector类似

5.3 迭代器
set和multiset的迭代器称为“双向访问迭代器”,不支持“随机访问”,支持星号*解除引用,仅支持++和--两个与算术相关的操作。

设it是一个迭代器,例如set<int>::iterator it;

若把it ++,则it会指向“下一个”元素。这里的“下一个”元素是指在元素从小到大排序的结果中,排在it下一名的元素。同理,若把it --,则it将会指向排在“上一个”的元素。

5.4 begin/end
返回集合的首、尾迭代器,时间复杂度均为 O(1)O(1)。

s.begin()是指向集合中最小元素的迭代器。

s.end()是指向集合中最大元素的下一个位置的迭代器。换言之,就像vector一样,是一个“前闭后开”的形式。因此-- s.end()是指向集合中最大元素的迭代器。

5.5 insert
s.insert(x)把一个元素x插入到集合s中,时间复杂度为 O(logn)O(logn)。

在set中,若元素已存在,则不会重复插入该元素,对集合的状态无影响。

5.6 find
s.find(x)在集合s中查找等于x的元素,并返回指向该元素的迭代器。若不存在,则返回s.end()。时间复杂度为 O(logn)O(logn)。

5.7 lower_bound/upper_bound
这两个函数的用法与find类似,但查找的条件略有不同,时间复杂度为 O(logn)O(logn)。

s.lower_bound(x)查找大于等于x的元素中最小的一个,并返回指向该元素的迭代器。

s.upper_bound(x)查找大于x的元素中最小的一个,并返回指向该元素的迭代器。

5.8 erase
设it是一个迭代器,s.erase(it)从s中删除迭代器it指向的元素,时间复杂度为 O(logn)O(logn)。

设x是一个元素,s.erase(x)从s中删除所有等于x的元素,时间复杂度为 O(k+logn)O(k+logn),其中 kk 是被删除的元素个数。

5.9 count
s.count(x)返回集合s中等于x的元素个数,时间复杂度为 O(k+logn)O(k+logn),其中 kk 为元素x的个数。

6. #include

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
map容器是一个键值 对key-value的映射,其内部实现是一棵以key为关键码的红黑树。Map的key和value可以是任意类型,其中key必须定义小于号运算符。

6.1 声明
map<key_type, value_type> name;

//例如:
map<long, long, bool> vis;
map<string, int> hash;
map<pair<int, int>, vector<int>> test;
6.2 size/empty/clear/begin/end
均与set类似。

6.3 insert/era se
与set类似,但其参数均是pair<key_type, value_type>。

6.4 find
h.find(x)在变量名为h的map中查找key为x的二元组。

6.5 []操作符
h[key]返回key映射的value的引用,时间复杂度为 O(logn)O(logn)。

[]操作符是map最吸引人的地方。我们可以很方便地通过h[key]来得到key对应的value,还可以对h[key]进行赋值操作,改变key对应的value。
1
2
3
4
5
6
7
Unordered_set<int> a;//哈希表,不能存储元素
Unordered_multiset <int> b; 哈希表,能存储元素

Unordered_map<int,int> c; //效率高 不支持二分


Bitset<1000> a,b; //支持运算;

ACWing 777 字符串乘方

1.由若干个重复而成 即为找出 字符串s的最小重复子数列
2.从s的第一位开始至最后慢慢加成一个新版的字符串s1 ,若 s.size()/s1.size() 为整数 且 s1* s.size()/s1.size() == s
3.个数n为 s.size() / 最小重复子数列.size()

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
#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

int main()
{
string s;
while (getline (cin,s))
{
if (s == ".") break;
string output = "";
for (int i = 0 ; s[i] ; i ++)
{
output += s[i];
string s1 = "";
for (int j = 0;j < s.size() / output.size();j ++)
{
s1 += output;
}
if (s1 == s) break;
}
cout << s.size() / output.size() <<endl;
}
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
输入整数 N,输出一个 N 阶的回字形二维数组。

数组的最外层为 1,次外层为 2,以此类推。

输入格式
输入包含多行,每行包含一个整数 N。

当输入行为 N=0 时,表示输入结束,且该行无需作任何处理。

输出格式
对于每个输入整数 N,输出一个满足要求的 N 阶二维数组。

每个数组占 N 行,每行包含 N 个用空格隔开的整数。

每个数组输出完毕后,输出一个空行。

数据范围
0≤N≤100

输入样例:
1
2
3
4
5
0
输出样例:
1

1 1
1 1

1 1 1
1 2 1
1 1 1

1 1 1 1
1 2 2 1
1 2 2 1
1 1 1 1

1 1 1 1 1
1 2 2 2 1
1 2 3 2 1
1 2 2 2 1
1 1 1 1 1

解题思路:

解法一(找规律 层层递进法)

// 这个方法的优点在于不用考虑奇偶,但是循环层数较多(三重循环),对思维的要求有一点偏高
①通过观察矩阵 我们发现层数为:(N + 1) / 2.
②我们不妨先将全部的数填充成初始值1,再去把去最外层的 (n-2)*(n-2)的矩阵全部填充为2,如此层层递进
③设最外层为第一层,层数循环 用i表示 我们发现 每次填充的数为 i ,填充矩阵开始位置为0+i-1 结束位置为 n + 1 -i
④填充完毕后再将 数组 有序输出

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
#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

int main()
{
for (int i = 1; i <= 100; i ++ )
{
int n;
cin >> n;
if (n == 0) break;
int Z[n][n];
for (int i = 1; i <= (n + 1) / 2; i ++ )
{
for (int j = 0 + i - 1; j < n + 1 -i; j ++ )
{
for (int k = 0+ i- 1; k < n + 1 -i; k ++ )
{
Z[j]k] = i;
}
}
}
for (int i = 0; i < n; i ++ )
{
for (int j = 0; j < n; j ++ )
{
cout << Z[i][j] << " ";
}
cout << endl;
}
cout << endl;
}
return 0;
}

作者:bearyuc
链接:https://www.acwing.com/activity/content/code/content/4512502/
来源:AcWing

解法二(图像翻转去重法)

①通过观察回字形矩阵, 矩阵关于对角线是左上方和右下方对称的
②利用二维行列循环, 获取行列+1的最小值(即min(i + 1, j + 1)), 可得如下图形(例如n == 4):
1 1 1 1
1 2 2 2
1 2 3 3
1 2 3 4
可以看出未划横线部分(左上部分)满足题解,此时如果使图像沿着对角线翻转,再重合,即可求解答案
③翻转图像,采用min(n - i, n - j)即可, 得到图像如下(例如n == 4):
4 3 2 1
3 3 2 1
2 2 2 1
1 1 1 1
④进行图像的重合, 对应位置取最小值即可求解min(Left上, right下)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include <iostream>
#include <cstring>
#include <cmath>

using namespace std;


int main(){
int n;

while (cin >> n, n){

for (int i = 0; i < n; i ++){
for(int j = 0; j < n; j ++){
cout << min(min(i + 1, j + 1), min(n - i, n - j)) << " ";
}
cout << endl ;
}
cout << endl;
}

return 0;
}

解法三(曼哈顿距离法)

值得一提的是也是我本人最喜欢的解法(唯一一点不好的是需要分奇偶讨论)

①当n为奇数时, 找取中间点n / 2分别于行i列j的距离的最大值(max(abs(n / 2 - i), abs(n / 2 - j))),可以的如下图形(例如n == 5):
2 2 2 2 2
2 1 1 1 2
2 1 0 1 2
2 1 1 1 2
2 2 2 2 2
②观察结果, 随着回形越深入,内外围回形相差为1, 因此想到 (n + 1) / 2
③当n为偶数时,采用同样的方法, 这里我们就让中心点在图形的中间位置 (n + 1) / 2.0 (不存在数值的中间位置,所以要用浮点数), 再求解其分别于行i列j的距离的最大值(max(abs((n - 1) / 2.0 - i), abs((n - 1) / 2.0 - j)))

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
#include <iostream>
#include <cstring>
#include <cmath>

using namespace std;

int main(){
int n;
while(cin >> n, n ) // 条件语句等价于 输入的n == 0的话退出while 循环
{
for (int i = 0; i < n; i ++){
for (int j = 0; j < n; j ++){
if (n % 2)
cout << (n + 1) / 2 - max(abs(n / 2 - i), abs(n / 2 - j)) << ' ';
else
cout << (n + 1) / 2.0 - max(abs((n - 1) / 2.0 - i), abs((n - 1) / 2.0 - j)) << ' ';
}
cout << endl;
}

cout << endl;
}

return 0;
}

解法四(利用蛇形矩阵求解)

由于要用到数组 不建议初学语法课的同学们看,建议学完算法提高课回头再来看看
此解法也非出自本人之手 代码末会注明出处
①设置一个计数器统计方向改变次数
②设置变量res表示回形当前圈数
③其他部分与蛇形矩阵相同

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
#include <iostream>
#include <cstring>
#include <cmath>

using namespace std;

const int N = 100 + 10;
int m[N][N];

int main(){
int n;
int dx[] = {-1, 0, 1, 0}, dy[] = {0, 1, 0, -1};

while(cin >> n, n ){
memset(m, 0, sizeof m);
int d = 1, x = 0, y = 0;
int cnt = 0; // 表示改变方向次数
int res = 1; // 回形当前圈数
for (int i = 0; i < n * n; i ++){
int a = x + dx[d], b = y + dy[d];
m[x][y] = res;

if (a < 0 || a >= n || b < 0 || b >= n || m[a][b]){
d = (d + 1) % 4;
a = x + dx[d], b = y + dy[d];
cnt ++;
if (!(cnt % 4)) res ++;
}
x = a, y = b;
}

for (int i = 0; i < n; i ++){
for (int j = 0; j < n; j ++)
cout << m[i][j] << ' ';
cout << endl;
}
cout << endl;
}

return 0;
}

作者:Chuckie
链接:https://www.acwing.com/solution/content/71619/
来源:AcWing

多种解法,参考y总和大佬们的见解加上本人的思路而来,如有错误,请多指教,我会第一时间更正。