NOIP模拟测试29(A)

T1：

　　题目大意：有一张有向无环图，第$x$次经过边$i$的代价为$a_ix+b_i$，最多经过$c_i$次，起点为1,$s$个点可作为终点，求走$k$次的最小代价。

　　我们新建一个汇点，将所有可做为终点的边到汇点连边，那么本题便成为了费用流模型。

　　贪心策略为：每次走最短路。

　　证明：路径的顺序是可以改变的，设每次走的路径代价是递增的，如果当前不走最短路，那么以后不可能有一条路能将代价追回，所以当前走最短路一定最优。

　　但是每次增广代价是不同的，我们只能进行完一次增广之后立即修改边权。

　　考虑EK，每次用spfa找一条代价最小的增广路，并更新费用即边权，若当前边是正向边，则将正向边权加$a_i$，反向边权减$a_i$，反之将正向边权减$a_i$，反向边权加$a_i$。正向边初始权值为$a_i+b_i$，由于反向边退流退的是上一层的费用，所以初值应赋为$-b_i$。

　　然后增广k次，若流量不能达到k，输出-1。

　　spfa复杂度视为$O(NM)$时，时间复杂度$O(NMK)$，但远远达不到。

Code：

 #include<iostream>

 #include<cstdio>

 #include<queue>

 using namespace std;

 const int N=;

 const int M=;

 const int inf=1e9+;

 int n,m,k,s,nm=,ans=;

 int fi[N],p[N],d[N];

 bool v[N];

 struct edge{

     int v,ne;

     int l,a,b;

 }e[M+N<<];

 queue<int> q;

 int read()

 {

     int s=;char c=getchar();

     while(c<''||c>'') c=getchar();

     while(c>=''&&c<=''){

         s=(s<<)+(s<<)+c-'';

         c=getchar();

     }

     return s;

 }

 void add(int x,int y,int z1,int z2,int z3)

 {

     e[++nm].v=y;e[nm].a=z1;e[nm].b=z1+z2;

     e[nm].l=z3;e[nm].ne=fi[x];fi[x]=nm;

     e[++nm].v=x;e[nm].a=-z1;e[nm].b=-z2;

     e[nm].l=;e[nm].ne=fi[y];fi[y]=nm;

 }

 bool spfa()

 {

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

         p[i]=;d[i]=inf;v[i]=false;

     }

     while(!q.empty()) q.pop();

     d[]=;v[]=true;q.push();

     while(!q.empty()){

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

         v[x]=false;

         for(int i=fi[x];i!=;i=e[i].ne){

             int y=e[i].v;

             if(e[i].l==) continue;

             if(d[y]>d[x]+e[i].b){

                 d[y]=d[x]+e[i].b;p[y]=i;

                 if(!v[y]){

                     v[y]=true;q.push(y);

                 }

             }

         }

     }

     if(d[n]<inf) return true;

     else return false;

 }

 void update()

 {

     int x=n;ans+=d[n];

     while(x!=){

         int y=p[x];

         if((y&)==) e[y].b+=e[y].a,e[y^].b+=e[y^].a;

         else e[y].b-=e[y].a,e[y^].b-=e[y^].a;

         e[y].l-=;e[y^].l+=;

         x=e[y^].v;

     }

 }

 int main()

 {

     scanf("%d%d%d%d",&n,&m,&k,&s);

     n++;

     for(int i=;i<=s;i++){

         int x=read();

         add(x,n,,,inf);

     }

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

         int x=read(),y=read(),a=read(),b=read(),c=read();

         add(x,y,a,b,c);

     }

     int tot=;

     while(tot<k&&spfa()){

         update();tot++;

     }

     if(tot!=k) printf("-1\n");

     else printf("%d\n",ans);

     return ;

 }

T2：

　　题目大意：有两串数字x和y，以及n串数字段，求$[x+1,y]$内至少含有n个数字段的数的个数，对$1e9+7$取模。

　　一个数字段可以被包含多次，重复的数字段也要重复计算。

　　由区间可以看出此题为数位DP，然后发现字串包含，于是想AC自动机。

　　然后这道题变为了AC自动机上的数位DP。

　　按照数位DP方法，我们先求出$[1,y]$中合法解的个数，再减去$[1,x]$中合法解的个数，即为答案。

　　建出AC自动机，每个点的权值为以该节点为结尾的串的数量，用trie图优化，注意每个节点要继承fail的信息。

　　设$dp[i][j][k][0/1]$，代表匹配到第i位，在节点j，匹配了k个子串的方案数，1代表有限制，0代表无限制。

　　对于每个数，有无前缀0与其大小无关，于是我们可以带着前缀0进行DP转移。

　　设$S$为指向$x$的点集，$w[i]$为节点i的权值，$t[i]$为节点i的类型，$a$为较大的边界，则：

　　　　$dp[i][x][j][0]= \sum _{y \in S} dp[i-1][y][j-w[x]][0]+[t[x]<a[i]]* \sum _{y \in S} dp[i-1][y][j-w[x]][1]$

　　　　$dp[i][x][j][1]=[t[x]==a[i]]* \sum _{y \in S} dp[i-1][y][j-w[x]][1]$

　　由于没有考虑前缀0影响，统计答案时只累加长度等于原串的答案即可。

　　时间复杂度$O(NSK)$，$S$为子串总长。

Code：

 #include<iostream>

 #include<cstdio>

 #include<string>

 #include<cstring>

 #include<queue>

 #define LL long long

 using namespace std;

 const LL mod=1e9+;

 int n,k,rt=,cnt=;

 string s;

 int a[][];

 LL dp[][][][];

 bool v[][][][];

 struct trie{

     int ch[],fail;

     int e;

 }t[];

 queue<int> q,q1,q2,q3,q4;

 void insert()

 {

     int now=rt;

     for(int i=;i<s.size();i++){

         int x=s[i]-'';

         if(t[now].ch[x]==)

             t[now].ch[x]=++cnt;

         now=t[now].ch[x];

     }

     t[now].e++;

 }

 void build()

 {

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

         if(t[rt].ch[i]!=) q.push(t[rt].ch[i]);

     }

     while(!q.empty()){

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

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

             if(t[x].ch[i]!=){

                 t[t[x].ch[i]].fail=t[t[x].fail].ch[i];

                 t[t[x].ch[i]].e+=t[t[t[x].fail].ch[i]].e;

                 q.push(t[x].ch[i]);

             }

             else t[x].ch[i]=t[t[x].fail].ch[i];

         }

     }

 }

 LL work(int id)

 {

     memset(dp,,sizeof(dp));

     memset(v,false,sizeof(v));

     while(!q1.empty()){

         q1.pop();q2.pop();q3.pop();q4.pop();

     }

     dp[][rt][][]=;v[][rt][][]=true;

     q1.push();q2.push(rt);q3.push();q4.push();

     while(!q1.empty()){

         int x=q1.front(),y=q2.front(),z=q3.front(),op=q4.front();

         v[x][y][z][op]=false;

         q1.pop();q2.pop();q3.pop();q4.pop();

         if(x==a[id][]) break;

         for(int i=;i<=((op&)==?a[id][x+]:);i++){

             int yy=t[y].ch[i];int zz=z+t[yy].e;

             if(zz>k) zz=k;

             if((op&)==&&i==){

                 if((op&)==&&i==a[id][x+]){

                     dp[x+][yy][zz][]=(dp[x+][yy][zz][]+dp[x][y][z][op])%mod;

                     if(!v[x+][yy][zz][]){

                         q1.push(x+);q2.push(yy);q3.push(zz);q4.push();

                         v[x+][yy][zz][]=true;

                     }

                 }

                 else{

                     dp[x+][yy][zz][]=(dp[x+][yy][zz][]+dp[x][y][z][op])%mod;

                     if(!v[x+][yy][zz][]){

                         q1.push(x+);q2.push(yy);q3.push(zz);q4.push();

                         v[x+][yy][zz][]=true;

                     }

                 }

             }

             else{

                 if((op&)==&&i==a[id][x+]){

                     dp[x+][yy][zz][]=(dp[x+][yy][zz][]+dp[x][y][z][op])%mod;

                     if(!v[x+][yy][zz][]){

                         q1.push(x+);q2.push(yy);q3.push(zz);q4.push();

                         v[x+][yy][zz][]=true;

                     }

                 }

                 else{

                     dp[x+][yy][zz][]=(dp[x+][yy][zz][]+dp[x][y][z][op])%mod;

                     if(!v[x+][yy][zz][]){

                         q1.push(x+);q2.push(yy);q3.push(zz);q4.push();

                         v[x+][yy][zz][]=true;

                     }

                 }

             }

         }

     }

     LL ans=;

     for(int j=;j<=cnt;j++){

         ans=(ans+dp[a[id][]][j][k][])%mod;

         ans=(ans+dp[a[id][]][j][k][])%mod;

     }

     return ans;

 }

 int main()

 {

     scanf("%d%d",&n,&k);

     cin>>s;a[][]=s.size();

     for(int i=;i<=a[][];i++) a[][i]=s[i-]-'';

     cin>>s;a[][]=s.size();

     for(int i=;i<=a[][];i++) a[][i]=s[i-]-'';

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

         cin>>s;insert();

     }

     build();

     LL ans=work();

     ans-=work();

     ans=(ans%mod+mod)%mod;

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

     return ;

 }

巴特西

NOIP模拟测试29(A)

最新文章

热门文章