数据结构与算法

OI赛制必备对拍！！！

参考标程：

cpp

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 1010;

int n, m;
int f[N];

int main() {
    freopen("input.txt", "r", stdin);
    freopen("DP.txt", "w", stdout);

    cin >> n >> m;

    for (int i = 1; i <= n; i++) {
        int v, w;
        cin >> v >> w;
        for (int j = m; j >= v; j--)
            f[j] = max(f[j], f[j - v] + w);
    }

    cout << f[m] << endl;
    return 0;

}

参考暴力写法

cpp

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 1010;

int n, m;
int v[N], w[N];
int ans;

void dfs(int u, int sum, int value) {
    if (u == n) ans = max(ans, value);
    else {
        dfs(u + 1, sum, value);

        if (sum + v[u] <= m)
            dfs(u + 1, sum + v[u], value + w[u]);
    }

}

int main() {
    freopen("input.txt", "r", stdin);
    freopen("DFS.txt", "w", stdout);

    cin >> n >> m;

    for (int i = 0; i < n; i++) cin >> v[i] >> w[i];

    dfs(0, 0, 0);

    cout << ans << endl;
    return 0;

}

参考数据生成器

cpp

#include <iostream>
#include <cstring>
#include <algorithm>
#include <fstream>
#include <ctime>

using namespace std;

void create_dataset() {
    ofstream fout("input.txt");

    int n = rand() % 20 + 1, m = rand() % 1001;

    fout << n << ' ' << m << endl;

    for (int i = 0; i < n; i++) {
        int v = rand() % 1001, w = rand() % 1001;
        fout << v << ' ' << w << endl;
    }

    fout.close();

}

bool work() {
    create_dataset();

    system("DP.exe");
    system("DFS.exe");

    return !system("fc DP.txt DFS.txt");

}

int main() {
        srand(time(0));

    for (int i = 0; i < 100000; i++) {
        if (!work()) break;
    }

    return 0;

}

数据结构

用 new 开数组时间太慢，故在算法题中不适用

数组模拟链表

单链表

应用

存储图
存储树

实现一个单链表，链表初始为空，支持三种操作：

(1) 向链表头插入一个数；

(2) 删除第k个插入的数后面的数；

(3) 在第k个插入的数后插入一个数

现在要对该链表进行M次操作，进行完所有操作后，从头到尾输出整个链表。

注意:题目中第k个插入的数·并不是指当前链表的第k个数。例如操作过程中一共插入了n个数，则按照插入的时间顺序，这n个数依次为：第1个插入的数，第2个插入的数，…第n个插入的数。

输入格式：

第一行包含整数M，表示操作次数。

接下来M行，每行包含一个操作命令，操作命令可能为以下几种：

(1) “H x”，表示向链表头插入一个数x。

(2) “D k”，表示删除第k个插入的数后面的数（当k为0时，表示删除头结点）。

(3) “I k x”，表示在第k个插入的数后面插入一个数x（此操作中k均大于0）。

输出格式：

共一行，将整个链表从头到尾输出。

数据范围：

1≤M≤1000001≤M≤100000 所有操作保证合法。

输入样例：

cpp

输出样例：

cpp

6 4 6 5

代码：

cpp

#include<iostream>
#include<vector>
#include<cstdio>

using namespace std;
const int N = 100010;
int ne[N] = {-1}, //存next指针
e[N],//存值
idx,//当前节点
head;//头节点
int n;

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

void add_to_head(int k) {
    e[idx] = k;//当前节点赋值为k
    ne[idx] = head;//令当前节点的next指针指向头指针
    head = idx++;//头指针指向当前节点
}

void add(int k, int x) {
    e[idx] = x;//当前节点赋值为x
    ne[idx] = ne[k];//当前节点的next指针指向k的下一位
    ne[k] = idx++;//k点next指针指向当前节点的下一位
}

void remove(int k) {
    ne[k] = ne[ne[k]];
    //k->next = k->next->next
}

int main() {
    cin >> n;
    char cos;
    int k, h;
    init();
    while (n--) {
        cin >> cos;
        if (cos == 'H') {
            cin >> k;
            add_to_head(k);
        } else if (cos == 'D') {
            cin >> k;
            if (!k)head = ne[head];
            remove(k - 1);
        } else {
            cin >> k >> h;
            add(k - 1, h);
        }
    }
    for (int i = head; i != -1; i = ne[i]) {
        cout << e[i] << " ";
    }
    return 0;
}

双链表

应用

对问题进行优化

实现一个双链表，双链表初始为空，支持 5 种操作：

在最左侧插入一个数；
在最右侧插入一个数；
将第 k 个插入的数删除；
在第 k 个插入的数左侧插入一个数；
在第 k 个插入的数右侧插入一个数

现在要对该链表进行 MM 次操作，进行完所有操作后，从左到右输出整个链表。

注意： 题目中第 k 个插入的数并不是指当前链表的第 k 个数。例如操作过程中一共插入了 n 个数，则按照插入的时间顺序，这 n 个数依次为：第 1 个插入的数，第 2 个插入的数，…第 n 个插入的数。

输入格式：

第一行包含整数 M，表示操作次数。

接下来 M 行，每行包含一个操作命令，操作命令可能为以下几种：

L x，表示在链表的最左端插入数 x。
R x，表示在链表的最右端插入数 x。
D k，表示将第 k 个插入的数删除。
IL k x，表示在第 k 个插入的数左侧插入一个数。
IR k x，表示在第 k 个插入的数右侧插入一个数。

输出格式：

共一行，将整个链表从左到右输出。

数据范围：

1≤M≤100000 所有操作保证合法。

输入样例：

10
R 7
D 1
L 3
IL 2 10
D 3
IL 2 7
L 8
R 9
IL 4 7
IR 2 2

输出样例：

cpp

8 7 7 3 2 9

代码：

cpp

#include <iostream>

int m, n, index, v;
const int N = 100010;
int e[N], l[N], r[N];

using namespace std;

void init() {
    r[0] = 1;
    l[1] = 0;
    index = 2;
}

void insert(int k, int x) {
    e[index] = x;
    l[index] = k;
    r[index] = r[k];
    l[r[k]] = index;
    r[k] = index++;
}

void eraseK(int k) {
    l[r[k]] = l[k];
    r[l[k]] = r[k];
}

int main() {
    init();
    cin >> m;
    string c;
    while (m--) {
        cin >> c;
        if (c == "R") {
            cin >> v;
            insert(l[1], v);
        } else if (c == "D") {
            cin >> n;
            eraseK(n + 1);
        } else if (c == "L") {
            cin >> v;
            insert(0, v);
        } else if (c == "IL") {
            cin >> n >> v;
            insert(l[n + 1], v);
        } else if (c == "IR") {
            cin >> n >> v;
            insert(n + 1, v);
        }
    }
    for (int i = r[0]; i != 1; i = r[i]) {
        cout << e[i] << " ";
    }
    return 0;
}

并查集

给定 n 个由小写字母构成的字符串。

现在，请你对它们进行归类。

对于两个字符串 a 和 b：

如果至少存在一个字母在 a 和 b 中同时出现，则 a 和 b 属于同一类字符串。
如果字符串 c 既与字符串 a 同类，又与字符串 b 同类，则 a 和 b 属于同一类字符串。

请问，最终所有字符串被划分为多少类。

输入格式

第一行包含整数 n。

接下来 n 行，每行包含一个仅由小写字母构成的字符串。

注意，输入字符串可能相同。

输出格式

一个整数，表示最终所有字符串被划分为的类的数量。

数据范围

前 6 个测试点满足 1≤n≤10。所有测试点满足 1≤n≤2×10⁵，输入字符串的长度范围 [1,50]，所有输入字符串的总长度范围 [1,10⁶] ，所有字符串均由小写英文字母构成。

输入样例1：

4
a
b
ab
d

输出样例1：

输入样例2：

3
ab
bc
abc

输出样例2：

输入样例3：

1
abcdefghijklmn

输出样例3：

cpp

思路：

st数组标记字符是否出现过，利用并查集进行归类

代码：

cpp

#include<iostream>

using namespace std;
const int N = 27;
int n, res, p[N];
bool st[N];

int find(int x) {
    if (x != p[x]) p[x] = find(p[x]);
    return p[x];
}

int main() {
    cin >> n;
    string s;
    for (int i = 0; i < N; ++i) p[i] = i;
    for (int i = 0; i < n; ++i) {
        cin >> s;
        int t = find(s[0] - 'a');
        st[s[0] - 'a'] = true;
        for (int j = 1; j < s.length(); ++j) {
            p[find(s[j] - 'a')] = t;
            st[s[j] - 'a'] = true;
        }
    }
    for (int i = 0; i < N; ++i)
        // 出现过的每一类都只有一个成员满足p[i] == i
        if (st[i] && p[i] == i)
            res++;
    cout << res << endl;
    return 0;
}

树状数组与线段树

树状数组

适用问题

某个位置上的数加上一个数
求某一个前缀和

cpp

c[x] = (x - lowbit(x), x] = (x - 2^k, x]
//c[x]的值为这个左开右闭区间的元素和, k为x的二进制表示中末尾0的个数, 即c[x]在树状数组中的层数

常用操作及其相应函数

某个位置上的数加上一个数

cpp

void add(int x, int v) {
    for (int i = x; i <= n; i += lowbit(i)) tr[i] += v;
}

求某一个前缀和

cpp

int query(int x) {
    int res = 0;
    for (int i = x; i > 0; i -= lowbit(i)) res += tr[i];
    return res;
}

给定 n 个数组成的一个数列，规定有两种操作，一是修改某个元素，二是求子数列 [a,b] 的连续和。

输入格式：

第一行包含两个整数 n 和 m，分别表示数的个数和操作次数。

第二行包含 n 个整数，表示完整数列。

接下来 m 行，每行包含三个整数 k,a,b（ k=0，表示求子数列[a,b][a,b]的和；k=1，表示第 a 个数加 b）。

数列从 1 开始计数。

输出格式：

输出若干行数字，表示 k=0 时，对应的子数列 [a,b][a,b] 的连续和。

数据范围：

1≤n≤100000,

1≤m≤100000,

1≤a≤b≤n

输入样例：

cpp

10 5
1 2 3 4 5 6 7 8 9 10
1 1 5
0 1 3
0 4 8
1 7 5
0 4 8

输出样例：

cpp

11
30
35

代码：

cpp

#include <iostream>

using namespace std;
int n, m;
const int N = 100010;
int a[N], tr[N];

int lowbit(int x) {
    return x & -x;
}

void add(int x, int v) {
    for (int i = x; i <= n; i += lowbit(i)) tr[i] += v;
}

int query(int x) {
    int res = 0;
    for (int i = x; i > 0; i -= lowbit(i)) res += tr[i];
    return res;
}

int main() {
    cin >> n >> m;
    for (int i = 1; i <= n; ++i) cin >> a[i];
    for (int i = 1; i <= n; ++i) add(i, a[i]);
    int c, x, y;
    for (int i = 0; i < m; ++i) {
        cin >> c >> x >> y;
        if (c) add(x, y);
        else cout << query(y) - query(x - 1) << endl;
    }
    return 0;
}

有 n 头奶牛，已知它们的身高为 1∼n 且各不相同，但不知道每头奶牛的具体身高。

现在这 n 头奶牛站成一列，已知第 i 头牛前面有 A_i 头牛比它低，求每头奶牛的身高。

输入格式

第 1 行：输入整数 n。

第 2..n 行：每行输入一个整数 A_i，第 i 行表示第 i 头牛前面有 A_i 头牛比它低。（注意：因为第 1 头牛前面没有牛，所以并没有将它列出）

输出格式

输出包含 n 行，每行输出一个整数表示牛的身高。

第 i 行输出第 i 头牛的身高。

数据范围 1≤n≤10⁵

输入样例：

cpp

输出样例：

cpp

思路：

tr数组的前缀和表示当前位置是第几大的数

代码：

cpp

#include<iostream>

using namespace std;

const int N = 100010;
int n, res, h[N], ans[N], tr[N];

int lowbit(int x) {
    return x & -x;
}

void add(int x, int c) {
    for (int i = c; i <= n; i += lowbit(i)) tr[i] += x;
}
// tr数组的前缀和表示当前位置是第几大的数
int sum(int x) {
    int res = 0;
    for (int i = x; i; i -= lowbit(i)) res += tr[i];
    return res;
}

int main() {
    cin >> n;
    for (int i = 2; i <= n; ++i) cin >> h[i];
    for (int i = 1; i <= n; ++i) tr[i] = lowbit(i); // add( i, 1)
    for (int i = n; i; --i) {
        int k = h[i] + 1;
        int l = 1, r = n;
        while (l < r) {
            int mid = (l + r) >> 1;
            if (sum(mid) >= k) r = mid;
            else l = mid + 1;
        }
        ans[i] = r;
        add(-1, r);  // 将该数删去
    }
    for (int i = 1; i <= n; ++i) cout << ans[i] << endl;
    return 0;
}

线段树

cpp

const int N = 100010;
int w[N];
struct Node {
    int l, r;
    int sum;
} tr[N * 4];

常用操作

单点修改
区间查询

常用函数

用子节点信息更新当前节点信息

cpp

void pushup(int u) {
    tr[u].sum = tr[u << 1].sum + tr[u << 1 | 1].sum;
}

在一段区间上初始化线段树

cpp

void build(int u, int l, int r) {
   if (l == r)tr[u] = {l, r, w[r]};
   else {
       tr[u] = {l, r};
       int mid = (l + r) >> 1;
       build(u << 1, l, mid), build(u << 1 | 1, mid + 1, r);
       pushup(u);
   }
}

修改

cpp

void modify(int u, int x, int v) {
    if (tr[u].l == tr[u].r)tr[u].sum += v;
    else {
        int mid = (tr[u].l + tr[u].r) >> 1;
        if (x <= mid)modify(u << 1, x, v);
        else modify(u << 1 | 1, x, v);
        pushup(u);
    }
}

查询

cpp

int query(int u, int l, int r) {
    if (tr[u].l >= l && tr[u].r <= r)return tr[u].sum;
    int mid = (tr[u].l + tr[u].r) >> 1;
    int sum = 0;
    if (l <= mid)sum += query(u << 1, l, r);
    if (r > mid)sum += query(u << 1 | 1, l, r);
    return sum;
}

输入一串数字，给你 M 个询问，每次询问就给你两个数字 X,Y，要求你说出 X 到 Y 这段区间内的最大数。

输入格式：

第一行两个整数 N,M 表示数字的个数和要询问的次数；

接下来一行为 N 个数；

接下来 M 行，每行都有两个整数 X,Y。

输出格式：

输出共 M 行，每行输出一个数。

数据范围：

1≤N≤105,

1≤M≤106,

1≤X≤Y≤N,

数列中的数字均不超过 2³¹−1

输入样例：

cpp

10 2
3 2 4 5 6 8 1 2 9 7
1 4
3 8

输出样例：

cpp

5
8

代码：

cpp

#include<iostream>
#include<cstdio>

using namespace std;
int n, m;
const int N = 100010;
int w[N];
struct Node {
    int l, r;
    int maxv;
} tr[N * 4];

void pushup(int u) {
    tr[u].maxv = max(tr[u << 1].maxv, tr[u << 1 | 1].maxv);
}

void build(int u, int l, int r) {
    if (l == r)tr[u] = {l, r, w[r]};
    else {
        tr[u] = {l, r};
        int mid = (l + r) >> 1;
        build(u << 1, l, mid), build(u << 1 | 1, mid + 1, r);
        pushup(u);
    }
}

int query(int u, int l, int r) {
    if (tr[u].l >= l && tr[u].r <= r)return tr[u].maxv;
    int mid = (tr[u].l + tr[u].r) >> 1;
    int mmax = 0;
    if (l <= mid)mmax = query(u << 1, l, r);
    if (r > mid)mmax = max(mmax, query(u << 1 | 1, l, r));
    return mmax;
}

int main() {
    cin >> n >> m;
    for (int i = 1; i <= n; ++i)scanf("%d", &w[i]);
    build(1, 1, n);
    int l, r;
    while (m--) {
        scanf("%d%d", &l, &r);
        printf("%d\n", query(1, l, r));
    }
    return 0;
}

哈希表

<big>841. 字符串哈希 </big>

给定一个长度为 n 的字符串，再给定 m 个询问，每个询问包含四个整数 l1,r1,l2,r2，请你判断 [l1,r1] 和 [l2,r2] 这两个区间所包含的字符串子串是否完全相同。

字符串中只包含大小写英文字母和数字。

输入格式

第一行包含整数 n 和 m，表示字符串长度和询问次数。

第二行包含一个长度为 n 的字符串，字符串中只包含大小写英文字母和数字。

接下来 m 行，每行包含四个整数 l1,r1,l2,r2，表示一次询问所涉及的两个区间。

注意，字符串的位置从 1 开始编号。

输出格式

对于每个询问输出一个结果，如果两个字符串子串完全相同则输出 Yes，否则输出 No。

每个结果占一行。

数据范围

1≤n,m≤10⁵

输入样例：

8 3
aabbaabb
1 3 5 7
1 3 6 8
1 2 1 2

输出样例：

Yes
No
Yes

思路：

p[i]表示P的i次方,

区间和公式的理解: "abcde "与 "abc"的前三个字符值是一样，只差两位.

乘上 p[2] 把 "abc" 变为 "abc00"，再用 "abcde" - "abc00" 便可得到 "de"的哈希值

代码：

cpp

#include<iostream>
#include <cstdio>

using namespace std;
typedef unsigned long long ULL;
//当存储的数据大于unsigned long long的存储范围时，会自动mod 2^64^?1，就不用mod其他质数来保证唯一性了。
const int N = 100010, P = 131;
//P必须是质数，经验值：131，13331
char str[N];
ULL h[N], p[N];

ULL get(int l, int r) {
    return h[r] - h[l - 1] * p[r - l + 1];
}

int main() {
    int n, m;
    scanf("%d%d%s", &n, &m, str + 1);
    //字符不能映射成0
    p[0] = 1;
    for (int i = 1; i <= n; ++i) {
        p[i] = p[i - 1] * P;
        h[i] = h[i - 1] * P + str[i];
    }
    int x, y, l, r;
    while (m--) {
        cin >> x >> y >> l >> r;
        if (get(x, y) == get(l, r))
            cout << "Yes" << endl;
        else
            cout << "No" << endl;
    }
    return 0;
}

堆

手写堆操作

插入一个数 heap[++size] = x; up(size);
求集合中最小数 heap[1];
删除最小数 heap[1] = heap(size); size --; down(1);
删除任一元素 heap[k] = heap(size); size --; down(k); up(k);
修改任一元素 heap[k] = x; down(k); up(k);

输入一个长度为 n 的整数数列，从小到大输出前 m 小的数。

输入格式

第一行包含整数 n 和 m。

第二行包含 n 个整数，表示整数数列。

输出格式

共一行，包含 m 个整数，表示整数数列中前 m 小的数。

数据范围

1≤m≤n≤10⁵， 1≤数列中元素≤10⁹

输入样例：

5 3
4 5 1 3 2

输出样例：

cpp

1 2 3

思路：

只需down函数即可完成

代码：

cpp

#include<iostream>

using namespace std;
const int N = 1e5 + 10;
int m;
int h[N], sz;

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

int main() {
    cin >> sz >> m;
    for (int i = 1; i <= sz; ++i) cin >> h[i];
    for (int i = sz / 2; i > 0; --i) down(i);
    while (m--) {
        cout << h[1] << " ";
        h[1] = h[sz];
        sz--;
        down(1);
    }
    return 0;
}

KMP

给定一个模式串 S，以及一个模板串 P，所有字符串中只包含大小写英文字母以及阿拉伯数字。

模板串 P 在模式串 S 中多次作为子串出现。

求出模板串 P 在模式串 S 中所有出现的位置的起始下标。

输入格式

第一行输入整数 N，表示字符串 P 的长度。

第二行输入字符串 P。

第三行输入整数 M，表示字符串 S 的长度。

第四行输入字符串 S。

输出格式

共一行，输出所有出现位置的起始下标（下标从 00 开始计数），整数之间用空格隔开。

数据范围

1≤N≤10⁵ 1≤M≤10⁶

输入样例：

3
aba
5
ababa

输出样例：

0 2

思路：

ne[i]表示以i为终点的后缀和从1开始的前缀相等的最长长度 ne[i] = j => p[1,j] = p[i-j+1,i]

代码：

cpp

#include <iostream>

using namespace std;
const int N = 1010, M = 100010;
char p[N], s[M];
int ne[N];
int m, n, k, t;

int main() {
    cin >> n >> (p + 1) >> m >> (s + 1);
    for (int i = 2, j = 0; i <= n; ++i) {
        while (j && s[i] != p[j + 1])
            j = ne[j];
        if (p[i] == p[j + 1])
            j++;
        ne[i] = j;
    }
    for (int i = 1, j = 0; i <= m; ++i) {
        while (j && s[i] != p[j + 1])
            j = ne[j];
        if (s[i] == p[j + 1])
            j++;
        if (j == n) {
            cout << i - m + 1 << " ";
            j = ne[j];
        }
    }
    return 0;
}

算法

枚举、模拟与排序

高精度

高精度加法

cpp

//加法				大整数a			大整数b
vector<int> add(vector<int> &a, vector<int> &b) {
    int temp = 0;
    vector<int> res;
    for (int i = 0; i < a.size() || i < b.size(); ++i) {
        if (i < a.size())temp += a[i];
        if (i < b.size())temp += b[i];
        res.push_back(temp % 10);
        temp /= 10;
    }
    //最后一个进位
    if (temp)res.push_back(temp);
    return res;
}

高精度减法

cpp

//判断a，b大小
bool cmp(vector<int> &a, vector<int> &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 true;
}
//减法				大整数a		大整数b
vector<int> sub(vector<int> &a, vector<int> &b) {
    if (!cmp(a, b)) {
        cout << "-";
        return sub(b, a);
    }
    vector<int> res;
    int temp = 0;
    for (int i = 0; i < a.size(); ++i) {
        if (i < b.size())temp += b[i];
        temp = a[i] - temp;
        res.push_back((temp + 10) % 10);
        if (temp < 0)temp = 1;
        else temp = 0;
    }
    //去除前导零
    while (res.size() > 1 && !res.back())res.pop_back();
    return res;
}

高精度乘法

cpp

//乘法  			  大整数a		 整数b
vector<int> mul(vector<int> &a, int b) {
    int temp = 0;
    vector<int> res;
    for (int i = 0; i < a.size() || temp; ++i) {
        if (i < a.size())
            temp += a[i] * b;
        res.push_back(temp % 10);
        temp /= 10;
    }
    //去除前导零
    while (res.back() == 0 && res.size() > 1)res.pop_back();
    return res;
}

高精度除法

cpp

//除法			大整数a		整数b		余数r
vector<int> div(vector<int> &a, int b, int &r) {
    int temp = 0;
    vector<int> res;
    //倒着运算 
    for (int i = a.size() - 1; i >= 0; --i) {
        temp *= 10;
        temp += a[i];
        res.push_back(temp / b);
        temp %= b;
    }
    //运算后反转
    reverse(res.begin(), res.end());
    //去除前导零
    while (res.back() == 0 && res.size() > 1)res.pop_back();
    r = temp;
    return res;
}

给定三个整数数组

A=[A1,A2,…AN]

B=[B1,B2,…BN]

C=[C1,C2,…CN]

请你统计有多少个三元组 (i,j,k)满足：

1 ≤ i , j , k ≤ N
Ai < Bj < Ck

输入格式：

第一行包含一个整数 N。

第二行包含 N 个整数 A1,A2,…AN。

第三行包含 N 个整数 B1,B2,…BN。

第四行包含 N 个整数 C1,C2,…CN。

输出格式：

一个整数表示答案。

数据范围：

1 ≤ N ≤ 10⁵, 0≤ Ai , Bi , Ci ≤ 10⁵

输入样例：

cpp

输出样例：

cpp

思路：

求数组 a 中比 b[ i ] 小的数的个数和数组 c 中比 b[ i ] 大的数的个数。

代码：

cpp

#include<iostream>
#include<cstdio>
#include<cstring>

using namespace std;
const int N = 100010;
int n;
int a[N], b[N], c[N], as[N], cs[N];
int cnt[N], s[N];

int main() {
    scanf("%d", &n);
    for (int i = 0; i < n; i++) scanf("%d", &a[i]), a[i]++;
    for (int i = 0; i < n; i++) scanf("%d", &b[i]), b[i]++;
    for (int i = 0; i < n; i++) scanf("%d", &c[i]), c[i]++;
    //求as[i]
    for (int i = 0; i < n; i++) cnt[a[i]]++;
    for (int i = 1; i < N; i++) s[i] = s[i - 1] + cnt[i];//cnt前缀和
    for (int i = 0; i < n; i++) as[i] = s[b[i] - 1];     //a中有多少比b[i]小的
    //求cs[i]
    memset(cnt, 0, sizeof cnt);
    memset(s, 0, sizeof s);
    for (int i = 0; i < n; i++) cnt[c[i]]++;
    for (int i = 1; i < N; i++) s[i] = s[i - 1] + cnt[i];//cnt前缀和
    for (int i = 0; i < n; i++) cs[i] = s[N - 1] - s[b[i]];     //a中有多少比b[i]小的
    long long ans = 0;
    for (int i = 0; i < n; i++) ans += (long long) as[i] * cs[i];
    cout << ans << endl;
    return 0;
}

递归与递推

递归

从 1~n 这 n 个整数中随机选出 m 个，输出所有可能的选择方案。

输入格式：

两个整数 n,m 在同一行用空格隔开。

输出格式：

按照从小到大的顺序输出所有方案，每行1个。

首先，同一行内的数升序排列，相邻两个数用一个空格隔开。

其次，对于两个不同的行，对应下标的数一一比较，字典序较小的排在前面（例如 1 3 5 7 排在 1 3 6 8 前面）。

数据范围：

n > 0 ,

0 ≤ m ≤ n ,

n + ( n − m ) ≤ 25

输入样例：

cpp

5 3

输出样例：

cpp

代码：

cpp

#include<iostream>

using namespace std;
int m, n;

void dfs(int t, int u, int state) {
    if (u + n < m + t)return;
    if (u == m) {
        for (int i = 0; i < n; i++) {
            if (state >> i & 1)
                cout << i + 1 << " ";
        }
        cout << endl;
        return;
    }
    dfs(t + 1, u + 1, state | 1 << t);
    dfs(t + 1, u, state);
}

int main() {
    cin >> n >> m;
    dfs(0, 0, 0);
    return 0;
}

递推

你玩过“拉灯”游戏吗？25 盏灯排成一个 5x5 的方形。每一个灯都有一个开关，游戏者可以改变它的状态。每一步，游戏者可以改变某一个灯的状态。游戏者改变一个灯的状态会产生连锁反应：和这个灯上下左右相邻的灯也要相应地改变其状态。

我们用数字“1”表示一盏开着的灯，用数字“0”表示关着的灯。下面这种状态

cpp

在改变了最左上角的灯的状态后将变成：

cpp

再改变它正中间的灯后状态将变成：

cpp

给定一些游戏的初始状态，编写程序判断游戏者是否可能在6步以内使所有的灯都变亮。

输入格式：

第一行输入正整数 n，代表数据中共有 n 个待解决的游戏初始状态。

以下若干行数据分为 n 组，每组数据有 5 行，每行 5 个字符。每组数据描述了一个游戏的初始状态。各组数据间用一个空行分隔。

输出格式：

一共输出 n 行数据，每行有一个小于等于 6 的整数，它表示对于输入数据中对应的游戏状态最少需要几步才能使所有灯变亮。

对于某一个游戏初始状态，若6步以内无法使所有灯变亮，则输出“-1”。

数据范围：

0 < n ≤ 500

输入样例：

cpp

输出样例：

cpp

3
2
-1

代码：

cpp

#include <iostream>
#include <cstring>

using namespace std;
const int INF = 1000000;
char g[10][10];
int dx[5] = {0, -1, 0, 1, 0};
int dy[5] = {0, 0, 1, 0, -1};

void turn(int x, int y) {
    for (int i = 0; i < 5; ++i) {
        int a = x + dx[i], b = y + dy[i];
        if (a >= 0 && a < 5 && b >= 0 && b < 5)
            g[a][b] ^= 1;
    }
}

int work() {
    int ans = INF;
    char backup[10][10];
    memcpy(backup, g, sizeof g);
    for (int i = 0; i < 1 << 5; ++i) {
        int res = 0;
        //先遍历第一行的所有情况（共有 2^5 三十二种，
        //故外层循环要循环32次来枚举第一行的所有操作）
        for (int j = 0; j < 5; ++j) {
            if (i >> j & 1) {
                res++;
                turn(0, j);
            }
        }
        //从第二行开始递推，算出第一行该操作所对应的唯一res
        for (int j = 0; j < 4; ++j) {
            for (int k = 0; k < 5; ++k) {
                if (g[j][k] == '0') {
                    res++;
                    turn(j + 1, k);
                }
            }
        }
        //判断将灯全部打开
        bool isSucc = true;
        for (int j = 0; j < 5; ++j) {
            if (g[4][j] == '0') {
                isSucc = false;
                break;
            }
        }
        if (isSucc)ans = min(ans, res);
        memcpy(g, backup, sizeof g);
    }
    if (ans > 6)return -1;
    return ans;
}

int main() {
    int n;
    cin >> n;
    while (n--) {
        for (int i = 0; i < 5; ++i)
            cin >> g[i];
        cout << work() << endl;
    }
    return 0;
}

二分

整数二分

整数二分要注意边界，最好背过一套模板

cpp

bool check(int x) {
    /*检查 x 是否满足要求*/
}

// 区间[l, r]被划分成[l, mid - 1]和[mid, r]时使用：
void bsearch_1(int l, int r) {
    while (l < r) {
        int mid = (l + r + 1) >> 1;
        if (check(mid))
            l = mid;
        else
            r = mid - 1;
    }
}
// 区间[l, r]被划分成[mid + 1, r]和[l, mid]时使用：
void bsearch_1(int l, int r) {
    while (l < r) {
        int mid = (l + r) >> 1;
        if (check(mid))
            l = mid + 1;
        else
            r = mid;
    }
}

给定一个按照升序排列的长度为n的整数数组，以及 q 个查询。

对于每个查询，返回一个元素k的起始位置和终止位置（位置从0开始计数）。

如果数组中不存在该元素，则返回“-1 -1”。

输入格式：

第一行包含整数n和q，表示数组长度和询问个数。

第二行包含n个整数（均在1~10000范围内），表示完整数组。

接下来q行，每行包含一个整数k，表示一个询问元素。

输出格式：

共q行，每行包含两个整数，表示所求元素的起始位置和终止位置。

如果数组中不存在该元素，则返回“-1 -1”。

数据范围：

1≤n≤100000,

1≤q≤10000,

1≤k≤10000

输入样例：

cpp

6 3
1 2 2 3 3 4
3
4
5

输出样例：

cpp

3 4
5 5
-1 -1

代码：

cpp

#include<iostream>

using namespace std;
const int N = 100001;
int a[N];

int main() {
    int n, k, x;
    cin >> n >> k;
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }
    for (int i = 0; i < k; i++) {
        cin >> x;
        //先找左端点
        int l = 0, r = n - 1;
        while (l < r) {
            int mid = (l + r) >> 1;
            if (a[mid] >= x)
                r = mid;
            else
                l = mid + 1;
        }
        if (a[r] == x) {
            cout << r << " ";
            //找到左端点后找右端点
            r = n - 1;
            while (l < r) {
                int mid = (l + r + 1) >> 1;
                if (a[mid] <= x)
                    l = mid;
                else
                    r = mid - 1;
            }
            cout << l << endl;
        } else//找不到左端点直接输出 -1 -1
            cout << "-1 -1" << endl;
    }
    return 0;
}

浮点数二分

相对整数二分来说简单多了~ 没有坑人的边界问题

cpp

bool check(int x) {
    /*检查 x 是否满足要求*/
}

void bserach(double l, double r) {
    while (r - l > 1e6) {//题目要求精度
        double mid = (l + r) / 2;
        if (check(mid))
            r = mid;
        else
            l = mid;
    }
}

给定一个浮点数n，求它的三次方根。

输入格式：

共一行，包含一个浮点数n。

输出格式：

共一行，包含一个浮点数，表示问题的解。

注意，结果保留6位小数。

数据范围：

−10000 ≤ n ≤ 10000

输入样例：

cpp

1000.00

输出样例：

cpp

10.000000

代码：

cpp

#include<iostream>
#include<cstdio>

using namespace std;

int main() {
    double n;
    bool fu = false;
    cin >> n;
    if (n < 0) {
        fu = true;
        n *= (-1);
    }
    double l = 0, r = 10001;
    double mid;
    while (r - l > 1e-8) {
        mid = (l + r) / 2;
        if (mid * mid * mid > n)
            r = mid;
        else
            l = mid;
    }
    if (fu)
        mid *= (-1);
    printf("%.6f", mid);
    return 0;
}

前缀和

前缀和与差分

前缀和

前缀和矩阵 $S_{xy} = S_{x-1,y} + S_{x,y-1} - S_{x-1,y-1} + a_{x,y}$ （容斥原理）
利用前缀和矩阵计算子矩阵的和 $[x_1y_1,x_2y_2] = S_{x_2,y_2} - S_{x_2,y_1-1} - S_{x_1-1,y_2} + S_{x_1-1,y_1-1}$

给定一个长度为 N 的数列，A1,A2,…AN，如果其中一段连续的子序列 Ai,Ai+1,…Aj 之和是 K 的倍数，我们就称这个区间[ i , j ]是 K 倍区间。

你能求出数列中总共有多少个 K 倍区间吗？

输入格式：

第一行包含两个整数 N 和 K。

以下 N 行每行包含一个整数 Ai。

输出格式：

输出一个整数，代表 K 倍区间的数目。

数据范围：

1 ≤ N , K ≤ 100000

1 ≤ Ai ≤ 100000

输入样例：

cpp

输出样例：

cpp

代码：

cpp

#include<iostream>

using namespace std;
const int N = 100010;
long long int n, k, x, ans = 0;
long long int s[N];
long long int res[N];

int main() {
    cin >> n >> k;
    res[0] = 1;
    //s[0]%k=0,故余数为0的数已经有一个了
    for (long long int i = 1; i <= n; i++) {
        cin >> x;
        s[i] = s[i - 1] + x;
        ans += res[s[i] % k];
        res[s[i] % k]++;
    }
    cout << ans << endl;
    return 0;
}

差分

将序列中 [ l , r ] 之间的每个数加上 c

cpp

void insert(int l, int r, int c) {
    b[l] += c;
    b[r + 1] -= c;
}

将( x1 , y1 ) , ( x2 , y2 )矩阵中的每个元素的值加上 c

cpp

void insert(int x1, int y1, int x2, int y2, int c) {
    b[x1][y1] += c;
    b[x2 + 1][y1] -= c;
    b[x1][y2 + 1] -= c;
    b[x2 + 1][y2 + 1] += c;
}

输入一个长度为 n 的整数序列。

接下来输入 m 个操作，每个操作包含三个整数 l,r,c，表示将序列中 [l,r][l,r] 之间的每个数加上 c。

请你输出进行完所有操作后的序列。

输入格式：

第一行包含两个整数 n 和 m。

第二行包含 n 个整数，表示整数序列。

接下来 m 行，每行包含三个整数 l，r，c，表示一个操作。

输出格式：

共一行，包含 n 个整数，表示最终序列。

数据范围：

1 ≤ n, m ≤ 100000, 1 ≤ l ≤ r ≤ n, −1000 ≤ c ≤ 1000, −1000≤整数序列中元素的值≤1000

输入样例：

cpp

6 3
1 2 2 1 2 1
1 3 1
3 5 1
1 6 1

输出样例：

cpp

3 4 5 3 4 2

代码：

cpp

#include <iostream>

using namespace std;
const int N = 100010;
int a[N],b[N];
int n,m;

void insert(int l, int r, int c){
    b[l]+=c;
    b[r + 1]-=c;
}

int main(){
   cin>>n>>m;
   for(int i = 1; i <= n; i ++){
       cin>>a[i];
       insert(i,i,a[i]);
   }
   int l,r,c;
   while(m--){
       cin>>l>>r>>c;
       insert(l,r,c);
   }
   for(int i = 1; i <= n; i++){
       a[i] = a[i-1]+b[i];
   }
   for(int i = 1; i <= n; i++){
       cout<<a[i]<<" ";
   }
   return 0;
}

输入一个n 行 m 列的整数矩阵，再输入 q 个操作，每个操作包含五个整数 x1,y1,x2,y2,c，其中 (x1,y1) 和 (x2,y2) 表示一个子矩阵的左上角坐标和右下角坐标。

每个操作都要将选中的子矩阵中的每个元素的值加上 c。

请你将进行完所有操作后的矩阵输出。

输入格式：

第一行包含整数 n,m,q。

接下来 n 行，每行包含 m 个整数，表示整数矩阵。

接下来 q 行，每行包含 55 个整数 x1,y1,x2,y2,c，表示一个操作。

输出格式：

共 n 行，每行 m 个整数，表示所有操作进行完毕后的最终矩阵。

数据范围：

1 ≤ n, m ≤ 1000, 1 ≤ q ≤ 100000, 1 ≤ x1 ≤ x2 ≤ n, 1 ≤ y1 ≤ y2 ≤ m, −1000 ≤ c ≤ 1000, −1000 ≤ 矩阵内元素的值 ≤ 1000

输入样例：

cpp

输出样例：

cpp

2 3 4 1
4 3 4 1
2 2 2 2

代码：

cpp

#include <iostream>

using namespace std;
const int N = 1010;
int a[N][N], b[N][N];
int q, n, m, x1, x2, y1, y2, c;

void insert(int x1, int y1, int x2, int y2, int c) {
    b[x1][y1] += c;
    b[x2 + 1][y1] -= c;
    b[x1][y2 + 1] -= c;
    b[x2 + 1][y2 + 1] += c;
}

int main() {
    cin >> n >> m >> q;
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= m; ++j) {
            cin >> a[i][j];
            insert(i, j, i, j, a[i][j]);
        }
    }
    while (q--) {
        cin >> x1 >> y1 >> x2 >> y2 >> c;
        insert(x1, y1, x2, y2, c);
    }
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= m; ++j) {
            b[i][j] += b[i - 1][j] + b[i][j - 1] - b[i - 1][j - 1];
            cout << b[i][j] << " ";
        }
        cout << endl;
    }
    return 0;
}

搜索

深度优先搜索

标记状态

n−皇后问题是指将 n个皇后放在 n×n 的国际象棋棋盘上，使得皇后不能相互攻击到，即任意两个皇后都不能处于同一行、同一列或同一斜线上。

现在给定整数 n，请你输出所有的满足条件的棋子摆法。

输入格式：

共一行，包含整数 n。

输出格式：

每个解决方案占 n 行，每行输出一个长度为 n 的字符串，用来表示完整的棋盘状态。

其中 . 表示某一个位置的方格状态为空，Q 表示某一个位置的方格上摆着皇后。

每个方案输出完成后，输出一个空行。

注意：行末不能有多余空格。

输出方案的顺序任意，只要不重复且没有遗漏即可。

数据范围：

1 ≤ n ≤ 9

输入样例：

cpp

输出样例：

cpp

.Q..
...Q
Q...
..Q.

..Q.
Q...
...Q
.Q..

思路：

记录当前放置皇后数量，遍历整个棋盘，判断能否放置皇后，并对放置皇后与不放置皇后两种操作分别进行搜索。

代码：

cpp

//
// Created by Black on 2021/8/6.
//

#include <iostream>

using namespace std;
const int N = 20;
char g[N][N];
bool col[N], row[N], dg[N], udg[N];
int n;

void dfs(int cur, int x, int y) {
    if (y == n) {
        if (cur == n) {
            for (int i = 0; i < n; ++i)
                cout << g[i] << endl;
            cout << endl;
        }
        return;
    }
    if (x == n) {
        dfs(cur, 0, y + 1);
        return;
    }
    dfs(cur, x + 1, y);
    if (!col[x] && !row[y] && !dg[x + y] && !udg[x - y + n]) {
        g[y][x] = 'Q';
        col[x] = row[y] = dg[x + y] = udg[x - y + n] = true;
        dfs(cur + 1, x + 1, y);
        g[y][x] = '.';
        col[x] = row[y] = dg[x + y] = udg[x - y + n] = false;
    }
}

int main() {
    cin >> n;
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            g[i][j] = '.';
        }
    }
    dfs(0, 0, 0);
    return 0;
}

给定 n 个正整数，将它们分组，使得每组中任意两个数互质。

至少要分成多少个组？

输入格式

第一行是一个正整数 n。

第二行是 n 个不大于10000的正整数。

输出格式

一个正整数，即最少需要的组数。

数据范围

1≤n≤10

输入样例：

6
14 20 33 117 143 175

输出样例：

思路：

利用最大公因数判断互质，然后对当前组序号，组内元素数量，搜索过的总个数和当前组搜索的元素序号进行搜索。

代码：

cpp

#include<iostream>

using namespace std;
const int N = 11;
int res = N, n, m;
int a[N];
bool st[N];
int g[N][N];

int gcd(int a, int b) {
    return b ? gcd(b, a % b) : a;
}

bool check(int group[], int gc, int i) {
    for (int j = 0; j < gc; ++j) {
        if (gcd(a[group[j]], a[i]) > 1) // 最大公因数大于1便不互质
            return false;
    }
    return true;
}

// u为最后一组的组序号, gc为当前组的组内数量，tc为搜索过的总个数, start为当前组搜索的数的序号
void dfs(int u, int gc, int tc, int start) {
    if (u >= res) return; // 剪枝
    if (tc == n) res = u; // 都搜完了就更新答案
    bool flag = true;
    for (int i = start; i < n; ++i) {
        if (st[i] || !check(g[u], gc, i)) continue;
        st[i] = true;
        g[u][gc] = i;
        // 继续搜索，组内数量+1,总数+1,序号+1
        dfs(u, gc + 1, tc + 1, i + 1);
        st[i] = false;
        flag = false;
    }
    // 新开一组，最后一组序号+1,当前组内数量为0,总数不变,当前组搜索的数的序号为0
    if (flag) dfs(u + 1, 0, tc, 0);
}

int main() {
    cin >> n;
    for (int i = 0; i < n; ++i) cin >> a[i];
    dfs(1, 0, 0, 0);
    cout << res << endl;
    return 0;
}

乔治拿来一组等长的木棒，将它们随机地砍断，使得每一节木棍的长度都不超过 50 个长度单位。

然后他又想把这些木棍恢复到为裁截前的状态，但忘记了初始时有多少木棒以及木棒的初始长度。

请你设计一个程序，帮助乔治计算木棒的可能最小长度。

每一节木棍的长度都用大于零的整数表示。

输入格式

输入包含多组数据，每组数据包括两行。

第一行是一个不超过 64 的整数，表示砍断之后共有多少节木棍。

第二行是截断以后，所得到的各节木棍的长度。

在最后一组数据之后，是一个零。

输出格式

为每组数据，分别输出原始木棒的可能最小长度，每组数据占一行。

数据范围

数据保证每一节木棍的长度均不大于 50。

输入样例：

9
5 2 1 5 2 1 5 2 1
4
1 2 3 4
0

输出样例：

6
5

思路

必须整除才进行枚举
优化搜索顺序，从大到小枚举
排除等效冗余
3.1 以组合数方式搜索
3.2 当前木棍放到当前棒中失败，则跳过后边所有长度相等的木棍
3.3 如果是木棒的第一个木棍失败，则一定失败
3.4 如果是木棒的最后一根木棍失败，则一定失败

代码

cpp

#include<iostream>
#include<vector>
#include<cstdio>
#include<cmath>
#include<cstring>
#include <algorithm>

using namespace std;

const int N = 65;
int m, n, k, cnt;
int a[N], res[N];
int length, sum;
bool st[N];

bool dfs(int u, int s, int start) {
    if (u * length == sum) return true;
    if (s == length) return dfs(u + 1, 0, 0);
    // 3.1 i从start开始
    for (int i = start; i < n; ++i) {
        if (st[i]) continue;
        if (s + a[i] > length) continue;    // 可行性剪枝
        st[i] = true;
        if (dfs(u, s + a[i], i + 1)) return true;
        st[i] = false;
        // 剪枝3.3
        if (!s) return false;
        // 剪枝3.4
        if (s + a[i] == length) return false;
        // 剪枝3.2
        int j = i;
        while (j < n && a[j] == a[i]) j++;
        i = j - 1;

    }
    return false;
}

int main() {
    while (cin >> n, n) {
        sum = 0;
        memset(st, false, sizeof(st));
        for (int i = 0; i < n; ++i) {
            cin >> a[i];
            sum += a[i];
        }
        length = 1;
        // 2. 优化搜索顺序
        sort(a, a + n);
        reverse(a, a + n);
        while (true) {
            if (sum % length == 0 && dfs(0, 0, 0)) {
                cout << length << endl;
                break;
            }
            length++;
            if (length > sum) break;
        }
    }
    return 0;
}

给定一棵 n 个节点的树。

节点的编号为 1∼n，其中 1 号节点为根节点，每个节点的编号都大于其父节点的编号。

现在，你需要回答 q 个询问。

每个询问给定两个整数 u_i,k_i。

我们希望你用 DFS（深度优先搜索）算法来遍历根节点为 u_i 的子树。

我们规定，当遍历（或回溯）到某一节点时，下一个遍历的目标应该是它的未经遍历的子节点中编号最小的那一个子节点。

例如，上图实例中：

如果遍历根节点为 1 号节点的子树，则子树内各节点的遍历顺序为 1,2,3,5,6,8,7,9,4。
如果遍历根节点为 3 号节点的子树，则子树内各节点的遍历顺序为 3,5,6,8,7,9。
如果遍历根节点为 7 号节点的子树，则子树内各节点的遍历顺序为 7,9。
如果遍历根节点为 9 号节点的子树，则子树内各节点的遍历顺序为 9。

每个询问就是让你计算采用规定的 DFS 算法来遍历根节点为 u_i 的子树时，第 k_i 个被遍历到的节点的编号。

输入格式

第一行包含两个整数 n,q。

第二行包含 n−1 个整数 p₂,p₃,…,p_n，其中 p_i 表示第 i 号节点的父节点的编号。

接下来 q 行，每行包含两个整数 u_i,k_i，表示一组询问。

输出格式

共 q 行，每组询问输出一行一个整数表示第 k_i 个被遍历到的节点的编号。

如果第 k_i 个被遍历到的节点不存在，则输出 −1。

数据范围

前三个测试点满足 2≤n≤20，1≤q≤20。所有测试点满足 2≤n≤2×10⁵，1≤q≤2×10⁵，1≤p_i<i，1≤u_i,k_i≤n。

输入样例：

9 6
1 1 1 3 5 3 5 7
3 1
1 5
3 4
7 3
1 8
1 9

输出样例：

思路

要用vector<int> h[N]写邻接链表，不要用h[N], e[N], ne[N]数组写，因为需要从小到大遍历点，所以用vector写可以方便排序

代码

cpp

#include<iostream>
#include<vector>
#include <algorithm>

using namespace std;

const int N = 2e5 + 10;
int m, n, k, t;
int res;
vector<int> h[N];
vector<int> p;
bool st[N];
int a[N], cnt[N];

int dfs(int x) {
    p.push_back(x);
    cnt[x] = 1;
    for (int i: h[x])
        cnt[x] += dfs(i);
    return cnt[x];
}

int main() {
    cin >> n >> m;
    for (int i = 2; i <= n; ++i) {
        cin >> t;
        h[t].push_back(i);
    }
    for (int i = 1; i <= n; ++i) sort(h[i].begin(), h[i].end());
    dfs(1);
    for (int i = 0; i < p.size(); ++i) a[p[i]] = i;
    while (m--) {
        cin >> t >> k;
        if (cnt[t] < k) cout << -1 << endl;
        else cout << p[a[t] + k - 1] << endl;
    }
    return 0;
}

广度优先搜索

在一个 3×33×3 的网格中，1∼81∼8 这 88 个数字和一个 x 恰好不重不漏地分布在这 3×33×3 的网格中。

例如：

cpp

1 2 3
x 4 6
7 5 8

在游戏过程中，可以把 x 与其上、下、左、右四个方向之一的数字交换（如果存在）。

我们的目的是通过交换，使得网格变为如下排列（称为正确排列）：

cpp

1 2 3
4 5 6
7 8 x

例如，示例中图形就可以通过让 x 先后与右、下、右三个方向的数字交换成功得到正确排列。

交换过程如下：

cpp

1 2 3   1 2 3   1 2 3   1 2 3
x 4 6   4 x 6   4 5 6   4 5 6
7 5 8   7 5 8   7 x 8   7 8 x

现在，给你一个初始网格，请你求出得到正确排列至少需要进行多少次交换。

输入格式：

输入占一行，将 3×33×3 的初始网格描绘出来。

例如，如果初始网格如下所示：

cpp

1 2 3 
x 4 6 
7 5 8

则输入为：1 2 3 x 4 6 7 5 8

输出格式：

输出占一行，包含一个整数，表示最少交换次数。

如果不存在解决方案，则输出 −1−1。

输入样例：

cpp

2  3  4  1  5  x  7  6  8

输出样例：

cpp

思路：

用字符串记录网格状态，用map记录交换次数

代码：

cpp

//
// Created by Black on 2021/8/11.
//

#include <iostream>
#include <queue>
#include <unordered_map>

using namespace std;
string s_start;
string s_end = "12345678x";
int dx[4] = {0, 1, 0, -1};
int dy[4] = {1, 0, -1, 0};

int bfs() {
    queue<string> q;
    q.push(s_start);
    unordered_map<string, int> d;
    d[s_start] = 0;
    while (q.size()) {
        auto t = q.front();
        q.pop();
        int dis = d[t];
        if (t == s_end)return dis;
        int k = t.find('x');
        int x = k / 3, y = k % 3;
        for (int i = 0; i < 4; ++i) {
            int a = x + dx[i], b = y + dy[i];
            if (a >= 0 && b >= 0 && a < 3 && b < 3) {
                swap(t[k], t[a * 3 + b]);
                if (!d.count(t)) {
                    d[t] = dis + 1;
                    q.push(t);
                }
                swap(t[k], t[a * 3 + b]);
            }
        }
    }
    return -1;
}


int main() {
    char c;
    for (int i = 0; i < 9; ++i) {
        cin >> c;
        s_start += c;
    }
    cout << bfs() << endl;
    return 0;
}

双端队列广搜

双端队列

双端队列广搜是一种类Dijkstra算法，主要解决图中边的权值只有0或者1的最短路问题。

操作：

每次从队头取出元素，并进行拓展其他元素时
1、若拓展某一元素的边权是0，则将该元素插入到队头 2、若拓展某一元素的边权是1，则将该元素插入到队尾

达达是来自异世界的魔女，她在漫无目的地四处漂流的时候，遇到了善良的少女翰翰，从而被收留在地球上。

翰翰的家里有一辆飞行车。

有一天飞行车的电路板突然出现了故障，导致无法启动。

电路板的整体结构是一个 R 行 C 列的网格（R,C≤500），如下图所示。

每个格点都是电线的接点，每个格子都包含一个电子元件。

电子元件的主要部分是一个可旋转的、连接一条对角线上的两个接点的短电缆。

在旋转之后，它就可以连接另一条对角线的两个接点。

电路板左上角的接点接入直流电源，右下角的接点接入飞行车的发动装置。

达达发现因为某些元件的方向不小心发生了改变，电路板可能处于断路的状态。

她准备通过计算，旋转最少数量的元件，使电源与发动装置通过若干条短缆相连。

不过，电路的规模实在是太大了，达达并不擅长编程，希望你能够帮她解决这个问题。

注意：只能走斜向的线段，水平和竖直线段不能走。

输入格式

输入文件包含多组测试数据。

第一行包含一个整数 T，表示测试数据的数目。

对于每组测试数据，第一行包含正整数 R 和 C，表示电路板的行数和列数。

之后 R 行，每行 C 个字符，字符是"/"和"\"中的一个，表示标准件的方向。

输出格式

对于每组测试数据，在单独的一行输出一个正整数，表示所需的最小旋转次数。

如果无论怎样都不能使得电源和发动机之间连通，输出 NO SOLUTION。

数据范围

1≤R,C≤500, 1≤T≤5

输入样例：

1
3 5
\\/\\
\\///
/\\\\

输出样例：

样例解释

样例的输入对应于题目描述中的情况。

只需要按照下面的方式旋转标准件，就可以使得电源和发动机之间连通。

思路：

即将不需要旋转就可以扩展到的点看成权重为0

将需要旋转才能扩展到的点看成权重为1

代码：

cpp

#include<iostream>
#include<deque>
#include<cstring>

using namespace std;

#define x first
#define y second
typedef pair<int, int> PII;
const int N = 510;
int m, n, t;
char g[N][N];
int dist[N][N];
bool st[N][N];
char c[5] = "\\/\\/";
//可以扩展到的4个位置的坐标
int dx[4] = {-1, -1, 1, 1}, dy[4] = {-1, 1, 1, -1};
//可以扩展到的4个位置的坐标差值(扩展到四个方位要踩过的格子)
int ix[4] = {-1, -1, 0, 0}, iy[4] = {-1, 0, 0, -1};

int bfs() {
    deque<PII> q;
    memset(dist, 0x3f, sizeof dist);
    memset(st, 0, sizeof st);
    dist[0][0] = 0;
    q.push_back({0, 0});
    while (q.size()) {
        auto t = q.front();
        q.pop_front();
        if (st[t.x][t.y]) continue;
        st[t.x][t.y] = true;
        for (int i = 0; i < 4; ++i) {
            int a = t.x + dx[i];
            int b = t.y + dy[i];
            if (a < 0 || a > n || b < 0 || b > m) continue;
            int ca = t.x + ix[i], cb = t.y + iy[i];
            //(g[ca][cb] != c[i])判断被踩过的格子的方向决定权重
            int d = dist[t.x][t.y] + (g[ca][cb] != c[i]);
            if (d < dist[a][b]) {
                dist[a][b] = d;
                if (g[ca][cb] != c[i]) q.push_back({a, b});
                else q.push_front({a, b});
            }
        }
    }
    return dist[n][m];
}

int main() {
    cin >> t;
    while (t--) {
        cin >> n >> m;
        for (int i = 0; i < n; ++i)
            cin >> g[i];
        if (n + m & 1) cout << "NO SOLUTION" << endl;
        else cout << bfs() << endl;
    }
    return 0;
}

双向广搜

同时从起点状态和终点状态开始广搜，从而提高搜索效率

已知有两个字串 A, B 及一组字串变换的规则（至多 6 个规则）:

A1→B1

A2→B2

…

规则的含义为：在 A 中的子串 A1 可以变换为 B1、A2 可以变换为 B2…。

例如：A＝abcd B＝xyz

变换规则为：

abc` →→ `xu` `ud` →→ `y` `y` →→ `yz

则此时，A 可以经过一系列的变换变为 B，其变换的过程为：

abcd` →→ `xud` →→ `xy` →→ `xyz

共进行了三次变换，使得 AA 变换为 BB。

输入格式

输入格式如下：

A B A1 B1 A2 B2 … …

第一行是两个给定的字符串 A 和 B。

接下来若干行，每行描述一组字串变换的规则。

所有字符串长度的上限为 20。

输出格式

若在 10 步（包含 10 步）以内能将 A 变换为 B ，则输出最少的变换步数；否则输出 NO ANSWER!。

输入样例：

abcd xyz
abc xu
ud y
y yz

输出样例：

思路：

从始末两个状态同时扩展，相遇时返回结果即可

代码：

cpp

#include<iostream>
#include<vector>
#include<cstdio>
#include<cmath>
#include<unordered_map>
#include<cstring>
#include<queue>

using namespace std;

#define x first
#define y second
typedef pair<int, int> PII;
const int N = 6;
int m, n;
int res;
string a[N], b[N];

// 记得&！！！
int extend(queue<string> &q, unordered_map<string, int> &da, unordered_map<string, int> &db, string a[], string b[]) {
    string t = q.front();
    q.pop();
    for (int i = 0; i < t.size(); i++) {
        for (int j = 0; j < n; ++j) {
            if (t.substr(i, a[j].size()) == a[j]) {
                // 替换
                string state = t.substr(0, i) + b[j] + t.substr(i + a[j].size());
                // 如果另一个方向扩展过这个状态便直接返回步数和
                if (db.count(state)) return da[t] + 1 + db[state];
                // 如果当前方向扩展过这个状态便进行下一次扩展
                if (da.count(state)) continue;
                // 否则存下当前状态及步数
                da[state] = da[t] + 1;
                q.push(state);
            }
        }
    }
    // 找不到就返回任意一个大于10的数字
    return 100;
}

int bfs(string A, string B) {
    if (A == B) return 0;
    queue<string> qa, qb;
    unordered_map<string, int> da, db;
    qa.push(A);
    da[A] = 0;
    qb.push(B);
    db[B] = 0;
    int t = 0;
    while (qa.size() && qb.size()) {
        // 优先扩展状态少的队列
        if (qa.size() <= qb.size()) t = extend(qa, da, db, a, b);
        else t = extend(qb, db, da, b, a);
        if (t <= 10) return t;
    }
    return 100;
}


int main() {
    string A, B;
    cin >> A >> B;
    while (cin >> a[n] >> b[n]) n++;
    int step = bfs(A, B);
    if (step > 10) puts("NO ANSWER!");
    else cout << step << endl;
    return 0;
}

A*算法

给定一张 N 个点（编号 1,2…N），M 条边的有向图，求从起点 S 到终点 T 的第 K 短路的长度，路径允许重复经过点或边。

注意： 每条最短路中至少要包含一条边。

输入格式

第一行包含两个整数 N 和 M。

接下来 M 行，每行包含三个整数 A,B 和 L，表示点 A 与点 B 之间存在有向边，且边长为 L。

最后一行包含三个整数 S,T 和 K，分别表示起点 S，终点 T 和第 K 短路。

输出格式

输出占一行，包含一个整数，表示第 K 短路的长度，如果第 K 短路不存在，则输出 −1。

数据范围

1≤S,T≤N≤1000, 0≤M≤10⁴, 1≤K≤1000, 1≤L≤100

输入样例：

输出样例：

思路：

代码：

cpp

#include<iostream>
#include<vector>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<queue>

using namespace std;

#define x first
#define y second
typedef long long LL;
typedef pair<int, int> PII;
typedef pair<int, PII> PIII;
const int N = 1010, M = 200010;
int m, n, k, s, tt;
int res, ans, sum;
int h[N], rh[N], e[M], w[M], ne[M], idx;
int dist[N], cnt[N];
bool st[N];

void add(int h[], int a, int b, int c) {
    e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx++;
}

void dijkstra() {
    priority_queue<PII, vector<PII>, greater<PII>> heap;
    heap.push({0, tt});
    memset(dist, 0x3f, sizeof(dist));
    dist[tt] = 0;
    while (!heap.empty()) {
        auto t = heap.top();
        heap.pop();
        int ver = t.y;
        if (st[ver]) continue;
        st[ver] = true;
        for (int i = rh[ver]; i != -1; i = ne[i]) {
            int j = e[i];
            if (dist[j] > dist[ver] + w[i]) {
                dist[j] = dist[ver] + w[i];
                heap.push({dist[j], j});
            }
        }
    }

}

int astar() {
    priority_queue<PIII, vector<PIII>, greater<PIII>> heap;
    heap.push({dist[s], {0, s}});
    while (!heap.empty()) {
        auto t = heap.top();
        heap.pop();
        int ver = t.y.y, distance = t.y.x;
        cnt[ver]++;
        if (cnt[tt] == k) return distance;
        for (int i = h[ver]; i != -1; i = ne[i]) {
            int j = e[i];
            if (cnt[ver] < k)
                heap.push({distance + w[i] + dist[j], {distance + w[i], j}});
        }
    }
    return -1;
}

int main() {
    cin >> n >> m;
    memset(h, -1, sizeof h);
    memset(rh, -1, sizeof rh);
    int a, b, c;
    for (int i = 0; i < m; ++i) {
        cin >> a >> b >> c;
        add(h, a, b, c);
        add(rh, b, a, c);
    }
    cin >> s >> tt >> k;
    if (s == tt)k++;
    dijkstra();
    cout << astar() << endl;
    return 0;
}

图论

拓扑排序

给定一个 n 个点 m 条边的有向图，点的编号是 1 到 n，图中可能存在重边和自环。

请输出任意一个该有向图的拓扑序列，如果拓扑序列不存在，则输出 −1。

若一个由图中所有点构成的序列 A 满足：对于图中的每条边 (x,y)，x 在 A 中都出现在 y 之前，则称 A 是该图的一个拓扑序列。

输入格式：

第一行包含两个整数 n 和 m。

接下来 m 行，每行包含两个整数 x 和 y，表示存在一条从点 x 到点 y 的有向边 (x,y)。

输出格式：

共一行，如果存在拓扑序列，则输出任意一个合法的拓扑序列即可。

否则输出 −1。

数据范围：

1 ≤ n,m ≤ 10⁵

输入样例：

cpp

输出样例：

cpp

1 2 3

思路：

使用邻接链表的方法存储图，声明整型数组来存储各个点的入度，将入度为0的点存入队列中。

代码：

cpp

//
// Created by Black on 2021/8/14.
//

#include <iostream>
#include <cstring>

using namespace std;
const int N = 200100;
int n, idx, hh, m, tt = -1;
int h[N], q[N], e[N], ne[N], d[N];

void add(int a, int b) {
    e[idx] = b;
    ne[idx] = h[a];
    h[a] = idx++;
}

bool topsort() {
    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];
            d[j]--;
            if (!d[j])
                q[++tt] = j;
        }
    }
    return tt == n - 1;
}

int main() {
    cin >> n >> m;
    int c, f;
    memset(h, -1, sizeof h);
    for (int i = 0; i < m; ++i) {
        cin >> c >> f;
        add(c, f);
        d[f]++;
    }
    if (topsort())
        for (int i = 0; i < n; ++i)
            cout << q[i] << " ";
    else
        cout << -1 << endl;
    return 0;
}

Dijkstra

单源最短路

给定一个 n 个点 m 条边的有向图，图中可能存在重边和自环，所有边权均为正值。

请你求出 1 号点到 n 号点的最短距离，如果无法从 1 号点走到 n 号点，则输出 −1。

输入格式：

第一行包含整数 n 和 m。

接下来 m 行每行包含三个整数 x,y,z，表示存在一条从点 x 到点 y 的有向边，边长为 z。

输出格式：

输出一个整数，表示 1 号点到 n 号点的最短距离。

如果路径不存在，则输出 −1。

数据范围：

1 ≤ n ≤ 500, 1 ≤ m ≤ 10⁵, 图中涉及边长均不超过10000。

输入样例：

cpp

输出样例：

cpp

思路：

每次找到最近的一个点，通过该点更新与其他各点的最短距离。

代码：

cpp

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>

#define x first;
#define y second;
using namespace std;

typedef long long LL;
typedef pair<int, int> PII;
const int N = 510;
int n, m, T;
int g[N][N];
int d[N];
bool st[N];

int dijkstra() {
    memset(d, 0x3f, sizeof d);
    d[1] = 0;
    for (int i = 1; i <= n; ++i) {
        int t = -1;
        for (int j = 1; j <= n; ++j)
            if (!st[j] && (t == -1 || d[t] > d[j]))
                t = j;
        st[t] = true;
        for (int j = 1; j <= n; ++j)
            d[j] = min(d[j], d[t] + g[t][j]);
    }
    if (d[n] == 0x3f3f3f3f)
        return -1;
    return d[n];
}


int main() {
    memset(g, 0x3f, sizeof g);
    cin >> n >> m;
    int a, b, c;
    while (m--) {
        cin >> a >> b >> c;
        g[a][b] = min(g[a][b], c);
    }
    int res = dijkstra();
    cout << res << endl;
    return 0;
}

堆优化版 Dijkstra

Floyd

给定一个 n 个点 m 条边的有向图，图中可能存在重边和自环，边权可能为负数。

再给定 kk 个询问，每个询问包含两个整数 x 和 y，表示查询从点 x 到点 y 的最短距离，如果路径不存在，则输出 impossible。

数据保证图中不存在负权回路。

输入格式：

第一行包含三个整数 n,m,k。

接下来 m 行，每行包含三个整数 x,y,z，表示存在一条从点 x 到点 y 的有向边，边长为 z。

接下来 kk 行，每行包含两个整数 x,y，表示询问点 x 到点 y 的最短距离。

输出格式：

共 k 行，每行输出一个整数，表示询问的结果，若询问两点间不存在路径，则输出 impossible。

数据范围：

1 ≤ n ≤ 200, 1 ≤ k ≤ n² 1 ≤ m ≤ 20000, 图中涉及边长绝对值均不超过 10000。

输入样例：

cpp

输出样例：

cpp

impossible
1

思路：

遍历中转点，更新各点间最短距离，三重循环即可

代码：

cpp

#include <iostream>
#include <algorithm>

using namespace std;
const int N = 210;
int n, m, T;
int g[N][N];

int main() {
    cin >> n >> m >> T;
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= n; ++j) {
            if (i == j)g[i][j] = 0;
            else g[i][j] = 200000;
        }
    }
    int a, b, c;
    while (m--) {
        cin >> a >> b >> c;
        g[a][b] = min(g[a][b], c);
    }
    for (int k = 1; k <= n; ++k)
        for (int i = 1; i <= n; ++i)
            for (int j = 1; j <= n; ++j)
                g[i][j] = min(g[i][j], g[i][k] + g[k][j]);
    while (T--) {
        cin >> a >> b;
        if (g[a][b] >= 10000)cout << "impossible" << endl;
        else cout << g[a][b] << endl;
    }
    return 0;
}

bellman-ford

给定一个 n 个点 m 条边的有向图，图中可能存在重边和自环， 边权可能为负数。

请你求出从 11 号点到 n 号点的最多经过 kk 条边的最短距离，如果无法从 1 号点走到 n 号点，输出 impossible。

注意：图中可能 存在负权回路 。

输入格式：

第一行包含三个整数 n,m,k。

接下来 m 行，每行包含三个整数 x,y,z，表示存在一条从点 x 到点 y 的有向边，边长为 z。

输出格式：

输出一个整数，表示从 1 号点到 n 号点的最多经过 k 条边的最短距离。

如果不存在满足条件的路径，则输出 impossible。

数据范围：

1≤n,k≤500,

1≤m≤10000,

任意边长的绝对值不超过 10000。

输入样例：

cpp

输出样例：

cpp

思路：

只更新k次最短路

代码：

cpp

#include <iostream>
#include <cstring>
#include <algorithm>
#include <cstdio>

using namespace std;
const int N = 100010;
struct p {
    int a, b, w;
};
int n, m, T;
p e[N];
int d[N], backup[N];

int bellman_ford() {
    for (int i = 0; i < T; ++i) {
        memcpy(backup, d, sizeof d);
        for (int j = 0; j < m; ++j) {
            int a = e[j].a;
            int b = e[j].b;
            int w = e[j].w;
            d[b] = min(backup[a] + w, d[b]);
        }
    }
    if (d[n] > 0x3f3f3f3f / 2)return -100000;
    return d[n];
}

int main() {
    cin >> n >> m >> T;
    memset(d, 0x3f, sizeof d);
    d[1] = 0;
    for (int i = 0; i < m; ++i)
        cin >> e[i].a >> e[i].b >> e[i].w;
    int t = bellman_ford();
    if (t == -100000)printf("impossible\n");
    else cout << t << endl;
    return 0;
}

spfa

不能有负权回路

给定一个 n 个点 m 条边的有向图，图中可能存在重边和自环， 边权可能为负数。

请你求出 1 号点到 n 号点的最短距离，如果无法从 1 号点走到 n 号点，则输出 impossible。

数据保证不存在负权回路。

输入格式：

第一行包含整数 n 和 m。

接下来 m 行每行包含三个整数 x,y,z，表示存在一条从点 x 到点 y 的有向边，边长为 z。

输出格式：

输出一个整数，表示 1 号点到 n 号点的最短距离。

如果路径不存在，则输出 impossible。

数据范围：

1 ≤ n,m ≤ 105, 图中涉及边长绝对值均不超过 10000。

输入样例：

cpp

输出样例：

cpp

思路：

使用邻接链表存储图，广搜更新距离

代码：

cpp

//
// Created by Black on 2021/8/17.
//

#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>

using namespace std;
const int N = 1000010;
int n, m, T;
bool st[N];
int d[N], w[N], e[N], h[N], ne[N], idx;

void add(int a, int b, int wi) {
    e[idx] = b;
    ne[idx] = h[a];
    w[idx] = wi;
    h[a] = idx++;
}

int spfa() {
    memset(d, 0x3f, sizeof d);
    d[1] = 0;
    queue<int> q;
    q.push(1);
    st[1] = true;
    while (q.size()) {
        int t = q.front();
        q.pop();
        st[t] = false;
        for (int i = h[t]; i != -1; i = ne[i]) {
            int j = e[i];
            if (d[j] > d[t] + w[i]) {
                d[j] = d[t] + w[i];
                if (!st[j]) {
                    q.push(j);
                    st[j] = true;
                }
            }
        }
    }
    if (d[n] == 0x3f3f3f3f)return -1;
    return d[n];
}

int main() {
    cin >> n >> m;
    memset(h, -1, sizeof h);
    int a, b, c;
    while (m--) {
        cin >> a >> b >> c;
        add(a, b, c);
    }
    int t = spfa();
    if (t == -1)
        cout << "impossible\n";
    else
        cout << t << endl;
    return 0;
}

Prim

Kruskal

数论

质数

n 中最多只包含一个大于sqrt( n )的质因子

约数

约数个数

( a₁ + 1 ) * ( a₂ + 1) * ( a₃ + 1) * ··· * ( a_k + 1)

约束之和

( a₁⁰ + a₁¹ + ··· + a₁^k ) * ( a₂⁰ + a₂¹ + ··· + a₂^k ) * ··· * ( a_k⁰ + a_k¹ + ··· + a_k^k )

欧几里得算法

cpp

//最大公因数
int gcd(int a, int b) {
    return b ? gcd(b, a % b) : a;
}

数学老师给小明出了一道等差数列求和的题目。

但是粗心的小明忘记了一部分的数列，只记得其中 N 个整数。

现在给出这 N 个整数，小明想知道包含这 N 个整数的最短的等差数列有几项？

输入格式：

输入的第一行包含一个整数 N。

第二行包含 NN 个整数 A1,A2,⋅⋅⋅,AN。(注意 A1∼AN 并不一定是按等差数列中的顺序给出)

输出格式：

输出一个整数表示答案。

数据范围：

2 ≤ N ≤ 100000 ,

0 ≤ Ai ≤ 109

输入样例：

cpp

5
2 6 4 10 20

输出样例：

cpp

样例解释：

包含 2、6、4、10、20 的最短的等差数列是 2、4、6、8、10、12、14、16、18、20。

代码：

cpp

#include <iostream>
#include <cstdio>
#include <algorithm>

using namespace std;
const int N = 100010;
int n, k, d[N];

int gcd(int a, int b) {
    return b ? gcd(b, a % b) : a;
}

int main() {
    cin >> n;
    for (int i = 0; i < n; ++i)
        scanf("%d", &d[i]);
    sort(d, d + n);
    for (int i = 0; i < n; ++i)
        k = gcd(k, d[i] - d[0]);
    if (k)
        cout << (d[n - 1] - d[0]) / k + 1 << endl;
    else
        cout << n << endl;
    return 0;
}

欧拉函数

算术基本定理

任何一个大于1的自然数 N ，如果 N 不为质数，都可以唯一分解成有限个质数的乘积

这里 P₁ < P₂ < ··· < P_n 均为质数，其诸指数 a_i 是正整数

线性筛法

cpp

//线性筛法
int getPrime(int x) {
    for (int i = 2; i < x; ++i) {
        if (!st[i])prime[cnt++] = i;
        for (int j = 0; prime[i] * j < x; ++j) {
            st[prime[i] * j] = true;    // 筛掉合数
            if (i % prime[j] == 0)      // prime[j] <= i
                break;
        }
    }
    return cnt;
}

输入正整数 X，求 X 的大于 1 的因子组成的满足任意前一项都能整除后一项的严格递增序列的最大长度，以及满足最大长度的序列的个数。

输入格式：

输入包含多组数据，每组数据占一行，包含一个正整数表示 X。

输出格式：

对于每组数据，输出序列的最大长度以及满足最大长度的序列的个数。

每个结果占一行。

数据范围：

1≤X≤220

输入样例：

cpp

输出样例：

cpp

代码：

cpp

//
// Created by Black on 2021/2/16.
//

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>

using namespace std;
const long long int N = (1 << 20) + 10;
int prime[N], cnt;
bool st[N];
int minp[N];
int fact[30], sum[N];

//线性筛法
int getPrime(int x) {
    for (int i = 2; i < x; ++i) {
        if (!st[i])minp[i] = i, prime[cnt++] = i;
        for (int j = 0; prime[j] * i <= x; ++j) {
            st[prime[j] * i] = true;    // 筛掉合数
            minp[i * prime[j]] = prime[j];
            if (i % prime[j] == 0)      // prime[j] <= i
                break;
        }
    }
    return cnt;
}

int main() {
    getPrime(N - 1);
    int x;
    while (scanf("%d", &x) != -1) {
        int k = 0, tot = 0;
        while (x > 1) {
            int p = minp[x];
            fact[k] = p, sum[k] = 0;
            while (x % p == 0) {
                x /= p;
                sum[k]++;
                tot++;
            }
            k++;
        }
        long long int res = 1;
        for (int i = 1; i <= tot; ++i)
            res *= i;
        for (int i = 0; i < k; ++i)
            for (int j = 1; j <= sum[i]; ++j)
                res /= j;
        printf("%d %lld\n", tot, res);
    }
    return 0;
}

裴蜀定理（扩展欧几里得）

若a,b是整数,且gcd ( a, b) = d，那么对于任意的整数 x , y ,ax+by都一定是 d 的倍数，特别地，一定存在整数 x,y，使ax+by=d 成立。

cpp

int exgcd(int a, int b, int &x, int &y) {
    if (!b) {
        x = 1, y = 0;
        return a;
    }
    int d = exgcd(b, a % b, y, x);
    y -= a / b * x;
    return d;
}

动态规划

数字三角形模型

小渊和小轩是好朋友也是同班同学，他们在一起总有谈不完的话题。

一次素质拓展活动中，班上同学安排坐成一个 m 行 n 列的矩阵，而小渊和小轩被安排在矩阵对角线的两端，因此，他们就无法直接交谈了。

幸运的是，他们可以通过传纸条来进行交流。

纸条要经由许多同学传到对方手里，小渊坐在矩阵的左上角，坐标 (1,1)，小轩坐在矩阵的右下角，坐标 (m,n)。

从小渊传到小轩的纸条只可以向下或者向右传递，从小轩传给小渊的纸条只可以向上或者向左传递。

在活动进行中，小渊希望给小轩传递一张纸条，同时希望小轩给他回复。

班里每个同学都可以帮他们传递，但只会帮他们一次，也就是说如果此人在小渊递给小轩纸条的时候帮忙，那么在小轩递给小渊的时候就不会再帮忙，反之亦然。

还有一件事情需要注意，全班每个同学愿意帮忙的好感度有高有低（注意：小渊和小轩的好心程度没有定义，输入时用 0 表示），可以用一个 0∼100 的自然数来表示，数越大表示越好心。

小渊和小轩希望尽可能找好心程度高的同学来帮忙传纸条，即找到来回两条传递路径，使得这两条路径上同学的好心程度之和最大。

现在，请你帮助小渊和小轩找到这样的两条路径。

输入格式

第一行有 2 个用空格隔开的整数 m 和 n，表示学生矩阵有 m 行 n 列。

接下来的 m 行是一个 m×n 的矩阵，矩阵中第 i 行 j 列的整数表示坐在第 i 行 j 列的学生的好心程度，每行的 n 个整数之间用空格隔开。

输出格式

输出一个整数，表示来回两条路上参与传递纸条的学生的好心程度之和的最大值。

数据范围

1≤n,m≤50

输入样例：

cpp

输出样例：

cpp

思路：

dp[k - 1, i, j] 到 dp[k, i, j] 两个人同时向右走 dp[k - 1, i, j - 1] 到 dp[k, i, j] 一个人向右走，一个向下走 dp[k, i, j] dp[k - 1, i - 1, j] 到 dp[k, i, j] 一个人向下走，一个向右走 dp[k, i, j] dp[k - 1, i - 1, j - 1] 到 dp[k, i, j] 两个人同时向下走 dp[k, i, j]

代码：

cpp

#include<iostream>
#include<vector>
#include<cstdio>
#include<cmath>
#include<cstring>

using namespace std;

const int N = 55;
int m, n;
int res, ans, sum;
int a[N][N], dp[N * 2][N][N];


int main() {
    cin >> n >> m;
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= m; ++j)
            cin >> a[i][j];
    for (int k = 2; k <= n + m; ++k) {
        for (int i = max(1, k - m); i <= min(n, k - 1); ++i) {
            for (int j = max(1, k - m); j <= min(n, k - 1); ++j) {
                for (int b = 0; b <= 1; ++b) {
                    for (int c = 0; c <= 1; ++c) {
                        int t = a[i][k - i]; // 走过a[i][k - i]
                        // 两次不重复 || 第一步 || 最后一步
                        if (i != j || k == 2 || k == n + m) {
                            t += a[j][k - j]; // 走过a[j][k - j]
                            dp[k][i][j] = max(dp[k][i][j], dp[k - 1][i - b][j - c] + t);
                        }
                    }
                }
            }
        }
    }
    cout << dp[n + m][n][n] << endl;
    return 0;
}

数据结构与算法 ​

OI赛制必备对拍！！！ ​

数据结构 ​

用 new 开数组时间太慢，故在算法题中不适用 ​

数组模拟链表 ​

单链表 ​

应用 ​

双链表 ​

应用 ​

并查集 ​

树状数组与线段树 ​

树状数组 ​

适用问题 ​

常用操作及其相应函数 ​

线段树 ​

常用操作 ​

常用函数 ​

哈希表 ​

**<big>​841. 字符串哈希**​ </big> ​

堆 ​

KMP ​

算法 ​

枚举、模拟与排序 ​

高精度 ​

高精度加法 ​

高精度减法 ​

高精度乘法 ​

高精度除法 ​

递归与递推 ​

递归 ​

递推 ​

二分 ​

整数二分 ​

浮点数二分 ​

前缀和 ​

前缀和与差分 ​

前缀和 ​

差分 ​

搜索 ​

深度优先搜索 ​

广度优先搜索 ​

双端队列广搜 ​

双向广搜 ​

A*算法 ​

图论 ​

拓扑排序 ​

Dijkstra ​

堆优化版 Dijkstra ​

Floyd ​

bellman-ford ​

spfa ​

Prim ​

Kruskal ​

数论 ​

质数 ​

约数 ​

欧几里得算法 ​

欧拉函数 ​

算术基本定理 ​

线性筛法 ​

裴蜀定理（扩展欧几里得） ​

动态规划 ​

数字三角形模型 ​

数据结构与算法

OI赛制必备对拍！！！

数据结构

用 new 开数组时间太慢，故在算法题中不适用

数组模拟链表

单链表

应用

双链表

应用

并查集

树状数组与线段树

树状数组

适用问题

常用操作及其相应函数

线段树

常用操作

常用函数

哈希表

<big>841. 字符串哈希 </big>

堆

KMP

算法

枚举、模拟与排序

高精度

高精度加法

高精度减法

高精度乘法

高精度除法

递归与递推

递归

递推

二分

整数二分

浮点数二分

前缀和

前缀和与差分

前缀和

差分

搜索

深度优先搜索

广度优先搜索

双端队列广搜

双向广搜

A*算法

图论

拓扑排序

Dijkstra

堆优化版 Dijkstra

Floyd

bellman-ford

spfa

Prim

Kruskal

数论

质数

约数

欧几里得算法

欧拉函数

算术基本定理

线性筛法

裴蜀定理（扩展欧几里得）

动态规划

数字三角形模型