刷题总结

前言

这里记录了一些补题和总结。
从头看到尾，算是一条学习算法的时间线。

方法技巧总结

在句子字符串中对单词的处理

（句子字符串代指所有其中含有空格或换行符的字符串）

读入问题

  1. 对 char a[N]类型的字符数组的读入

    1
    2
    fgets(a,sizeof a,stdin);
    //stdin表示从键盘中读入

  2. 在 c++中对 string a 的读入

    1
    getline(cin,a);

  3. 在已知单词数目的情况下直接逐个读入单词

    1
    2
    3
    4
    5
    6
    for(int i = 0;i<n;i++)
    {
    	string a;
    	cin >> a;
    }
    //n是字符串中单词的数目，每次读入的a就是其中的单个的单词

逐个分析单词

使用字符串流来分割句子

1
2
3
4
5
6
7
#include <sstream>
istringstream iss(a);
string word;
while(iss >> word)
{
	//在这个循环中可以对每一个单词进行处理
}

使用方法三读入可以直接在循环中逐个分析单词

string 中 find 函数的使用

find 的原型如下

1
size_t find(const string& str, size_t pos = 0) const noexcept;

其中 str 是要查找的子字符串，pos 是开始查找的位置，默认为 0(pos 在 find 函数中可以省略)

返回值：如果找到子字符串，返回子字符串的第一个字符在原字符串中的位置；如果没有找到，返回 npos（一个常数）

一般的用法如下

1
2
3
4
//比如我们要查找的子字符串是lec
string sentence;
string temp = "lec";
auto weizhi = sentence.find(temp,0);

方格图小技巧

1.分析上下左右

在分析一个点上下左右的坐标时，我们可以先写出上下左右的四个向量，在需要分析时直接循环加上即可

1
2
3
4
5
6
7
8
9
int D[4][2] = {{-1,0},{1,0},{0,-1}.{0,1}};
int x,y;//假设x，y即为现在节点的横纵坐标

for(int i = 0;i < 4;i ++)
{
	int xx = x + D[i][0]; int yy = y + D[i][1];
	//后续直接对点（xx，yy）进行分析即可
	//这样就可以在一个循环中处理上下左右四个点
}

2.对角线的表示

对于一个 n*n 的矩形方格图，我们用每条对角线的纵截距 b 来作为它的编号，则

对于点（u，i），它所在的对角线分别是 d[u+i]和 d[i-u+n]

这里加上 n 是给它一个偏移量让数组的下标始终是大于 0 的

3.方格图中信息变字符串

把一个 n*m 的矩形方格图中的量按顺序写进字符串中，那么方格图中的某个元素（x，y）和其在字符串中的位置 k 存在这样的关系

$ x = \left\lfloor \frac{k}{n} \right\rfloor $ //代表向下取整

$ y = k % n $

注意这里的矩形必须是从行到列遍历的

货仓选址小结论

在一条数轴上有 n 个商店坐标分别为 a[0]~a[n-1]，当且仅当货仓建在这个数组的中位数的位置上时，货仓到每家店的距离之和最小。

什么时候用 DFS

那什么时候可以用到 DFS 呢？总结来说，当问题需要枚举所有可能的解，并且问题的结构适合逐步构建解的时候，可以考虑 DFS。例如排列问题、组合问题、路径问题等。在这种情况下，DFS 通过递归或者栈的方式，尝试每一种可能的选择，并回溯到上一步尝试其他选择，直到找到解或者遍历完所有可能性。

即如果我们想要枚举一下答案的某一种情况然后对于每一种情况判断其合法性的话我们就可以用 dfs

虽然是一种暴力搜索 但是面对数据量较小的时候还是能很好地解决问题

当我们有想法想要把所有的方案都枚举出来找合法解的时候 就可以想想能不能 dfs

统计出现次数

当需要统计某些元素的出现次数时，可以用以下几种数据结构

map set 哈希

map 可以通过键对关系储存每一种元素的出现次数 可以避免重复的情况 好处是可以直接通过键对值得到元素的出现次数

set 可以直接把元素塞进去 不用考虑是否重复 因为最后只会留下不同的元素 好处是插入后的元素是默认从小到大排序的

但坏处是如果要记录次数的话 还需要另外开一个 map 来记载一下出现次数

1
2
3
4
set<int> a;
a.insert(); a.size(); a.empty(); a.clear(); a.find(); //find函数跟其他地方一样 如果没有找到还是返回end()迭代器
//可以用for循环遍历set
for(int num : a)

哈希我不太常用 先略去

关于倍数问题的小结论

两个数 a,b，如果(a - b) % c == 0 那么一定有 a % c == b % c

依靠这个结论 可以避免全部枚举 只需要记录余数相同的位置即可 具体可以看下面的题 （P3131）

DFS 的两种应用

DFS 求连通块

可以理解为 洪水从外到内渗透 统计渗透不到的点 可以用染色法解决 即我们把所有可以搜索到的点都进行染色 最后没有被染色的点就是需要求的点 下面是两道例题

image-20250408110315030

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

int dx[] = {1,-1,0,0};
int dy[] = {0,0,1,-1};
int a[510][510];
int m,n;

void dfs(int x,int y) {
    a[x][y] = 1; // 能被搜索到的地方进行染色
    for(int i = 0;i < 4;i ++){ //向四周蔓延
        int x0 = x + dx[i]; int y0 = y + dy[i];
        if(x0 >= 0 && x0 < n && y0 >= 0 && y0 < m && a[x0][y0] == 0 ) dfs(x0,y0); // 起点变为下一个可以搜到的地方
    }
}

int main()
{
    cin >> n >> m;
    for(int i = 0;i < n;i ++){
        for(int j = 0;j < m;j ++) {
            char c; cin >> c;
            if(c == '*') a[i][j] = 1;
            else if(c == '0') a[i][j] = 0;
        }
    }
    //注意一定是从边界往里搜的  所以只需要搜索第一列 最后一列 第一排 最后一排
    for(int i = 0;i < m;i ++) {
        if(a[0][i] == 0) dfs(0,i);
        if(a[n - 1][i] == 0) dfs(n - 1,i);
    }

    for(int i = 0;i < n;i ++) {
        if(a[i][0] == 0) dfs(i,0);
        if(a[i][m - 1] == 0) dfs(i,m - 1);
    }

    int cnt = 0;
    for(int i = 0;i < n;i ++) {
        for(int j = 0;j < m;j ++) {
            if(a[i][j] == 0) cnt ++;
        }
    }

    cout << cnt << endl;



}

image-20250408110917640

这道题不一样的地方在于 搜索过的染色应该用其他数字标记 才能在最后复原矩阵 （当然开两个数组也可以 但是有点麻烦）

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

int dx[] = {1,0,-1,0};
int dy[] = {0,1,0,-1};
int n,a[35][35];

void dfs(int x,int y) {
    a[x][y] = 3;
    for(int i = 0;i < 4;i ++) {
        int x0 = x + dx[i];
        int y0 = y + dy[i];
        if(x0 >= 0 && x0 < n && y0 >=0 && y0 < n && a[x0][y0] == 0) dfs(x0,y0);
    }
}

int main()
{
    cin >> n;
    for(int i = 0;i < n;i ++) {
        for(int j = 0;j < n;j ++) cin >> a[i][j];
    }

    for(int i = 0;i < n;i ++) {
        if(a[0][i] == 0) dfs(0,i);
        if(a[n - 1][i] == 0) dfs(n - 1,i);
    }

    for(int i = 0;i < n;i ++) {
        if(a[i][0] == 0) dfs(i,0);
        if(a[i][n - 1] == 0) dfs(i,n - 1);
    }

    int cnt = 0;
    for(int i = 0;i < n;i ++) {
        for(int j = 0;j < n;j ++) {
            if(a[i][j] == 0) a[i][j] = 2;
            if(a[i][j] == 3) a[i][j] = 0;
        }
    }

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

    return 0;

}

DFS 求所有排列

即爆搜出所有的可能排列 然后判断是否存在满足条件的排列或者从中选出最优解 一般的 会在搜索过程中进行剪枝 可以看 飞机降落

和 接龙数列 这两道题

是否需要回溯

考虑是否回溯其实就是考虑 dfs 会不会对后续的搜索造成影响 如果会造成影响的话 就应该在搜索后回溯 否则的话就不用回溯

比如在求所有的排列时 某个数是否应用是在搜索过程中改变了的 所以需要在搜索后进行回溯

但在染色法求连通块 或者遍历树这些不改变元素性质 不会重复访问的问题里 就不需要回溯 比如说P2036

在 DFS 中，是否需要显式地在函数开头添加结束条件判断（如if (搜索完) return;），取决于问题的性质和解的生成方式。以下是关键区分点：

1. 何时需要显式结束条件？

当 “解的完整性” 必须在递归的某一层被明确判断时，需要在 DFS 开头检查结束条件。常见场景包括：

  • 组合/排列问题：只有选满特定数量的元素才算有效解（如全排列、组合数问题）。
  • 路径终点问题：必须到达某个特定节点才算解（如迷宫出口、二叉树叶子节点）。
  • 约束满足问题：必须满足所有约束条件才能形成有效解（如数独填满且合法）。
示例：全排列问题

cpp

复制

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
void dfs(vector<int>& path) {
    if (path.size() == n) { // 显式判断是否完成排列
        print(path);
        return;
    }
    for (int i = 1; i <= n; i++) {
        if (!used[i]) {
            used[i] = true;
            path.push_back(i);
            dfs(path);
            path.pop_back();
            used[i] = false;
        }
    }
}

解释：必须显式判断path.size() == n，因为只有选满 n 个数才是一个有效排列。

2. 何时不需要显式结束条件？

当 “解的局部状态” 可以随时更新答案，且递归的终止由无法继续搜索隐式触发时，无需显式结束判断。常见场景包括：

  • 最长/最短路径问题：每一步都可能更新当前最优解（如字符串拼接最长长度）。
  • 连通性/遍历问题：递归自然终止于无法继续扩展的节点（如岛屿数量、图的遍历）。
示例：字符串拼接问题

cpp

复制

1
2
3
4
5
6
7
8
void dfs(string current) {
    ans = max(ans, current.length()); // 随时更新答案
    for (auto& s : candidates) {
        if (can_append(current, s)) {
            dfs(append(current, s)); // 隐式终止于无法拼接
        }
    }
}

解释：每次递归都尝试延长当前字符串，并更新最大长度。当无法继续拼接时，循环自然结束，无需显式判断终止。

3. 关键区分原则

特征 需要显式结束条件 不需要显式结束条件
解的形式 必须完整（如全排列） 局部状态即可更新（如最长路径）
递归终止触发方式 显式判断完整性后返回 无法继续搜索时自然返回
答案更新时机 仅在完整解时更新 每一步都可能更新

BFS

BFS 具有最短路性质 即它是贪心的 每一步都选择了最优解 因为每次搜索都选择的是距离最近的点（队列实现）

模板

1
2
3
4
5
6
7
8
9
10
queue<类型>Q;
Q.push(最初状态);
while(!Q.empty()){
	类型 u=Q.front(); Q.pop(); //每次处理的下一步就是这里的u
	for(枚举所有可扩展到的状态){
		if(满足入队条件){
			Q.push(状态); //维护某些必要信息
		}
	}
}

例题

image-20250408163244410

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 <bits/stdc++.h>
using namespace std;
typedef pair<int,int> pp;
#define fi first
#define se second

const int N = 1005;
int vi[N],k[N];

int main()
{
    int n,a,b; cin >> n >> a >> b;
    for(int i = 1;i <= n;i ++) cin >> k[i];
    if(a == b) {
        cout << 0 << endl;
        return 0;
    }
    queue<pp> q;
    q.push({0,a}); //初始状态 pair里fi代表现在按了几次键 se代表现在的楼层（id）
    while(!q.empty()) {
        pp u = q.front();
        if(u.se == b) {
            cout << u.fi << endl;
            return 0;
        }
        q.pop();
        if(u.se + k[u.se] <= n && vi[u.se + k[u.se]] == 0) {
            q.push({u.fi + 1,u.se + k[u.se]});
            vi[u.se + k[u.se]] = 1;
        }
        if(u.se - k[u.se] >= 1 && vi[u.se - k[u.se]] == 0) {
            q.push({u.fi + 1,u.se - k[u.se]});
            vi[u.se - k[u.se]] = 1;
        } //注意这里不要用else if 因为这两种情况是有可能同时成立的 所以要直接用两个if
    }
    cout << -1 << endl;
    return 0;


}

选数问题

从 n 个数中选择 k 个数 要想没有遗漏地枚举出所有的选择情况 就必须遵循 不降原则

即每次选择的时候不选择比上次选择的数小的数字

比如说要从 n 个数中选择 3 个数 那么最暴力的枚举就应该是

1
2
3
4
5
6
7
for(int i = 0;i < n;i ++) {
	for(int j = i + 1;j < n;j ++) {
		for(int k = j + 1;k < n;k ++) {
			//选出的三个数即为i j k
		}
	}
}

一道例题

image-20250408193853045

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

const int N = 22;
int n,k,cnt;
int x[N],vi[N];

bool check(int u) {
    for(int i = 2;i <= u / i;i ++) {
        if(u % i == 0) return false;
    }
    return true;
}

void dfs(int u,int sum,int now) { // 用now来记录上次选择的数的下一个 从而遵循不降原则
    if(u == k) {
        if(check(sum)) cnt ++;
        return;
    }
    //通过不降原则实现dfs
    for(int i = now;i < n;i ++) {
        dfs(u + 1,sum + x[i],i + 1);
    }
}

int main()
{
    cin >> n >> k;
    for(int i = 0;i < n;i ++) cin >> x[i];
    dfs(0,0,0);
    cout << cnt << endl;
    return 0;

}

洛谷刷题小记

P1083 借教室

像题目中这样，有一天不满足其后的每一天都不满足的情况就完全满足二分答案的单调性特征。

当题目中的数据范围能恰好达到 1e9 时，不妨在作运算的量上开 longlong 防止加和后超过 2e9 爆 int

1
代码见https://www.luogu.com.cn/problem/P1083#submit

P1030 求先序排列

1. 先序遍历（Pre-order Traversal）

定义：先序遍历按照以下顺序访问二叉树的节点：

  • 访问根节点。
  • 先序遍历左子树。
  • 先序遍历右子树。

特点：先访问根节点，然后依次访问左右子树。对于每个子树，也遵循同样的规则。

应用：常用于创建树的复制或输出树的结构信息，因为它首先处理根节点。

示例： 假设有一棵如下所示的二叉树：

深色版本

1
2
3
4
5
    A
   / \
  B   C
 / \   \
D   E   F

先序遍历的顺序为：A -> B -> D -> E -> C -> F

2. 中序遍历（In-order Traversal）

定义：中序遍历按照以下顺序访问二叉树的节点：

  • 中序遍历左子树。
  • 访问根节点。
  • 中序遍历右子树。

特点：先访问左子树，再访问根节点，最后访问右子树。对于每个子树，也遵循同样的规则。

应用：广泛应用于二叉搜索树（BST），因为中序遍历会以升序访问节点值，适用于排序和查找操作。

示例： 对于上述相同的二叉树，中序遍历的顺序为：D -> B -> E -> A -> C -> F

注意这里是递归的先访问子树再访问这个子树的根，不断向上寻找

3. 后序遍历（Post-order Traversal）

定义：后序遍历按照以下顺序访问二叉树的节点：

  • 后序遍历左子树。
  • 后序遍历右子树。
  • 访问根节点。

特点：先访问左右子树，最后访问根节点。对于每个子树，也遵循同样的规则。

应用：常用于释放树占用的内存或计算表达式的值，因为在删除或计算时通常需要先处理子节点再处理父节点。

示例： 对于上述相同的二叉树，后序遍历的顺序为：D -> E -> B -> F -> C -> A

总结

  • 先序遍历：根 -> 左 -> 右
  • 中序遍历：左 -> 根 -> 右
  • 后序遍历：左 -> 右 -> 根

示例图解

为了更直观地理解，我们可以通过一个简单的二叉树来展示这三种遍历的结果：

深色版本

1
2
3
4
5
    1
   / \
  2   3
 / \
4   5
  • 先序遍历：1 -> 2 -> 4 -> 5 -> 3
  • 中序遍历：4 -> 2 -> 5 -> 1 -> 3
  • 后序遍历：4 -> 5 -> 2 -> 3 -> 1
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
如果当前子树范围无效（即 ml > mr 或 al > ar），直接返回。
输出后序遍历中的最后一个元素 aft[ar]，这是当前子树的根节点。
查找这个根节点在中序遍历中的位置 k。

根据找到的位置 k，递归处理左子树和右子树：

左子树：中序遍历 [ml, k-1] 和后序遍历 [al, al+k-ml-1]。
已知后序遍历序列的起始位置是 al，由于后序遍历的顺序是先左子树，再右子树，最后根节点，所以左子树在后序遍历中的结束位置可以通过以下方式计算：
假设 n 是当前子树的节点数量，对于左子树，其节点数量为 k - ml。
我们从后序遍历序列的起始位置 al 开始，由于左子树有 k - ml 个节点，所以左子树在后序遍历中的结束位置是 al + (k - ml) - 1，也就是 al + k - ml - 1。

右子树：中序遍历 [k+1, mr] 和后序遍历 [al+k-ml, ar-1]。
我们知道左子树的节点数量是 k - ml，所以右子树在后序遍历中的起始位置是 al + (k - ml)，即 al + k - ml。因为左子树在后序遍历中占据了 k - ml 个位置，所以右子树的起始位置是从左子树结束的下一个位置开始。
ar 是整个子树后序遍历的结束位置，由于根节点是最后一个元素，右子树的结束位置是根节点的前一个位置，所以是 ar - 1。


这样每次输出子树的根节点最后就能得出先序排列的结果
代码见https://www.luogu.com.cn/problem/P1030#submit

P10905 [蓝桥杯 2024 省 C] 回文字符串

一开始的想法是直接把字符串右端由 lqb 这三个字符组成的字符串给去掉 如果剩下的字符串回文那么久可以使它变得回文

但是这样做只能过百分之五十，因为没有考虑像 qwq这样的情况

P1044 栈

image-20250328084606790

可以用一个 dp 来做

1.考虑状态 我们设置这样一个函数C(i,j) 其中 i 表示输入序列中待处理的数字 j 表示目前栈中的数字个数

所以我们要求的就是C(n,0) 这个状态

2.状态转移

对于每一次操作显然有两种操作 一是把输入序列中的数压入栈中 c(i - 1,j + 1) 二是把栈中的数压出到输出序列中去

c(i,j - 1)

所以状态转移方程为

$$f_{x,y}=f_{x-1,y+1}+f_{x,y-1}$$

3.边界条件特判

当 i == 0 的时候说明输入序列已经全部输出完 已成序列 说明只有一种走法

当 j == 0 的时候说明栈内还没有数字 只能执行 push 压入操作

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#include <bits/stdc++.h>
using namespace std;
int main()
{
	int n; cin >> n;
	int f[22][22];
	for(int i = 0;i <= n;i ++) {
		for(int j = 0;j <= n;j ++) {
			if(i == 0) f[i][j] = 1;
			else if(j == 0) f[i][j] = f[i - 1][j + 1];
			else f[i][j] = f[i - 1][j + 1] + f[i][j - 1];
		}
	}
	cout << f[n][0];
}

P1359 租用游艇

image-20250328085847167

image-20250328085829365

1.状态表示 : 用 dp[i]来记录从 i 到 n 站之间的最小花费

2.状态转移：假设有三个点 顺序分别为 i j n 那么从 i 到 n 有两种走法 一是从 i - > j ,j - > n 此时花费为 a[i] [j] + dp[j]

二是直接从 i - > n 此时花费为 dp[i] 要最少花费只需要对它们取一个 min 即可

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
//用dp[i]来表示从i到n的最小花费


#include <bits/stdc++.h>
using namespace std;

int a[210][210];
int dp[210];

int main()
{
	int n; cin >> n;
	for(int i = 1;i < n;i ++) {
		for(int j = i + 1;j <= n;j ++) {
			cin >> a[i][j];
			dp[i] = 0x3f3f3f3f; //注意这里需要初始化为正无穷
		}
	}
	for(int i = n - 1;i >= 1;i --) { //所以从后往前遍历
		for(int j = i + 1;j <= n;j ++) { //i为上流 j为i相对的下流
			dp[i] = min(dp[i],a[i][j] + dp[j]);
		}
	}
	cout << dp[1] << endl;
	return 0;
}

P3131（对于倍数问题的优化）

image-20250407201655470

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

//对7取模的结果只会是 0 ~ 6
int last[7],first[7];

int main()
{
    int n; cin >> n; int a[n + 1],sum[n + 1];
    sum[0] = 0;
    for(int i = 1;i <= n;i ++) {
        cin >> a[i];
        sum[i] = (sum[i - 1] + a[i] ) % 7; // 直接记录前缀和对7取模的余数 (a - b) % c == (a % c) - (b % c)
    }
    int ans = 0;

    //滚动数组
    for(int i = n;i >= 1;i --) first[sum[i]] = i; //更新该余数第一次出现的位置
    for(int i = 1;i <= n;i ++) last[sum[i]] = i; //更新该余数最后一次出现的位置

    first[0] = 0; //注意 当一个奶牛都不取的时候  ID为0 余数也为0 没有这个赋值会错

    //枚举余数 从而判断最大长度
    for(int i = 0;i <= 6;i ++) ans = max(ans,last[i] - first[i] );

    cout << ans << endl;

}

P2036

image-20250408171247020

P2196 挖地雷（图上 DFS）

image-20250409233215501

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

const int N = 22;
int a[N][N],n,ans; // 数据比较小 用邻接矩阵来存图
int f[N];
int cnt1,cnt2; //cnt1为op的路径长度 cnt2为p的路径长度
int op[N]; int p[N]; //用op来记录每次的路径 用p来记录最优路径

void dfs(int x,int sum){  //x为起始节点 sum为挖到的地雷数目
	for(int i = x + 1;i <= n;i ++) { //从上往下挖 所以从x + 1开始
		if(a[x][i]) {  //如果连通 则可以继续往下面挖
			op[++cnt1] = i;
			dfs(i,sum + f[i]);
			cnt1 --; //回溯
		}
	}

	if(sum > ans) {
		ans = sum;
		for(int i = 1;i <= cnt1;i ++) p[i] = op[i];
		cnt2 = cnt1;
	}
	return;
}

int main()
{
	cin >> n;
	for(int i = 1;i <= n;i ++) cin >> f[i];
	for(int i = 1;i <= n;i ++) {
		for(int j = i + 1;j <= n;j ++) {
			cin >> a[i][j];
		}
	}
	for(int i = 1;i <= n;i ++) { // 枚举每一个节点作为起点
		op[++cnt1] = i;
		dfs(i,f[i]);
		cnt1 --;
	}
	for(int i=1;i<=cnt2;i++)
	{
		printf("%d ",p[i]);
	}
	printf("\n%d",ans);
	return 0;
}

acm 新生赛

第十六届西南石油大学程序设计新生赛ACM/NOI/CSP/CCPC/ICPC 算法编程高难度练习赛牛客竞赛 OJ

A 小刘的最短路

简单 ifelse 分情况判断，画图分析会更加清晰一点

B 建造新家

image-20241209105805539

对于表达式中的 x++，来观察整个式子值的变化，剔除与初始式子相同的部分，剩下的部分就是每次改变的部分，那么就可以用类似前缀和计算的方法用 o(1)的时间复杂度算出每一个 x 的取值的对应值，最后枚举得以实现 o(n)算法

即我们可以得到每次取 x 的式子表达式变为

$$
\text{now} = \text{f(i)} = \text{f(i-1)} + s1 \times 2 \times (i - 1) - s2 \times 2 + s1
$$

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
#include <bits/stdc++.h>
using i64 = long long;

void solve() {
    int n;
    std::cin >> n;
    std::vector<i64> a(n + 1, 0);
    for (int i = 1; i <= n; ++i) {
        std::cin >> a[i];
    }
    i64 s1 = 0, s2 = 0;
    for (i64 i = 1; i <= n; ++i) {
        s1 += a[i];
        s2 += a[i] * i;
    }
    //预处理式子改变量中的常数部分
    i64 ans = 0, now = 0;
    for (i64 i = 1; i <= n; ++i) {
        now += a[i] * (1 - i) * (1 - i);
    }
    ans = now; // x取1时的表达式值，用于作为初始值

    for (i64 i = 2; i <= n; ++i) {
        now = now + s1 * 2 * (i - 1) - s2 * 2 + s1; //通过上面的公式计算新值（注意上面公式里面的x对应的应该是i-1哦！）
        ans = std::min(ans, now); //枚举x的过程中动态更新答案即可
    }

    std::cout << ans << "\n";
}

这个题中由于表达式是二次函数故而不需要复杂的求导就能直接找到取最小值时的点，故而也可以直接算出 f(i)之和表达式的对称轴，由对称轴计算即可

1
2
3
4
5
//代码在https://ac.nowcoder.com/acm/contest/view-submission?submissionId=74064589
//ceil是向上取整，floor是向下取整
//为什么考试的时候没写对呢?哦哦原来是没有开longlong啊！
//还有需要注意的是因为在运算中用到了i和a[i]，所以它们都需要开成longlong
//答应我，下次算一下看看是不是要开longlong

C 合成大雪球

对于求第 k 小/大的问题，一般都可以想到二分，二分的条件一般是求比它小的元素有多少个，需要注意的是，如果比它小的元素有 k 个那么它应该是第 k+1 小的元素（必须考虑它自身）

对于这个题的数据很明显双遍历得到体积和的方案一定会超时的，由于这里的和由两个元素决定，所以跟之前招新考试的一个题类似，即枚举其中一个数来二分另外一个数。

这是外层的一个二分，即二分另一个数，但同时在这个二分中我们还需要另外一个二分即来二分判断是否是满足第 k 小的条件

1
2
3
4
//考试的时候就一直在想怎么能对遍历求和进行优化
//所以学到了枚举一个数二分另一个数
//不要忘了对题目需要满足的条件进行二分判断
//代码在https://ac.nowcoder.com/acm/contest/view-submission?submissionId=74098503

D 羽毛球比赛

（我还没学 dfs 呢，等会儿再来）

E 小青找宝藏

斐波拉契数列中第 45 项就已经大于 1e9 了，所以对于 0 到 1e9 的 n 来说，直接遍历三个斐波拉契数使其相加等于 n 时间复杂度最多也不过 o(45^3)即 o(91125)，所以是可以直接枚举出答案的

1
2
3
//谁能想到这个题是单纯枚举呢？？？？？
//可以记一下 斐波拉契数列45项就＞1e9，我下次一定会遍历的
//代码见https://ac.nowcoder.com/acm/contest/view-submission?submissionId=74100320

F 矩形面积

单调栈模板题

看过程，需要找到左边小于基准量的第一个位置和右边小于基准量的第一个位置，符合单调栈的工作原理

特别需要注意的是，为了能够进入计算部分，需要在左右分别添加一个值为 0 的哨兵元素，是为了处理数组本身就单调的情况。

1
2
3
4
//谁能想到其实在刚开学那个月就做过这个题了呢
//那个时候都还不知道啥是栈哇
//光阴似箭岁月如梭
//代码见https://ac.nowcoder.com/acm/contest/view-submission?submissionId=74102790

这时候就有人要问了，中间的题去哪了呢？？答案是太简单 or 太难了 hah

K 赚差价

image-20241209203326445

1
2
3
4
//我说白了这个题的数学运算实在是太复杂了所以直接贴付队发的解题思路
//可以学的是找到问题的实质到底是什么，通过一些关系来减少模拟次数（比如说这里m/p相同就合并）
//还有就是在使用各种算法或模拟之外，也可以讨论数学上的推论
//代码见https://ac.nowcoder.com/acm/contest/view-submission?submissionId=74068323

L 编辑器

此题特殊在各种操作都与现在的光标相关，故而我们需要两个数据结构分别去维护光标，又因为各种操作其实都是对上一个储存的元素就行访问所以想到用栈来处理。

通过对顶堆想到对顶栈，用一个栈来记录开头到光标位置，另一个栈来记录光标到结尾位置，两个栈都以光标位置作为栈顶，两个栈合起来就维护了整个序列。

而对于每个询问来说，直接再开一个数组来维护栈的前缀和即可

1
2
3
4
//对顶栈维护整个序列的操作学到了
//每次对左栈修改后就维护一次左边的前缀和，还是比较巧妙地
//代码见https://www.acwing.com/problem/content/description/130/
//不知道为什么我这个代码只在acwing上能过捏 但是我觉得应该是没什么问题嘟

牛客刷题小记

校外的树

1
2
题外话，记录这个题很大程度上是因为这是我第一场招新考试做到的题，纪念意义max；
当然最主要的还是这个题因为数据的不同可以有几种做法

处理重复区间的最优方法

按照题目的意思来看，是给每个区间内的树撤去，即减去这一部分的存在，然而由于有重复区间的存在，所以如果用减法就不可避免的多减，要避免此，每次都给减过的点打一个标记未免太过麻烦。所以我们可以转化思想，即初始化整个序列为 0，让每一个出现的区间中的数都加一，最后统计还为 0 的点就是最后剩下得树，这样的处理方法可以使得无论一个点被重复处理了多少次都不会影响最后剩下的树。

当然还有一种方法是通过 bool 数组给每一个点都打标记，这样就可以只统计没有被标记的点即是剩下的树了。

不同数据下的不同做法

1.在数据比较小的时候，可以直接使用遍历的做法，即给每一个区间内的点都去打标记，最后再统计没有被标记过的点的数量。

1
代码见https://ac.nowcoder.com/acm/contest/view-submission?submissionId=74264751&returnHomeType=1&uid=401013592

2.当数据比较大即遍历显然会超时的时候，结合题目让一个区间内的数改变，，可以用差分来实现，需要注意的还是上面介绍的应该是加 1，最后统计为 0 的点

1
代码见https://ac.nowcoder.com/acm/contest/view-submission?submissionId=74269667&returnHomeType=1&uid=401013592

3.如果数据特别特别大，显然对于这些独立的需要处理的区间我们可以用离散化来处理，由于存在重叠的部分所以不妨直接先进行一次区间合并然后直接通过合并后的区间内的树的数目来计算（总数目-移走的数目）

1
代码见https://ac.nowcoder.com/acm/contest/view-submission?submissionId=74270870&returnHomeType=1&uid=401013592

二分（这个题跟二分无关）

1
题目和代码见https://ac.nowcoder.com/acm/problem/207053

一道二分背景上的差分题目，我觉得还是挺有启发的。

最暴力的想法肯定是枚举每个数，最多符合条件的就应该是答案，显然过不了需要优化

可以想到，既然无法去判断每句话的真假那么不妨假设每句话都是真实的，并且依靠每一个判断给元素加权，最后我们找到权最大的就肯定是答案（即最多符合条件的点）

所以在这样的判断里可以想到用差分（对区间内的数做出改变），但同时因为边界可以达到正负 1e9，所以我们需要用 map 来离散化（因为我们需要判断的只有出现的几个数字）。最后判断加权的时候就相当于求这个 map 差分数组的前缀和。

寒假刷题小记

1.全排列

给出 n 的全排列

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
#include <iostream>
using namespace std;

const int N = 10;
int ans[N],n;
bool is[N];

void dfs(int u){
    if(u == n) {
        for(int i = 0;i < n;i ++) cout << ans[i] << " ";
        cout << endl;
        return ;
    }
    for(int i = 1;i <= n;i ++){
        if(!is[i]){
            ans[u] = i;
            is[i] = true;
            dfs(u + 1);
            ans[u] = 0;
            is[i] = false;
        }
    }
}

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

2.N 皇后

给出一个 n×nn\times nn×n 的国际象棋棋盘，你需要在棋盘中摆放 nnn 个皇后，使得任意两个皇后之间不能互相攻击。具体来说，不能存在两个皇后位于同一行、同一列，或者同一对角线。请问共有多少种摆放方式满足条件。

输入描述:

1
一行，一个整数n(1≤n≤12)n(1\le n \le 12)n(1≤n≤12)，表示棋盘的大小。

输出描述:

1
输出一行一个整数，表示总共有多少种摆放皇后的方案，使得它们两两不能互相攻击。

代码实现：

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

using namespace std;

const int N = 25;
bool a[N],ug[N],g[N];
int n,t;

void dfs(int u)
{
    if(u > n) { // 搜完了所有的行 即完成了一种排列
        t ++;
        return ;
    }
    else{
        for(int i = 1;i <= n;i ++) // 确定u相当于确定了行 故而只用遍历列
        {
            if(!a[i] && !ug[i + u] && !g[n - u + i]) { // 保证它不在同一列 同一对角线 同一反对角线
                a[i] = ug[u + i] = g[n - u + i] = true;
                dfs(u + 1); // 如果当前满足了 就继续往前搜
                a[i] = ug[i + u] = g[i - u + n] = false; //回溯复原
            }
        }
    }
}

int main()
{
    cin >> n;
    dfs(1);
    cout << t << endl;
    return 0;
}

特别需要关注的几个点有：

一，在一个方格图中，采用的是确定行来遍历列的思想，在其他情况，有可能就是去分析行列谁放在外循环谁放在内循环的区别

二，在方格图中关于对角线，反对角线的表述，以及其与坐标的下标之间的关系

3.马走日

题目描述

在 n 行 m 列的棋盘上有一个中国象棋的马，马走日字且不能向左走，设原本坐标为(x,y)走一步可以达到的位置有(x+1,y+2),(x+2,y+1),(x+2,y−1)(x+1,y-2)并且不能走出棋盘。请找到可行路径的条数，使得马从棋盘的左下角(1,1)走到右上角(n,m)。

1
输入一行，两个整数n,m(1≤n,m≤15)n,m(1\le n,m \le 15)n,m(1≤n,m≤15)，表示棋盘的大小。
1
输出一行一个整数，表示马从左下角到右上角的不同路径数。
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
#include <iostream>

using namespace std;

const int N = 100;
int n,m,t;
int dx[4] = {1,1,2,2};
int dy[4] = {2,-2,1,-1}; // 用两个数组来表示方向的移动向量，在移动的时候只需要去遍历数组即可，类似于上面对上下左右的处理

void dfs(int x,int y)
{
    if(x == n && y == m)
    {
        t ++;
        return ;
    }
    else if(x > n || x < 1 || y > m || y < 1) return;
    else {
        for(int i = 0;i < 4;i ++) dfs(x + dx[i],y + dy[i]);
        //每次循环就相当于往一种情况移动，再以这种移动进入dfs直到出界或者走到终点，如果出界的话就会被return到上一层的dfs，相当于进行了一次回溯
    }
}

int main()
{
    cin >> m >> n;
    dfs(1,1);
    cout << t << endl;
    return 0;
}

注意这里的 dfs 是多个方向的一条路走到黑，多个方向的选择是通过数组的循环来实现的

比如说，第一次 dfs 后，向第一种方向走，以这种状态进入第二层 dfs，然后又向第一种方向走，进入第三层 dfs，如果此时出界了就会 return 回第二层 dfs，由于之前第一方向已经走过了，所以就会向第二种方向走、

就是通过这样的不断迭代和回溯来实现对所有走法的可行路径的全统计

4. 数独

image-20250110154326439

代码实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
#include <iostream>

using namespace std;

const int N = 100;
int mp[12][12],cnt;
bool h[12][12],l[12][12],gong[12][12];
//dfs的一个关键点是如何判断可行从而进行下一步搜索
//根据数独的要求这里分为行列和九宫格三个判断条件

struct sp{
    int x;
    int y;
}space[N];

const int g[10][10] = { {0,0,0,0,0,0,0,0,0,0},
					 {0,1,1,1,2,2,2,3,3,3},
					 {0,1,1,1,2,2,2,3,3,3},
					 {0,1,1,1,2,2,2,3,3,3},
					 {0,4,4,4,5,5,5,6,6,6},
					 {0,4,4,4,5,5,5,6,6,6},
					 {0,4,4,4,5,5,5,6,6,6},
					 {0,7,7,7,8,8,8,9,9,9},
					 {0,7,7,7,8,8,8,9,9,9},
					 {0,7,7,7,8,8,8,9,9,9}, };
//这里使用了一个打表的小技巧，通过二维数组的值来代指目前的位置处于第几个九宫格 巧思啊！

void print()
{
    for(int i = 1;i <= 9;i ++)
        for(int j = 1;j <= 9;j ++) {
            cout << mp[i][j];
            if(j == 9) cout << endl;
            else cout << " ";
        }
}

void dfs(int u)
{
    if(u > cnt) {
        print();
        return;
    }
    else {
        for(int i = 1;i <= 9; i ++)
        {
            int xx = space[u].x; int yy = space[u].y;
            if(!h[xx][i] && !l[yy][i] && !gong[g[xx][yy]][i])
            {
                h[xx][i] = 1, l[yy][i] = 1, gong[g[xx][yy]][i] = 1;
                mp[xx][yy] = i;
                dfs(u + 1);
                h[xx][i] = l[yy][i] = gong[g[xx][yy]][i] = 0;
                mp[xx][yy] = 0;
            }
        }
    }
}

int main()
{
   for(int i = 1;i <= 9;i ++)
   {
       for(int j = 1;j <= 9;j ++) {
           cin >> mp[i][j];
           if(mp[i][j] == 0) {
               space[++cnt].x = i;
               space[cnt].y = j;
           }
           h[i][mp[i][j]] = true;
           l[j][mp[i][j]] = true;
           gong[g[i][j]][mp[i][j]] = true;
           //这里的三个布尔数组的意思为，第i行的这个数已经存在以此类推
           //故而在dfs过程中，实际上深搜的是从1~9的每个数，即这个数可以放在哪些地方
       }
   }
    dfs(1);
    return 0;
}

dfs 小结

在 dfs 的相关问题中，主要的步骤是进行递归和回溯。

进行的关键点在于什么时候进入递归，以及回溯的准确性。

什么时候进入递归？？

当前状态可行 ->先将当前标记为已走过 ** -> **深入到下一步状态**

回溯？？

回溯需要重新标记为没有走过

如果没有标记的需要，那么回溯一般表现为 return 回上一层 dfs

5.(这里有四道题)牛客周赛

1
题目见https://ac.nowcoder.com/acm/contest/99990

q1 :

理清楚逻辑即可，关于周末双休计算 n 天贡献的题还是蛮常见的

q2 ：

构造题，做的时候想太多了，关键在于字符串中单一个字母也可以称其为字串，故而直接找到字符串中出现次数最多的字母即可

补充一下关于记录字母出现次数方法：

1
2
3
4
5
6
7
8
9
10
string s;
//建立计数数组
cnt[N];
int n = s.length();
for(int i = 0;i < n;i ++)
{
	cnt[s[i]- 'a'] ++; // 此处的s[i]- 'a'实际为在字母表中出现的位置，故而后面可以还原这个字母
}
//假设出现次数最多的是cnt[t],还原字母(0 < t < 26)
char a = (char)('a' + t);

q3 :

一道关于最大公约数 gcd 的思维题，先在这里介绍一下 gcd

1
2
3
4
5
6
7
8
9
//在c ++ 中可以直接调用函数
#include <numeric>
int a = gcd(4,6);
//底层的计算逻辑如下
int gcd(int a,int b)
{
	if(b == 0) return a;
	else return gcd(b,a % b);
}

关于这道题本身，因为可以进行任意次操作将两个数都变为它们的最大公约数，故而可以知道，要使整个数组的元素之和最小，就要使数组中的每个数都变成所有数的最大公约数

最大公约数的传递性：如果我们对多个数连续应用 GCD 操作，结果等于这些数的最大公约数。例如，对于三个数 a,b,ca,b,_c_，有 gcd(a,gcd(b,c))=gcd(a,b,c)gcd(a,gcd(b,c))=gcd(a,b,c)。

最小化和的关键：由于我们可以选择任意两个数进行 GCD 操作，并且可以进行任意次操作，实际上我们可以将整个数组的所有元素通过一系列的 GCD 操作合并成一个值，即所有元素的最大公约数。因为 GCD 的结果不会大于原来的任何一个数，所以这是能获得的最小可能值。

所以我们计算完所有元素的最大公约数 q 后，最后的数组和即为 n * q

q4 :

这道题出错了。。 可以想一下贪心的思维，要最小化，就可以从最大的开始处理，故而用一个大根堆可以处理

6.双人迷宫相遇问题

image-20250114162104562

即一个双重 bfs，两个人同时进行 bfs，当 a 中途走到了 b 走过的地方即证明已经相遇了，关键就是在于如何去建立 ab 两人之间的关系

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
#include <iostream>
#include <queue>

using namespace std;

typedef pair<int,int> pp;

char b[1005][1005];
int x1,y1,x2,y2;
int n,m;
queue<pp>q[2]; //q[0]即为小B，q[1]为小A
//用0，1其实是一个小技巧，在需要联系另一个人的时候直接非！一次即可
bool flag ,v[2][1005][1005] ; //同理我们用这样一个三维的bool数组来分开标记a和b走过的地方
int ans = 0;
int dx[] = {0,0,1,-1,1,1,-1,-1}; int dy[] = {1,-1,0,0,1,-1,1,-1};

bool bfs(int a)
{
    int x = 0,y = 0;
    int t = q[a].size();
    while(t --)
    {
        auto qq = q[a].front();
        q[a].pop();
        for(int i = 0;i < 4 + (a?4:0);i ++)
        {
            x =qq.first + dx[i],y = qq.second + dy[i];
            if(x < 0 || x >= n || y < 0 || y >= m || b[x][y] == '#'|| v[a][x][y]) continue;
            if(v[!a][x][y]) {
                flag = 1;
                return true;
            }
            v[a][x][y] = 1;
            q[a].push({x,y});
        }
    }
    return false;
}

int main()
{
    cin >> n >> m;
    for(int i = 0;i < n; i ++)
    {
        for(int j = 0;j < m;j ++){
            cin >> b[i][j];
            if(b[i][j] == 'D') x1 = i, y1 = j;
            if(b[i][j] == 'C') x2 = i, y2 = j;
        }
    }
    v[0][x1][y1] = true; q[0].push({x1,y1});
    v[1][x2][y2] = true; q[1].push({x2,y2});
    while(!q[1].empty() || !q[0].empty())
    {
        ans ++;
        if(bfs(0)) break;
        if(bfs(0)) break;
        if(bfs(1)) break;
    }
    if(flag) cout << "YES" << endl << ans;
    else cout << "NO";
    return 0;
}

7.地雷递推

image-20250114221410059

关键在于找到规律，对于地雷问题

image-20250114221603813

即我们需要把题目的描述转化为状态方程，进而模拟过程，对于这类问题，特别需要注意的就是特殊情况的特判

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
#include <iostream>
#include <cstring>
using namespace std;
const int N = 1e4 + 10;
int ans,n,a[N],f[N];
int flag;

int hi()
{
    for(int i = 2;i < n;i ++)
    {
        int t = a[i] - f[i-1] - f[i];
        if(t < 0 || t > 1) return 0;
        else f[i+1] = t;
    }
    if(f[n] + f[n-1] != a[n]) return 0;
    return 1;
}

int main()
{
    cin >> n;
    for(int i = 1;i <= n;i ++){
        cin >> a[i];
        if(a[i] > 3) flag = 1;
    }
    if(a[0] > 2 || a[n-1] > 2 || flag)
    {
        cout << 0 << endl;
        return 0;
    }
    if(a[1] == 2)
    {
        f[1] = 1;
        f[2] = 1;
        ans += hi();
    }
    else if(a[1] == 0)
    {
        f[1] = 0;
        ans += hi();
    }
    else if(a[1] == 1)
    {
        f[1] = 1;
        ans += hi();
        memset(f,0,sizeof f);
        f[2] = 1;
        ans += hi();
    }
    cout << ans << endl;
}

8.贪心拼数

image-20250115104844171

按照字典序大的排列即可，这里的做法是给 sort 自定义一个 cmp 来排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include <iostream>
#include <algorithm>
using namespace std;

bool cmp(string a,string b)
{
    return a + b > b + a;
}

int main()
{
    int n; cin >> n;
    string s[n];
    for(int i = 0;i < n;i ++) cin >> s[i];
    sort(s,s + n,cmp);
    for(int i = 0;i < n;i ++) cout << s[i];
    return 0;
}

9.贪心排座椅

image-20250115112746614

要使得上课交头接耳的学生对数最少，即要使我们划分的过道能够隔开最多的交头接耳学生对数

那么每次划分时，都对这条线隔开的同学对数计数（由于需要划分的行列可能是相同的，故而每次划分就是对这条过道的 cnt++）

最后要找到最优解只需要按照计数排序就可以得到

还需要注意的是输出的答案是有序的，故而还需要对划分的行进行排序

故而每一个划分都有数量和行数两个属性，用结构体储存

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
#include <iostream>
#include <algorithm>
using namespace std;

const int N = 1e4;
struct node{
    int cnt;
    int id;
}ct1[N],ct2[N];

bool cmpcnt(node a,node b)
{
    return a.cnt > b.cnt; //从大到小找最优解
}

bool cmpid(node a,node b)
{
    return a.id < b.id; //从小到大满足输出要求
}

int main()
{
    int m,n,k,l,d; cin >> m >> n >> k >> l >> d;
    while(d --)
    {
        int x,y,p,q; cin >> x >> y >> p >> q;
        if(x == p)
        {
            int yy = min(y,q);
            ct1[yy].cnt ++;
            ct1[yy].id = yy;
        }
        else if(y == q)
        {
            int xx = min(x,p);
            ct2[xx].cnt ++;
            ct2[xx].id = xx;
        }
    }
    sort(ct1,ct1 + n,cmpcnt);
    sort(ct2,ct2 + m,cmpcnt);
    sort(ct1,ct1 + l,cmpid);
    sort(ct2,ct2 + k,cmpid);
    for(int i = 0;i < k;i ++) cout << ct2[i].id << " ";
    cout << endl;
    for(int i = 0;i < l;i ++) cout << ct1[i].id << " ";
    return 0;

}

10.贪心国王的问题

image-20250115204622555

我们对于国王身后的两个点来分析

队列可能是这样的：

* Left Right
king: img img
p1 img img
p2 img img

那么我们计算可得img

队列也有可能是这样的

* Left Right
king: img img
p2 img img
p1 img img

那么我们计算可得img

我们来对比一下两个答案：

img

img

可以替换得：

img

img

显然我们可以得到:

img

img

即：img

img

如果img

那么易得：

img

即： img

变形可得：

img

当img时，我们也能够得到img的结论

所以，为了img取到最小值，我们需要将img较小的放在前面

这即是需要的贪心的关键点。而后需要写高精度来满足题目

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
#include<bits/stdc++.h>
using namespace std;
struct node{
    int fir,sec;
    bool operator < (const node &a)const{
        return fir*sec<a.fir*a.sec;
    }
}st[1005];
int sum[5050];
int vis[5050];
int arr[5050];
int len=1,tex=1;
void cheng(int b)
{
    for(int i=1;i<=len;i++)
    {
        vis[i]*=b;
    }
    for(int i=1;i<=len;i++)
    {
        vis[i+1]+=vis[i]/10;
        vis[i]%=10;
    }
    if(vis[len+1]!=0) len++;
    while(vis[len]>10)
    {
        vis[len+1]+=vis[len]/10;
        vis[len]%=10;
        len++;
    }
}
void chu(int b)
{
    int t=0,flag=0,ans=0;
    for(int i=len;i>=1;i--)
    {
        t=t*10+vis[i];
        if(t<b&&flag==0) continue;
        else{
            flag=1;
            arr[++ans]=t/b;
            t%=b;
        }
    }
    if(ans>tex)
    {
        for(int i=1;i<=ans;i++) sum[i]=arr[i];
        tex=ans;
    }
    else{
        if(ans==tex)
        {
            for(int i=1;i<=ans;i++)
            {
                if(arr[i]>sum[i])
                {
                    for(int i=1;i<=ans;i++)
                    {
                        sum[i]=arr[i];
                    }
                    break;
                }
            }
        }
    }
}
int main()
{
    int n;
    cin>>n;
    for(int i=0;i<=n;i++)
    {
        cin>>st[i].fir>>st[i].sec;
    }
    sort(st+1,st+1+n);
    sum[1]=vis[1]=1;
    for(int i=1;i<=n;i++)
    {
        cheng(st[i-1].fir);
        chu(st[i].sec);
    }
    for(int i=1;i<=tex;i++) cout<<sum[i];
    cout<<"\n";
    return 0;
}

贪心小结

贪心问题，一般需要安排某种情况使得结果最优，获得这种最优解的方法一般有两种

一是直接按照题意模拟出情况，最后排序得出最优的情况（例如上面的拼座椅）

二是按照题意推出得到最优解的关键条件，进而对数据进行排序，从而直接得到最优的结果（例如上面的国王的问题和拼数）

当然可以看出，贪心中一个很重要的点就是排序，关键是找到排序的关键词！！！

11.先序排列

之前写过这里就不写了

12.二分晾衣服

image-20250117092642591

首先看到问题是求最短时间，故而考虑是二分还是贪心

观察题目，时间少就不能完全烘干，时间长就不满足最短的限制，故而答案是单调的，进而应该选择二分答案

这道题的主要误区在于容易陷入贪心的思维，即想要对烘干顺序进行安排，但注意这里我们已经得出是单调二分，故而思维应该着重在 验证

怎么写这个 check 函数呢，现在的这个时间需要让所有衣服都被烘干，那么只需要算出把每件衣服全都烘干的时间，跟此时的答案比较即可

1
2
3
4
5
6
7
8
9
10
11
12
13
bool check(int x)
{
	int b[N];
	memcpy(b,a,sizeof a);
	ll ci = 0; //第一个容易错的点，最终的时间和是可能爆int的
	for(int i = 1;i <= n;i ++)
	{
		b[i] -= x; //x的时间，每一个时间减少1水分，x时间减少x水分
		if(b[i] > 0) ci += ceil((double)b[i] / (k - 1)); //由于每分钟自己减少的1已经计算，所以会额外减少k-1水分。
		//为什么要用ceil是由于必须要把每件衣服都烘干，宁多不少
	}
	return ci <= x;
}

还注意一个特判，如果烘干机每分钟烘干的水分比自然减少的 1 还少的话，那么就不用烘干机，所有衣服水分中的最大值作为时间就可以烘干所有的衣服。

下面看完整代码

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
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cmath>
using namespace std;
typedef long long ll;

const int N = 1e5 + 10;
int a[N],n,k;

bool check(int x)
{
    int b[N];
    ll sum = 0;
    memcpy(b,a,sizeof a);
    for(int i = 1;i <= n;i ++)
    {
        b[i] -= x;
        if(b[i] > 0) sum += ceil((double)b[i] / (k - 1));
    }
    if(sum > x) return false;
    return true ;
}

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

    int l = 0, r = 0x3f3f3f3f;
    while(l < r)
    {
        int mid = (l + r) / 2;
        if(check(mid)) r = mid;
        else l = mid + 1;
    }
    cout << l;
    return 0;
}

13.表达式求值

作为一道很典的题，一般是用栈分别存下数字和运算符，但不可避的问题是

14.并查集

这道题虽然是并查集的模板题，但还要用字符串去储存名字，所以可以很直观地认识并查集的原理，在这里记录一下

15.牛客周赛 a+b（2）

（因为是赛后随便看了一下所以没有做后面的题） 这里记录一下 b，不知道应该算是博弈还是贪心

image-20250121111842766

其实是一道思维题，不管是平均数还是中位数，最优的情况一定是能拿到足够多的大数，故而 k1k2 对于最优情况的考虑是没有意义的

由于这道题是需要自己先选，故而想要让菲菲拿到最少的大数，故而最优的划分情况应该是自己拿前 n-1 个数字，只留下最后一个数字给菲菲

又由于平均数肯定会小于或等于前 n-1 个数，那么是否拥有必胜策略就只需要看最后一个数是否大于前面 n-1 个数即可

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 2e5 + 10;
int a[N];
int main()
{
    int n,k1,k2; cin >> n >> k1 >> k2;
    int mx = -1;
    for(int i = 0;i < n;i ++) {
        cin >> a[i];
        mx = max(mx,a[i]);
    }
    if(mx > a[n-1]) cout << "Yes" << endl;
    else cout << "No" << endl;
}

16.cfdiv2（2）

a.image-20250121113015971

其实就是一个简单的模拟，但需要关注的是怎么最简单的得出

image-20250121113124881

image-20250121113139110

观察样例图解可知，其实

$$
整体周长 = 每一次移动形成的矩形的周长 - 重叠部分矩形的周长
$$

重叠部分的矩形的对顶点实则是

$$
上一个正方形的右上顶点和下一个正方形的左下起点
$$

故而直接每次记录即可（因为保证了肯定是向左上方移动的）

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
#include <iostream>
using namespace std;
int main()
{
    int t;
    cin >> t;
    while(t --)
    {
        int ans = 0;
        int n, m;
        cin >> n >> m;
        int a, b;
        cin >> a >> b;
        ans += 4 * m;
        n = n - 1;
        while(n --)
        {
            int x1, y1;
            cin >> x1 >> y1;
            ans += 4 * m;
            if(m > x1 && m > y1)
                ans -= (m - x1 + m - y1) * 2;
        }
        cout << ans << endl;
    }
}

c.

17.牛客寒假训练营 1

1
比赛链接https://ac.nowcoder.com/acm/contest/95323（包括题目和代码）

前言

这次比赛发现的最大的问题就是关于提前终止读入导致数据错位的问题，即比如说在多组数据中，在某一组的读入环节提前终止了读入，就会导致后续的读入都发生错误

比如说image-20250122141308415

在读入数组数据的过程中出现 1 就停止，就会导致后续数据错位

正确做法应该是给一个标记，在所有数据读入完后再输出

image-20250122141413358

a.

简单逻辑题，什么数能够确保它不是任何数的倍数，任何数也不是它的倍数呢

对于第一个限制条件，很显然它需要是一个倍数，对于第二个限制条件，只需要它比数组内可能的最大值大即可

数组内的数的范围是 1e9，故而直接输出一个大于 1e9 的数即可

b.

要求找一条路能够不重不漏地通过树上的所有节点，那么什么时候才可能出现这样的路径呢

image-20250122141923225

显然这棵树必须要是链状的才能满足

而要判断是不是链状的，我们只需要把这个树以图的方式储存下来，判断其的入度即可，只要度数大于 2，则树肯定非链状，直接输出-1 即可。

如果已经证明是链状的，只需要找到度数为 1 的点，根据上图可以看出，度数为 1 的点一定是起点或者终点，故而输出两个找到的点即可

这里的代码是用邻接表存的

d.

这里 wa 了好几发的主要原因还是数据错位的问题，这里就不再多说了

只是这里再次说一下，关于数据出现的次数问题，用哈希表可以比较简便地记录，如果是记录出现次数就使用 intint 的哈希表即可，如果是记录是否出现过就直接用 intbool 的哈希表即可

e.

非常有意思的一道题，其实在面对这种题的时候我一般都是很手足无措的，听完讲解后觉得可以这么想

对于这种经过操作构造目标，求操作次数的题，我们可以先关注结论，即预期的目标，再反推是怎么得来的，一般这种问题中秋最小操作次数都跟模拟无关，而是我们需要从中找到规律然后贪心地解决

对于这个题，不管怎么操作，最终数组都会变成 a…aaab..bbbb 的形式，即前半部分变为若干个 a 后半部分变为若干个 b，前后部分数目相同，并且这两部分变成多少（即 ab 的值）是无所谓的，我们只需要关注操作次数最小

分开考虑，那么问题就变成

1
数轴上有n个数，在数轴上找到一个数，使得数轴上的所有数移到该点所需的步数最少

即变成了 货仓选址问题 也就是中位数定理

中位数定理：给定一个数组，每次操作加 1 或者减 1，将所有元素变成相同的最小操作次数则是将所有元素变成中位数即可。

有一个特判是可能两边的中位数相等，只需要任意一边改变一下即可，我们可以枚举几种改变取最优（枚举的方法非常优美）

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
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long ll;

void solve(){
    int n; cin >> n;
    int a[n];
    for(int i = 0;i < n;i ++) cin >> a[i];
    sort(a,a + n);
    int l1 = a[(n / 2) / 2];
    int l2 = a[n/2 + (n / 2) / 2];
    ll ans = 1e18;
    for(auto xl : {l1,l1 - 1}){
        for(auto xr : {l2,l2 + 1}){
            if(xl == xr) continue;
            ll res = 0 ;
            for(int i = 0;i < n / 2;i ++) {
                res += abs(a[i] - xl);
                res += abs(a[n / 2 + i] - xr);
            }
            ans = min(ans,res);
        }
    }
     cout << ans << endl;
}

int main()
{
    int t; cin >>  t;
    while(t --){
        solve();
    }
}

g.

很经典的一种数组操作，即对左右加一减一，这样操作的关键点在于不管操作多少次数组中所有数的和都是不会发生改变的

故而第一个判断能不能成为排列只需要判断这个数组的和跟排列的和相等于否即可，如果相等的话就可能变为排列，不相等的话就不能

至于如何计算最小操作次数，一开始想的是排序数组后算出每一个位置上跟期望值之间的差是多少，但实际上这样有负有正不能算出来最小操作次数，相反，只需要算期望差中的正数或者负数即可，因为每一次操作加一和减一都是成对出现的，故而只关注一边即能计算出最小操作次数。

同样的思路，不管正负计算每个位置上差值的绝对值，最后除以二也能得到最小操作次数

h.

其实是一个贪心问题，放置每一个数都需要选择一个区间，为了能够完全地构造，我们需要尽可能地在每次选择的时候都让剩余的区间能够放的数更多，例如现在能放 2 的区间有[2,7]和[2,4]那么最优的选择就是放在[2,4],因为另一个区间可以放的数字更多

那么问题就转化为了，首先选择所有可以放置的区间（左边界），然后按照右边界排序（最优选择），故而对于区间的排序应该以左边界为第一关键字，以右边界为第二关键字。

怎么做到每次选择都可以最优呢，就可以用优先队列（一个小根堆）按顺序储存完每一个区间，每次拿出再弹出即可

注意在优先队列里重载运算符（这道题你让我写得好苦啊！）

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

//重载运算符使存放区间的vec按照左边界排好序
struct node{
    pp fan;
    int pos;
    bool operator<(const node &a){
        return fan.first < a.fan.first;
    }
};

//重载优先队列的比较器
struct compare{
    bool operator()(pp a,pp b){
        return a.first > b.first;
    }
};

int main() {
    int n;
    cin >> n;
    vector<node>a(n + 1);
    vector<int> ans(n + 1, -1);
    priority_queue<pp, vector<pp>, compare> b; //贪心，我们需要找到右区间最小的
    for (int i = 1; i <= n; i++) {
        int l,r; cin >> l >> r;
        a[i].fan = {l,r};
        a[i].pos = i;
    }
    sort(a.begin(),a.end());
    int cnt = 1;
    for(int i = 1;i <= n;i ++){//从1到n开始放数
        while(cnt <= n && a[cnt].fan.first <= i) { //左区间小于当前数就把这些区间放进去
            b.push({a[cnt].fan.second,a[cnt].pos});
            cnt ++;
        }
        if(b.empty()) {
            cout << -1 << endl;
            return 0;
        }
        auto t = b.top(); b.pop();
        if(t.first < i) {
            cout << - 1 << endl;
            return 0;
        }
        else {
            ans[t.second] = i; //把数字放到对应的位置上
        }
    }
    for(int i = 1;i <= n;i ++) cout << ans[i] << " ";
    return 0;
}

18.牛客寒假训练营 2

前言

由于回老家的原因这场比赛没打，没想到这场比赛不会做的题还挺多的，感觉最大的问题还是确实不太会做字符串问题的题了。特别是关于子串之类的问题。

a.

直接判断输入的数字里有没有不能出现的数字即可，注意如果是多组数据的话记得不能提前终止

b.

一开始想偏了想到了二分，但后来发现，想要让它至少比一般的碗都小，直接找到中位数，然后中位数减 1 不就恰好能够满足条件吗，所以做题还是多从思维入手

c.

d.

一道字符串的贪心和构造问题，关键在于如何

蓝桥杯真题补题

十四届蓝桥杯 cb 省赛

a 日期统计

1.想法方面 直接八重循环去遍历所有的八位字符串显然是不现实的 所以应该先处理出所有的 2023 年的日期 然后对于每个日期都在原字符串中进行匹配

启发是当一个方法行不通的时候可以换一个角度想 比如这里就把从原字符串中找字符串变成了从原字符串中匹配字符串

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
#include <bits/stdc++.h>
using namespace std;
int month[] = {0,31,28,31,30,31,30,31,31,30,31,30,31};
char temp[8];
int main()
{
	int ans = 0;
	string s = "5686916124919823647759503875815861830379270588570991944686338516346707827689565614010094809128502533";
	for(int i = 1;i <= 12;i ++) {
		for(int j = 1;j <= month[i];j ++) {
			sprintf(temp,"2023%02d%02d",i,j);
			int id = 0;
			for(int k = 0;k < 100;k ++){
				if(s[k] == temp[id]) {
					id ++;
				}
				if(id == 8) {
					ans ++;
					break; （因为如果日期一样的话只算作一个）
				}
			}
		}
	}
	cout << ans << endl;
	return 0;
}

b01 串的熵

这道题还是想多了的缘故 其实对于填空题不用进行太复杂的数学推理论证 这里也是直接考虑暴力枚举即可 让计算机来完成大部分的运算量

可以做的一些优化是 由于 0 的数量要小于 1 的数量 所以 0 的数量肯定是要小于 n / 2 的

还需要注意的是对于浮点数 在判断相等的时候不能直接用等于 要考虑精度的问题

(精度可以先默认成 0.01 如果这时输出的答案不止一个的话就可以考虑再提高精度)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include <bits/stdc++.h>
using namespace std;
int main()
{
	double ans = 11625907.5798;
	double n = 23333333;
	for(int i = 0;i < n / 2;i ++)
	{
		double shang = 0;
		shang -= i * (i / n) * log2(i / n) + (n - i) * ((n - i) / n ) * log2((n - i) / n);
		if(abs(shang - ans) < 0.01 ) {
			cout << i << endl;
			break;
		}
	}
	return 0;
}

c 冶炼金属

其实是一个直接推导公式的题 关键是要根据题目推导出 v 的范围

1.根据题目有以下公式推导： 因为
⌊𝐴/𝑉⌋=𝐵 有 𝐵<=𝐴/𝑉<𝐵+1
取倒数有
1/(𝐵+1)<𝑉/𝐴<=1/𝐵
两边同时乘 𝐴:

𝐴/(𝐵+1)<𝑉<=𝐴/𝐵 2.这样，区间左边取
𝐴/(𝐵+1)+1 最大值（这里要加 1 是因为其实是取不到原数的，取到的应该是下一个整数），右边取 𝐴/𝐵 最小值即可

最后把每一个数据中 v 的范围取一个交集即可以满足所有的条件

注意在数轴上画一下区间取交集是怎么取的 应该是

左边界取较大 右边界取较小

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#include <bits/stdc++.h>
using namespace std;
int main()
{
	int mn = 1; int mx = 1e9;
	int n; cin >> n;
	for(int i = 0;i < n;i ++)
	{
		int a,b; cin >> a >> b;
		mn = max(mn,a / (b + 1) + 1);
		mx = min(mx,a / b);
	}
	cout << mn << " " << mx;
	return 0;
}

反思一下可能后面看到这样的上下取整问题都可以这样推导一下下

d 飞机降落

引发一个大问题 就是什么时候用 dfs 除了路径 迷宫这些问题外其实很少想到用 dfs

那什么时候可以用到 DFS 呢？总结来说，当问题需要枚举所有可能的解，并且问题的结构适合逐步构建解的时候，可以考虑 DFS。例如排列问题、组合问题、路径问题等。在这种情况下，DFS 通过递归或者栈的方式，尝试每一种可能的选择，并回溯到上一步尝试其他选择，直到找到解或者遍历完所有可能性。即如果我们想要枚举一下答案的某一种情况然后对于每一种情况判断其合法性的话我们就可以用 dfs

然后分析问题，其实是问我们有没有一种排列方式能够使得每一架飞机都能够成功平安降落 数据量要比较小 所以我们用 dfs 来枚举每一种排列方式 看看有没有合法的就可以了

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

const int N = 15;

struct plane{
  int t; int d; int l;
}p[N];

int n;
bool vis[N];
bool flag;

void  dfs(int u,int last)
{
  if(u == n) {
    flag = true;
    return ;
  }
  for(int i = 0;i < n;i ++) //开始遍历排列
  {
    if(!vis[i] && p[i].t + p[i].d >= last)
    {
      vis[i] = true;
      dfs(u + 1,max(p[i].t,last) + p[i].l);
      vis[i] = false; // 回溯
    }
  }
}

int main()
{
  int t; cin >> t;
  while(t --)
  {
    cin >> n;
    for(int i = 0;i < n;i ++) cin >> p[i].t >> p[i].d >> p[i].l;
    flag = false; dfs(0,0);
    if(!flag) cout << "NO" << endl;
    else cout << "YES" << endl;
  }
}

e 接龙数列

其实这是一道 dp 的题 我暂时还不会 就只把暴力 dfs 放在这里吧

但是其实这里要想一下为什么会想到 dfs

该题要求的是最少从中删除多少个数 可以使剩下的序列是接龙序列 但显然考虑删除是很难有解法的 所以不如换个思路想 这个问题的另一种说法不就是 最多能剩下几个数可以使得当前剩下的序列是一个接龙序列 也就是说 我们只需要 枚举出所有可能的接龙序列 然后取取这些接龙序列长度的最大值 l 那么最少需要删除的数字就是 n - l 了！

那么怎么枚举这些序列呢 可以作这样的思考

从某一个数开始 每一个数都面临着选或者不选的情况 所以最终可以形成这样一颗二叉树

image-20250305195433802

现在就能看出来 想求出最终的排列其实就是一个树的遍历 也就是一个 dfs

当然 直接这样 dfs 的时间复杂度 是 2 ^ n 显然能过的测试点太少了 所以我们应该在搜索过程中再进行一个剪枝，即我们每一步都只需要符合题意的解 即后一位的首位为前一位的末位

最终这样就能过大概百分之五十的测试点 其实也应该比较够用了吧

f 岛屿个数

似乎是个 dfs + bfs 的题 有点太难了 看不懂思密达

g 子串简写

暴力拿了 14 分 后面运行超时了 其实仔细想一下优化还是挺简单的 用一个前缀和储存一下就好了

这道题的意思就是在字符串中找到一个长度至少为 k 的以 c1 开头 c2 结尾的子串

考虑优化我们可以先用前缀和记录每个位置和之前包含 c1 的数量 然后去遍历字符串找到为 c2 的点 如果距离大于 k 的话那么就将结果++

记得开 long long 不然会错一个测试点

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 5e5 + 10;
int c[N];
int cnt = 0;

signed main()
{
    int k; string s; char a,b; cin >> k >> s >> a >> b;
    int n = s.length();
    for(int i = 1;i <= n;i ++) c[i] += c[i - 1] + (s[i - 1] == a ? 1 : 0);
    for(int i = k;i <= n;i ++) if(s[i - 1] == b) cnt += c[i - k + 1];
    cout << cnt << endl;

}

但其实还在题解区看到了一个更妙妙的解法即用一个类似滑动窗口的思想 固定好子串的长度至少为 k

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include <bits/stdc++.h>
using namespace std;

int K;
long long ans = 0, c1_sum = 0;
string S;
char c1, c2;

int main() {
    cin >> K >> S >> c1 >> c2;
    for (int i = K-1, j = 0; i < S.length(); i++, j++) { //注意循环的初始条件 这样可以使得子串的长度至少为k
        if (S[j] == c1) c1_sum++;       // 记录当前起始位置j是否为c1 子串的起点
        if (S[i] == c2) ans += c1_sum;  // 若i是c2，累加合法子串数 子串的终点
    }
    cout << ans;
    return 0;
}

由于子串的起点是从左往右遍历的 所以当 if (S[i] == c2) ans += c1_sum; 的时候 加上的 c1_sum 即子串可能的起点数目是 j 往前的所有点 所以保证了子串的长度 >= k

妙啊！

h 整数删除

这道题的难度其实在于每次动态地判断最小的整数 其实现在看来可以很快地想到用小根堆来实现

天梯赛选拔模拟

静静的推荐

image-20250310162919117

关键只在于对题意的理解

原则上一批推荐名单应该是严格单调递增（即不能有相同的） 但如果学生的分数一样但是 pat 成绩达标的话就不受影响 也可以加入名单

那么问题就转化成了这样：

1
2
3
1、如果学生天梯赛分数不足175 不考虑
2、如果学生天梯赛分数不小于175但是pat分数不够的话那么就应该遵循原则 即每个批次出现一次 最多只能出现k次（k个批次）
3、日光学生天梯赛分数不小于175同时pat分数也够的话那么就可以无视原则 随便出现了 （因为批次内没有人数要求）
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 <bits/stdc++.h>
using namespace std;

const int N = 300;
int ci[N];

int main()
{
	int n,k,s; cin >> n >> k >> s;
	int ans = 0;
	for(int i = 0;i < n;i ++)
	{
		int t,p; cin >> t >> p;

		if(t >= 175)
		{
			if(p >= s) ans ++;
			else  if(ci[t] < k) {
					ci[t] ++;
					ans ++;
			}
		}

	}
	cout << ans << endl;
	return 0;
}

病毒溯源

image-20250310172705840

理解一下题意其实意思就是在一颗有根的树里找到最长路径 如果路径一样长的话就输出编号较小的那条路径

应该从这个题里学到的知识点有 ： 单链表存图 根节点的找法 有根树的遍历

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

const int N = 110;
int n;
int h[N],e[N],ne[N],idx;
int son[N];
bool st[N];

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

int dfs(int u)
{
	son[u] = -1;
	int len = 0;
	for(int i = h[u];i != - 1;i = ne[i])
	{
		int j = e[i];
		int d = dfs(j);
		if(len < d) len = d,son[u] = j;
		else if(len == d) son[u] = min(son[u],j);
	}
	return len + 1;
}

int main()
{
	memset(h,-1,sizeof h);
	cin >> n;
	for(int i = 0;i < n;i ++)
	{
		int k; cin >> k;
		if(k == 0) continue;
		for(int j = 0;j < k;j ++)
		{
			int x; cin >> x;
			add(i,x);
			st[x] = true;
		}
	}

	int root = 0;

	while(st[root]) root ++;

	int mx = dfs(root);
	cout << mx << endl;

	cout << root ;

	while(son[root] != -1)
	{
		root = son[root];
		cout << " " << root;
	}

	return 0;

}

清点代码

image-20250310194915375

stl 大模拟 需要注意的点可能是不要写昏头了

还有就是需要统计出现数量的时候可以用的几种数据结构 ： set map 哈希

但由于这里既要输出出现次数又要输出所有输出 所以用 map 最方便

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
#include <bits/stdc++.h>
using namespace std;
typedef pair<int,vector<int>> pp;


map<vector<int>,int> cnt;
vector<pp> ans;


int main()
{
    int n,m; cin >> n >> m;
    for(int i = 0;i < n;i ++)
    {
        vector<int> temp;
        for(int j = 0;j < m;j ++) {
            int x; cin >> x;
            temp.push_back(x);
        }
        cnt[temp] ++;
    }

    for(auto p : cnt) ans.push_back({-p.second,p.first}); // 注意，排序是默认从小到大排序的 但我们需要按照出现次数从大到小排  所以我们直接放相反数进去 最后取相反数的话就能满足题意了
    sort(ans.begin(),ans.end()); //pair的排序是默认先排first 再排 second 同时vector的排序是默认字典序的  所以用上面两个特性就很方便地按照题目要求输出了
    cout << cnt.size() << endl;
    for(auto p : ans)
    {
        cout << -p.first ;
        for(auto x : p.second)
        {
            cout << " " << x;
        }
        cout << endl;
    }

    return 0;

}

哲哲打游戏

image-20250310205518112

还是一道大模拟 比较恶心的一点在于所有的起点都是从 1 开始的 所以需要处理好索引问题防止出现越界的情况

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

const int N = 110;
const int M = 1e5 + 10;
int cun[N];
vector<int> a[M];

int main()
{
	int n,m; cin >> n >> m;
	for(int i = 1;i <= n;i ++) //这里从1开始计数保证了是从1开始的
	{
		int k; cin >> k;
		for(int j = 1;j <= k;j ++)
		{
			int x; cin >> x;
			a[i].push_back(x); //注意这里直接push_back的话元素是从0的位置开始的
		}
	}
	int now = 1; //从1开始
	for(int i = 1;i <= m;i ++)
	{
		int num; cin >> num;
		if(num == 0)
		{
			int j; cin >> j;
			now = a[now][j - 1]; //前面解释了 二维是从0开始的 所以这里需要-1
		}
		else if(num == 1)
		{
			int j; cin >> j;
			cun[j] = now;
			cout << now << endl;
		}
		else if(num == 2)
		{
			int j; cin >> j;
			now = cun[j];
		}
	}
	cout << now << endl;
	return 0;
}

完全二叉树的层序遍历

image-20250310211442315

之前找二叉树的几种遍历的时候其实自己用的方法就是递归吧 所以这里也应该想到要使用递归

特殊之处在于这里的输入是放在函数里面进行的 因为每次我们都只输入一下根

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

int n;
int tree[40];

void create(int u)
{
	if(u <= n){
		create(2 * u);
		create(2 * u + 1);
		cin >> tree[u];
	}

}

int main()
{
	cin >> n;
	create(1);
	for(int i = 1;i <= n;i ++) cout << tree[i] << " ";
	cout << tree[n] << endl;
	return 0;

}

杂题（具体代码都在杂题文件夹里）

k 倍区间

image-20250314083741933

前缀和+数学

如果用前缀和直接暴力遍历的话 只能过两个测试点 但是这种做法也想不到其他的优化了 所以应该关注其他的性质

数学性质推导

假设一个数列为 a1,a2,a3,….,an，一个小的前缀区间 s1 为 a1,a2,a3,….,ap,还有一个大的前缀区间 s2 为 a1,a2,a3,…,a(p+m)，p,p+m<n，

当我们对 s1、s2 的和分别取模，得到

(a1+a2+a3+…+ap)%k 和(a1+a2+a3+…+ap+m)%k，

当这两个值相等的时候，我们则可以列出这个等式：

(a1+a2+a3+…+ap)%k-(a1+a2+a3+…+ap+m)%k=0，

根据取模也具有分配律可得到，

(a1+a2+a3+…+ap-a1-a2-a3-…-ap+m)%k=0

因此可以推出结论，s2-s1 得出的区间必定为 k 倍区间。

那么我们可以记录每一个区间和对 k 取模的值 储存一下这些值的数量 即取模值相等的区间 在这些区间中任选两个相减的区间必定为 k 倍区间

所以问题就转换为了从 x 个取模值相等的区间中任选两个（组合数）

那 n 个中取任何两个区间都可以组成 k 倍区间，问有多少 k 倍区间，就转换成 n 个区间取两个的情况有多少个，就是 Cn2=n*(n-1)/2，所以对于每个%k 值相等的区间都添加一次组合就可以算出总共有多少 k 倍区间了

分巧克力

image-20250314085801444

二分

看到最值先想一下二分 然后想一下是否满足二分条件 如果二分边长的话sum += (h / u) * (w / u); 需要 sum == k

k 越大 sum 越小 也就是说这个表达式是满足单调性的 所以可以二分

玩三国杀

image-20250314090738027

贪心

关键在于理解题意 需要所有的事都确定发生与否 问最多发生多少个事件能使得某一国胜利 所以关键问题在于怎么去考虑每件事发生或没有发生的影响

如果单纯记录发生或者没有发生的状态 即写一个 dfs 暴搜 每个事件都有发生或没有发生两种情况 时间复杂度会是 2^n 次方 只能过两个测试点

所以不能暴力地去考虑状态 换个思路 我们只需要关注每件事情发生的贡献即可

以魏国获胜为例 即 X > Y + Z 那么每次事件发生的贡献即为 ai - bi - ci 如果这个贡献大于 0 则是有利的 应该让它发生否则就不发生最好

对于每一个国家用 sum 来记录贡献和 如果 sum 还大于 0 则说明该国家此时还可以获胜

想要求得最多发生多少 可以算出三个国家分别获胜的最多事件 最后取一个 max 就行

天梯赛选拔

比赛链接

西南石油大学天梯赛选拔赛ACM/NOI/CSP/CCPC/ICPC 算法编程高难度练习赛牛客竞赛 OJ

L1 - A 进制

进制转化题 无限像豪豪历险记 想要任意转换只需要把大于 10 的部分用字母记录一下即可 用栈来储存余数

image-20250316111455471

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

#define int long long

signed main()
{
    int x,k; cin >> x >> k;
    char c[17] = {'0', '1', '2', '3', '4', '5', '6', '7', '8', '9', 'A', 'B', 'C', 'D', 'E', 'F'};
    stack<int> m;

    if(x == 0) {
        cout << 0 << endl;
        return 0;
    }

    while(x)
    {
        m.push(x % k);
        x /= k;
    }

    while(!m.empty())
    {
        int n = m.top();
        cout << c[n];
        m.pop();
    }

    return 0;
}

L1-麻将

除了能跟着题意写大模拟之外 现在应该更多地考虑优化简化代码 赛时写的代码太冗长了 容易出错 debug 还很麻烦

注意写的时候一定一定要冷静 然后就是每次都需要查找值 所以应该用数组记录 因为只需要找到胜者 所以直接用 max 记录

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
#include <bits/stdc++.h>
using namespace std;
int main()
{
	int a[33];
	for(int i = 1;i <= 32;i ++) cin >> a[i];
	int t = a[1];
	for(int i = 1;i <= 32;i += 4) sort(a + i,a + i + 4);
	if(t == a[1] || a[2] == t) {
		cout << 17 << endl;
		return 0;
	}

	int b[9];
	b[1] = max(a[4],a[7]);
	b[2] = max(a[12],a[15]);
	b[3] = max(a[20],a[23]);
	b[4] = max(a[28],a[31]);
	b[5] = max(a[8],a[3]);
	b[6] = max(a[16],a[11]);
	b[7] = max(a[24],a[19]);
	b[8] = max(a[32],a[27]);

	bool flag = false;
	for(int i = 1;i <= 8;i ++){
		if(t == b[i]) {
			flag = true;
			break;
		}
	}

	if(!flag) {
		cout << 9 << endl;
		return 0;
	}

	flag = false;

	int c[5];
	c[1] = max(b[1],b[2]);
	c[2] = max(b[3],b[4]);
	c[3] = max(b[5],b[6]);
	c[4] = max(b[7],b[8]);

	for(int i = 1;i <= 4;i ++){
		if(t == c[i]) {
			flag = true;
			break;
		}
	}

	if(!flag) {
		cout << 5 << endl;
		return 0;
	}

	int c1,c2;
	c1 = max(c[1],c[2]); c2 = max(c[3],c[4]);

	if(t != c1 && t != c2) {
		cout << 3 << endl;
		return 0;
	}

	if(c1 > c2) {
		if(t == c1) cout << 1 << endl;
		else cout << 2 << endl;
	}

	else if(c2 > c1){
		if(t == c2) cout << 1 << endl;
		else cout << 2 << endl;
	}

	return 0;
}

L1-位运算

关于位运算的题目 一个小要点是位运算没有进位 所以应该按位考虑 每一位的计算和贡献都是独立的

如果题目的数据范围是 2 的多少次方就应该考虑转换为 2 进制用位运算解决问题

位运算题目的重点是对题目给出式子的分析和推导

对于该题

image-20250317111310192

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

#define int long long

void solve()
{
	int n,k; cin >> n >> k; int x = 2;
	vector<int> s;

    // 将数字转化为2进制表示
	while(n){
		s.push_back(n & 1);
		n >>= 1;
	}
	while(s.size() < k){
		s.push_back(0);
	}

    //每一位的可能组合之间应该相乘
	int ans = 1;
	for(int i = 0;i < s.size();i ++)
	{
		if(s[i] == 0) ans *= 4;
		else if(s[i] == 1) ans *= 12;
	}
	cout << ans << endl;
}

signed main(){
	int t; cin >> t;
	while(t --){
		solve();
	}
	return 0;
}

L2-查无此号

一道字符串加数据结构大模拟 需要注意两个点

1、耐心读题 把题读懂先

邮箱地址由邮箱用户名和域名构成 只要邮箱用户名相同 就能登录相同的 dd 账号

所以 由邮箱用户名和账号名来确定一个账号

只需要判断这个账号的登录次数即可

2.字符串函数和 stl 的使用

由于就连昵称中都有可能出现空格 所以只能把邮箱 昵称 ip 地址整体getline进来

用 substr 来分割出我们所需要的部分

我们用 pair 来储存一个账号 用 map 来记录 ip 登录的种数

这里有一个之前没想到的问题是如果用 pair int 的 map 来记录的话 需要再给 ip 开一个 string bool 的 map 但是这样就没法把 ip 跟账号对应出来 会导致出错 所以我们应该开一个 pair set的 map 来记录对应账号的 ip 情况 根据 set 的大小来判断登录次数

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

map<pp, set<string> > cnt;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    int n,k; cin >> n >> k;
    string ch; getline(cin,ch);
    for(int i = 0;i < n;i ++)
    {
        string s; getline(cin,s);
        string mail = s.substr(0,s.find('@'));
        string ip = s.substr(s.size() - 15);
        string name = s.substr(s.find(".com") + 5);
        name = name.substr(0,name.size() - 15);
        set<string> &temp = cnt[{mail, name}];  // 注意这里应该直接取地址 这样的话 对temp的改变会直接改变map的键值 如果重新定义一个set的话每次清空再插入就会超时
        int ts = temp.size();
        if(temp.find(ip) == temp.end()){
            temp.insert(ip);
            if(ts + 1 < k) {
                cout << "zheng chang deng lu" << endl;
            }
            else if(ts + 1 == k) {
                cout << "zui hou yi ci la!!! xiao xin yi dian!!!" << endl;
            }
            else if(ts + 1 == k + 1) {
                cout << "hahaha bei feng hao le ba!!!" << endl;
                temp.insert("123456");
            }
            else cout << "cha wu ci hao" << endl;
        }
        else {
            if(ts <= k) cout << "zheng chang deng lu" << endl;
            else cout << "cha wu ci hao" << endl;
        }
    }
    return 0;
}

天梯赛准备

敲笨钟

image-20250317205457959

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
#include <bits/stdc++.h>
using namespace std;
int main()
{
    int n; cin >> n;
    string ch; getline(cin,ch);  // 在用getline前 吸收掉cin产生的换行符
    while(n --){
        string s;  getline(cin,s);
        string s2 = s.substr(s.find(',') + 1);
        string s1 = s.substr(0,s.size() - s2.size() - 1);
        string wei1 = (s1.size() >= 3) ? s1.substr(s1.size() - 3, 3) : "";
        string wei2 = (s2.size() >= 4) ? s2.substr(s2.size() - 4, 3) : "";
        //注意这里的判断条件 防止因为字符串长度不够造成越界访问 一开始就是这里没改导致了运行错误！！！
        if(wei2 == "ong" && wei1 == "ong") {
            int cnt2 = 0;
            int cnt0 = 0;
            cout << s1 << ",";
            for(int i = s2.size() - 1;i >= 0;i --){
                cnt2 ++;
                if(s2[i] == ' ') cnt0 ++;
                if(cnt0 == 3) break;
            }
            //小知识点 当出现这种中间有空格的句子型的字符串的时候 可以用一个指针找空格出现的次数就可以达到分割单词的效果
            s2.erase(s2.size() - cnt2);
            cout << s2 << " " << "qiao ben zhong" << "." << endl;
        }
        else cout << "Skipped" << endl;
    }
    return 0;
}

这里重温一下字符串中 substr 和 erase 和 find 函数的应用

substr 函数 用于从原字符串中提取指定长度的子字符串

1
2
3
4
5
string substr (size_t pos = 0, size_t len = npos) const;
//应用时
string s1;
string s2 = s.substr(s.find(',') + 1);
string s1 = s.substr(0,s.size() - s2.size() - 1);

◦ pos：表示子字符串开始的位置，索引从 0 开始。
◦ len：表示子字符串的长度。若省略该参数，就会提取从 pos 开始直到字符串末尾的所有字符。

erase 函数 用于在原字符串中删除指定长度的子字符串

1
2
3
erase(size_t pos = 0, size_t len = npos)
// 应用时
  s2.erase(s2.size() - cnt2);

◦ pos：表示子字符串开始的位置，索引从 0 开始。
◦ len：表示子字符串的长度。若省略该参数，就会提取从 pos 开始删除直到字符串末尾的所有字符。

find 函数 用于在原字符串中寻找某个字符或某个子串的位置

1
2
3
string s;
int pos1 = s.find(',');
int pos2 = s.find("NJY");

查找子字符串的时候 返回的位置是这个字符串的第一个字符出现的位置

如果没有找到 会返回 -1