class Solution {
public:
    // 最小化最大值
    // 二分 + check贪心
    // 技巧：限制是最大间距，所以是至少t个，题目一定要用m个，如果t > m, return false

    bool check(int mid, int m, vector<int>& nums) {
        int sum = 0, t = 0;
        for (int i = 0; i < nums.size(); i ++) {
            if (nums[i] > mid) return false; // 单个元素已超过最大间距
            if (sum + nums[i] > mid) {
                t ++;
                sum = nums[i];
            } else {
                sum += nums[i];
            }
        }
        t ++; // 最后一段
        // 至少t个，但题目一定要用m个
        if (t > m) return false; // 先去看不满足条件的情况
        return true;

    }

    int splitArray(vector<int>& nums, int m) {
        int l = 1, r = 1e9;
        while (l < r) {
            int mid = l + r >> 1;
            if (check(mid, m, nums)) r = mid;
            else l = mid + 1;
        }
        return l;
    }
};

这题数据范围很小，可以用floyd来做，不过这里我用的是spfa算法（因为也挺好写的啦）

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

using namespace std;

const int N = 410, M = N;
int n, m;

int e[M], ne[M], w[M], idx, h[N];
bool st[N];
int dist[N];

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

int spfa() {
    memset(dist, 0x3f, sizeof dist);
    dist[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 (dist[j] > dist[t] + w[i]) {
                dist[j] = dist[t] + w[i];
                if (st[j] == false) {
                    q.push(j);
                    st[j] = true;
                }
            }
        }
    }

    int res = 0;
    for (int i = 1; i <= n; i ++) {
        res = max(res, dist[i]);
    }

    if (res == 0x3f3f3f3f) return -1;
    return res;
}

int main() {
    cin >> n >> m;

    memset(h, -1, sizeof h);

    for (int i = 0; i < m; i ++) {
        int a, b, c;
        cin >> a >> b >> c;
        add(a, b, c), add(b, a, c);
    }    

    cout << spfa() << endl;

    return 0;
}

这种题不难的，但一定要画图来解，画个图很清楚的（分步骤画），用两个指针进行交换两个节点的操作。

画图分析完后，按照图的步骤一步步写代码就行了

迭代写法：时间O(n)，空间O(1)

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    // 迭代写法
    ListNode* swapPairs(ListNode* head) {
        auto dummy = new ListNode(-1); // 创建一个虚拟头结点
        dummy->next = head;
        auto p = dummy;
        while (p->next != NULL && p->next->next != NULL) {
            auto a = p->next, b = p->next->next; // (1)
            p->next = b;           // (2) 
            a->next = b->next;     // (3)
            b->next = a;           // (4)
            p = a;                 // (5)
        }
        return dummy->next;
    }
};

class Solution {
public:
    // (s + s).find(s, 1) 这个时间复杂度是O(m*n)的
    // 字符串哈希，时间复杂度O(n)
    // abcabcabcabcabcabc
    //    abcabcabc
    typedef unsigned long long ULL;
    static const int N = 2e4 + 7, P = 131;
    ULL h[N], p[N];

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

    bool repeatedSubstringPattern(string s) {
        int n = s.size();
        s = " " + s + s;

        p[0] = 1;
        for (int i = 1; i <= 2 * n; i ++) {
            h[i] = h[i - 1] * P + s[i];
            p[i] = p[i - 1] * P;
        }

        for (int i = 2; i <= n; i ++) {
            if (get(i, i + n - 1) == get(1, n)) {
                return true;
            }
        }
        return false;
    }
};

#include <iostream>

using namespace std;

int f[6010];

int main() {
    int n, m;
    cin >> n >> m;

    for (int i = 1; i <= n; i ++) {
        int v, w, s;
        cin >> v >> w >> s;
        // 这样写多重背包问题II，必须要用一维的f[]，因为我没有去统计有多少个01背包物品
        for (int k = 1; k <= s; k *= 2) {
            for (int j = m; j >= k * v; j --) {
                f[j] = max(f[j], f[j - k * v] + k * w);
            }
            s -= k;
        }
        if (s > 0) {
            for (int j = m; j >= s * v; j --) {
                f[j] = max(f[j], f[j - s * v] + s * w);
            }
        }
    }

    cout << f[m] << endl;

    return 0;
}

// 八皇后遍历题型：整个棋盘是一个状态，需要恢复现场(回溯法)
#include <iostream>
#include <cstring>

using namespace std;

const int N = 12;
int n, m, sx, sy;
int res; // 用于统计全局答案
bool g[N][N];
int dx[] = {1, 1, -1, -1, 2, 2, -2, -2};
int dy[] = {2, -2, 2, -2, 1, -1, 1, -1};

// dfs功能：返回有多少中途径能走完棋盘
void dfs(int u, int x, int y) {
    if (u == n * m) {
        res ++;          
        return;
    }

    for (int d = 0; d < 8; d ++) {
        int a = x + dx[d], b = y + dy[d];
        if (0 <= a && a < n && 0 <= b && b < m && g[a][b] == false) {
            g[a][b] = true;
            dfs(u + 1, a, b);
            g[a][b] = false;
        }
    }

}

int main() {
    int T;
    cin >> T;

    while (T --) {
        cin >> n >> m >> sx >> sy;
        memset(g, false, sizeof g);
        res = 0; // 每组初始化res
        g[sx][sy] = true;
        dfs(1, sx, sy);         
        cout << res << endl;
    }

    return 0;
}

字符串哈希模板题

#include <iostream>

using namespace std;

typedef unsigned long long ULL;
const int N = 1e6 + 7, P = 131;
ULL h[N], p[N];

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

int main() {
    string s;
    cin >> s;

    int n = s.size();
    s = " " + s;

    p[0] = 1;
    for (int i = 1; i <= n; i ++) {
        h[i] = h[i - 1] * P + s[i];
        p[i] = p[i - 1] * P;
    }

    int m;
    cin >> m;

    while (m --) {
        int l1, r1, l2, r2;
        cin >> l1 >> r1 >> l2 >> r2;
        if (get(l1, r1) == get(l2, r2)) puts("Yes");
        else puts("No");
    }

    return 0;
}

思路：这个题其实就是一个分组背包问题，每组物品可以选0, 1, … M个设备，求最大盈利值不难，稍微难的是求出具体方案，不过这种题我写多了，很熟悉，只要记录下当前 $f[i][j]$ 这个状态是从哪个物品转移过来的即可，也就是第 $i$ 组物品选了几个设备， $path[i][j] = k$ 表示$i,j$这个状态选了 $k$。

// 分组背包 + 逆推方案
#include <iostream>
#include <cstring>

using namespace std;

const int N = 16;

int f[N][N];
int w[N][N];
int path[N][N];


int main() {
    int n, m;
    cin >> n >> m;

    for (int i = 1; i <= n; i ++) {
        for (int j = 1; j <= m; j ++) {
            cin >> w[i][j]; // 第i个公司分配j台机器时的盈利值
        }
    }

    // 分组背包
    // f[i][j]表示只在前i个公司分配设备，且设备数不超过j的最大盈利值
    for (int i = 1; i <= n; i ++) {
        for (int j = 0; j <= m; j ++) {
            for (int k = 0; k <= m; k ++) { // 从第i组物品中去选，只能选其中一个。设备数k可以为0
                if (j >= k) {
                    if (f[i][j] < f[i - 1][j - k] + w[i][k]) {
                        f[i][j] = f[i - 1][j - k] + w[i][k];
                        path[i][j] = k; // i,j这个状态选了k
                    }
                }
            }
        }
    }

    cout << f[n][m] << endl;

    // 逆推：求出每组选了哪种物品
    int i = n, j = m;
    while (i >= 1 && j >= 0) {
        cout << i << " " << path[i][j] << endl;
        j -= path[i][j];
        i --;
    }

    return 0;
}

思路：这个题其实就是一个分组背包问题，每组物品可以选0, 1, … M个设备，求最大盈利值不难，稍微难的是求出具体方案，不过这种题我写多了，很熟悉，只要记录下当前 $f[i][j]$ 这个状态是从哪个物品转移过来的即可，也就是第 $i$ 组物品选了几个设备， $path[i][j] = k$ 表示$i,j$这个状态选了 $k$。

// 分组背包 + 逆推方案
#include <iostream>
#include <cstring>

using namespace std;

const int N = 16;

int f[N][N];
int w[N][N];
int path[N][N];


int main() {
    int n, m;
    cin >> n >> m;

    for (int i = 1; i <= n; i ++) {
        for (int j = 1; j <= m; j ++) {
            cin >> w[i][j]; // 第i个公司分配j台机器时的盈利值
        }
    }

    // 分组背包
    // f[i][j]表示只在前i个公司分配设备，且设备数不超过j的最大盈利值
    for (int i = 1; i <= n; i ++) {
        for (int j = 0; j <= m; j ++) {
            for (int k = 0; k <= m; k ++) { // 从第i组物品中去选，只能选其中一个。设备数k可以为0
                if (j >= k) {
                    if (f[i][j] < f[i - 1][j - k] + w[i][k]) {
                        f[i][j] = f[i - 1][j - k] + w[i][k];
                        path[i][j] = k; // i,j这个状态选了k
                    }
                }
            }
        }
    }

    cout << f[n][m] << endl;

    // 逆推：求出每组选了哪种物品
    int i = n, j = m;
    while (i >= 1 && j >= 0) {
        cout << i << " " << path[i][j] << endl;
        j -= path[i][j];
        i --;
    }

    return 0;
}

class Solution {
public:
    int longestConsecutive(vector<int>& nums) {
        unordered_set <int> hash; // 只要是unordered开头，都是哈希
        for (auto x : nums) hash.insert(x);

        int res = 0;
        for (auto num : nums) {
            // set已经去重：2,3,4,5  8,9, 20,21,22
            // 只去计算2, 8, 20
            if (hash.count(num - 1) == 0) {
                int end = num;
                while (hash.count(end)) end ++;
                res = max(res, end - num);
            }
        }
        return res;
    }
};