模拟15 题解（waiting）

T1

60%算法

定义f[i][j]表示枚举到i位置，已经使用过了j个队，

$f[i][j]+=f[i-1][t] ( t \in [max(0,j-k),j])$滚动一下

这是个O(n^3)的，考虑如何优化，发现可以使用前缀和，避免枚举t，$O(n^2)$

 #include<iostream>

 #include<cstdio>

 #include<cmath>

 #include<cstring>

 #include<algorithm>

 #define R register

 #define ll long long

 using namespace std;

 inline int read()

 {

     int f=,x=;char ch=getchar();

     while(ch>''||ch<''){if(ch=='-')f=-;ch=getchar();}

     while(ch<=''&&ch>=''){x=(x<<)+(x<<)+(ch^);ch=getchar();}

     return f*x;

 }

 const int mod=;

 const int maxn=;

 int n,m,k;

 ll f[][maxn],g[][maxn];

 int main()

 {

     //freopen("data1","r",stdin);

     //freopen("1.out","w",stdout);

     n=read(),m=read(),k=read();

     m-=n;k--;

     f[][]=g[][]=;

     for(R int j=;j<=k;++j)

     {

         f[][j]=;

         g[][j]=(g[][j-]+f[][j])%mod;

     }

     for(int j=k+;j<=m;j++)

         g[][j]=g[][j-]%mod;

     R int cnt=;

     for(R int i=;i<=n;++i)

     {

         cnt^=;

         for(R int j=;j<=m;++j)

         {

             R int l=max(,j-k),r=j;

             R ll tot=;

             if(l==)tot=g[cnt^][r];

             else tot=(g[cnt^][r]-g[cnt^][l-]+mod)%mod;

             f[cnt][j]=tot%mod;

             g[cnt][j]=f[cnt][j]%mod;

             if(j)  (g[cnt][j]+=g[cnt][j-])%=mod;

         }

     }

     printf("%lld\n",f[cnt][m]%mod);

 }

100%算法

问题转化成：m个物品，放到n个抽屉里，每个至少放一个，最多放k个

若任何的限制: C(m+n-1,n-1)表示一共有m个物品，分成n组就要用n-1个挡板，把挡板也看成空位，总共m+n-1个空位，选出来n-1个

若考虑至少放一个：C(m-n+n-1,n-1)先用n个物品给每个抽屉放一个，剩了m-n个物品，再加上n-1个空，剩下的同上

再考虑k的限制：C(n,i)*C(m-n-i*k+n-1,n-1)表示至少有i个的数量已经超过k(>=k+1)所以先给n个抽屉放一个之后，再给n个放上k个，使之成为k+1个

就是m-n-i*k，再加上n-1个空

数组开2e7就行，显然n>m直接return0

 #include<iostream>

 #include<cstdio>

 #include<cmath>

 #include<cstring>

 #include<algorithm>

 #define R register

 #define ll long long

 using namespace std;

 inline ll read()

 {

     ll f=,x=;char ch=getchar();

     while(ch>''||ch<''){if(ch=='-')f=-;ch=getchar();}

     while(ch<=''&&ch>=''){x=(x<<)+(x<<)+(ch^);ch=getchar();}

     return f*x;

 }

 const ll mod=;

 const ll maxn=;

 ll fac[maxn],inv[maxn],facinv[maxn];

 ll n,m,k;

 void init()

 {

     fac[]=;

     inv[]=inv[]=facinv[]=facinv[]=;

     for(ll i=;i<=m+n;i++)

     {

         fac[i]=fac[i-]*i*1ll%mod;

         inv[i]=(mod-mod/i)*inv[mod%i]%mod;

         facinv[i]=facinv[i-]*inv[i]%mod;

     }

 }

 ll C(ll n,ll m)

 {

     if(n<m)    return ;

     return 1ll*fac[n]*facinv[n-m]%mod*facinv[m]%mod;

 }

 int main()

 {

     n=read(),m=read(),k=read();

     if(n>m||n*k<m){puts("");return ;}

     init();

     ll ans=C(m-,n-)%mod;

     for(ll i=;i<=n;i++)

     {

         if(m-n<i*k)break;

         ll f=(i&)?-:;

         ans=(ans+1ll*f*C(m-i*k-,n-)%mod*C(n,i)%mod+mod)%mod;

     }

     printf("%lld\n",ans%mod);

 }

T2

对于无环的情况，最优解就是，图中的最长链的长度，，，为什么？

注意审题：只是炸城市，道路不炸，故某一城市毁了，其他城市的联通性不变，所以最长链上最少要炸的次数就是链长，而其他的路径，当然可以在炸最长链上的每个节点的同时也一起炸，有环的话，tarjan所点成scc，然后拓扑排序，把入度为0的节点放入队列中，枚举其子节点，子节点的答案为，父节点答案加上子节点的scc大小，并且这个点可能使用多次，所以要每次取最大值

 #include<iostream>

 #include<cstdio>

 #include<cmath>

 #include<cstring>

 #include<algorithm>

 #include<vector>

 #include<queue>

 using namespace std;

 inline int read()

 {

     int f=,x=;char ch=getchar();

     while(ch>''||ch<''){if(ch=='-')f=-;ch=getchar();}

     while(ch<=''&&ch>=''){x=(x<<)+(x<<)+(ch^);ch=getchar();}

     return f*x;

 }

 const int maxn=;

 int n,m;

 struct node{

     int v,nxt;

 }e[*maxn];int h[maxn],nu;

 void add(int x,int y)

 {

     e[++nu].v=y;

     e[nu].nxt=h[x];

     h[x]=nu;

 }

 struct nodc{

     int v,nxt;

 }ec[maxn*];int hc[maxn],nuc;

 void add_c(int x,int y)

 {

     ec[++nuc].v=y;

     ec[nuc].nxt=hc[x];

     hc[x]=nuc;

 }

 int dfn[maxn],low[maxn],num,top,cnt;

 int sta[maxn],ins[maxn],bl[maxn];

 vector<int>scc[maxn];

 void tarjan(int x)

 {

     dfn[x]=low[x]=++num;

     sta[++top]=x,ins[x]=;

     for(int i=h[x];i;i=e[i].nxt)

     {

         int y=e[i].v;

         if(!dfn[y])

         {

             tarjan(y);

             low[x]=min(low[x],low[y]);

         }

         else if(ins[y])

             low[x]=min(low[x],dfn[y]);

     }

     if(dfn[x]==low[x]){

         int y;cnt++;

         do{

             y=sta[top--],ins[y]=;

             scc[cnt].push_back(y);bl[y]=cnt;

         }while(y!=x);

     }

 }

 int ind[maxn],ans[maxn];

 void topo()

 {

     queue<int>q;

     for(int i=;i<=cnt;i++)

         if(!ind[i])

             q.push(i),ans[i]=scc[i].size();

     while(q.size())

     {//cout<<" ^^^";

         int x=q.front();q.pop();

         for(int i=hc[x];i;i=ec[i].nxt)

         {

             int y=ec[i].v;ind[y]--;

             if(!ind[y])q.push(y);

             int w=scc[y].size();

             if(ans[y]<ans[x]+w)ans[y]=ans[x]+w;

         }

     }

 }

 int main()

 {

     //freopen("data","r",stdin);

     n=read(),m=read();

     for(int i=;i<=m;i++)

     {

         int x=read(),y=read();

         add(x,y);

     }

 //    cout<<"^^^";

     for(int i=;i<=n;i++)

         if(!dfn[i])

             tarjan(i);

     for(int x=;x<=n;x++)

     {

         for(int i=h[x];i;i=e[i].nxt)

         {

             int y=e[i].v;

             if(bl[x]!=bl[y])

                 add_c(bl[x],bl[y]),ind[bl[y]]++;

         }

     }

     topo();

     int an=;

     for(int i=;i<=n;i++)

         an=max(ans[i],an);

     printf("%d\n",an);

 }

巴特西

模拟15 题解（waiting）

T1

60%算法

100%算法

T2

最新文章

热门文章