代码编织梦想

A - Arithmetic Progression

给你A,B,D,输出A,A+D,A+2*D,...到B为止,一个循环就可以解决。

#include <bits/stdc++.h>
//#define int long long
#define per(i,j,k) for(int (i)=(j);(i)<=(k);++(i))
#define rep(i,j,k) for(int (i)=(j);(i)>=(k);--(i))
#define fr first
#define se second
#define endl '\n'
using namespace std;

int a,b,d;

void solve(){
    cin>>a>>b>>d;
    for(int i=a;i<=b;i+=d)cout<<i<<" ";
}

signed main(){
    ios::sync_with_stdio(false),cin.tie(nullptr);
    int t=1;
    while(t--)solve();
    return 0;
}

B - Append

输入1,往序列后面添加x。

输入2,查询从后往前第k个数。

可以用数组模拟扩展,也可以用vector直接来做。

#include <bits/stdc++.h>
//#define int long long
#define per(i,j,k) for(int (i)=(j);(i)<=(k);++(i))
#define rep(i,j,k) for(int (i)=(j);(i)>=(k);--(i))
#define fr first
#define se second
#define endl '\n'
using namespace std;

int q,opt,x,k;

vector<int>a;

void solve(){
    cin>>q;
    while(q--){
        cin>>opt;
        if(opt==1){
            cin>>x;
            a.push_back(x);
        }else if(opt==2){
            cin>>k;
            cout<<a[a.size()-k]<<endl;
        }
    }
}

signed main(){
    ios::sync_with_stdio(false),cin.tie(nullptr);
    int t=1;
    while(t--)solve();
    return 0;
}

补题:C - Divide and Divide

给你一个数N,写在黑板上。对黑板上大于等于2的执行操作,设其为x,擦除x(答案就是擦除的总数),写上x/2向下取整和x/2向上取整。

N<=1e17,数组开不下的话只能动态dp或者记忆化搜索,因为下面的正常搜索写出来测试了大概10秒钟也不出答案,那复杂度就超了,想办法剪枝或者记忆重复搜索的内容。

void dfs(int x){
if(x<2)return;
ans+=x;
if(x%2==1)dfs(x>>1),dfs(x/2+1);
else dfs(x>>1),dfs(x>>1);
}
思路如果只局限在这里的代码,那就具体举例子,把10怎么分的画出来
分出5 5 然后分出2 3 2 3,显然是一个二叉树,可以画出来找规律。

暂时留空。

D - Super Takahashi Bros.

题目应该是比较容易读懂的,每一个舞台都可以花费A[i]到达下一个舞台,或者花费B[i]到达X[i]舞台。

如果只考虑当前这个点怎么做单次决策那就做不了这道题,因为X[i]会多次来回跳,所以正常的贪心和dp都做不了这道题。

舞台 i 能到 i+1 还能到 x[i],还有花费,如果能想到建图,那这道题就解决了。

因为权值都是正的,N=2e5,所以采用优先队列优化的dijkstra算法(正常的dj算法不一定能过,N*N复杂度有风险,这道题节点固定为N个,所以优先队列来优化选点更好)

#include <bits/stdc++.h>
#define int long long
#define per(i,j,k) for(int (i)=(j);(i)<=(k);++(i))
#define rep(i,j,k) for(int (i)=(j);(i)>=(k);--(i))
#define fr first
#define se second
#define endl '\n'
using namespace std;
const int N=2e5+5,MAX=LONG_LONG_MAX>>1;

int n,a,b,x,dist[N];
priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>>q;
vector<pair<int,int>>e[N];
bitset<N>vis;

void solve(){
    cin>>n;
    per(i,1,n-1){
        cin>>a>>b>>x;
        e[i].push_back({a,i+1});
        e[i].push_back({b,x});
    }

    per(i,2,n)dist[i]=MAX;
    q.push({0,1});
    while(!q.empty()){
        int now=q.top().second;
        int nowDis=q.top().first;
        q.pop();

        if(vis[now])continue;
        vis[now]=true;
        for(auto i:e[now]){
            int toNextLength=i.first;
            int nxt=i.second;

            if(dist[nxt]>dist[now]+toNextLength){
                dist[nxt]=dist[now]+toNextLength;
                if(!vis[nxt]){
                    q.push({dist[nxt],nxt});
                }
            }
        }
    }

    cout<<dist[n]<<endl;
}

signed main(){
    ios::sync_with_stdio(false),cin.tie(nullptr);
    int t=1;
    while(t--)solve();
    return 0;
}

记得开longlong。

版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/qq_17807067/article/details/136092994

[数据结构]----[线段树]-----线段树常见操作和例题-爱代码爱编程

基本操作, 单点修改,区间和: 洛谷P3374 【模板】树状数组 1. 区间修改,单点查询: 洛谷P3368 【模板】树状数组 2. 区间修改,区间求和: 洛谷P3372 【模板】线段树 1. 区间最值:洛谷P1531 I Hate It. 洛谷P1816 忠诚. 洛谷P2880 [USACO07JAN]Balanced Lineup G.

【数据结构】单向链表实现 超详细-爱代码爱编程

目录 一. 单链表的实现 1.准备工作及其注意事项 1.1 先创建三个文件 1.2 注意事项:帮助高效记忆和理解 2.链表的基本功能接口 2.0 创建一个 链表 2.1 链表的打印  3.链表的创建新节点接口 4.链表的节点插入功能接口 4.1 尾插接口 4.2 头插接口     4.3 指定位置 pos 之前 插入接口  4

【数据结构】实现顺序表-爱代码爱编程

大家好,我是苏貝,本篇博客带大家了解顺序表,如果你觉得我写的还不错的话,可以给我一个赞👍吗,感谢❤️ 目录 一.概念及结构二.接口实现2.1 创建顺序表结构体2.2 初始化顺序表2.3 销毁顺

数据结构_找环,破环题-爱代码爱编程

一. 判断单链表有无环 a. 错误的思路:遍历陷入死循环 1)和相交的遍历思路一样,找指向相同。 错误点 一直在死循环。 思考点:如何破环 b. 个人思路:反转链表回首结点 1)目前的经验,无非就是增删查改,反

数据结构之快速排序-爱代码爱编程

  快速排序的基本思想是: 通过一趟排序将待排的记录划分为独立的两部分,称为前半区和后半区,其中,前半区中记录的关键字均不大于后半区记录的关键字,然后再分别对这两部分记录继续进行快速排序,从而使整个序列有序。   一趟快速排

2.6:冒泡、简选、直插、快排,递归,宏-爱代码爱编程

1.冒泡排序、简单选择排序、直接插入排序、快速排序(升序) 程序代码: 1 #include<stdio.h> 2 #include<string.h> 3 #include<stdlib.h> 4 void Bubble(int arr[],int len); 5 void simple_sor

数据结构:单链表-爱代码爱编程

文章目录 1. 单链表的概念及结构2. 单链表相关操作2.1 创建节点2.2 尾插2.3 打印2.4 头插2.5 尾删2.6 头删2.7 查找2.8 指定位置后插入2.9 指定位置前插入2.10 删除指定位置2

【数据结构】链表oj面试题4(题库+解析)-爱代码爱编程

 1.前言  前五题在这http://t.csdnimg.cn/UeggB 后三题在这http://t.csdnimg.cn/gbohQ 给定一个链表,判断链表中是否有环。http://t.csdnimg.cn/Rcdyc  记录每天的刷题,继续坚持! 2.OJ题目训练 10. 给定一个链表,返回链表开始入环的第一个结点。 如果链表无环,则返回

排序算法-爱代码爱编程

原创不易,转载请注明出处。欢迎点赞收藏~ 插入排序是一种简单直观的排序算法,它的基本思想是将待排序的元素分为已排序和未排序两部分,每次从未排序部分中选择一个元素插入到已排序部分的合适位置,直到所有元素都插入到已排序部分,完成排序。 具体的插入排序算法如下: 从第一个元素开始,将其视为已排序部分。取出下一个未排序元素,在已排序部分从后往前扫描

【数据结构】顺序表-爱代码爱编程

目录 1.介绍顺序表 2.初始化 3.插入 4.删除 5.获取长度 6.按位置获取元素和查找指定元素的位置 7.完整代码 8.小问题 1.介绍顺序表 前面我们说到,既然数组无法实现这样的高级表结构,那么我就基于数组,对其进行强化,也就是说,我们存放数据还是使用数组,但是我们可以为其编写一些额外的操作来强化为线性表,像这样底

数据结构(c语言)代码实现(八)——顺序栈实现&数值转换&行编辑程序&括号分配&汉诺塔-爱代码爱编程

目录  参考资料 顺序栈的实现 头文件SqStack.h(顺序栈函数声明) 源文件SqStack.cpp(顺序栈函数实现) 顺序栈的三个应用 数值转换 行编辑程序 顺序栈的实现测试 栈与递归的实现(以汉诺塔为例)  参考资料 1.本文文章结构参考这篇博客,部分代码也引用自这篇博客。 2021-9-22【数据结构/严蔚敏】

【算法与数据结构】42、leetcode接雨水-爱代码爱编程

文章目录 一、题目二、解法三、完整代码 所有的LeetCode题解索引,可以看这篇文章——【算法和数据结构】LeetCode题解。 一、题目 二、解法   思路分析:   程序如下

【redis】深入理解 redis 常用数据类型源码及底层实现(3.详解string数据结构)-爱代码爱编程

【Redis】深入理解 Redis 常用数据类型源码及底层实现(1.结构与源码概述)-CSDN博客 【Redis】深入理解 Redis 常用数据类型源码及底层实现(2.版本区别+dictEntry & redisObject详解)-CSDN博客 紧接着前两篇的总体介绍,从这篇开始,我们结合源码依次解析下String、Hash、List、Set、

kajima corporation contest 2024(atcoder beginner contest 340)abcdef 视频讲解-爱代码爱编程

这场比较郁闷,C题短路,连续4次WA,导致罚时太多 A - Arithmetic Progression Problem Statement Print an arithmetic sequen