【比賽記錄】2025CSP-S模擬賽10
A. 返鄉
當所有 \(a+b+c\) 都相等時，顯然沒有偏序。使這個和為 \(\lfloor\frac{3\times n}{2}\rfloor\) 時，顯然是數量最多的。
然后實際上這就是最優構造，因為它顯然無法再往里加東西了。
Code
#include<bits/stdc++.h>
#define ll long long
#define il inline
#define mp make_pair
#define fir first
#define sec second
#define pb push_back
using namespace std;
namespace asbt{
int n;
vector<pair<pair<int,int>,int> > p;
int main(){
ios::sync_with_stdio(0),cin.tie(0);
cin>>n;
int sum=n*3/2;
for(int i=0;i<=n;i++){
for(int j=0;j<=n;j++){
int k=sum-i-j;
if(k>=0&&k<=n){
p.pb(mp(mp(i,j),k));
}
}
}
cout<<p.size()<<"\n";
for(auto x:p){
cout<<x.fir.fir<<" "<<x.fir.sec<<" "<<x.sec<<"\n";
}
return 0;
}
}
int main(){return asbt::main();}
B. 連接
首先有一個性質，我們取的鋼管一定至少有一端在分界線上。且如果另一端不在分界線上，總質量必然取到了 \(L\) 或 \(R\)。原因是如果沒有取到，就一定可以向大密度方向繼續延伸（或將小密度鋼管縮掉）。
于是我們只消分別計算這兩種情況。對于只有一端是分界線的情況，我們可以枚舉這個分界線，然后二分出另一端的位置。注意分界線有可能在左邊或右邊。對于兩端都是分界線的情況，我們直接去二分答案，枚舉左端點并雙指針出右端點所在的區間，判斷能否取到比 \(mid\) 更大的密度即可。
具體的判斷，進行一個前綴長度和 \(sa\) 和前綴質量和 \(sm\)，如果能更大，那么一定有：
\[\frac{sm_i-sm_{l-1}}{sl_i-sl_{l-1}}>mid\\
\Leftrightarrow sm_i-mid\times sl_i>sm_{l-1}-mid\times sl_{l-1}
\]
所以用單調隊列維護 \(sm_i-mid\times sl_i\) 的最大值即可。
Code
#include<bits/stdc++.h>
#define int long long
#define il inline
using namespace std;
namespace asbt{
const int maxn=3e5+5;
int n,ll,rr,a[maxn],b[maxn],sa[maxn],sm[maxn],q[maxn];
double ans;
il void solve(){
for(int i=1;i<=n;i++){
sa[i]=sa[i-1]+a[i];
sm[i]=sm[i-1]+a[i]*b[i];
}
for(int i=1,l,r;i<=n;i++){
// cout<<i<<"\n";
l=i,r=n;
while(l<r){
int mid=(l+r)>>1;
if(sm[mid]-sm[i-1]<ll){
l=mid+1;
}
else{
r=mid;
}
}
if(sm[l]-sm[i-1]>=ll){
// cout<<l<<" "<<ll/(sa[l-1]-sa[i-1]+(ll-sm[l-1]+sm[i-1])*1.0/b[l])<<"\n";
ans=max(ans,ll/(sa[l-1]-sa[i-1]+(ll-sm[l-1]+sm[i-1])*1.0/b[l]));
}
l=i,r=n;
while(l<r){
int mid=(l+r)>>1;
if(sm[mid]-sm[i-1]<rr){
l=mid+1;
}
else{
r=mid;
}
}
if(sm[l]-sm[i-1]>=rr){
// cout<<l<<" "<<rr/(sa[l-1]-sa[i-1]+(rr-sm[l-1]+sm[i-1])*1.0/b[l])<<"\n";
ans=max(ans,rr/(sa[l-1]-sa[i-1]+(rr-sm[l-1]+sm[i-1])*1.0/b[l]));
}
}
}
signed main(){
scanf("%lld%lld%lld",&n,&ll,&rr);
for(int i=1;i<=n;i++){
scanf("%lld",a+i);
}
for(int i=1;i<=n;i++){
scanf("%lld",b+i);
}
solve();
// cout<<ans<<"\n";
reverse(a+1,a+n+1);
reverse(b+1,b+n+1);
solve();
double L=1,R=1e6;
while(R-L>1e-7){
double mid=(L+R)/2;
for(int i=1,l=1,r=0,hd=1,tl=0;i<=n;i++){
while(r<n&&sm[r+1]-sm[i-1]<=rr){
r++;
while(hd<=tl&&sm[r]-sa[r]*mid>=sm[q[tl]]-sa[q[tl]]*mid){
tl--;
}
q[++tl]=r;
}
while(l<n&&sm[l]-sm[i-1]<ll){
l++;
while(hd<=tl&&q[hd]<l){
hd++;
}
}
if(hd>tl||sm[l]-sm[i-1]<ll||sm[r]-sm[i-1]>rr){
continue;
}
if(sm[q[hd]]-sa[q[hd]]*mid>sm[i-1]-sa[i-1]*mid){
L=mid;
goto togo;
}
}
R=mid;
togo:;
}
printf("%.8f",max(ans,L));
return 0;
}
}
signed main(){return asbt::main();}
C. 習慣孤獨
考慮第 \(i\) 次切要切掉的子樹大小，為 \(a_{i-1}-a_i\)。切掉的子樹就沒用了，故這 \(k\) 次切割就成了相互獨立的了。\(k\) 又那么小，考慮狀壓 DP。
設 \(f_{u,S}\) 表示 \(u\) 的子樹，切割狀態為 \(S\) 的方案數。那么用兒子更新父親是容易的。然后還要考慮 \(u\) 本身。這時需要注意，\(u\) 的切割是必須放在 \(u\) 的子樹之后的。
然后還得考慮 \(u\) 子樹外的貢獻，顯然需要換根。但是這個形式，直接從總貢獻中剔除一個點是比較困難的。因此需要對 \(u\) 的兒子做前后綴和。注意此時還得再算上 \(u\) 單獨的貢獻。
最后統計答案，我們要求 \(u\) 最后留下，所以不能用 \(f\) 統計答案。需要另計一個 \(g\) 來計算 \(u\) 的子樹除了 \(u\) 的貢獻。最后答案需要再除以 \(a_k\)。
Code
#include<bits/stdc++.h>
#define ll long long
#define il inline
#define pb push_back
using namespace std;
namespace asbt{
const int maxn=5e3+5,maxm=(1<<6)+5,mod=998244353;
typedef int DP[maxn][maxm];
int n,m,U,a[10],sz[maxn],hp[maxm];
DP f,g,pre,suf,h;
vector<int> e[maxn];
il int qpow(int x,int y=mod-2){
int res=1;
while(y){
if(y&1){
res=res*1ll*x%mod;
}
x=x*1ll*x%mod,y>>=1;
}
return res;
}
il void dfs1(int u,int fa){
sz[u]=1,f[u][0]=1;
int fid=-1;
for(int i=0,v;i<e[u].size();i++){
v=e[u][i];
if(v==fa){
fid=i;
continue;
}
dfs1(v,u);
sz[u]+=sz[v];
for(int j=0;j<=U;j++){
hp[j]=f[u][j];
f[u][j]=0;
// cout<<hp[j]<<" ";
}
// puts("");
for(int j=0,S;j<=U;j++){
S=U^j;
for(int k=S;;k=(k-1)&S){
(f[u][j|k]+=hp[j]*1ll*f[v][k]%mod)%=mod;
if(!k){
break;
}
}
}
}
if(~fid){
e[u].erase(e[u].begin()+fid);
}
for(int i=0;i<=U;i++){
g[u][i]=f[u][i];
}
for(int i=0,sum;i<=U;i++){
sum=0;
for(int j=1;j<=m;j++){
if(i>>(j-1)&1){
sum+=a[j];
}
}
sum=sz[u]-sum;
for(int j=m;j;j--){
if(i>>(j-1)&1){
break;
}
if(sum==a[j]){
(f[u][i|1<<(j-1)]+=g[u][i])%=mod;
}
}
}
}
il void dfs2(int u){
for(int i=0;i<=e[u].size()+1;i++){
for(int j=0;j<=U;j++){
pre[i][j]=suf[i][j]=0;
}
}
pre[0][0]=suf[e[u].size()+1][0]=1;
for(int i=0,v;i<e[u].size();i++){
v=e[u][i];
for(int j=0,S;j<=U;j++){
S=U^j;
for(int k=S;;k=(k-1)&S){
(pre[i+1][j|k]+=pre[i][j]*1ll*f[v][k]%mod)%=mod;
if(!k){
break;
}
}
}
}
for(int i=e[u].size(),v;i;i--){
v=e[u][i-1];
for(int j=0,S;j<=U;j++){
S=U^j;
for(int k=S;;k=(k-1)&S){
(suf[i][j|k]+=suf[i+1][j]*1ll*f[v][k]%mod)%=mod;
if(!k){
break;
}
}
}
}
for(int i=0,v;i<e[u].size();i++){
v=e[u][i];
for(int j=0,S;j<=U;j++){
S=U^j;
for(int k=S;;k=(k-1)&S){
(h[v][j|k]+=pre[i][j]*1ll*suf[i+2][k]%mod)%=mod;
if(!k){
break;
}
}
}
for(int j=0;j<=U;j++){
hp[j]=h[v][j];
h[v][j]=0;
}
for(int j=0,S;j<=U;j++){
S=U^j;
for(int k=S;;k=(k-1)&S){
(h[v][j|k]+=hp[j]*1ll*h[u][k]%mod)%=mod;
if(!k){
break;
}
}
}
for(int j=0;j<=U;j++){
hp[j]=h[v][j];
}
for(int j=0,sum;j<=U;j++){
sum=0;
for(int k=1;k<=m;k++){
if(j>>(k-1)&1){
sum+=a[k];
}
}
sum=n-sz[v]-sum;
for(int k=m;k;k--){
if(j>>(k-1)&1){
break;
}
if(sum==a[k]){
(h[v][j|1<<(k-1)]+=hp[j])%=mod;
}
}
}
}
for(int v:e[u]){
dfs2(v);
}
}
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);
}
cin>>m;
U=(1<<m)-1;
for(int i=1;i<=m;i++){
cin>>a[i];
}
a[0]=n;
for(int i=m+1;i;i--){
a[i]=a[i-1]-a[i];
}
dfs1(1,0);
h[1][0]=1;
dfs2(1);
// puts("666");
int ans=0;
for(int u=1;u<=n;u++){
// cout<<u<<"\n";
for(int i=0;i<=U;i++){
hp[i]=0;
}
for(int i=0,S;i<=U;i++){
// cout<<f[u][i]<<" "<<g[u][i]<<" "<<h[u][i]<<"\n";
S=U^i;
for(int j=S;;j=(j-1)&S){
(hp[i|j]+=g[u][i]*1ll*h[u][j]%mod)%=mod;
if(!j){
break;
}
}
}
(ans+=hp[U])%=mod;
}
cout<<ans*1ll*qpow(a[m+1])%mod;
return 0;
}
}
int main(){return asbt::main();}
浙公網安備 33010602011771號