第二十六周代码（总结 + 查缺补漏）

2024-04-12 23:46:01
开发
11

蓝桥云课：刷题数量通过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;
	}
}

原文地址:https://blog.csdn.net/CH3CH2CH4/article/details/137497108 本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：https://www.suanlizi.com/kf/1778811819599728640.html 如若内容造成侵权/违法违规/事实不符，请联系《酸梨子》网邮箱：1419361763@qq.com进行投诉反馈，一经查实，立即删除！

阅读全部