前言：本来就是个小作业，不过不发出来感觉码这么多字实在是不划算
暑假集训总结：
通过近一个月学习，可能因为上课的不够认真导致所收获的知识理解得都不是很透彻qwq 没救了
以下是知识点总结（自己所熟知的几个，写错就尴尬了不是）,ԾㅂԾ,：
一.搜索
-
1.深度优先搜索（dfs）
这次课程基本框架记得最清楚的算法，没有之一bushi
原理：
递归或栈实现的"一条路走到底"策略
适用于路径探索、状态空间遍历等场景（应该是吧……例 走迷宫核心代码：
void dfs(int x, int y) {
if (x == n && y == m) {
cnt++;
return;
}
for (int i = 0; i < 4; i++) {
int nx = x + dx[i];
int ny = y + dy[i];
if (nx < 1 || nx > n || ny < 1 || ny > m || vis[nx][ny] || s[nx][ny] == '#') {
continue;
}
vis[nx][ny] = true;
dfs(nx, ny);
vis[nx][ny] = false;
}
}
-
2.广度优先搜索（bfs）
原理：
队列实现的"层层推进"策略
适用于最短路径、最小步数等问题 -
3.搜索剪枝
核心思路
提前终止无效搜索路径
常见剪枝策略：
- 可行性剪枝 （当前状态不可能满足条件
- 最优性剪枝 （当前解不可能优于已有解
- 4.记忆化搜索
原理
DFS+动态规划的结合
存储已计算子问题的结果
二.初赛
基本上来说，常见的题型也就是本身不是很理解的在写了几套卷子后大多都理解了，日后再复盘一下初赛八成是能过了
想起来下午我们英俊潇洒、温文尔雅、学富五车的朱老师说今晚要交，现在实在是来不及了（肯定不是因为我太困了），写得并不是很完整，明天必定抽时间完善，论坛发
咳咳，明天再补充
补充：
二、初赛（补充）
- 1.计算机基础知识 + 进制与编码
计算机组成
CPU（中央处理器）：运算器、控制器
存储器：RAM（随机存取存储器）、ROM（只读存储器）、Cache（高速缓存）
输入/输出设备：键盘、鼠标、显示器、打印机等
总线（Bus）：数据总线、地址总线、控制总线
数据表示
二进制、八进制、十六进制转换
原码、反码、补码（重点）
ASCII 码
浮点数表示
操作系统
Windous, Unix, Linux
提供用户接口、网络支持、文件系统、安全保护，管理计算机资源
- 2.数据结构
数组：一维、二维数组，基本操作
链表：单链表、双向链表、循环链表
栈（Stack）：LIFO（后进先出），应用（表达式求值、DFS）
队列（Queue）：FIFO（先进先出），应用（BFS）
哈希表（Hash Table）：冲突解决方法（开放寻址法、链地址法
- 3.算法常识
树与图
二叉树：前序、中序、后序遍历
堆（Heap）：大根堆、小根堆，堆排序
并查集（Disjoint Set）：路径压缩、按秩合并
图的表示：邻接矩阵、邻接表
最短路径
排序算法
简单排序：冒泡排序（O(n²) 、选择排序（O(n²)）
高效排序：快速排序（O(n log n)）、归并排序（O(n log n)）
查找算法：
顺序查找（O(n)）、二分查找（O(log n)）
递归与分治：斐波那契数列、汉诺塔
贪心算法：区间调度、背包问题（部分背包）
动态规划（DP）
- 4.数学类
基本概念
单位圆定义：
sinθ = y（对边/斜边）
cosθ = x（邻边/斜边）
tanθ = sinθ / cosθ
印象最深刻的一题
上学！！ 难好像不是特别难，但是差点召唤神龙qwq
首次尝试
/*
2. 上学
*/
#include <bits/stdc++.h>
using namespace std;
const int N = 10;
int n, m;
int dx[] = {0, 1, 0, -1};
int dy[] = {-1, 0, 1, 0};
bool vis[N][N];
string s[N];
int cnt = 0;
void dfs(int x, int y) {
if (x == n && y == m) {
cnt++;
return;
}
for (int i = 0; i < 4; i++) {
int nx = x + dx[i];
int ny = y + dy[i];
if (nx < 1 || nx > n || ny < 1 || ny > m || vis[nx][ny] || s[nx][ny] == '#') {
continue;
}
vis[nx][ny] = true;
dfs(nx, ny);
vis[nx][ny] = false;
}
}
int main ()
{
cin >> n >> m;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
cin >> s[i][j];
}
}
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
dfs(1, 1);
if (vis[i][j]) cout << i << " " << j << "\n";
else {
cout << -1;
return 0;
}
}
}
return 0;
}
第二次
/*
2. 上学
*/
#include <bits/stdc++.h>
using namespace std;
const int N = 1e4 + 10;
int n, m;
int dx[] = {0, 1, 0, -1};
int dy[] = {-1, 0, 1, 0};
bool vis[N][N];
char s[N][N];
int cnt = 0;
void dfs(int x, int y) {
if (x == n && y == m) {
cnt++;
return;
}
for (int i = 0; i < 4; i++) {
int nx = x + dx[i];
int ny = y + dy[i];
if (nx < 1 || nx > n || ny < 1 || ny > m || vis[nx][ny] || s[nx][ny] == '#') {
continue;
}
vis[nx][ny] = true;
dfs(nx, ny);
vis[nx][ny] = false;
}
}
int main ()
{
cin >> n >> m;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
cin >> s[i][j];
}
}
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
dfs(1, 1);
if (vis[i][j]) cout << i << " " << j << "\n";
else {
cout << -1;
return 0;
}
}
}
return 0;
}
第三次骗分
#include <bits/stdc++.h>
using namespace std;
int main ()
{
cout << -1;
return 0;
}
第四次
/*
2. 上学
记录路径
记录每个点找到最短路时的
上一个点的坐标
queue<int> q;
struct node {
int x, y;
} pre[N][N];
while (!q.empty()){
q.front();
q.pop();
int x, y;
for (){
int nx, ny;
if (越界) continue;
vis[nx][ny = true;
pre[nx][ny] = {now.x, now.y};
q.push();
}
}
找路径代码：
从终点出发
int x = n, y = m;
while (x == 0 && y == 0) {
cout << x << " " << y << "\n";
if (x == 1 && y == 1) break;
node t = pre[x][y];
x = t.x;
y = t.y;
}
题目需要从起点输出到重点，注意需要存下来倒序输出
*/
#include <bits/stdc++.h>
using namespace std;
const int N = 1e4 + 10;
int n, m;
int dx[] = {0, 1, 0, -1};
int dy[] = {-1, 0, 1, 0};
bool vis[N][N];
char s[N][N];
queue<int> q;
int cnt = 0;
struct node {
int x, y;
int d;
} pre[N][N];
void bfs(int x, int y) {
queue<node> q;
q.push(node{x, y, 0});
vis[x][y] = true;
if (x == n && y == m) {
cnt++;
return;
}
while (!q.empty()) {
node now = q.front();
q.pop();
int x, y;
for (int i = 0; i < 4; i++) {
int nx = now.x + dx[i], ny = now.y + dy[i];
if (nx < 0 || nx > n || ny < 0 || ny > m || vis[nx][ny]) continue;
vis[nx][ny] = true;
pre[nx][ny] = {now.x, now.y};
q.push(node{nx, ny, now.d + 1});
}
int xx = n, yy = m;
if (!vis[xx][yy]) cout << cnt << "\n";
while (xx == 0 && yy == 0) {
cout << xx << " " << yy << "\n";
if (xx == 1 && yy == 1) break;
node t = pre[xx][yy];
xx = t.x;
yy = t.y;
}
}
}
int main ()
{
cin >> n >> m;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
cin >> s[i][j];
s[i][j] = s[i][j] + '#';
bfs(i, j);
}
}
if (!vis[n][m]) cout << -1;
return 0;
}
第五次
/*
2. 上学
记录路径
记录每个点找到最短路时的
上一个点的坐标
queue<int> q;
struct node {
int x, y;
} pre[N][N];
while (!q.empty()){
q.front();
q.pop();
int x, y;
for (){
int nx, ny;
if (越界) continue;
vis[nx][ny = true;
pre[nx][ny] = {now.x, now.y};
q.push();
}
}
找路径代码：
从终点出发
int x = n, y = m;
while (x == 0 && y == 0) {
cout << x << " " << y << "\n";
if (x == 1 && y == 1) break;
node t = pre[x][y];
x = t.x;
y = t.y;
}
题目需要从起点输出到重点，注意需要存下来倒序输出
*/
#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 10;
int n, m;
int dx[] = {0, 1, 0, -1};
int dy[] = {-1, 0, 1, 0};
bool vis[N][N];
char s[N][N];
int cnt = 0;
struct node {
int x, y;
int d;
} pre[N][N];
queue<node> q;
bool bfs(int x, int y) {
q.push(node{x, y, 0});
vis[x][y] = true;
// if (x == n && y == m) {
// cnt++;
// return 0;
// }
while (!q.empty()) {
node now = q.front();
q.pop();
//int x, y;
for (int i = 0; i < 4; i++) {
int nx = now.x + dx[i], ny = now.y + dy[i];
if (nx < 0 || nx > n || ny < 0 || ny > m || vis[nx][ny] || s[nx][ny] == '#') continue;
vis[nx][ny] = true;
pre[nx][ny] = {now.x, now.y};
q.push(node{nx, ny, now.d + 1});
}
int xx = n, yy = m;
if (xx == 0 && yy == 0) {
cout << now.d + 1;
return 1;
}
if (!vis[xx][yy]) {
cout << -1;
return 0;
}
while (1) {
cout << xx << " " << yy << "\n";
node t = pre[xx][yy];
xx = t.x;
yy = t.y;
}
}
}
int main ()
{
cin >> n >> m;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
cin >> s[i][j];
s[i][j] = s[i][j] + '#';
bfs(i, j);
}
}
return 0;
}
第六次（交错题了qwq
/*
A. [202507A]小信的糖果游戏
*/
#include <bits/stdc++.h>
using namespace std;
const int N = 1e3 + 10;
int a[N], d[N];
bool vis[N] = {true};
int main ()
{
freopen ( "202507A.in", "r", stdin);
freopen ( "202507A.out", "w", stdout);
int n, k;
cin >> n >> k;
for (int i = 1; i <= 2 * k; i++) {
cin >> d[i];
for (int j = 1; j <= d[i]; j++) {
cin >> a[j];
vis[a[j]] = false;
}
}
int cnt = 0;
for (int i = 1; i <= n; i++) {
if (vis[i] == true) cnt++;
}
cout << cnt;
return 0;
}
最后也是AC了，代码就不展示了，不然开学要被宰了┭┮﹏┭┮
总结
夏训终章：代码与星辰的相遇
一、启程：键盘上的盛夏
这个夏天，我们与 C++ 共舞，在 for 循环的涟漪里见证重复的力量，在 递归的迷宫 中寻找出口。
- 变量 是沉默的容器，盛放逻辑的微光；
- 指针 如星辰的坐标，指引内存的航道；
- STL 像古老的魔法书，
vector铺展画卷，sort排列时光。
“代码是诗人的另一种语言，而调试是修行。”
二、探索：算法的四季
-
春·搜索（DFS/BFS）
- 像探险家走进密林，DFS 执着地深入每一条小径，用栈记录足迹；
- BFS 则如潮水漫过沙地，层层推进，队列是它的罗盘。
- 「剪枝」 是智慧的断舍离，抛弃无望的分支，让时间开花。
-
夏·动态规划（DP）
- 将问题拆解成 重叠的子问题，像拼凑记忆的碎片；
dp[i][j]是命运的备忘录，存储每一步的最优解。- “状态转移方程，是写给未来的情书。”
-
秋·数据结构
- 栈 如叠起的落叶，后进先出；
- 队列 似车站的人流，先进先出；
- 二叉树 是倒悬的星河，递归遍历时，听见根与叶的对话。
-
冬·数论与数学
- 质数 是孤独的守夜人，筛法如雪落无声；
- 模运算 像钟表的轮回，
%是时间的节拍器； - 而 三角函数，是几何写给代数的诗。
三、鏖战：初赛的江湖
- 选择题 如暗器，需快准狠——硬件组成、网络协议，是基本功的试炼；
- 程序填空 像解谜，
______的空缺处，藏着逻辑的钥匙； - 阅读理解 则是与出题人的对弈，从代码的缝隙间窥见意图。
“最难的题，常是『无解』时仍能写出部分分。”
四、收获：光与影的馈赠
-
技术的礼物
-
从 Hello World 到 快速排序，用代码重新定义世界的秩序；
-
调试 教会我们：每个错误都是通往完美的阶梯。
-
-
心灵的印记
- 那些 WA 的夜晚，星光比AC更亮；
- 团队讨论时，思路碰撞的火花，胜过独自苦想的寂寥。
-
未来的伏笔
- 未攻克的 图论，是待攀的山峰；
- 未理解的 位运算，像未破译的密码——它们将在秋风中继续生长。
- 未掌握的 算法， 皆是沿途最靓丽的风景
五、终章：代码未央
这个夏天，我们以键盘为笔，内存为纸，写下一行行 倔强的信仰。
- 或许某天，当
cin与cout的喧嚣褪去， - 仍会记得，曾有一群少年，在 时间复杂度 的标尺下，
- 追逐过 最优解，也拥抱过 无解 的浪漫。
“算法是逻辑的诗，竞赛是青春的注脚。”
—— 致我们的夏训
爆改文艺风哈哈
，ε=(´ο｀*)))唉，因为考试的时候不让上论坛！！，我太惨了，又要等半年