Lvat_s Blog

首先我们排个序，然后列一个dp方程

设$f[i][j]$为前i小的糖果至少匹配j个药片的数量

那么我们可以利用单调性把这个dp优化到$O(n^2)$

之后我们发现这个可能会重复统计

我们考虑怎么消除重复的部分

首先一个糖果匹配后面药片的总数为$n!$

然后其中重复统计的个数为之后计算的所有dp数组的值乘上一个组合数

那么我们倒着容斥就做完了

详见代码

#include<cstdio>
#include<algorithm>
using namespace std;

const int N=2005;
const long long P=1000000009ll;

int n,m,k;
long long a[N],b[N],C[N][N],fac[N],f[N][N];

int main(){
freopen("3622.in","r",stdin);
freopen("3622.out","w",stdout);
scanf("%d %d",&n,&m);
if((n+m)&1){puts("0");return 0;}
m=n+m>>1;
C[0][0]=fac[0]=f[0][0]=1;
for(int i=1;i<=n;i++)scanf("%lld",&a[i]);
for(int i=1;i<=n;i++)scanf("%lld",&b[i]);
sort(a+1,a+n+1);sort(b+1,b+n+1);
for(int i=1;i<=n;i++){
	fac[i]=fac[i-1]*i%P;
	C[i][0]=C[i][i]=1;
	for(int j=1;j<i;j++)C[i][j]=(C[i-1][j]+C[i-1][j-1])%P;
}
for(int i=1;i<=n;i++){
	while(k<n && a[i]>b[k+1])k++;f[i][0]=1;
	for(int j=0;j<=i;j++)f[i][j]=(f[i-1][j]+f[i-1][j-1]*max(k-j+1,0))%P;
}
for(int i=n;i>=m;i--){
	f[n][i]=f[n][i]*fac[n-i]%P;
	for(int j=i+1;j<=n;j++){
		f[n][i]-=f[n][j]*C[j][i];
		f[n][i]=(f[n][i]+P)%P;
	}
}
printf("%lld\n",f[n][m]);
return 0;
}

类似虚树的东西

首先我们发现答案就是当前存在的点所构成的树的边权和的两倍

所以我们考虑用set维护dfs序，最后减掉一个lca(最前,最后)即可

具体为什么是这样么……你需要自己手动模拟一下

非常妙

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<set>
#include<algorithm>
using namespace std;

const int N=100005;
const long long INF=21000000000000ll;

int n,m,en,h[N],dep[N],pos[N],f[N],lg[N<<1],tag[N],Index,Size;
long long ans,d[N<<1][19],di[N];
set<int> St;

struct Edge{
int b,next;
long long v;
}e[N<<1];

void dfs(int u){
d[pos[u]=++Index][0]=di[u];
for(int i=h[u];i;i=e[i].next){
    int v=e[i].b;
    if(dep[v])continue;
    f[v]=u;
    di[v]=di[u]+e[i].v;
    dep[v]=dep[u]+1;
    dfs(v);
    d[++Index][0]=di[u];
}
}

template<typename T>inline void Read(T &x){char ch;while((ch=getchar())<'0'||ch>'9');x=ch-'0';while((ch=getchar())>='0'&&ch<='9')x=x*10+ch-'0';}
void AddEdge(int sa,int sb,long long sc){e[++en].b=sb;e[en].v=sc;e[en].next=h[sa];h[sa]=en;}
set<int>::iterator Pre(const set<int>::iterator &x){set<int>::iterator Tx=x;return --Tx;}
set<int>::iterator Nxt(const set<int>::iterator &x){set<int>::iterator Tx=x;return ++Tx;}
long long Mn(int u,int v){int w=lg[v-u+1];return min(d[u][w],d[v-(1<<w)+1][w]);}
long long Dist(){if(!Size)return 0ll;int u=*St.begin(),v=*Pre(St.end());return Mn(u,v);}

void Ins(int x){
ans+=d[x][0];
St.insert(x);
Size++;
if(Size==1)return;
set<int>::iterator Tx=St.find(x);
if(Tx==St.begin()){ans-=Mn(*Tx,*Nxt(Tx));return;}
if(Nxt(Tx)==St.end()){ans-=Mn(*Pre(Tx),*Tx);return;}
ans+=Mn(*Pre(Tx),*Nxt(Tx))-Mn(*Tx,*Nxt(Tx))-Mn(*Pre(Tx),*Tx);
}

void Del(int x){
ans-=d[x][0];
if(Size==1){St.erase(x);Size--;return;}
set<int>::iterator Tx=St.find(x);
if(Tx==St.begin()){ans+=Mn(*Tx,*Nxt(Tx));St.erase(x);Size--;return;}
if(Nxt(Tx)==St.end()){ans+=Mn(*Pre(Tx),*Tx);St.erase(x);Size--;return;}
ans-=Mn(*Pre(Tx),*Nxt(Tx))-Mn(*Tx,*Nxt(Tx))-Mn(*Pre(Tx),*Tx);
St.erase(x);
Size--;
}

int main(){
freopen("3991.in","r",stdin);
freopen("3991.out","w",stdout);
Read(n);Read(m);
for(int i=1;i<n;i++){
    int u,v;
    long long w;
    Read(u);Read(v);Read(w);
    AddEdge(u,v,w);
	AddEdge(v,u,w);
}
dfs(1);
for(int i=2;i<=Index;i++)lg[i]=lg[i>>1]+1;
for(int i=1;i<=lg[Index];i++)for(int j=1;j+(1<<i)-1<=Index;j++)d[j][i]=min(d[j][i-1],d[j+(1<<i-1)][i-1]);
for(int i=1;i<=m;i++){
    int x;
    Read(x);
    tag[x]^=1;
    if(tag[x])Ins(pos[x]);
    else Del(pos[x]);
    printf("%lld\n",ans-Dist()<<1);
}
return 0;
}