【比賽記錄】2025CSP-S模擬賽16
考場唯一成果→
| A | B | C | D | Sum | Rank |
|---|---|---|---|---|---|
| 36 | 25 | 0 | 25 | 86 | 13/21 |
超絕降智場??
A. 醉
首先求出一條直徑，一個顯然的結論是從任何一個點出發，直徑的兩個端點之一一定是能走到的最遠的點。這可以用反證法證明。于是問題變成以直徑端點為根的 \(k\) 級祖先。離線下來跑 dfs 即可。時間復雜度線性。
Code
#include<bits/stdc++.h>
#define ll long long
#define il inline
#define pb push_back
#define pii pair<int,int>
#define mp make_pair
#define fir first
#define sec second
using namespace std;
namespace asbt{
const int maxn=2e5+5;
int n,m,dep[maxn],mxd[maxn],mxp[maxn];
int dd[maxn],ans[maxn];
vector<int> e[maxn];
vector<pii> q[maxn];
il void dfs1(int u,int fa){
mxd[u]=dep[u]=dep[fa]+1;
mxp[u]=u;
for(int v:e[u]){
if(v==fa){
continue;
}
dfs1(v,u);
if(mxd[u]<mxd[v]){
mxd[u]=mxd[v];
mxp[u]=mxp[v];
}
}
}
il void dfs2(int u,int fa){
dep[u]=dep[fa]+1;
dd[dep[u]]=u;
for(pii i:q[u]){
int d=i.fir,id=i.sec;
if(ans[id]==-1&&dep[u]>d){
ans[id]=dd[dep[u]-d];
}
}
for(int v:e[u]){
if(v==fa){
continue;
}
dfs2(v,u);
}
}
int main(){
ios::sync_with_stdio(0),cin.tie(0);
cin>>n;
for(int i=1,u,v;i<n;i++){
cin>>u>>v;
e[u].pb(v),e[v].pb(u);
}
dfs1(1,0);
int d1=mxp[1];
dfs1(d1,0);
int d2=mxp[d1];
cin>>m;
for(int i=1,u,d;i<=m;i++){
cin>>u>>d;
q[u].pb(mp(d,i));
}
memset(ans,-1,sizeof(ans));
dfs2(d1,0),dfs2(d2,0);
for(int i=1;i<=m;i++){
cout<<ans[i]<<"\n";
}
return 0;
}
}
int main(){return asbt::main();}
B. 與
設 \(f_{i,j}\) 表示 \(i\) 左側最大的第 \(j\) 為 \(1\) 的點，容易遞推求出。
設 \(g_{i,j}\) 表示 \(i\) 左側第 \(j\) 位為 \(1\) 最大的能走到 \(i\) 的點。枚舉從第 \(k\) 位走到 \(i\)，于是有轉移：
-
\(f_{i,k}\) 第 \(j\) 位為 \(1\)，\(g_{i,j}\leftarrow f_{i,k}\)。
-
\(g_{i,j}\leftarrow g_{f_{i,k},j}\)。因為 \(f_{i,k}\) 是最大的，從它轉移一定最優。
Code
#include<bits/stdc++.h>
#define ll long long
#define il inline
using namespace std;
namespace asbt{
const int maxn=3e5+5;
int n,m,a[maxn],f[maxn][22],g[maxn][22];
int main(){
ios::sync_with_stdio(0),cin.tie(0);
cin>>n>>m;
for(int i=1;i<=n;i++){
cin>>a[i];
for(int j=0;j<=19;j++){
if(a[i-1]>>j&1){
f[i][j]=i-1;
}
else{
f[i][j]=f[i-1][j];
}
}
}
for(int i=1;i<=n;i++){
for(int j=0;j<=19;j++){
for(int k=0;k<=19;k++){
if(a[i]>>k&1){
if(a[f[i][k]]>>j&1){
g[i][j]=max(g[i][j],f[i][k]);
}
g[i][j]=max(g[i][j],g[f[i][k]][j]);
}
}
}
}
while(m--){
int l,r;
cin>>l>>r;
for(int i=0;i<=19;i++){
if((a[l]>>i&1)&&g[r][i]>=l){
cout<<"Shi\n";
goto togo;
}
}
cout<<"Fou\n";
togo:;
}
return 0;
}
}
int main(){return asbt::main();}
C. 小恐龍
將隕石塊分塊，預處理出每個塊在 \(i\) 時間內能增長的魔法值 \(f_i\)。對于每個小恐龍，枚舉每一個塊，如果先看這個塊有沒有被清空過，被清空過就判斷它能不能把小恐龍跑死，跑死就直接跑，跑不死就直接用 \(f\) 數組處理答案；如果沒清空過那就只好暴力跑了，但顯然每一個塊頂多這樣暴力一次，因此總復雜度 \(O((n+q)\sqrt{n})\)。空間限制比較吃緊，因此需要一個塊一個塊地跑，于是空間是線性的。
Code
#include<bits/stdc++.h>
#define int long long
#define il inline
using namespace std;
namespace asbt{
const int maxn=4e5+5,B=450,T=4e5;
int n,m,c[maxn],r[maxn],t[maxn],h[maxn];
int a[maxn],f[maxn],bn,L[505],R[505];
bool flag;
il void work(int x,int y,int t){
flag=0;
for(int i=L[x];i<=R[x];i++){
a[i]=min(a[i]+r[i]*t,c[i]);
if(a[i]<=h[y]){
h[y]-=a[i],a[i]=0;
}
else{
flag=1;
a[i]-=h[y],h[y]=0;
}
}
}
il void solve(int x){
memset(f,0,sizeof(f));
for(int i=L[x];i<=R[x];i++){
f[1]+=r[i],f[min(c[i]/r[i],T)+1]-=r[i];
}
for(int i=1;i<=T;i++){
f[i]+=f[i-1];
}
for(int i=L[x];i<=R[x];i++){
f[min(c[i]/r[i],T)+1]+=c[i]%r[i];
}
for(int i=1;i<=T;i++){
f[i]+=f[i-1];
}
flag=1;
for(int i=1,lst=0;i<=m;i++){
if(!h[i]){
continue;
}
int tmp=t[i]-lst;
if(flag){
work(x,i,tmp);
}
else if(h[i]<=f[tmp]){
work(x,i,tmp);
}
else{
h[i]-=f[tmp];
}
lst=t[i];
}
}
int main(){
ios::sync_with_stdio(0),cin.tie(0);
cin>>n;
for(int i=1;i<=n;i++){
cin>>c[i]>>r[i];
a[i]=c[i];
}
cin>>m;
for(int i=1;i<=m;i++){
cin>>t[i]>>h[i];
}
bn=(n+B-1)/B;
for(int i=1;i<=bn;i++){
L[i]=R[i-1]+1;
R[i]=min(R[i-1]+B,n);
}
for(int i=1;i<=bn;i++){
solve(i);
}
int ans=0;
for(int i=1;i<=m;i++){
ans+=h[i];
}
cout<<ans;
return 0;
}
}
signed main(){return asbt::main();}
/*bb*/
浙公網安備 33010602011771號