D. From 1 to Infinity

题意

有一个无限长的序列，是把所有正整数按次序拼接：$\text{123456789101112131415...}$。求这个序列前 $k(k\le 10^{15})$ 位的数位和。

思路

二分出第 $k$ 位是到哪个数字。

首先，需要预处理出所有 $i$ 位数的 位数和（注：不是数位和） 和最小的 $i$ 位数是多少。

// 预处理部分：
for(int i=1;i<=18;i++){digCnt[i]=9*pw(10,i-1)*i;digCnt[i]+=digCnt[i-1];// 计算前缀和数组mn[i]=pw(10,i-1);// 最小的i位数，pw函数为快速幂
}

二分部分如下：

int l=1,r=1e14;
while(l<r){int mid=l+r+1>>1;// 等价于(l+r)/2if(check(mid)>n) r=mid-1;else l=mid;
}

对于 check() 函数内部，其实就是需要返回：前 $k$ 个数字拼接起来的位数，那么我们再写一个函数来计算一个数的位数。

int dig(int x){int res=0;while(x>0){x/=10; res++;}return res;
}

所以，check() 就是计算所有 $<dig(x)$ 位数的位数和，即 $digCn{t}_{dig(x)-1}$；加上最小的 $dig(x)$ 位数到 $x$ 的位数和，即 $(x-m{n}_{dig(x)}+1)\times dig(x)$，所以返回值就是 $digCn{t}_{dig(x)-1}+(x-m{n}_{dig(x)}+1)\times dig(x)$ ，具体写法内容如下：

int check(int x){int p=dig(x);int res=digCnt[p-1]+(x-ID[p]+1)*p;return res;
}

剩下的部分就是一个模板题了：求 $1\sim l$ 的数位和，就不具体解释了：

int sum(int n) {int res=0,p=1;while(p<=n){int r=n%(p*10);res+=(r/p)*(r/p-1)/2*p;res+=n/(p*10)*45*p+r/p*(r%p+1);p*=10;}return res;
}

最后，注意多出来的部分要补全。

C++ 代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
int digCnt[20],mn[20];
int pw(int a,int b){int res=1;while(b){if(b&1) res=res*a;a=a*a;b>>=1;}return res;
}
int dig(int x){int res=0;while(x>0){x/=10; res++;}return res;
}
int check(int x){int p=dig(x);int res=digCnt[p-1]+(x-mn[p]+1)*p;return res;
}
int sum(int n) {int res=0;int p=1;while(p<=n){int r=n%(p*10);res+=(r/p)*(r/p-1)/2*p;res+=n/(p*10)*45*p+r/p*(r%p+1);p*=10;}return res;
}
void solve(){int n; cin>>n;int l=1,r=1e14;while(l<r){int mid=l+r+1>>1;if(check(mid)>n) r=mid-1;else l=mid;}int ans=sum(l);int cur=check(l);if(cur<n){vector<int> x;int p=l+1;while(p>0){x.push_back(p%10);p/=10;}reverse(x.begin(),x.end());for(int i=0;i<n-cur;i++) ans+=x[i];}cout<<ans<<endl;
}
signed main(){for(int i=1;i<=18;i++){digCnt[i]=9*pw(10,i-1)*i;digCnt[i]+=digCnt[i-1];mn[i]=pw(10,i-1);}int T; cin>>T;while(T--) solve();return 0;
}

E. Arithmetics Competition

题意

有两组卡片。第一组有 $n$ 张，点数为 $a_i$。第二组有 $m$ 张，点数为 $b_i$。共 $q$ 次询问，每次给定 $x,y,z$。问：从第一组选择 $0\sim x$ 张，第二组选择 $0\sim y$ 张，并且总共选择恰好 $z$ 张的情况下，点数和最大是多少？

思路

可以把这两组卡片分别排序，观察每次从第一组选出的数 $p$ 的增大对总点数和的影响。发现这是一个先增后减的单峰函数。

对于单峰函数，考虑三分 $p$ 的值即可。

C++ 代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int maxn=200005;
int a[maxn],b[maxn];
void solve(){int n,m,Q;cin>>n>>m>>Q;for(int i=1;i<=n;i++) cin>>a[i];for(int i=1;i<=m;i++) cin>>b[i];sort(a+1,a+1+n,greater<int>());sort(b+1,b+1+m,greater<int>());for(int i=1;i<=n;i++) a[i]+=a[i-1];for(int i=1;i<=m;i++) b[i]+=b[i-1];while(Q--){int u,v,w;cin>>u>>v>>w;int ans=a[min(u,w)]+b[max(w-u,0ll)];int l=max(w-v,0ll),r=min(u,w);while(l<r){int p=(2*l+r)/3,q=(l+2*r+2)/3;// 取三等分点，左边向下取整，右边向上取整int xx=a[p]+b[w-p],yy=a[q]+b[w-q];if(xx<yy) l=p+1;else if(xx>yy) r=q-1;else{l=p+1;r=q-1;}}ans=max(ans,a[l]+b[w-l]);if(l+1<=min(u,w)) ans=max(ans,a[l+1]+b[w-l-1]);cout<<ans<<endl;}
}
signed main(){int T; cin>>T;while(T--) solve();return 0;
}

F. Rada and the Chamomile Valley

说一句题外话，我这题挂了。死因：那天下午才学完边双，没有准备边双板子……

题意

有一个 $n$ 个点 $m$ 条边简单无向连通图，第 $i$ 条边连接 $u_i$ 和 $v_i$。共 $q$ 次询问，第 $k$ 次询问为：求距离点 $c_k$ 最近的 [从 $1$ 走到 $n$ 的必经之边] 的编号。

思路

这个很显然，就是求边双连通分量（简称 $\text{BCC}$），然后缩点，缩完点以后一定是一颗树，需要建出这棵树。

记点 $u$ 所在的 BCC 为 $co{l}_u$

在这一棵树上，找到从 $co{l}_1$ 到 $co{l}_n$ 的那一条路径，这条路径上的边就是所有的必经之边。把这些边标记一下。

然后，重新回到原图，求每个点到最近的必经边的距离和对应的边。从路径上的每条边所连接的点出发，跑一边 $\text{bfs}$ 最短路，注意，每次只能跑未被标记的边，因为经过了标记的边也不会对答案造成影响，下次它还是重新变回 $1$。

C++ 代码

#include<bits/stdc++.h>
#define mpr make_pair
#define pb emplace_back
using namespace std;
typedef pair<int,int> pii;
const int inf=2e9;
const int maxn=200005;
int dfn[maxn],low[maxn],bel[maxn],good[maxn],kd[maxn],to[maxn],tobel[maxn];
vector<pii> g[maxn],h[maxn],gg[maxn];
vector<int> ans,path,ansv,pathv;
pii edge[maxn],f[maxn];
bool used[maxn];
int n,m,k,cnt;
vector<int> st;
void tarjan(int u,int lst){low[u]=dfn[u]=++cnt; st.pb(u);for(auto i:g[u]){if(i.second==(lst^1)) continue;if(!dfn[i.first]){tarjan(i.first,i.second);low[u]=min(low[u],low[i.first]);}else{low[u]=min(low[u],dfn[i.first]);}}if(dfn[u]==low[u]){k++;bel[u]=k;while(st.back()!=u){bel[st.back()]=k;st.pop_back();}st.pop_back();}
}
void findpath(int u,int fa,int ed){pathv.pb(u);if(u==ed){ansv=pathv;ans=path;return;}for(auto[v,id]:h[u]){if(v!=fa){path.pb(id); findpath(v,u,ed); path.pop_back();}}pathv.pop_back();
}
void bfs(int u,int Id){vector<bool> vis(kd[bel[u]]+1,0);queue<int> q; q.push(u);vis[to[u]]=true;if(f[u].first>1) f[u]=mpr(1,Id);else f[u].second=min(Id,f[u].second);while(!q.empty()){int u=q.front(); q.pop();for(auto[v,id]:gg[u]){if(good[id]!=1){if(vis[to[v]]) continue;vis[to[v]]=true;if(f[u].first+1>f[v].first) continue;if(f[u].first+1==f[v].first){f[v].second=min(f[v].second,Id);continue;}f[v]=mpr(f[u].first+1,Id);q.push(v);}}}
}
void dfs(int u,int root){used[u]=true;tobel[u]=root;for(auto[v,id]:h[u]) if(good[id]!=1&&!used[v]) dfs(v,root);
}
void clear(){ansv.clear(); pathv.clear();ans.clear(); path.clear();k=cnt=0; st.clear();for(int i=1;i<=n;i++) dfn[i]=low[i]=bel[i]=kd[i]=to[i]=used[i]=tobel[i]=0,g[i].clear(),gg[i].clear(),h[i].clear(),f[i]=mpr(inf,inf);for(int i=1;i<=m;i++) good[i]=0;
}
void solve(){cin>>n>>m; clear();for(int i=1;i<=m;i++){int u,v; cin>>u>>v;g[u].pb(mpr(v,i<<1)); g[v].pb(mpr(u,i<<1|1));edge[i]=mpr(u,v);gg[u].pb(mpr(v,i));gg[v].pb(mpr(u,i));}for(int i=1;i<=n;i++) if(!dfn[i]) tarjan(i,-1);for(int u=1;u<=n;u++){for(auto[v,id]:gg[u]){if(bel[u]>=bel[v]) continue;h[bel[u]].pb(mpr(bel[v],id));h[bel[v]].pb(mpr(bel[u],id));}}findpath(bel[1],-1,bel[n]);sort(ans.begin(),ans.end());for(int u:ans) good[u]=1;for(int u:ansv) dfs(u,u);for(int i=1;i<=n;i++) to[i]=++kd[tobel[bel[i]]];for(int id:ans){auto[xx,yy]=edge[id];bfs(xx,id);bfs(yy,id);}int Q; cin>>Q;while(Q--){int u; cin>>u;if(f[u].second!=inf) cout<<f[u].second<<" ";else cout<<-1<<" ";}cout<<endl;
}
int main(){int T; cin>>T;while(T--) solve();return 0;
}