蓝桥云课：刷题数量通过139题，尝试解决（未做出）18题。
- 其中蓝桥杯往年真题74题，尝试解决（未做出）6题
- 算法模板题5题
- 经典算法题20题，尝试解决（未做出）1题
- 算法赛赛题37题，尝试解决（未做出）11题
力扣：已通过题目5题，提交未通过1题
洛谷：已通过题目31题，尝试解决（未做出）4题
Acwing：4-5题
牛客：已通过题目3题
全部平台共通过题目183题，看看能不能拿省一
2024/04/08 周一
盖印章【算法赛】
题目链接
【参考代码】
#include <bits/stdc++.h>
using namespace std;
//a+b = k
//3a+2b = 1的总数(count1)
int main() //解方程，数论
{
int n,m,k;
cin>>n>>m>>k;
int count1 = 0;
for(int i=0; i<n*m; i++)
{
char c;
cin>>c;
if(c == '1')
count1++;
}
cout << count1 - 2*k << ' ' << 3*k - count1 << endl;
return 0;
}字符迁移【算法赛】
题目链接
【参考代码】
暴力66.7%，使用多行注释那段无法通过。
#include <bits/stdc++.h>
using namespace std;
int main() //暴力66.7%
{
int n, q;
cin>>n>>q;
string s;
cin>>s;
while(q--)
{
int l, r, k;
cin>>l>>r>>k;
for(int i=l-1; i<=r-1; i++)
{
//因为z的ASCII码是122，ASCII码的最大值是127，
//假设起始值是z，+25，ASCII码值的计算中很容易出界。所以需要先减去'a'保证不会出界
s[i] = 'a' + (s[i] - 'a' + k) % 26;
/*
s[i] += k % 26;
if(s[i] >= 'z')
s[i] = s[i] - 26;
*/
}
}
cout << s << endl;
return 0;
}2024/04/10 周三
城市规划（kruskal算法）
题目链接
【参考代码】
//kruskal算法
#include <bits/stdc++.h>
using namespace std;
const int N = 2001; // 定义常量N为2001，表示城市数量的最大值
int f[N], X[N], Y[N]; // 定义并查集数组f，以及城市的X和Y坐标数组
long long result = 0; // 定义结果变量result，用于存储最小生成树的总权值
int find(int index) // 查找函数，用于查找并查集中的根节点
{
if(f[index] != index) // 如果当前节点不是根节点
return f[index] = find(f[index]); // 递归查找根节点，并进行路径压缩
return index; // 返回根节点
}
int getDistance(int x1, int x2, int y1, int y2) // 计算两个城市之间的距离
{
return abs(x1-x2) + abs(y1-y2); // 返回两点之间的曼哈顿距离
}
struct node // 定义结构体node，表示边的信息
{
int from; // 起点城市编号
int to; // 终点城市编号
int distance; // 边的权值（距离）
node(int num1, int num2, int num3) // 构造函数，初始化城市编号和距离
{
from = num1;
to = num2;
distance = num3;
}
};
bool compare(node e1, node e2) // 比较函数，用于对边进行排序
{
return e1.distance < e2.distance; // 按照距离从小到大排序
}
vector<node> v; // 定义向量v，用于存储所有的边
set< pair<int, int> > set1; // 定义集合set1，用于存储关系不好的城市对
int main()
{
int n, k,x,y; // 定义变量n、k、x、y，分别表示城市对数量、关系不好的城市对数量、城市坐标xy
cin >> n >> k; // 输入城市数量和关系不好的城市对数量
for(int i=1;i<=n;i++) // 循环输入每个城市的坐标
{
cin>>X[i]>>Y[i];
}
while(k--) // 输入k个关系不好的城市并插入set
{
cin>>x>>y; // 输入关系不好的城市对
set1.insert(make_pair(x, y)); // 将城市对插入集合set1中
set1.insert(make_pair(y, x)); // 注意这里也要插入反向的城市对，因为无向图是双向的
}
//并查集初始化
for(int i=1; i<=n; i++) // 初始化并查集，每个节点的父节点都是自己
{
f[i] = i;
}
for(int i=1; i<=n; i++) // 遍历所有城市的组合
{
for(int j=i+1; j<=n; j++) // 注意这里是从i+1开始，避免重复计算和自环的情况
{
if(set1.find(make_pair(i, j) ) != set1.end() || set1.find(make_pair(j, i) ) != set1.end()) // 如果这两个城市是关系不好的城市对，则跳过
continue;
int dis = getDistance(X[i], X[j], Y[i], Y[j]); // 计算两个城市之间的距离
v.push_back(node(i, j, dis) ); // 将边的信息存入向量v中
v.push_back(node(j, i, dis) ); // 注意这里也要插入反向的边，因为无向图是双向的
}
}
sort(v.begin(), v.end(), compare); // 对所有边按照距离进行排序
for(auto &e: v) // 遍历所有的边
{
int boss1 = find(e.from); // 查找起点城市的根节点
int boss2 = find(e.to); // 查找终点城市的根节点
if(boss1 == boss2) // 如果两个城市已经在同一个连通分量中，则跳过这条边
continue;
f[boss1] = boss2; // 合并两个连通分量，即将一个城市的根节点指向另一个城市的根节点
result += e.distance; // 累加边的权值到结果变量result中
}
cout << result << endl; // 输出最小生成树的总权值
return 0;
}修建公路（kruskal算法 & prim算法）
题目链接
【参考代码】
kruskal算法
//kruskal算法
#include <bits/stdc++.h>
using namespace std;
const int N = 3e5+1; // 定义常量N为300001
int f[N]; // 定义数组f，用于存储并查集的父节点信息
// 查找函数，用于查找元素index的根节点
int find(int index)
{
if(f[index] != index) // 如果当前元素的父节点不是它自己
return f[index] = find(f[index]); // 递归查找父节点，并将结果赋值给当前元素
return index; // 返回当前元素的根节点
}
// 定义结构体node，表示边的信息
struct node
{
int from; // 起点
int to; // 终点
int distance; // 距离
}edge[N]; // 定义数组edge，用于存储所有的边
// 比较函数，用于比较两个边的距离大小
bool compare(node e1, node e2)
{
return e1.distance < e2.distance;
}
int main()
{
int n, m, u, v, w;
cin >> n >> m; // 输入点的数量n和边的数量m
for(int i=1;i<=m;i++) // 输入每条边
{
cin>>edge[i].from>>edge[i].to>>edge[i].distance;
}
// 初始化并查集，将每个点的父节点设置为它自己
for(int i=1; i<=n; i++)
{
f[i] = i;
}
// 根据边的距离对边进行排序
sort(edge+1, edge+1+m, compare);
long long result = 0, roadcount = 0; // 初始化结果result和道路数量roadcount
for(int i=1; i<=m; i++) // 遍历每条边
{
int boss1 = find(edge[i].from); // 查找起点的根节点
int boss2 = find(edge[i].to); // 查找终点的根节点
if(boss1 == boss2) // 如果起点和终点在同一个集合中，跳过这条边
continue;
f[boss1] = boss2; // 合并两个集合
result += edge[i].distance; // 累加边的距离
roadcount++; // 道路数量加1
}
if(roadcount < n-1) // 如果道路数量小于n-1，输出-1
cout << -1 << endl;
else
cout << result << endl; // 输出结果result
return 0;
}prim算法
//Prim算法
#include <bits/stdc++.h> // 引入C++标准库
using namespace std; // 使用标准命名空间
typedef long long ll; // 定义长整型别名ll
const ll INF = 0x3f3f3f3f3f3f3f3fll; // 定义无穷大常量
const int N = 1e5+10; // 定义节点数量上限
bool visit[N]; // 定义访问标记数组
ll distance1[N]; // 定义距离数组
ll ans = 0; // 定义答案变量
// 定义边的结构体
struct edge{
int id; // 边的终点
ll weight; // 边的权重
edge(int num1, ll num2) // 构造函数
{
id = num1;
weight = num2;
}
bool operator < (const edge &e1) const{ // 重载小于运算符，用于优先队列的比较
return e1.weight < weight;
}
};
vector<edge> e[N]; // 定义边的向量数组
// Prim算法实现
ll prim(int n, int start)
{
memset(distance1, 0x3f, sizeof(distance1)); // 初始化距离数组为无穷大
priority_queue<edge> q; // 定义优先队列
q.push(edge(start, 0)); // 将起始点加入优先队列
distance1[start] = 0; // 起始点到自身的距离为0
while(!q.empty()) // 当优先队列不为空时
{
edge u = q.top(); // 取出队首元素
q.pop(); // 弹出队首元素
if(visit[u.id] == true) // 如果该点已被访问过，则跳过
continue;
visit[u.id] = true; // 标记该点已被访问
ans += u.weight; // 累加权重
for(int i=0; i<e[u.id].size(); i++) // 遍历与该点相连的所有边
{
int v = e[u.id][i].id; // 获取终点
ll w = e[u.id][i].weight; // 获取权重
if(visit[v] == true) // 如果终点已被访问过，则跳过
continue;
if(w < distance1[v]) // 如果当前权重小于已知的最小权重，则更新距离数组
{
distance1[v] = w;
q.push(edge(v, distance1[v])); // 将新的点加入优先队列
}
}
}
for(int i=1; i<=n; i++) // 检查是否所有点都被访问过
{
if(visit[i] == false) // 如果有未被访问过的点，返回-1
return -1;
}
return ans; // 返回最小生成树的权重和
}
int main() // 主函数
{
int n, m; // 定义节点数和边数
cin>>n>>m; // 输入节点数和边数
while(m--) // 根据边数循环输入边的信息
{
int x, y; // 定义边的起点和终点
ll d; // 定义边的权重
cin>>x>>y>>d; // 输入边的信息
e[x].push_back(edge(y, d)); // 将边加入起点的边向量中
e[y].push_back(edge(x, d)); // 将边加入终点的边向量中
}
cout << prim(n, 1) << endl; // 输出Prim算法的结果
return 0; // 程序结束
}2024/04/12 周五
P5716 【深基3.例9】月份天数
题目链接
【参考代码】
#include <bits/stdc++.h>
using namespace std;
int day[] = {0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};
void leapyear(int year)
{
if(year % 4 == 0 && year % 100 != 0 || year % 400 == 0)
day[2] = 29; //2月天数改29
else
day[2] = 28;
}
int main()
{
int year, month;
cin>>year>>month;
leapyear(year);
cout << day[month] << endl;
}分解质因数
题目链接
【参考代码】
#include <stdio.h>
int isprime(int n) //判断是否为质数
{
int i;
for (i = 2; i < n; i++)
{
if (n % i == 0)
return 0;
}
return 1;
}
int main()
{
int amin = 0;
int bmax = 0;
int i = 0;
int j = 0;
int count = 0;
scanf("%d %d", &amin, &bmax);
for (i = amin; i <= bmax; i++)
{
if (isprime(i)) //直接判断是否为质数
{
printf("%d=%d\n", i, i);
}
else
{
int tmp = i;
printf("%d=", i);
for (j = 2; j < tmp; j++) //等于号补上
{
if (tmp % j == 0 && isprime(j))
{
tmp /= j;
printf("%d*", j);
j=1; //因为在循环末尾需要+1，j=1+1=2
}
}
printf("%d\n", tmp);
}
}
}生日蜡烛
题目链接
【参考代码】
#include <iostream>
using namespace std;
//有很多问题，比如说1/2计算机不会算
//两个变量a1和n放在一起，a1*n也出问题
//两个循环判断范围，假设情况：
//第一次循环1-100，第二次2-50，第三次3-25......
int main() {
int n = 1;
int i, j, sum = 0;
for (i = 1; i <= 100; i++) {
for (j = i; j <= 100; j++) {
sum += j;
if (sum == 236)
{
cout << i;
break;
}
}
sum = 0;
}
}
