最近模拟赛抽象题太多了，让他们聚一聚
T1 多校A层冲刺NOIP2024模拟赛18 T3 DBA
暴力比较显然，直接数位dp就好，记搜的复杂度是\(O(n^4)\)的，用递推加前缀和优化可以优化为\(O(n^3)\)，但我还是不理解\(O(n^3)\)凭啥能\(拿97pts\)，虽然和正解没啥关系，但还是放一下记搜的代码：
点击查看代码
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=2000+5,p=1e9+7;
int n,m,a[N];
int x,y,z,l,r,k,t;
int dp[N][15000],ans,tot;
//dp[i][j]表示截止到第i位，和为j的方案数
int dfs(int pos,int sum,bool limit){
if(pos>n){
if(sum==tot)return 1;
else return 0;
}
if(sum>tot)return 0;
if(dp[pos][sum]!=-1&&(!limit))return dp[pos][sum];
int lim=limit?a[pos]:m-1,res=0;
for(int i=0;i<=lim;i++){
res+=dfs(pos+1,sum+i,limit&&i==lim);
}
dp[pos][sum]=res%p;
return res%p;
}
signed main(){
freopen("dba.in","r",stdin);
freopen("dba.out","w",stdout);
ios::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
cin>>m>>n;
memset(dp,-1,sizeof dp);
for(int i=1;i<=n;i++)cin>>a[i],tot+=a[i];
cout<<dfs(1,0,1)-1<<endl;
return 0;
}
点击查看代码
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=2000+5,p=1e9+7;
int n,m,fac[N*N],inv[N*N];
int x,y,z,l,r,k,t,sum;
int ans,tot,a[N];
inline int quickpow(int a,int b){
int res=1;
while(b){
if(b&1)res=res*a%p;
b>>=1;
a=a*a%p;
}return res;
}
void iint(){
fac[0]=1;
for(int i=1;i<=n*m;i++)fac[i]=fac[i-1]*i%p;
inv[n*m]=quickpow(fac[n*m],p-2);
for(int i=n*m-1;i>=0;i--)inv[i]=inv[i+1]*(i+1)%p;
}
inline int C(int n,int m){
if(n<m)return 0;
return fac[n]*inv[n-m]%p*inv[m]%p;
}
inline int slove(int a,int w){
int res=0;
for(int i=0,f=1;i<=a&&i*m<=sum;i++,f=-f){
res+=f*(C(sum-i*m+a,a)-C(sum-w-i*m+a,a)+p)%p*C(a,i)%p+p;
}return res%p;
}
signed main(){
freopen("dba.in","r",stdin);
freopen("dba.out","w",stdout);
ios::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
cin>>m>>n;
iint();
for(int i=1;i<=n;i++)cin>>a[i],sum+=a[i];
for(int i=1;i<n;i++)ans+=slove(n-i,a[i]),sum-=a[i];
cout<<ans%p<<'\n';
return 0;
}
T2 多校A层冲刺NOIP2024模拟赛18 T4 银行的源起
首先讲一下\(O(n^2)\)的做法。
先考虑如果只有一个银行，有一个比较一眼但又不太好想到的性质即为：对于每条边将树分为两部分1，2，如果要想让其最优，要么1中的点全都通过这条边跑到2，要么2中的点全都通过这条边跑到1，即对于每条边的贡献为\(e[i].w*min(size[x],totsize-size[x])\)，这样可以保证让每条边的贡献是最优的，推广到全局即能保证答案最优，这样就可以\(O(n)\)求解最小代价。
考虑两个银行怎么做，如果有两个银行，那么有一条边肯定是不会被任何点经过的，那么原图就被分成了两个部分，这两个部分都只有一个银行，可以直接\(O(n)\)求解，具体如图：
直接枚举哪条边未被经过即可，复杂度\(O(n^2)\)
既然我讲了\(O(n^2)\)做法，那正解肯定和它有点关系，考虑如果要想保证答案正确性，枚举那条边未被经过这个过程肯定不能少，那只能考虑去优化求解贡献的过程，这个时候看这个式子是带着\(min\)的，考虑拆开分类讨论一下：
当\(size[x]>totsize/2\)时贡献为\(e[i].w*size[x]\)，反之\(size[x]<=totsize/2\)贡献为\(totsize*e[i].w-size[x]*e[i].w\)，观察到贡献是和\(size[x]\)紧密相关的，可以直接开一个以\(size\)为下标的权值线段树，查询贡献时直接找到\(size=totsize/2\)的位置，左边，右边分别算贡献即可。
考虑线段树要维护什么信息，看上面的式子，分别用到了\(e[i].w，e[i].w*size[x]\),直接分别维护即可，至于线段树信息怎么更新，额....，好问题，你发现如果只考虑一棵子树内的贡献的话，你直接线段树合并即可，但是另一部分的答案就会变得很难统计，这个时候就不太能用这个线段树上的信息来计算了，所以这个时候我们就要考虑怎么再去维护那一部分的信息。
首先先上一个图，便于一会描述：
现在我们以箭头指向的那条边为界将树分为了两部分：绿色子树和（红+黑）的那棵树
首先绿色子树的贡献直接就可以线段树合并的时候计算，没啥要说的
主要还是红黑部分的贡献的计算：
首先这红黑两部分的\(size_{红黑}=totsize-size_{绿色子树}\)
先考虑红色这条链的贡献计算，可以发现红色这条链完全可以用一个权值树状数组，当你进入一个节点时加上它的贡献，离开时再减去就好，贡献的计算和上面一样，只不过它这条链上的每一个节点的\(size\)都减去了一个\(size_{绿色子树}\)，查询时分界点稍微左偏一下即可
再考虑黑色部分的贡献，虽说它的\(size\)并没有发生改变，但你发现它根本没法用任何东西维护，这个时候就可以直接统计全局对于\(size_{红黑}\)的贡献，然后直接减去绿色子树和红色链上对于\(size_{红黑}\)的贡献就好了，这两个东西都是可以\(O(log)\)做的，至于全局贡献直接开个前缀和数组记一下就好了，直接\(O(1)\)解决了
然后就没啥了，哦，记得离散化一下\(size\)再拿来做下标，要不然可能有点卡常，最后贴个代码：
点击查看代码
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define ls lc[rt]
#define rs rc[rt]
#define pii pair<int,int>
#define fi first
#define se second
#define met(x) memset(x,0,sizeof x)
const int N=1e6+5;
int n,m,a[N],ans[N],sum1[N],sum2[N],w[N];
int x,y,z,l,r,k,t,sum,res,len,root[N];
int h[N],tot,b[N],size[N],wp[N],h1,h2;
struct sb{
int nxt,to,w;
}e[N];
inline void add(int x,int y,int z){
e[++tot]={h[x],y,z};
h[x]=tot;
}
inline int read(){
int s=0;char c=getchar_unlocked();
while(c<'0'&&c>'9')c=getchar_unlocked();
while(c>='0'&&c<='9'){s=(s<<1)+(s<<3)+(c^48);c=getchar_unlocked();}
return s;
}
inline void dfs(int x,int fa){
size[x]=a[x];
for(int i=h[x];i;i=e[i].nxt){
int y=e[i].to;
if(y==fa)continue;
dfs(y,x);
w[y]=e[i].w;
size[x]+=size[y];
}
b[x]=size[x];
// cout<<x<<" "<<b[x]<<endl;
}
struct tree{
int tot,w1[N<<2],w2[N<<2],lc[N<<2],rc[N<<2];
inline void clear(){tot=0;met(w1);met(w2);met(lc);met(rc);}
inline void tag(int rt,int v1,int v2){w1[rt]+=v1,w2[rt]+=v2;}
inline void pushup(int rt){w1[rt]=w1[ls]+w1[rs];w2[rt]=w2[ls]+w2[rs];}
inline void add(pii &a,pii b){a.fi+=b.fi;a.se+=b.se;}
inline void add(int &rt,int l,int r,int pos,int v1,int v2){
if(!rt)rt=++tot;
if(l==r)return tag(rt,v1,v2);
int mid=(l+r)>>1;
pos<=mid?add(ls,l,mid,pos,v1,v2):add(rs,mid+1,r,pos,v1,v2);
pushup(rt);
}
inline pii query(int rt,int l,int r,int L,int R){
if(!rt)return {0,0};
if(L<=l&&r<=R)return {w1[rt],w2[rt]};
int mid=(l+r)>>1;pii res={0,0};
if(L<=mid)add(res,query(ls,l,mid,L,R));
if(R>mid)add(res,query(rs,mid+1,r,L,R));
return res;
}
inline int merge(int x,int y){
if(!x||!y)return x^y;
w1[x]+=w1[y];w2[x]+=w2[y];
lc[x]=merge(lc[x],lc[y]);
rc[x]=merge(rc[x],rc[y]);
return x;
}
}T1;
struct shu{
//支持单点修改，前缀查询
int c1[N],c2[N];
inline int lb(int x){return x&-x;}
inline void clear(){for(int i=1;i<=n;i++)c1[i]=c2[i]=0;}
inline void add(int x,int w1,int w2){while(x<=len)c1[x]+=w1,c2[x]+=w2,x+=lb(x);}
inline pii ask(int x){pii res={0,0};while(x){res.fi+=c1[x],res.se+=c2[x],x-=lb(x);}return res;}
}T2;
//ans=size[x]*e[i].w(size[x]<=totsize/2)+(totsize-size[x])*e[i].w(size[x]>totsize/2)
//ans=size[x]*e[i].w(<=) -size[x]*e[i].w(>) +totsize*((size[x]>totsize/2)*e[i].w)
//开一个下标为size的值域线段树存储两个信息 e[i].w e[i].w*size[x]
inline void get_ans(int x,int fa,int w){
T1.add(root[x],1,len,wp[x],w,size[x]*w);
T2.add(wp[x],w,size[x]*w);ans[x]=0;
h1+=w;h2+=size[x]*w;
for(int i=h[x];i;i=e[i].nxt){
int y=e[i].to;
if(y==fa)continue;
get_ans(y,x,e[i].w);
//子树内
pii res=T1.query(root[y],1,len,upper_bound(b+1,b+1+len,size[y]/2)-b,len);
ans[y]+=res.fi*size[y]-res.se//size>size[y]/2的贡献
+T1.w2[root[y]]-res.se;//size<size[y]/2的贡献
//链上
int sz=size[1]-size[y];
int pos=upper_bound(b+1,b+1+len,sz/2+size[y])-b;
res=T2.ask(pos-1);
ans[y]+=res.se-res.fi*size[y]+(h1-res.fi)*size[y]+(h1-res.fi)*sz-(h2-res.se);
//全局贡献(对于size==size[1]-size[y])(一会再减去算重的贡献)
pos=upper_bound(b+1,b+1+len,sz/2)-b;
ans[y]+=sum2[pos-1]//size<sz/2的贡献
+sz*(sum1[len]-sum1[pos-1])-(sum2[len]-sum2[pos-1]);//size>sz/2的贡献
//减去子树里重复的贡献
res=T1.query(root[y],1,len,pos,len);
ans[y]-=res.fi*sz-res.se//size>size[y]/2的贡献
+T1.w2[root[y]]-res.se;//size<size[y]/2的贡献
//减去链上重复的贡献
res=T2.ask(pos-1);
ans[y]-=res.se+(h1-res.fi)*sz-(h2-res.se);
T1.merge(root[x],root[y]);
}
T2.add(wp[x],-w,-size[x]*w);
h1-=w;h2-=size[x]*w;
}
signed main(){
freopen("banking.in","r",stdin);
freopen("banking.out","w",stdout);
ios::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
t=read();
while(t--){
n=read();tot=0;
T1.clear();T2.clear();
for(int i=1;i<=n;i++)root[i]=h[i]=0;
for(int i=1;i<=n;i++)a[i]=read();
for(int i=1;i<n;i++){
x=read(),y=read(),z=read();
add(x,y,z);add(y,x,z);
}
dfs(1,0);
sort(b+1,b+1+n);
len=unique(b+1,b+1+n)-b-1;
for(int i=1;i<=n;i++)sum1[i]=sum2[i]=0;
for(int i=1;i<=n;i++){
wp[i]=lower_bound(b+1,b+1+len,size[i])-b;
sum1[wp[i]]+=w[i];sum2[wp[i]]+=w[i]*size[i];
}
for(int i=1;i<=len;i++)sum1[i]+=sum1[i-1],sum2[i]+=sum2[i-1];
get_ans(1,0,0);
int ANS=1e18;
for(int i=2;i<=n;i++)ANS=min(ANS,ans[i]);
cout<<ANS<<'\n';
}
return 0;
}