NOIP模拟测试6

看题目就知道这是一个悲伤的故事。。。

但还有更悲伤的

考崩了，难以描述。

T1把数据范围看成2^12,我TM也是够了。。。

T2思路接近正解，但不知道想了个神魔东西跑了N遍dijstra

T3最狗了，暴力二十分没拿到，因为我打的贪心。。

T1：很水的DP+组合数学

DP转移显然：f[i][j]=sum[i-1][j-1]-sum[i-1][j-m];
但是这样时空复杂度都是（N*d）
但期望复杂度是（N^2）
考虑如何优化
发现f[i][j]实际上有许多零出现，但我们还把它当成有用的状态转移了，因此考虑抹去这些冗余。
用组合数学，f[i][j]的定义改为送出礼物的i天 注意取模！



 AC代码：

 #include<bits/stdc++.h>

 #define MAXN 2005

 #define mem(a) memset(a,0,sizeof(a))

 using namespace std;

 const long long mod=;

 long long C[MAXN],inv[MAXN];

 inline long long Rd()

 {

     long long x=;char c=getchar();long long f=;

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

     while(c>=''&&c<=''){x=x*+c-'';c=getchar();}

     return x*f;

 }

 long long n,d,m;

 long long f[MAXN][MAXN],sum[MAXN][MAXN];

 inline long long qpower(long long a,long long b)

 {

     long long ans=;

     while(b)

     {

         if(b&)ans=ans*a%mod;

         a=a*a%mod;

         b>>=;

     }

     return ans%mod;

 }

 inline void Get_C()

 {

     C[]=d%mod;

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

     {

         C[i]=C[i-]*inv[i]%mod*((d-i+)%mod)%mod;

     }

 }

 int main()

 {

     //freopen("out.in","r",stdin);

     //freopen("a.txt","w",stdout);

     for(long long i=;i<=;i++)inv[i]=qpower(i,mod-);

     while()

     {

         mem(sum);mem(f);

         n=Rd();d=Rd();m=Rd();

         long long ans=;

         Get_C();

         if(n==&&d==&&m==)return ;

         for(long long i=;i<m;i++)f[][i]=,sum[][i]=sum[][i-]+f[][i];

         for(long long i=m;i<=n;i++)sum[][i]=sum[][m-];

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

         {

             for(long long j=;j<=n;j++)

             {

                 if(j>=m)f[i][j]=(mod+sum[i-][j-]-sum[i-][j-m])%mod;

                 else f[i][j]=sum[i-][j-];

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

             }

         }

         for(int i=;i<=n;i++)ans=(ans+C[i]*f[i][n]%mod)%mod;

         cout<<ans%mod<<endl;

     }

     return ;

 }

T2：找最小环

想了一个**算法，时间复杂度O（n^2log(n)）空间复杂度（n^2）

 #include<cstdio>

 #include<queue>

 #include<bits/stdc++.h>

 #define ts puts("---------------");

 #define MAXN 20005

 #define mem(a) memset(a,0,sizeof(a))

 using namespace std;

 int head[MAXN],nxt[MAXN],to[MAXN],cnt,s[MAXN],top,dfn[MAXN],low[MAXN],ans,tot,v[MAXN],val[MAXN];

 bool yes_get,vst[],in_s[MAXN],Fail[MAXN*];

 int edge[][],d[],di[],pre[];

 void clear()

 {

     mem(head);mem(s);mem(dfn);mem(in_s);mem(v);mem(Fail);mem(vst);mem(pre);

     yes_get=ans=tot=cnt=top=;

 }

 inline int Rd()

 {

     int x=;char c=getchar();int f=;

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

     while(c>=''&&c<=''){x=x*+c-'';c=getchar();}

     return x*f;

 }

 void add(int u,int v,int w)

 {

     to[++cnt]=v;

     nxt[cnt]=head[u];

     val[cnt]=w;

     head[u]=cnt;

     return ;

 }

 void Tarjan(int x,int fa)

 {

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

     s[++top]=x;

     in_s[x]=;

     for(int i=head[x];i;i=nxt[i])

     {

         int y=to[i];

         if(y==fa)continue;

         if(!dfn[y])

         {

             v[y]=val[i];

             Tarjan(y,x);

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

         }

         else

         {

             if(in_s[y])

             {

                 if(dfn[y]<low[x])v[x]+=val[i];

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

             }

         }

     }

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

     {

         ans=;

         while(top)

         {

             int p=s[top--];

             in_s[p]=;

             ans+=v[p];

             if(p==)yes_get=;

             if(p==x)break;

         }

     }

     if(!yes_get||!ans)ans=-;

     else return ;

 }

 int Getmin(int i)

 {

     priority_queue<pair<int,int> >Q;

     while(Q.size())Q.pop();

     memset(di,0x3f,sizeof(di));

     mem(vst);

     di[]=;

     Q.push(make_pair(,));

     while(!Q.empty())

     {

         pair<int,int>k=Q.top();Q.pop();

         int x=k.second;

         if(vst[x])continue;

         if(x==i)return di[x];

         vst[x]=;

         for(int i=head[x];i;i=nxt[i])

         {

             if(Fail[i])continue;

             int y=to[i],va=val[i];

             if(va+di[x]<di[y])

             {

                 di[y]=va+di[x];

                 Q.push(make_pair(-di[y],y));

             }

         }

     }

     return di[];

 }

 void pre_Get()

 {

     priority_queue<pair<int,int> >Q;

     memset(d,0x3f,sizeof(d));

     mem(vst);

     d[]=;

     Q.push(make_pair(,));

     while(!Q.empty())

     {

         pair<int,int>k=Q.top();Q.pop();

         int x=k.second;

         if(vst[x])continue;

         vst[x]=;

         for(int i=head[x];i;i=nxt[i])

         {

             int y=to[i],va=val[i];

             if(va+d[x]<d[y])

             {

                 pre[y]=x;

                 d[y]=va+d[x];

                 Q.push(make_pair(-d[y],y));

             }

         }

     }

     return ;

 }

 int main()

 {

 //    freopen("out.in","r",stdin);

 //    freopen("b.txt","w",stdout);

     int t=Rd();

     while(t--)

     {

         clear();

         int n=Rd(),m=Rd();

         if(n==m)

         {

             while(m--)

             {

                 int u=Rd(),v=Rd(),w=Rd();

                 add(u,v,w);

                 add(v,u,w);

             }

             Tarjan(,);

             cout<<ans<<endl;

         }

         else

         {

             ans=0x7f7f7f7f;

             while(m--)

             {

                 int u=Rd(),v=Rd(),w=Rd();

                 add(u,v,w);

                 edge[u][v]=cnt;

                 add(v,u,w);

                 edge[v][u]=cnt;

             }

             pre_Get();

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

             {

                 if(d[i]==d[])continue;

                 int t=i;

                 while(t!=&&t!=)

                 {

                     Fail[edge[pre[t]][t]]=;

                     Fail[edge[t][pre[t]]]=;

                     t=pre[t];

                 }

                 if(Getmin(i)!=di[])ans=min(ans,Getmin(i)+d[i]);

                 t=i;

                 while(t!=)

                 {

                     Fail[edge[pre[t]][t]]=;

                     Fail[edge[t][pre[t]]]=;

                     t=pre[t];

                 }

             }

             cout<<(ans==0x7f7f7f7f?-:ans)<<endl;

         }

     }

     return ;

 }

 /*

 1

 4 5

 1 2 2

 2 3 2

 3 4 2

 1 4 2

 1 3 5

 */

献出我的sb算法

但实际上仔细想想发现，我的算法是有许多冗余的，只需要枚举和一直接相邻的边就够了。

因此。。。

AC代码

 #include<cstdio>

 #include<queue>

 #include<bits/stdc++.h>

 #define ts puts("---------------");

 #define MAXN 80005

 #define mem(a) memset(a,0,sizeof(a))

 using namespace std;

 int head[MAXN],nxt[MAXN],to[MAXN],cnt=,ans,val[MAXN];

 bool Fail[MAXN],vst[];

 int di[];

 void clear()

 {

     mem(head);mem(Fail);

     cnt=;

 }

 inline int Rd()

 {

     int x=;char c=getchar();int f=;

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

     while(c>=''&&c<=''){x=x*+c-'';c=getchar();}

     return x*f;

 }

 void add(int u,int v,int w)

 {

     to[++cnt]=v;

     nxt[cnt]=head[u];

     val[cnt]=w;

     head[u]=cnt;

     return ;

 }

 int Getmin(int i,int ww)

 {

     priority_queue<pair<int,int> >Q;

     while(Q.size())Q.pop();

     memset(di,0x3f,sizeof(di));

     mem(vst);

     di[]=;

     Q.push(make_pair(,));

     while(!Q.empty())

     {

         pair<int,int>k=Q.top();Q.pop();

         int x=k.second;

         if(di[x]+ww>ans)return di[x]+ww;

         if(vst[x])continue;

         if(x==i)return di[x]+ww;

         vst[x]=;

         for(int i=head[x];i;i=nxt[i])

         {

             if(Fail[i])continue;

             int y=to[i],va=val[i];

             if(va+di[x]<di[y])

             {

                 di[y]=va+di[x];

                 Q.push(make_pair(-di[y],y));

             }

         }

     }

     return di[];

 }

 int main()

 {

 //    freopen("out.in","r",stdin);

 //    freopen("b.txt","w",stdout);

     int t=Rd();

     while(t--)

     {

         clear();

         int n=Rd(),m=Rd();

         ans=0x3f3f3f3f;

         while(m--)

         {

             int u=Rd(),v=Rd(),w=Rd();

             add(u,v,w);

             add(v,u,w);

         }

         for(int i=head[];i;i=nxt[i])

         {

             int k=to[i];

             Fail[i]=Fail[i^]=;

             ans=min(ans,Getmin(k,val[i]));

             Fail[i]=Fail[i^]=;

         }

         cout<<(ans==0x3f3f3f3f?-:ans)<<endl;

     }

     return ;

 }

 /*

 1

 4 5

 1 2 2

 2 3 2

 3 4 2

 1 4 2

 1 3 5

 */

LNC的A*算法（借鉴一下，无意侵权）

 #include<iostream>

 #include<cstring>

 #include<cstdio>

 #include<cstring>

 #include<queue>

 using namespace std;

 const int maxn=1e4+,maxm=4e4+,INF=0x3f3f3f3f;

 int T,n,m,x,y,z,dex,yes,tot=,top,cld[maxn],yet[maxn],instack[maxn],stack[maxn],first[maxn];

 struct road{

     int u,t,w,nxt;

 }eage[maxm<<];

 struct point1{

     int id,dis;

     bool friend operator < (const point1 a,const point1 b)

     {

         return a.dis>b.dis;

     }

 }dis[maxn];

 struct point2{

     int id,h;

     bool friend operator < (const point2 a,const point2 b)

     {

         return dis[a.id].dis+a.h>dis[b.id].dis+b.h;

     }

 };

 priority_queue<point1> q1;

 priority_queue<point2> q2;

 void add(int x,int y,int z)

 {

     eage[++tot].u=x;

     eage[tot].t=y;

     eage[tot].w=z;

     eage[tot].nxt=first[x];

     first[x]=tot;

 }

 void clear()

 {

     top=;tot=;

     memset(first,,sizeof(first));

     memset(cld,,sizeof(cld));

     memset(yet,,sizeof(yet));

     memset(instack,,sizeof(instack));

 }

 void dijk()

 {

     memset(yet,,sizeof(yet));

     for(int i=;i<=n;i++) dis[i].id=i,dis[i].dis=INF;

     dis[].dis=;

     q1.push(dis[]);

     while(q1.empty()==)

     {

         int x=q1.top().id;q1.pop();

         if(yet[x]) continue;

         yet[x]=;

         for(int i=first[x];i;i=eage[i].nxt)

             if(dis[x].dis+eage[i].w<dis[eage[i].t].dis)

                 dis[eage[i].t].dis=dis[x].dis+eage[i].w,q1.push(dis[eage[i].t]);

     }

     memset(yet,,sizeof(yet));

 }

 int work(int st)

 {

     while(q2.empty()==) q2.pop();

     point2 x,tmp;

     x.id=st;x.h=;

     q2.push(x);

     int ans=INF;

     while(q2.empty()==)

     {

         x=q2.top();q2.pop();

         yet[x.id]=;

         if(x.id==)

         {

             ans=x.h;

             break;

         }

         for(int i=first[x.id];i;i=eage[i].nxt)

             if(i!=dex&&yet[eage[i].t]==)

             {

                 tmp.id=eage[i].t;

                 tmp.h=eage[i].w+x.h;

                 q2.push(tmp);

             }

     }

     memset(yet,,sizeof(yet));

     return ans;

 }

 void Astar()

 {

     dijk();

     int ans=INF;

     for(int i=first[];i;i=eage[i].nxt)

     {

         dex=i^;

         int t=eage[i].t,d=work(t)+eage[i].w;

         ans=min(d,ans);

     }

     printf("%d\n",ans>?-:ans);

     return ;

 }

 int main()

 {

     scanf("%d",&T);

     while(T--)

     {

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

         while(m--)

         {

             scanf("%d%d%d",&x,&y,&z);

             add(x,y,z);add(y,x,z);

         }

         Astar();

         clear();

     }

 }

T3：又是一道足以把评测机卡崩的题好题标记

毫无头绪？

是的毫无头绪是真的毫无头绪，但根据数据范围可以推测复杂度应该接近O（n）（T=50，5000ms限制啧啧啧）

就此展开，感觉dp否了，递推。。。也不大可能，所以我们自然会想到搜索图论，（好吧我承认有点牵强，但说实话，O(n)的算法真的不多，这总不能单队维护吧QwQ）

然后就会有奇妙的发现：如果两两连边HiaHiaHia，没神魔卵用，就会发现其实操作只是把边反过来而已。而题目的目标就是每个点的入度<=1。

既然这样，那就继续探索。把这个图画出来，手玩小样例后发现图被分成了几个连通块，然后就可以分类讨论了：

1.m>n 显然是不对的，因为要保证每条边都指向一个点，每个点又要被不大于一条边指（这这这不可能）。

2.m=n 是棵基环树！！！！先考虑环，环可以顺时针也可以逆时针，所以分两种情况，再看以环为根的子树，不管环咋转，子树永远是外向的，所以一遍dfs即可

3.m<n 要保证图联通所以这一定是棵树，而且是棵外向树，快乐吗？可问题是根是不确定的。

下面引入新概念：

二次扫描和换根法：对于不定根的树状DP，暴力枚举是O(n^2)，但我们可以先考虑一个点，再考虑用已知点更新未知点，即考虑换根的代价。

但只适用于不管换不换根，旧根与新根的共同子树状态不变。（纯属博猪个人理解，如有错误，多谢指正）

好啦，有了这个强大的方法，我们就可以成功AC了

AC 代码：

 #include<bits/stdc++.h>

 #define mem(a) memset(a,0,sizeof(a))

 #define MAXN 200000

 using namespace std;

 const int mod=;

 struct node{

     int head[MAXN],to[MAXN],nxt[MAXN],cnt,dfn[MAXN],now_minn,now_tot,v[MAXN];long long tot;

     int use,sum,fa[MAXN],d[MAXN],f[MAXN];

     long long ans,minn;

     bool orz[MAXN],vst[MAXN],inlop[MAXN],vst1[MAXN],vst2[MAXN];

     vector<int>lop;

     void clear()

     {

         lop.clear();cnt=;ans=;minn=;tot=;mem(fa);mem(v);

         mem(inlop);mem(vst);mem(vst1);mem(vst2);

         mem(d);mem(f);

         mem(dfn);

         mem(head);

     }

     void add(int u,int v,int opt)

     {

         to[++cnt]=v;

         nxt[cnt]=head[u];

         head[u]=cnt;

         orz[cnt]=opt;

         return ;

     }

     inline int Rd()

     {

         int x=;

         char c=getchar();

         int f=;

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

         while(c>=''&&c<=''){x=x*+c-'';c=getchar();}

         return x*f;

     }

     bool Getlop(int x,int edge)

     {

         dfn[x]=++tot;

         for(int i=head[x];i;i=nxt[i])

         {

             if(i==(edge^))continue;

             int y=to[i];

             if(dfn[y])

             {

                 if(sum==){sum++;continue;}

                 if(sum>)return ;

                 sum++;

                 inlop[y]=;

                 lop.push_back(y);

                 if(orz[i])use=;

                 else use=;

                 int p=x;

                 while(p!=y)

                 {

                     lop.push_back(p);

                     inlop[p]=;

                     use+=v[p];

                     p=fa[p];

                 }

             }

             else {fa[y]=x,v[y]=orz[i];if(Getlop(y,i)==)return ;}

         }

         return ;

     }

     void dp(int x)

     {

         vst[x]=;

         for(int i=head[x];i;i=nxt[i])

         {

             int y=to[i];

             if(vst[y]||inlop[y])continue;

             dp(y);

             d[x]+=d[y];

             if(!orz[i])d[x]++;

         }

         return ;

     }

     void dprt(int x)

     {

         vst2[x]=;

         for(int i=head[x];i;i=nxt[i])

         {

             int y=to[i];

             if(vst2[y]||inlop[y])continue;

             if(orz[i])f[y]=f[x]+;

             else f[y]=f[x]-;

             dprt(y);

         }

         return ;

     }

     void Getans(int x)

     {

         vst1[x]=;

         if(f[x]==now_minn){now_tot++;}

         else if(f[x]<now_minn){now_tot=;now_minn=f[x];}

         for(int i=head[x];i;i=nxt[i])

         {

             int y=to[i];

             if(vst1[y]||inlop[y])continue;

             Getans(y);

         }

         return ;

     }

     void work()

     {

         clear();

     //    cout<<tot<<endl;

         int n=Rd();

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

         {

             int a=Rd(),b=Rd();

             add(b,a,);

             add(a,b,);

         }

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

         {

             if(dfn[i]||!head[i])continue;

             lop.clear();sum=;

             use=;

             bool ok=Getlop(i,);

             if(!ok){puts("-1 -1");return ;}

             else

             {

                 if(!lop.size())

                 {

                     now_minn=0x7f7f7f7f;

                     now_tot=;dp(i);

                     f[i]=d[i];

                     dprt(i);

                     Getans(i);

                     minn+=now_minn;

                     ans=ans*now_tot%mod;

                 }

                 else

                 {

                     int len=lop.size();

                     //cout<<len<<" "<<use<<endl;

                     if(use+use^len)

                     {

                         minn+=min(use,len-use);

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

                         {

                             now_minn=0x7f7f7f7f;

                             now_tot=;dp(lop[i]);

                             now_minn=d[lop[i]];

                             minn+=now_minn;

                         }

                     }

                     else

                     {

                         minn+=use;

                         ans=ans*%mod;

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

                         {

                             now_minn=0x7f7f7f7f;

                             now_tot=;dp(lop[i]);

                             now_minn=d[lop[i]];

                             minn+=now_minn;

                         }

                     }

                 }

             }

         }

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

     }

 }E;

 int main()

 {

 //    freopen("out.in","r",stdin);

 //    freopen("b.txt","w",stdout);

     int t=E.Rd();

     while(t--)E.work();

     return ;

 }

总结：

1.考试审题！囧

2.仔细想想自己的复杂度能不能下降，能不能避免不必要的枚举，哪怕搜索打个剪枝也是好的。

3.暴力别打错了！

4.结合着期望的复杂度去思考问题，相信自己。

下次加油！

巴特西

NOIP模拟测试6

最新文章

热门文章