# AtCoder ABC340 A-D题解

Problem A:

``````#include <bits/stdc++.h>
using namespace std;
int main(){
int a,b,d;
cin>>a>>b>>d;
for(int i=a;i<=b;i+=d)
cout<<i<<endl;
return 0;
}``````

Problem B:

``````#include <bits/stdc++.h>
using namespace std;
int main(){
int q;
cin>>q;
vector<int> a;
while(q--){
int tp,x;
cin>>tp>>x;
if(tp==1)
a.push_back(x);
else
cout<<a[a.size()-x]<<endl;
}
return 0;
}``````

Problem C:

``````#include <bits/stdc++.h>
using namespace std;
map<int,int> mem;
int dfs(int x){
if(x<2)
return 0;
if(mem.count(x))
return mem[x];
return mem[x]=dfs(x/2)+dfs(x/2+bool(x%2))+x;
}
int main(){
int n;
cin>>n;
cout<<dfs(n)<<endl;
return 0;
}``````

Problem D:

``````#include <bits/stdc++.h>
using namespace std;
const int maxn=200005;
long long dis[maxn];
bool vis[maxn];
vector<long long> graph[maxn],cost[maxn];
struct node{
long long dist;
long long p;
friend bool operator < (node a,node b){
return a.dist>b.dist;
}
};
priority_queue<node> pq;
void dijkstra(int s){
dis[s]=0;
pq.push((node){0,s});
while(pq.size()){
node tmp=pq.top();
pq.pop();
int u=tmp.p;
if(vis[u])
continue;
vis[u]=true;
for(int i=0;i<graph[u].size();i++){
long long v=graph[u][i];
long long w=cost[u][i];
if(dis[v]>dis[u]+w){
dis[v]=dis[u]+w;
if(!vis[v])
pq.push((node){dis[v],v});
}
}
}
}
int main(){
int n;
cin>>n;
//记得初始化dis数组
for(int i=1;i<n;i++){
int a,b,x;
cin>>a>>b>>x;
graph[i].push_back(i+1);
cost[i].push_back(a);
graph[i].push_back(x);
cost[i].push_back(b);
}
dijkstra(1);
cout<<dis[n]<<endl;
return 0;
}``````

OK，以上就是本期的全部内容了。下期更新ABC341的题解。

THE END