Atcoder ABC340(A-D)

A题
题意：
给出一个首项为A，尾项为B，公差为D的算数序列，要求输出符合条件的序列
思路：
只需要从首项开始每次加上公差输出即可
代码：

#include<bits/stdc++.h>
#define ios ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)

using namespace std;

int add(int x, int y){return x ? add((x & y) << 1, x ^ y): y;}

#define ONLINE_JUDGE

int a,b,d;

int main()
{
#ifndef ONLINE_JUDGE
    freopen("1.in", "r", stdin);
    freopen("1.out", "w", stdout);
#endif
    ios;
    cin>>a>>b>>d;
    while(a<=b)
    {
        cout<<a<<" ";
        a+=d;
    }
    cout<<"\n";
    return 0;
}

B题
题意：
最开始给出一个空序列A和Q次查询。查询以下有两种类型：
1 x 将x追加到A的末尾
2 k 从A的末尾开始查找第K个数的值。当给出这个查询时，保证A序列的长度至少为k。
思路：
用一个数组A存贮A序列的值，cnt代表序列长度，每次执行将x追加到A的末尾时，将cnt+1，从A的末尾开始查找第K个数的值时输出A[cnt-k+1]即可。
代码：

#include<bits/stdc++.h>
#define ios ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)

using namespace std;

int add(int x, int y){return x ? add((x & y) << 1, x ^ y): y;}

#define ONLINE_JUDGE

int n,cnt;
int a[110];

int main()
{
#ifndef ONLINE_JUDGE
    freopen("1.in", "r", stdin);
    freopen("1.out", "w", stdout);
#endif
    ios;
    cin>>n;
    int k,x;
    for(int i=1;i<=n;i++)
    {
        cin>>k>>x;
        if(k==1)
        {
            a[++cnt]=x;
        }
        else
        {
            cout<<a[cnt-x+1]<<"\n";
        }
    }

    return 0;
}

C题
题意：
给出一个N，有一个操作将X分解为(X/2)与((X+1)/2)，每次执行这个操作的花费为X，一直重复这个操作直到分解出的所有数都小于2为止，要求求出所需的花费为多少。
思路：
思路一：
由题可知X=(X/2)+((X+1)/2),利用递归将结果求出。
思路二：
当所有(X/2)与((X+1)/2)相同时，N为2的K次，花费为kN，
当N不为2的k次时，令m为小于N的最大的2的k次，，则还缺少N-m的花费，其花费为2(N-m),那么最终花费为kN+2(N-m)。
代码：

#include<bits/stdc++.h>
#define ios ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)

using namespace std;

int add(int x, int y){return x ? add((x & y) << 1, x ^ y): y;}

#define ONLINE_JUDGE

typedef long long ll;
ll n;
ll res=2,sum;

int main()
{
#ifndef ONLINE_JUDGE
    freopen("1.in", "r", stdin);
    freopen("1.out", "w", stdout);
#endif
    ios;
    cin>>n;
    sum=n;
    while((res<<1)<=n)
    {
        res<<=1;
        sum+=n;
    }
    sum+=((n-res)<<1);
    cout<<sum<<"\n";
    return 0;
}

D题
题意：
一个游戏由N个阶段组成，最初只有1阶段可以玩。
对于每一个阶段i，有以下两个操作：
1.花费ai时间通过阶段i，进入阶段i+1
2.花费bi时间通过阶段i，进入阶段xi
要求求出至少需要多少时间才能通关N。
思路：
最开始我想到的是dp，但是dp很难处理有环的情况，因此dp无法通过这一题，考虑建图求最短路来通过这题。
建立一个有向图将信息存贮，每一个节点i分别连接两个节点i+1与xi，权值分别为ai和bi，跑一遍最短路即可得到答案。
代码：

#include<bits/stdc++.h>
#define ios ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)

using namespace std;

int add(int x, int y){return x ? add((x & y) << 1, x ^ y): y;}

#define ONLINE_JUDGE

typedef long long ll;
typedef pair<ll,ll> PLL;
const int N=2e5+10;
ll n,d[N],vis[N];
vector<PLL> e[N];

int main()
{
#ifndef ONLINE_JUDGE
    freopen("1.in", "r", stdin);
    freopen("1.out", "w", stdout);
#endif
    ios;
    cin>>n;
    for(ll i=1;i<n;i++)
    {
        ll a,b,x;
        cin>>a>>b>>x;
        e[i].push_back({i+1,a});
        e[i].push_back({x,b});
    }
    memset(d,0x3f,sizeof(d));
    priority_queue<PLL> q;
    q.push({0,1});
    d[1]=0;
    while(!q.empty())
    {
        ll u=q.top().second;
        q.pop();
        if(vis[u])
        {
            continue;
        }
        vis[u]=1;
        for(auto p : e[u])
        {
            ll v=p.first,w=p.second;
            if(d[v]>d[u]+w)
            {
                d[v]=d[u]+w;
                if(!vis[v])
                {
                    q.push({-d[v],v});
                }
            }
        }
    }
    cout<<d[n]<<"\n";
    return 0;
}