#include<bits/stdc++.h>
using namespace std;
const int N = 1010;
int f[N][N];
char s[N], ch[N];

int main()
{
    int n, m;
    cin >> n >> (s + 1);
    cin >> m >> (ch + 1);
    for(int i = 0;i <= n;i++) f[i][0] = i;
    for(int i = 0;i <= m;i++) f[0][i] = i;
    for(int i = 1;i <= n;i++) {
        for(int j = 1;j <= m;j++) {
            f[i][j] = min(f[i - 1][j], f[i][j - 1]) + 1;
            if(s[i] != ch[j]) f[i][j] = min(f[i][j], f[i - 1][j - 1] + 1);
            else f[i][j] = min(f[i][j], f[i - 1][j - 1]);
        }
    }
    cout << f[n][m] << endl;
    return 0;
}

#include<bits/stdc++.h>
using namespace std;
const int N = 100010;
int a[N], q[N];
int main()
{
    int n;
    cin >> n;
    for(int i = 0;i < n;i++) cin >> a[i];
    q[0] = -2e9;
    int len = 0;
    for(int i = 0;i < n;i++) {
        int l = 0, r = len;
        while(l < r) {
            int mid = l + r + 1 >> 1;
            if(q[mid] < a[i]) l = mid;
            else r = mid - 1;
        }
        len = max(len, r + 1);
        q[r + 1] = a[i];
    }
    cout << len << endl;
    return 0;
}

附近最小(蓝桥杯模拟题2023)

题目来源
https://www.lanqiao.cn/problems/2415/learning/?page=1&first_category_id=1&sort=students_count&name=%E9%99%84%E8%BF%91%E6%9C%80%E5%B0%8F

解释

参考滑动窗口一题

#include<bits/stdc++.h>
using namespace std;
const int N = 2000010;
int f[N], q[N], p[N];
int main()
{
    int n, k;
    cin >> n;
    for(int i = 1;i <= n;i++) cin >> f[i];
    cin >> k;
    int t = k * 2 + 1;
    //继续开数给数组
    for(int i = n + 1;i <= n + k;i++) f[i] = 0x3f3f3f3f;
    //队列
    //hh是队头，tt是队尾
    int hh = 0, tt = -1;
    for(int i = 1;i <= n + k;i++) {
        //当队列不为空的同时呢，满足队列元素大于等于t，即2 * k + 1时，删除队头元素
        if(hh <= tt && i - t + 1 > q[hh]) hh++;
        //当队列不为空的同时呢，满足队列里面是单调递增的，不满足的话就删除队尾元素
        while(hh <= tt && f[q[tt]] >= f[i]) tt--;
        //添加新的元素进到队列里面
        q[++tt] = i;
        //满足队列里面的元素是 i - k >= 1 的，即找到一组解，输出答案
        if(i - k - 1 >= 0) cout << f[q[hh]] << ' ';
    }
    return 0; 
}

两点路径问题

想法来源

在周四晚上pta竞选赛时写了一道题目，题目给出了一个无向图，没有闭环，给出了两个点a, b, 要求求出a到b之间有多少种路径，输出路径的数量，在考试的时候我直接跳过了，因为当时时间紧任务重没思路跳过了，考完试后便开始思考这道题怎么写，可以计算出所有路径的同时还可以把路径给输出出来，于是乎，便有了这么一个学习笔记(逼真)！

下面我们来模拟来一道题目

模拟题目

给定一个无向图，不存在重根和闭环，给出两个点n, m，要求求出从n点开始到m点有多少种走法，请输出所有的走法和走法的数量

输入格式

第一行输入两个值n和m，分别表示点的数量和路径数

第2行到第n + 1行， 输入两个点a , b，表示a点和b点之间有一条双向路径

最后一行输入两个点op和ed，表示询问op到ed有多少条路可走

输出格式

输出所有可行的路径，隔行输出走法的数量

数据范围

1 <= n, m <= 10^3

样例输入：

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

样例输出：

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

题解(算法分析)

由于题目要求我们把所有的路径给输出出来，所以我们可以运用深度优先搜索进行暴搜，对于路径的存储，我们可以使用一个二维数组，或者可以写一个邻接矩阵来写，两种都行，下面给出的是邻接矩阵的写法，这样即使n和m的数据范围开到10^5也是可以存储的，只是dfs不一定可以跑那么快

我们可以开一个数组来存储可能的情况

邻接矩阵写法：

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

dfs写法：

void dfs(int x) {
    //如果x是ed的话就说明找到一组解了
    if(x == ed) {
        //把记忆数组输出
        for(int i = 0;i < res;i++) {
            cout << dist[i] << ' ';
        }
        cout << ed << endl;
        return;
    }
    //x搜过了，判断为true
    st[x] = true;
    //把x加入记忆数组中
    dist[res++] = x;
    //遍历x与哪些点相交
    for(int i = h[x];i != -1;i = ne[i]) {
        int j = e[i];
        //如果这个点没有被遍历过
        if(!st[j]) {
            //对这个点进行dfs
            dfs(j);
        }
    }
    //还原现场
    st[x] = false;
    res--;
}

全代码 — 纯净版

#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
const int N = 1010;
typedef long long ll;
int dist[N];
int n, m, res, sum;
int op, ed;
int ne[N], e[N], idx, h[N];
bool st[N];
void add(int a, int b) {
    e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}

void dfs(int x) {
    if(x == ed) {
        for(int i = 0;i < res;i++) {
            cout << dist[i] << ' ';
        }
        cout << ed << endl;
        sum++;
        return;
    }
    st[x] = true;
    dist[res++] = x;
    for(int i = h[x];i != -1;i = ne[i]) {
        int j = e[i];
        if(!st[j]) {
            dfs(j);
        }
    }
    st[x] = false;
    res--;
}
int main()
{
    cin >> n >> m;
    memset(h, -1, sizeof(h));
    for(int i = 1;i <= m;i++) {
        int a, b;
        cin >> a >> b;
        add(a, b), add(b, a);
    }
    cin >> op >> ed;
    dfs(op);
    cout << sum << endl;
    return 0;
}

#include<bits/stdc++.h>
using namespace std;
const int N = 233333;
typedef long long ll;

void pmi(int a, int k, int p) {
    int res = 1;
    while(k) {
        if(k & 1) res = (ll)res * a % p;
        a = (ll)a * a % p;
        k >>= 1;
    }
    cout << res << endl;
}

int main()
{
    int x, n;
    cin >> x >> n;
    pmi(x, n, N);
    return 0;
}

#include<bits/stdc++.h>
using namespace std;
const int N = 100010;
int dist[N];
int n, m;
int ne[N], e[N], idx, h[N];
bool st[N];
void add(int a, int b) {
    e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}

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(dist[j] == 0 || find(dist[j])) {
                dist[j] = x;
                return true;
            }
        }
    }
    return false;
}
int main()
{
    int n, m;
    cin >> n >> m;
    memset(h, -1, sizeof(h));
    for(int i = 1;i <= n;i++) {
        int t;
        cin >> t;
        while(t -- ) {
            int b;
            cin >> b;
            add(i, b);
        }
    }
    int res = 0;
    for(int i = 1;i <= n;i++) {
        memset(st, false, sizeof(st));
        if(find(i)) res ++;
    }
    cout << res << endl;
    return 0;
}

#include<bits/stdc++.h>
using namespace std;
const int N = 1010;
int pri[N], idx;
bool st[N];
bool isprime(int x) {
    for(int i = 2;i < x;i++) {
        if(x % i == 0) return false;
    }
    return true;
}

int main()
{
    vector<int> dist;
    for(int i = 2;i <= 1000;i++) {
        if(isprime(i)) pri[idx++] = i, st[i] = true;
    }
    for(int i = 1;i < idx;i++) {
        int x = pri[i - 1] + pri[i] + 1;
        if(st[x]) dist.push_back(x); 
    }
    int T, n, k;
    cin >> T;
    while(T -- ) {
        cin >> n >> k;
        if(dist.size() < k || dist[k - 1] > n) cout << "NO" << endl;
        else cout << "YES" << endl;
    }
    return 0;
}

#include<bits/stdc++.h>
using namespace std;
const int N = 200010;
int n, m, k, t;
int ne[N], e[N], idx, w[N], h[N], target[N];
int dist[N];
bool st[N];
queue<int> q;

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

void spfa() {
    while(q.size()) {
        auto x = q.front();
        q.pop();
        st[x] = false;
        for(int i = h[x];i != -1;i = ne[i]) {
            int y = e[i], z = target[i];
            if(dist[z] > max(dist[x], dist[y]) + max(w[x], w[y])) {
                dist[z] = max(dist[x], dist[y]) + max(w[x], w[y]);
                if (!st[z])
                {
                    q.push(z);
                    st[z] = true;
                }
            }
        }
    }
}

int main()
{
    memset(h, -1, sizeof(h));
    cin >> n >> m >> k >> t;
    for(int i = 1;i <= n;i++) cin >> w[i];
    memset(dist, 0x3f, sizeof(dist));

    for(int i = 1;i <= m;i++) {
        int x;
        cin >> x;
        dist[x] = 0;
        q.push(x);
        st[x] = true;
    }
    for(int i = 1;i <= k;i++) {
        int a, b, c;
        cin >> a >> b >> c;
        add(a, b, c), add(b, a, c);
    }
    spfa();
    cout << dist[t] << endl;
    return 0;
}

#include<bits/stdc++.h>
using namespace std;
const int N = 1010;
int dist[N][N], last[N][N];
int n, m;
bool st[N][N], sk[N];


void floyd()
{
    for(int k = 1;k <= n;k++)
        for(int i = 1;i <= n;i++)
            for(int j = 1;j <= n;j++)
                dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
}

void floyd2()
{
    for(int k = 1;k <= n;k++)
        for(int i = 1;i <= n;i++)
            for(int j = 1;j <= n;j++)
                last[i][j] = min(last[i][j], last[i][k] + last[k][j]);
}

int main()
{
    cin >> n >> m;
    int ans1, ans2;
    memset(dist, 0x3f, sizeof(dist));
    for(int i = 1;i <= n;i++) {
        dist[i][i] = 0;
        st[i][i] = true;
    }
    for(int i = 1;i <= m;i++) {
        int a, b;
        cin >> a >> b;
        dist[a][b] = dist[b][a] = 1;
        st[a][b] = st[b][a] = true;
    }
    floyd();
    ans1 = dist[1][n];
    memset(last, 0x3f, sizeof(last));
    for(int i = 1;i <= n;i++) {
        for(int j = 1;j <= n;j++) {
            if(!st[i][j]) {
                if(i == j) last[i][j] = last[j][i] = 0;
                else last[i][j] = last[j][i] = 1;
                st[i][j] = st[j][i] = true;
            } 
        }
    }
    floyd2();
    ans2 = last[1][n];
    if(ans1 > 0x3f3f3f3f / 2 || ans2 > 0x3f3f3f3f / 2) cout << -1 << endl;
    else cout << max(ans1, ans2) << endl;
    return 0;
}

对其他人的题解的理解

#include<bits/stdc++.h>
using namespace std;
const int N = 1000010;
char s[N];
int nxt[N];

int main()
{
    cin >> (s + 1);
    int n = strlen(s + 1);
    int head = 1, len = 1;
    printf("%d %d\n", 1, 1);
    //cout << 1 << ' ' << 1 << endl;
    for(int i = 2;i <= n;i++) {
        //判断是否要刷新最大字符串
        if(s[i] > s[head]) {
            head = i;
            len = 1;
            printf("%d %d\n", head, head);
            //cout << head << ' ' << head << endl;
            continue;
        }
        //判断在不刷新首字母大小的同时更新首字母的位置和字符串的长度
        //就是更新除开第一个字符以外的，判断是否要更新其它字符
        while(nxt[len] != 0 && s[head + nxt[len]] < s[i]) {
            head = head + len - nxt[len];
            len = nxt[len];
        }
        //找到和当前最大字符串中字符重复的位置
        if(s[head + nxt[len]] == s[i]) {
            nxt[len + 1] = nxt[len] + 1;
            len++;
        }
        //排除掉不可能的位置
        else if(s[head + nxt[len]] > s[i]) {
            nxt[++len] = 0;
        }
        printf("%d %d\n", head, head + len - 1);
        //cout << head << ' ' << head + len - 1 << endl;
    }
    return 0;
}