由于第三题超出了我的能力范围...于是只写了前两道

 

 对于20%,我们设f[i][j]表示前i个商店消费了j元的方案数是多少，那么我们枚举每个商店花费了多少钱就可以做到nkw。

对于50%,我们可以令f[i][j]表示前i个商店消费0...j-1的方案数之和是多少，也就是前缀和的思想，来将复杂度优化到nk。

对于100%的数据，我们发现是哪m个商店有限制其实没关系，所以可以先计算m个有限制的商店，复杂度为n^2*w,然后剩下的问题就是将某个数分成若干段的方案数，其实就是一个组合数问题，隔板法解决，注意特判n==m的情况。

 

1 #include
      
        2 #include
       
         3 #include
        
          4   5 using namespace std; 6 void rd(int &x){ 7  x=0;int f=1;char ch=getchar(); 8  while(ch<'0' || ch>'9'){
    if(ch=='-')f=-1;ch=getchar();} 9  while(ch<='9' && ch>='0')x=x*10+ch-'0',ch=getchar();10  x*=f;11 }12  13 const int mod=1e9+7;14 const int inf=1e7+10;15  16 int n,m,k;17 int w[305];18 int f[2][100005];19 int fac[inf],inv[inf];20  21 int fst(int x,int y){22  int ans;23  for(ans=1;y;x=1ll*x*x%mod,y>>=1)24   if(y&1)ans=1ll*ans*x%mod;25  return ans;26 }27  28 int C(int x,int y){29     if(y==-1)return x==-1;30  return 1ll*fac[x]*inv[y]%mod*inv[x-y]%mod;31 }32  33 int main(){34     rd(n);rd(m);rd(k);35     for(int i=1;i<=m;i++)rd(w[i]);36     for(int i=1;i<=100000;i++)f[0][i]=1;37     for(int i=1;i<=m;i++){38         int o=i&1;39      for(int j=1;j<=100000;j++){40       f[o][j]=f[o][j-1];41       (f[o][j]+=(f[o^1][j]-f[o^1][max(j-w[i]-1,0)]+mod)%mod)%=mod;42         }43     }44     int o=m&1;45     for(int i=100000;i>=1;i--)f[o][i]=(f[o][i]-f[o][i-1]+mod)%mod;46     fac[0]=1;47     for(int i=1;i<=k+n;i++)fac[i]=1ll*fac[i-1]*i%mod;48     inv[k+n]=fst(fac[k+n],mod-2);49     for(int i=k+n-1;i>=0;i--)inv[i]=1ll*inv[i+1]*(i+1)%mod;50     int ans=0,lst=n-m;51     for(int i=1;i<=min(k+1,100000);i++){52         ans+=1ll*f[o][i]*C(k-i+1+lst-1,lst-1)%mod;53         ans%=mod;54     }55     printf("%d\n",ans);56     return 0;57 }
        
       
      

 

 

 

 

对于30%，每次询问暴力最小生成森林即可。(与最小生成树过程一致)

对于另外30%，边权随编号递增。我们对于编号为l到r的这个区间，从左到右依次插入每一条边，如果两端点不在同一个联通块内，那么就连上，否则不连。我们可以发现，如果我们求出了l...m这个区间，想得到l...r所需要连的边是什么，只需要在l...m对应的边中找到编号小于r的边是哪些即可。因为r+1...m的插入不会影响l...r的边。于是问题就变成了如何求出所有的l...m。我们可以从第m条边倒着插入，如果两端点不连通，就连上，不然删掉两端点的路径上权值最大的边，再加入这条边。删边直接暴力找即可。用树状数组维护编号小于r的和。可以对询问离线排序后解决。

1 #include
      
        2 #include
       
         3 #include
        
          4 #define LL long long 5   6 using namespace std; 7 void rd(int &x){ 8  x=0;int f=1;char ch=getchar(); 9  while(ch<'0' || ch>'9'){
    if(ch=='-')f=-1;ch=getchar();}10  while(ch<='9' && ch>='0')x=x*10+ch-'0',ch=getchar();11  x*=f;12 }13  14 const int inf=105;15  16 int n,m,q;17 struct edge{18     int u,v,c;19 }e[100005];20 struct query{21     int l,r;22     int id;23     int ans;24     bool operator < (const query &o)const{25      return l
         
          mxc)mxc=e[a[x][fa2[x]]].c,mxu=x,mxv=fa2[x];55   x=fa2[x];56     }57     add(a[mxu][mxv],-mxc);58     a[mxu][mxv]=0;a[mxv][mxu]=0;59 }60  61 int main(){62     rd(n);rd(m);rd(q);63     for(int i=1;i<=m;i++)rd(e[i].u),rd(e[i].v),rd(e[i].c);64     for(int i=1;i<=q;i++)rd(t[i].l),rd(t[i].r),t[i].id=i;65     sort(t+1,t+q+1);66     for(int i=1;i<=n;i++)fa[i]=i;67     int now=q;68     for(int i=m;i>=1;i--){69      init();70      int f1=get_fa(e[i].u),f2=get_fa(e[i].v);71      if(f1==f2)del(e[i].u,e[i].v);72      fa[f1]=f2;73      a[e[i].u][e[i].v]=a[e[i].v][e[i].u]=i;74      add(i,e[i].c);75      while(now>=1 && t[now].l==i)t[now].ans=sum(t[now].r),now--;76     }77     sort(t+1,t+q+1,cmp);78     for(int i=1;i<=q;i++)printf("%d\n",t[i].ans);79     return 0;80 }
         
        
       
      

对于100%的数据，我们可以用线段树来维护。每个节点维护其对应的边区间选择哪些边最优，最多选择n-1条边，合并即对两个节点的所有答案边重新跑一边kruskal。求答案的时候先取出对应的log个区间，然后两两合并会比所有的一起合并快一个loglogm，而且会好写一点。

1 #include
      
        2 #include
       
         3 #include
        
          4 #define LL long long 5   6 using namespace std; 7 void rd(int &x){ 8  x=0;int f=1;char ch=getchar(); 9  while(ch<'0' || ch>'9'){
    if(ch=='-')f=-1;ch=getchar();}10  while(ch<='9' && ch>='0')x=x*10+ch-'0',ch=getchar();11  x*=f;12 }13  14 const int inf=100005;15  16 int n,m,q;17 struct edge{18  int u,v,c,id;19  bool operator < (const edge &o)const{20   return c
         
          >1)50 #define ls o<<151 #define rs o<<1|152  53 void build(int l,int r,int o){54  if(l==r)t[o].insert(l);55  else {56   build(l,mid,ls);build(mid+1,r,rs);57   t[o]=merge(t[ls],t[rs]);58     }59 }60  61 node sta[inf];62 int top;63  64 void get_segment(int l,int r,int o,int L,int R){65  if(l>=L && r<=R)sta[++top]=t[o];66  else {67   if(mid>=L)get_segment(l,mid,ls,L,R);68   if(mid