20231005 B 组模拟赛 题解
前言
终于找到时间补以前的题解了。
这场我记得好像爆大零了，因为由于标题原因，我把这场当成 CSP 模拟赛就在冲 T1。事实证明不管什么考试还是应该先看一遍所有题再考虑做哪道。
T4 要用 【10】最小树形图，准备学了最小树形图再写。
T1
首先容易发现，若 \(a_1+b_1+c_1=a_2+b_2+c_2\)，除非 \(a_1=a_2,b_1=b_2,c_1=c_2\)，否则 \((a_1,b_1,c_1),(a_2,b_2,c_2)\) 必然不互相偏序，且容易发现若把总和相同的所有三元组都取完了，那么再加任意一个三元组必定会被偏序。
总和相同的三元组可以 \(O(n^2)\) 枚举，这道题可以 \(O(n^3)\) 过，\(O(n)\) 枚举总和就可过了，但其实你打表可以发现在 \(sum=\frac{3n}{2}\) 时个数取到最大值。
严谨证明可以参考附件里的官方题解。
参考代码
#include<bits/stdc++.h>
#define mem(a,b) memset(a,b,sizeof(a))
#define forup(i,s,e) for(int i=(s);i<=(e);i++)
#define fordown(i,s,e) for(int i=(s);i>=(e);i--)
using namespace std;
#define gc getchar()
inline int read(){
int x=0,f=1;char c;
while(!isdigit(c=gc)) if(c=='-') f=-1;
while(isdigit(c)){x=(x<<3)+(x<<1)+(c^48);c=gc;}
return x*f;
}
#undef gc
const int N=605,inf=0x3f3f3f3f;
int n,m;
struct Node{
int x,y,z;
};
vector<Node> ans;
signed main(){
n=read();m=(n*3)/2;
forup(i,0,n){
forup(j,0,n){
int k=m-i-j;
if(k<0||k>n) continue;
ans.push_back(Node{i,j,k});
}
}
printf("%d\n",(int)ans.size());
for(auto i:ans){
printf("%d %d %d\n",i.x,i.y,i.z);
}
}
T2
首先直接做是不好做的，长度为实数的区间个数是正无穷的，考虑寻找性质。
首先容易发现若 \([l,r]\) 两端都不是某单一材质区间的（下文“区间”均指这个，询问区间用“\([l,r]\)”指代）端点，那么可以考虑左右两边哪边密度大调整到对应的端点（如果密度一样那么调整之后不会变劣）。故我们可以得出结论，\([l,r]\) 中必定有至少一边是区间端点。
但是现在区间个数显然还是正无穷的，考虑另一边。容易想到，若另一边不是区间端点，\([l,r]\) 的密度又不是上界 \(R\) 或下界 \(L\)，那么这样必定是不优的，因为若最后一段密度较大，显然取到上界/下一个端点会比较优，若密度较小，显然取到下界/上一个端点会比较优。
那么我们可以得出结论了：最终的 \([l,r]\) 要么两边都是区间端点，要么一边是区间端点，区间质量取到 \(L\) 或 \(R\)。第二种情况区间个数是 \(O(n)\) 的，可以直接暴力全求出来，我们考虑第一种情况怎么求。
我们设质量的前缀和为 \(summ_i\)，长度的前缀和为 \(suml_i\)。如果答案取到的区间为 \((s,t]\)，密度为 \(P\)，那么容易发现 \(\frac{summ_t-summ_s}{suml_t-suml_s}=P\)，这玩意长得就很 01 分数规划，稍微移一下项容易发现 \(summ_r-Psuml_r=summ_l-Psuml_l\)，然后就可以二分答案了。关于 checker，其实就是区间在线求最大值，可以单调队列维护。
复杂度 \(O(n\log n)\)。
参考代码
#include<bits/stdc++.h>
#define mem(a,b) memset(a,b,sizeof(a))
#define forup(i,s,e) for(i64 i=(s);i<=(e);i++)
#define fordown(i,s,e) for(i64 i=(s);i>=(e);i--)
using namespace std;
using i64=long long;
#define gc getchar()
inline i64 read(){
i64 x=0,f=1;char c;
while(!isdigit(c=gc)) if(c=='-') f=-1;
while(isdigit(c)){x=(x<<3)+(x<<1)+(c^48);c=gc;}
return x*f;
}
#undef gc
const i64 N=3e5+5,inf=0x3f3f3f3f;
const double eps=1e-7;
i64 n;
double l[N],sl[N],p[N],sm[N],L,R;
double ans=0;
void work(double M){
i64 r=1;
while(r<n&&sm[r+1]<=M) ++r;
forup(i,1,n){
while(r<n&&sm[r+1]-sm[i-1]<=M) ++r;
double mm=sm[r]-sm[i-1],am=M-mm;
double len=sl[r]-sl[i-1];
len+=am/p[r+1];
ans=max(ans,M/len);
}
}
void dwork(double M){
i64 r=n+1;
while(r>1&&sm[n]-sm[r-2]<=M) --r;
fordown(i,n,1){
while(r>1&&sm[i]-sm[r-2]<=M) --r;
double mm=sm[i]-sm[r-1],am=M-mm;
double len=sl[i]-sl[r-1];
len+=am/p[r-1];
ans=max(ans,M/len);
}
}
double a[N];
bool chk(double mm){
forup(i,1,n){
a[i]=sm[i]-sl[i]*mm;
}
deque<int> q;
int r=1;
forup(i,1,n){
while(r<i&&sm[i]-sm[r]>=L){
while(q.size()&&a[q.back()]>=a[r]) q.pop_back();
q.push_back(r);
++r;
}
while(q.size()&&sm[i]-sm[q.front()]>R) q.pop_front();
if(q.size()&&a[i]>=a[q.front()]) return true;
}
return false;
}
signed main(){
n=read();L=read();R=read();
forup(i,1,n){
l[i]=read();
sl[i]=sl[i-1]+l[i];
}
forup(i,1,n){
p[i]=read();
sm[i]=sm[i-1]+p[i]*l[i];
}
work(L);work(R);
dwork(L);dwork(R);
double ll=0,rr=1e6,mm;
while(rr-ll>=eps){
mm=(ll+rr)/2;
if(chk(mm)) ll=mm;
else rr=mm;
}
ans=max(ans,ll);
printf("%.10lf",ans);
}
T3
树上问题通常可以优先考虑树形 DP，但是这道题给的信息不太好直接维护，因为切下来的块可能是“除去某棵子树”的部分。考虑转化一下。
其实也非常简单，我们看成两种操作，一种是保留当前子树，另一种是删除当前子树。而每个保留子树操作所删除的子树大小其实是很好求出的，这样所有信息都能在子树内维护了。
然后考虑怎么设计状态，由于 \(k\) 是很小的，考虑状态压缩。那么设 \(dp_{i,msk,j}\) 表示在 \(i\) 子树内，进行过的操作集合为 \(msk\)，第一次保留子树的操作是 \(j\) 的方案数。为什么要记保留子树的操作呢？因为很多操作的可行性和这棵子树是否保留有关。若该子树内未进行保留子树操作 \(j\) 取 \(k+1\)。
然后考虑 DP 转移，假设现在要把 \(u,v\) 两结点的状态 \(dp_{u,s_1,j_1},dp_{v,s_2,j_2}\) 合并，那么两状态能合并，当且仅当：
- \((u,v)\in E\)：不解释。
- \(j_1=k+1\vee j_2=k+1\)：这个显然吧，不可能两棵子树同时都有保留子树操作，因为保留了一边的话另一边必然被删掉了。
- \(s_1\cap s_2=\varnothing\)：这个也显然吧，一个操作只会进行一次。
那么我们可以枚举子集维护条件 \(3\)，然后直接维护条件 \(2\)，这一部分复杂度是 \(O(nk3^k)\) 的。
然后考虑对于状态 \(dp_{u,msk,j}\) 当前子树和父亲的边能不能断开作为一个全新的操作 \(j'\)。
首先，无论如何，\(j'\) 都不能在 \(msk\) 中，因为你不能进行一个操作两次，若这是一个保留子树操作，那么显然有 \(j'<j\)，因为你不可能先保留后面的再保留前面的吧。若这是一个删除子树操作，那么必然 \(j'\) 比 \(msk\) 中最大值还大，因为假如你把这条边断开了，那么下面的子树就不存在了，显然是不对的。然后对于子树大小问题，可以简单维护，这里不做赘述。
复杂度 \(O(nk3^k+nk2^k)\)。
参考代码
#include<bits/stdc++.h>
#define mem(a,b) memset(a,b,sizeof(a))
#define forup(i,s,e) for(int i=(s);i<=(e);i++)
#define fordown(i,s,e) for(int i=(s);i>=(e);i--)
using namespace std;
#define gc getchar()
inline int read(){
int x=0,f=1;char c;
while(!isdigit(c=gc)) if(c=='-') f=-1;
while(isdigit(c)){x=(x<<3)+(x<<1)+(c^48);c=gc;}
return x*f;
}
#undef gc
const int N=5005,mod=998244353;
int n,m,a[N],s[N],sz[N],mx[1<<6|5];
vector<int> e[N];
int dp[N][1<<6|5][10],f[1<<6|5][10];
void dfs(int x,int fa){
dp[x][0][m+1]=1;
sz[x]=1;
for(auto i:e[x]){
if(i==fa) continue;
dfs(i,x);
sz[x]+=sz[i];
forup(i,0,(1<<m)-1){
forup(j,1,m+1){
f[i][j]=dp[x][i][j];
dp[x][i][j]=0;
}
}
forup(s1,0,(1<<m)-1){
int pp=((1<<m)-1)^s1;
for(int s2=pp;s2;s2=(s2-1)&pp){
int msk=s1|s2;
forup(j,1,m){
if(mx[s2]<j) (dp[x][msk][j]+=1ll*f[s1][j]*dp[i][s2][m+1]%mod)%=mod;
if(mx[s1]<j) (dp[x][msk][j]+=1ll*f[s1][m+1]*dp[i][s2][j]%mod)%=mod;
}
(dp[x][msk][m+1]+=1ll*f[s1][m+1]*dp[i][s2][m+1]%mod)%=mod;
}
int s2=0,msk=s1|s2;
forup(j,1,m){
if(mx[s2]<j) (dp[x][msk][j]+=1ll*f[s1][j]*dp[i][s2][m+1]%mod)%=mod;
}
(dp[x][msk][m+1]+=1ll*f[s1][m+1]*dp[i][s2][m+1]%mod)%=mod;
}
}
if(x==1) return;
forup(i,0,(1<<m)-1){
forup(j,1,m+1){
f[i][j]=dp[x][i][j];
}
}
forup(msk,0,(1<<m)-1){
int sum=0;
forup(j,1,m){
if(msk&(1<<(j-1))){
sum+=s[j];
}
}
forup(k,mx[msk]+1,m){
if(sum+s[k]==sz[x]){
(dp[x][msk|(1<<(k-1))][m+1]+=f[msk][m+1])%=mod;
}
}
forup(j,1,m+1){
if(!f[msk][j]) continue;
int nw=0;
forup(k,1,j-1){
if(msk&(1<<(k-1))){
nw+=s[k];
continue;
}
if(sz[x]==a[k]+nw){
(dp[x][msk|(1<<(k-1))][k]+=f[msk][j])%=mod;
}
}
}
}
}
signed main(){
n=read();
forup(i,1,n-1){
int u=read(),v=read();
e[u].push_back(v);
e[v].push_back(u);
}
m=read();
int nw=0;
forup(i,1,1<<m){
if(i==(i&-i)) ++nw;
mx[i]=nw;
}
a[0]=n;
forup(i,1,m){
a[i]=read();
s[i]=a[i-1]-a[i];
}
dfs(1,0);
int ans=0;
forup(i,1,m+1) (ans+=dp[1][(1<<m)-1][i])%=mod;
printf("%d\n",ans);
}