\(\huge{C}\)
link
首先，考虑暴力，用一个堆，存所有数，每次拿出最大的数，拆开加入堆，计入答案，直到最大的\(\le1\)，时间复杂度\(O(\text{不能过})\)。
考虑想求出\(n\)，要什么。
求\(n\)一定是第一次把\(n\)拆成\(\lfloor{\frac{n}{2}}\rfloor\)和\(\lceil{\frac{n}{2}}\rceil\)，答案加上\(n\)，之后再继续拆\(\lfloor{\frac{n}{2}}\rfloor\)和\(\lceil{\frac{n}{2}}\rceil\)，再继续拆……简单考虑一下即可得，\(n\)的答案就是\(n\)+\(\lfloor{\frac{n}{2}}\rfloor\)和\(\lceil{\frac{n}{2}}\rceil\)的答案。
这时，可以递归，加一个记忆化，时间复杂度\(O(\text{能过})\)。
特殊情况
- \(n=2\)时，答案为\(2\)。
点击查看代码
#include<bits/stdc++.h>
#define int long long
using namespace std;
int n;
map<int,int> mp;
int dfs(int x){
if(x == 2) return 2;
if(x == 1) return 0;
if(mp.find(x) != mp.end()) return mp[x];
mp[x] = dfs(x/2)+dfs((x+1)/2)+x;
return mp[x];
}
signed main(){
cin >> n;
cout << dfs(n);
return 0;
}
\(\huge{D}\)
link
每个点可以到\(i+1\)和\(x_i\)，考虑\(i\)向\(i+1\)和\(x_i\)连边，跑\(Dijkstra\)即可。
点击查看代码
#include<bits/stdc++.h>
#define int long long
#define PII pair<int,int>
using namespace std;
int n;
int a[200005],b[200005],x[200005];
vector<pair<int,int> > ed[200005];
int f[200005];
void dijkstra(int s){
priority_queue<PII,vector<PII>,greater<PII> > q;
q.push({0,s});
for(int i = 1;i <= n;++ i)
f[i] = 1e15;
f[s] = 0;
while(!q.empty()){
int t = q.top().first,x = q.top().second;
q.pop();
if(t > f[x]) continue;
for(int i = 0;i < ed[x].size();++ i){
int y = ed[x][i].first;
int w = ed[x][i].second;
if(f[y] > f[x]+w){
f[y] = f[x]+w;
q.push({f[y],y});
}
}
}
}
signed main(){
cin >> n;
for(int i = 1;i < n;++ i){
cin >> a[i] >> b[i] >> x[i];
ed[i].push_back({i+1,a[i]});
ed[i].push_back({x[i],b[i]});
}
dijkstra(1);
cout << f[n];
return 0;
}
\(\huge{E}\)
link
最开始我看到每个加1，于是考虑到了差分，可是差分无法随时找出\(a_{b_i}\)，无法用。
于是，我们需要一个即能区间修改值，又能随时查询某个点的值得数据结构——线段树。
每次输入了\(b_i\)（后面用\(x\)），找出\(x\)的值