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～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～x$ 張，第二組選擇 $0～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;
}