noip2012~2015刷题小记录

2012d1t1 密码

模拟题

 #include<cstdio>

 #include<cstdlib>

 #include<cstring>

 #include<cmath>

 #include<iostream>

 #include<algorithm>

 #include<set>

 #include<queue>

 #include<vector>

 using namespace std;

 const int N=;

 char s[N],c[N],p[][];

 int myabs(int x){return x> ? x:-x;}

 void init()

 {

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

     {

         int k=i;

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

         {

             if(k==) k=;

             p[i][j]=k;

             k++;

         }

     }

 }

 char fd(char a,char b)

 {

     int tmp=,x,y;

     if(a>='a' && a<='z') x=a-'a';

     else x=a-'A';

     if(b>='a' && b<='z') tmp=,y=b-'a';

     else y=b-'A';

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

     {

         if(p[x][i]==y)

         {

             if(tmp==) return i+'A';

             return i+'a';

         }

     }

 }

 int main()

 {

     freopen("a.in","r",stdin);

     scanf("%s",s+);

     scanf("%s",c+);

     init();

     int sl=strlen(s+);

     int cl=strlen(c+);

     int j=;

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

     {

         if(j==sl+) j=;

         printf("%c",fd(s[j],c[i]));

         j++;

     }

     return ;

 }

2012d1t2 国王游戏

考虑相邻的两个交换。要打高精度。

 #include<cstdio>

 #include<cstdlib>

 #include<cstring>

 #include<cmath>

 #include<iostream>

 #include<algorithm>

 #include<set>

 #include<queue>

 #include<vector>

 using namespace std;

 const int N=;

 int n;

 struct nd{int a,b;}p[N];

 struct node{int sl,s[N];};

 bool cmp(nd x,nd y){return x.a*x.b < y.a*y.b;}

 node maxx(node a,node b)

 {

     if(a.sl!=b.sl) return (a.sl>b.sl) ? a:b;

     for(int i=a.sl;i>=;i--)

     {

         if(a.s[i]!=b.s[i]) return (a.s[i]>b.s[i]) ? a:b;

     }

     return a;

 }

 node mult(node a,int b)

 {

     node c;

     int x=b,sl=;

     while(x) {sl++;x/=;}

     c.sl=a.sl+sl;

     memset(c.s,,sizeof(c.s));

     for(int i=;i<=c.sl;i++)//debug c.sl not a.sl

     {

         c.s[i]+=a.s[i]*b;

         if(c.s[i]>=) c.s[i+]+=c.s[i]/,c.s[i]%=;

     }

     while(c.sl> && c.s[c.sl]==) c.sl--;

     while(c.s[c.sl]>=) c.s[c.sl+]+=c.s[c.sl]/,c.s[c.sl]%=,c.sl++;

     return c;

 }

 node div(node a,int b)

 {

     node c;

     c.sl=a.sl;

     memset(c.s,,sizeof(c.s));

     int now=;

     for(int i=a.sl;i>=;i--)

     {

         now=now*+a.s[i];

         if(now>=b) c.s[i]+=now/b,now=now%b;

     }

     for(int i=;i<=c.sl;i++)

     {

         if(c.s[i]>=) c.s[i+]+=c.s[i]/,c.s[i]%=;

     }

     while(c.sl> && c.s[c.sl]==) c.sl--;

     return c;

 }

 int main()

 {

     freopen("a.in","r",stdin);

     freopen("a.out","w",stdout);

     scanf("%d",&n);

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

     {

         scanf("%d%d",&p[i].a,&p[i].b);

     }

     sort(p+,p++n,cmp);

     node t,ans;int x=p[].a;

     t.sl=;ans.sl=;

     memset(ans.s,,sizeof(ans.s));

     while(x)

     {

         t.s[++t.sl]=x%;

         x/=;

     }

     int i;

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

     {

         ans=maxx(ans,div(t,p[i].b));

         t=mult(t,p[i].a);

     }

     output(ans);

     return ;

 }

2012d1t3 开车旅行

倍增。然后因为inf开得不够大wa了一发？

 #include<cstdio>

 #include<cstdlib>

 #include<cstring>

 #include<cmath>

 #include<iostream>

 #include<algorithm>

 #include<set>

 #include<queue>

 #include<vector>

 using namespace std;

 typedef long long LL;//////

 const LL N=,S=,D=,INF=(LL)1e15;

 const double inf=(double)1e9;

 LL n,m,h[N],nt1[N],nt2[N],f[N][S],fa[N][S],fb[N][S];

 struct cmp{

     bool operator()(const LL &x,const LL &y)const

     {

         if(h[x]!=h[y]) return h[x]<h[y];

         return x<y;

     }

 };

 set<LL,cmp> s;

 LL myabs(LL x){return x> ? x:-x;}

 void fd(LL x,LL len,LL &al,LL &bl)

 {

     al=;bl=;

     for(LL i=D;i>=;i--)

     {

         if(f[x][i] && al+fa[x][i]+bl+fb[x][i]<=len) al+=fa[x][i],bl+=fb[x][i],x=f[x][i];

     }

     if(nt2[x] && al+bl+myabs(h[nt2[x]]-h[x])<=len) al+=myabs(h[nt2[x]]-h[x]);

     return;

 }

 int main()

 {

     freopen("a.in","r",stdin);

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

     scanf("%lld",&n);

     s.clear();

     set<LL>::iterator it,itt;

     h[]=-INF;s.insert();

     h[n+]=INF;s.insert(n+);

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

     {

         scanf("%lld",&h[i]);

     }

     memset(nt1,,sizeof(nt1));

     memset(nt2,,sizeof(nt2));

     LL x,y;

     for(LL i=n;i>=;i--)

     {

         it=s.lower_bound(i);x=(*it);

         itt=it;itt--;y=(*itt);

         if(x==n+ && y==)

         {

             s.insert(i);

             continue;

         }

         if(h[x]-h[i]<h[i]-h[y])

         {

             nt1[i]=x;

             it++;x=(*it);

         }

         else

         {

             nt1[i]=y;

             itt--;y=(*itt);

         }

         s.insert(i);

         if(x==n+ && y==) continue;

         if(h[x]-h[i]<h[i]-h[y]) nt2[i]=x;

         else nt2[i]=y;

     }

     memset(f,,sizeof(f));

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

     {

         LL x=nt2[i],y=nt1[x];

         if(x && y)

         {

             f[i][]=y;

             fa[i][]=myabs(h[x]-h[i]);

             fb[i][]=myabs(h[y]-h[x]);

         }

     }

     for(LL j=;j<=D;j++)

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

         {

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

             if(f[i][j]) fa[i][j]=fa[i][j-]+fa[f[i][j-]][j-];

             if(f[i][j]) fb[i][j]=fb[i][j-]+fb[f[i][j-]][j-];

         }

     LL al,bl,len,st,id;

     double ans=inf+,now;

     scanf("%lld",&len);

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

     {

         fd(i,len,al,bl);

         if(bl==) now=inf;

         else now=(double)al/(double)bl;

         if(now<ans) ans=now,id=i;

         else if(now==ans && h[i]>h[id]) id=i;

     }

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

     scanf("%lld",&m);

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

     {

         scanf("%lld%lld",&st,&len);

         fd(st,len,al,bl);

         printf("%lld %lld\n",al,bl);

     }

     return ;

 }

2012d2t1 同余方程

exgcd裸题。

 #include<cstdio>

 #include<cstdlib>

 #include<cstring>

 #include<cmath>

 #include<iostream>

 #include<algorithm>

 #include<set>

 #include<queue>

 #include<vector>

 using namespace std;

 void exgcd(int a,int b,int &x,int &y)

 {

     if(b==) {x=;y=;return ;}

     int tx,ty;

     exgcd(b,a%b,tx,ty);

     x=ty;y=tx-(a/b)*ty;

     return;

 }

 int main()

 {

     freopen("a.in","r",stdin);

     int a,b,x,y;

     scanf("%d%d",&a,&b);

     exgcd(a,b,x,y);

     x=(x%b+b)%b;

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

     return ;

 }

2012d2t2 借教室

原本想用线段树的。。后来发现（被大神告诉说）二分就可以了。

 #include<cstdio>

 #include<cstdlib>

 #include<cstring>

 #include<cmath>

 #include<iostream>

 #include<algorithm>

 #include<set>

 #include<queue>

 #include<vector>

 using namespace std;

 typedef long long LL;

 const LL N=;

 LL n,m,a[N],b[N];

 struct node{

     LL l,r,d;

 }q[N];

 bool check(LL x)

 {

     memset(b,,sizeof(b));

     for(LL i=;i<=x;i++)

     {

         b[q[i].l]+=q[i].d;

         b[q[i].r+]-=q[i].d;

     }

     LL now=;

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

     {

         now+=b[i];

         if(a[i]-now<) return ;

     }

     return ;

 }

 int main()

 {

     freopen("a.in","r",stdin);

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

     for(LL i=;i<=n;i++) scanf("%lld",&a[i]);

     for(LL i=;i<=m;i++) scanf("%lld%lld%lld",&q[i].d,&q[i].l,&q[i].r);

     if(check(m)) printf("0\n");

     else

     {

         LL l=,r=m,mid;

         while(l<r)

         {

             mid=(l+r)/;

             if(check(mid)) l=mid+;

             else r=mid;

         }

         printf("-1\n%lld\n",l);

     }

     return ;

 }

2012d2t3 疫情控制

难得自己推出来。。当然是在大神告诉我坑点的情况下。

二分+贪心。

坑点：一个军队如果先把它放到根节点上，然后它可能会回不到原来那棵子树。要判断搞一下。

 #include<cstdio>

 #include<cstdlib>

 #include<cstring>

 #include<cmath>

 #include<iostream>

 #include<algorithm>

 #include<set>

 #include<queue>

 #include<vector>

 using namespace std;

 typedef long long LL;

 const int N=,M=*N;

 const LL INF=(LL)1e15;

 int n,m,len,ql,Ql;

 int first[N],c[N],t[N],fa[N],in[N],usd[N],q[N],Q[N];

 LL res[N],ned[N],dis[N];

 struct node{

     int x,y,next;LL d;

 }a[M];

 bool cmp1(int x,int y){return res[x]>res[y];}

 bool cmp2(int x,int y){return ned[x]>ned[y];}

 LL minn(LL x,LL y){return x<y ? x:y;}

 void ins(int x,int y,LL d)

 {

     a[++len].x=x;a[len].y=y;a[len].d=d;

     a[len].next=first[x];first[x]=len;

 }

 int findfa(int x)

 {

     if(fa[x]!=x) fa[x]=findfa(fa[x]);

     return fa[x];

 }

 void dfs(int x,int f)

 {

     if(f!=) fa[findfa(x)]=findfa(f);

     for(int i=first[x];i;i=a[i].next)

     {

         int y=a[i].y;

         if(y==f) continue;

         dis[y]=dis[x]+a[i].d;

         ned[y]=a[i].d;

         dfs(y,x);

     }

 }

 LL DFS(int x,int f,LL d,int &cnt)

 {

     LL now,ans=INF;int son=;

     if(t[x]) ans=dis[x];

     bool bk=,ok=;

     for(int i=first[x];i;i=a[i].next)

     {

         int y=a[i].y;

         if(y==f) continue;

         son++;

         now=DFS(y,x,d,cnt);

         if(now-d <= dis[x]) bk=;

         if(now-d > dis[y]) ok=;

         ans=minn(ans,now);

     }

     if(!son)

     {

         if(ans>=INF && f==) {cnt++;Q[++Ql]=x;}

     }

     else

     {

         if(!bk && !ok && f==) {cnt++;Q[++Ql]=x;}

     }

     return ans;

 }

 bool check(LL d)

 {

     ql=;Ql=;

     memset(t,,sizeof(t));

     memset(res,,sizeof(res));

     memset(in,,sizeof(in));

     memset(usd,,sizeof(usd));

     int x,y,sum=,cnt=;

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

     {

         if(d>dis[c[i]])

         {

             sum++;

             res[i]=d-dis[c[i]];

             in[fa[c[i]]]++;

             q[++ql]=i;

         }

         else t[c[i]]++;

     }

     // for(LL i=1;i<=n;i++) printf("dis %lld = %lld\n",i,t[i]);

     // for(LL i=1;i<=n;i++) printf("dis %lld = %lld\n",i,dis[i]);

     DFS(,,d,cnt);

     if(cnt>sum) return ;

     int i=,j=;bool bk=;

     sort(q+,q++ql,cmp1);

     sort(Q+,Q++Ql,cmp2);

     while(i<=Ql)

     {

         x=Q[i];i++;

         if(in[x]-usd[x]>=) usd[x]++;

         else

         {

             y=q[j];

             while(in[fa[c[y]]]==usd[fa[c[y]]])

             {

                 in[fa[c[y]]]--;

                 usd[fa[c[y]]]--;

                 j++;

                 y=q[j];

             }

             if(res[y]<ned[x]) {bk=;break;}

             j++;in[fa[c[y]]]--;

         }

     }

     return bk;

 }

 int main()

 {

     freopen("a.in","r",stdin);

     scanf("%d",&n);

     int x,y,cnt;

     LL d,l=,r=,mid;

     len=;

     memset(first,,sizeof(first));

     for(int i=;i<=n;i++) fa[i]=i;

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

     {

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

         r+=d;

         ins(x,y,d);

         ins(y,x,d);

     }

     ned[]=;dis[]=;dfs(,);

     scanf("%d",&m);

     for(int i=;i<=m;i++) scanf("%d",&c[i]);

     cnt=;

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

     {

         findfa(i);

         if(fa[i]==i) cnt++;

     }

     if(m<cnt) printf("-1\n");

     else

     {

         while(l<r)

         {

             mid=(l+r)/;

             if(check(mid)) r=mid;

             else l=mid+;

         }

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

     }

     return ;

 }

2013d1t1 转圈游戏

模拟题。

 #include<cstdio>

 #include<cstdlib>

 #include<cstring>

 #include<cmath>

 #include<iostream>

 #include<algorithm>

 #include<set>

 using namespace std;

 typedef long long LL;

 const int N=;

 LL gcd(LL x,LL y)

 {

     if(y==) return x;

     return gcd(y,x%y);

 }

 LL lcm(LL x,LL y)

 {

     LL g=gcd(x,y);

     return (x/g)*y;

 }

 LL quickpow(LL x,LL y,LL mod)

 {

     LL ans=;

     while(y)

     {

         if(y&) ans=ans*x%mod;

         x=x*x%mod;

         y/=;

     }

     return ans;

 }

 int main()

 {

     freopen("a.in","r",stdin);

     LL n,m,k,x,len,c;

     scanf("%lld%lld%lld%lld",&n,&m,&k,&x);

     len=lcm(n,m);

     c=len/m;

     k=quickpow(,k,c);

     printf("%lld\n",(x+k*m)%n);

     return ;

 }

2013d1t2 火柴排队

贪心。转化为求逆序对。

 #include<cstdio>

 #include<cstdlib>

 #include<cstring>

 #include<cmath>

 #include<iostream>

 #include<algorithm>

 #include<set>

 using namespace std;

 const int N=,mod=;

 int n,c[N];

 struct node{

     int d,id,iid;

 }a[N],b[N];

 bool cmp_d(node x,node y){

     if(x.d!=y.d) return x.d<y.d;

     return x.id<y.id;

 }

 bool cmp_id(node x,node y){return x.id<y.id;}

 void add(int x)

 {

     for(int i=x;i>=;i-=(i&(-i))) c[i]++;

 }

 int getsum(int x)

 {

     int ans=;

     for(int i=x;i<=n;i+=(i&(-i))) ans+=c[i];

     return ans;

 }

 int main()

 {

     freopen("a.in","r",stdin);

     scanf("%d",&n);

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

     {

         scanf("%d",&a[i].d);

         a[i].id=i;

     }

     sort(a+,a++n,cmp_d);

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

     {

         scanf("%d",&b[i].d);

         b[i].id=i;

     }

     sort(b+,b++n,cmp_d);

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

     {

         b[i].iid=a[i].id;

     }

     sort(b+,b++n,cmp_id);

     memset(c,,sizeof(c));

     int ans=;

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

     {

         ans=(ans+getsum(b[i].iid))%mod;

         add(b[i].iid);

     }

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

     return ;

 }

2013d1t3 货车运输

最大生成树+树链剖分。

 #include<cstdio>

 #include<cstdlib>

 #include<cstring>

 #include<cmath>

 #include<iostream>

 #include<algorithm>

 #include<set>

 #include<queue>

 using namespace std;

 const int N=,M=,INF=(int)1e9;

 int n,m,num,al,bl,tl,ql;

 int af[N],bf[N],fa[N],f[N],dfn[N],dep[N],size[N],top[N],zs[N],tof[N];

 bool in[N];

 struct node{int x,y,d,bk,next;}a[M],b[M];

 struct trnode{int l,r,lc,rc,d;}t[*N];

 deque<int> q;

 int minn(int x,int y){return x<y ? x:y;}

 int findfa(int x)

 {

     if(fa[x]!=x) fa[x]=findfa(fa[x]);

     return fa[x];

 }

 void ins_a(int x,int y,int d)

 {

     a[++al].x=x;a[al].y=y;a[al].d=d;

     a[al].next=af[x];af[x]=al;

 }

 void ins_b(int x,int y,int d)

 {

     b[++bl].x=x;b[bl].y=y;b[bl].d=d;b[bl].bk=;

     b[bl].next=bf[x];bf[x]=bl;

 }

 bool cmp(node x,node y){return x.d>y.d;}

 void kruskal()

 {

     sort(b+,b++bl,cmp);

     int x,y,xx,yy;

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

     {

         x=b[i].x,y=b[i].y;

         xx=findfa(x),yy=findfa(y);

         if(xx!=yy)

         {

             b[i].bk=;

             fa[xx]=yy;

         }

     }

 }

 int bt(int l,int r)

 {

     int x=++tl;

     t[x].l=l;t[x].r=r;

     t[x].lc=t[x].rc=;

     if(l<r)

     {

         int mid=(l+r)/;

         t[x].lc=bt(l,mid);

         t[x].rc=bt(mid+,r);

         int lc=t[x].lc,rc=t[x].rc;

         t[x].d=minn(t[lc].d,t[rc].d);

     }

     else t[x].d=tof[l];

     return x;

 }

 int query(int x,int l,int r)

 {

     if(t[x].l==l && t[x].r==r) return t[x].d;

     int lc=t[x].lc,rc=t[x].rc,mid=(t[x].l+t[x].r)/;

     if(r<=mid) return query(lc,l,r);

     if(l>mid)  return query(rc,l,r);

     return minn(query(lc,l,mid),query(rc,mid+,r));

 }

 void dfs(int x,int ff)

 {

     size[x]=;

     zs[x]=;

     f[x]=ff;

     dep[x]=dep[ff]+;

     for(int i=af[x];i;i=a[i].next)

     {

         int y=a[i].y;

         if(y==ff) continue;

         dfs(y,x);

         size[x]+=size[y];

         if(zs[x]== || size[y]>size[zs[x]]) zs[x]=y;

     }

 }

 void fd_top(int x,int ff)

 {

     dfn[x]=++num;

     if(zs[x])

     {

         top[zs[x]]=top[x];

         fd_top(zs[x],x);

     }

     for(int i=af[x];i;i=a[i].next)

     {

         int y=a[i].y;

         if(y==ff) continue;

         if(y==zs[x])

         {

             tof[dfn[zs[x]]]=a[i].d;

             continue;

         }

         top[y]=y;

         fd_top(y,x);

         tof[dfn[y]]=a[i].d;

     }

 }

 int solve(int x,int y)

 {

     int tx=top[x],ty=top[y],ans=INF;

     while(tx!=ty)

     {

         if(dep[tx]<dep[ty]) swap(x,y),swap(tx,ty);

         ans=minn(ans,query(,dfn[tx],dfn[x]));

         x=f[top[x]];tx=top[x];

     }

     if(x==y) return ans;

     if(dep[x]<dep[y]) swap(x,y);

     ans=minn(ans,query(,dfn[y]+,dfn[x]));

     return ans;

 }

 int main()

 {

     freopen("a.in","r",stdin);

     freopen("a.out","w",stdout);

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

     int x,y,d;

     al=;bl=;

     memset(af,,sizeof(af));

     memset(bf,,sizeof(bf));

     for(int i=;i<=n;i++) fa[i]=i;

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

     {

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

         ins_b(x,y,d);

         ins_b(y,x,d);

     }

     kruskal();

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

     {

         if(b[i].bk)

         {

             ins_a(b[i].x,b[i].y,b[i].d);

             ins_a(b[i].y,b[i].x,b[i].d);

         }

     }

     tl=;num=;dep[]=;size[]=;

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

     {

         if(fa[i]==i)

         {

             dfs(i,);

             top[i]=i;fd_top(i,);

         }

     }

     bt(,n);

     scanf("%d",&ql);

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

     {

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

         if(findfa(x)!=findfa(y)) printf("-1\n");

         else printf("%d\n",solve(x,y));

     }

     return ;

 }

2013d2t1 积木大赛

取差值即可。

 #include<cstdio>

 #include<cstdlib>

 #include<cstring>

 #include<cmath>

 #include<iostream>

 #include<algorithm>

 #include<set>

 #include<queue>

 using namespace std;

 int main()

 {

     freopen("a.in","r",stdin);

     int n,x,p,ans;

     scanf("%d",&n);

     p=;ans=;

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

     {

         scanf("%d",&x);

         if(x>p) ans+=x-p;

         p=x;

     }

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

     return ;

 }

2013d2t2 花匠

贪心。

 #include<cstdio>

 #include<cstdlib>

 #include<cstring>

 #include<cmath>

 #include<iostream>

 #include<algorithm>

 #include<set>

 #include<queue>

 using namespace std;

 const int N=,INF=(int)1e9;

 int n,a[N];

 int maxx(int x,int y){return x>y ? x:y;}

 int main()

 {

     freopen("a.in","r",stdin);

     scanf("%d",&n);

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

     {

         scanf("%d",&a[i]);

     }

     int ans=,now=,last=;

     a[]=;

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

     {

         if(now&)

         {

             if(a[i]<a[last]) now++,last=i;

             else if(a[i]>a[last]) last=i;

         }

         else

         {

             if(a[i]>a[last]) now++,last=i;

             else if(a[i]<a[last]) last=i;

         }

     }

     // printf("now = %d\n",now);

     ans=now;now=;last=;

     a[]=INF;

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

     {

         if(!(now&))

         {

             if(a[i]<a[last]) now++,last=i;

             else if(a[i]>a[last]) last=i;

         }

         else

         {

             if(a[i]>a[last]) now++,last=i;

             else if(a[i]<a[last]) last=i;

         }

     }

     ans=maxx(ans,now);

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

     return ;

 }

2013d2t3 华容道

bfs神题。反正我给跪了，调了好久才调出来。

 #include<cstdio>

 #include<cstdlib>

 #include<cstring>

 #include<cmath>

 #include<iostream>

 #include<algorithm>

 #include<set>

 #include<queue>

 using namespace std;

 const int N=,S=,INF=(int)1e9;

 int n,m,ans,xed,yed,tot,len,first[*N*N],dis[*N*N],id[N][N][];

 int dx[]={,-,,,};

 int dy[]={,,,-,};

 bool map[N][N],vis[N][N],in[*N*N];

 struct node{int x,y,d,next;}a[];

 struct nd{int x,y,sum;}b[*N*N];

 queue<int> q;

 queue<nd> Q;

 int minn(int x,int y){return x<y ? x:y;}

 void ins(int x,int y,int d)

 {

     a[++len].x=x;a[len].y=y;a[len].d=d;

     a[len].next=first[x];first[x]=len;

 }

 bool check(nd k)

 {

     if(k.x< || k.y< || k.x>n || k.y>m || !map[k.x][k.y]) return ;

     return ;

 }

 void fd(int x0,int y0,int x1,int y1)

 {

     nd t,k;

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

     memset(vis,,sizeof(vis));

     t.x=x0;t.y=y0;t.sum=;

     vis[t.x][t.y]=;

     Q.push(t);

     while(!Q.empty())

     {

         t=Q.front();Q.pop();

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

         {

             k.x=t.x+dx[i];

             k.y=t.y+dy[i];

             k.sum=t.sum+;

             if(!check(k)) continue;

             if(k.x==x1 && k.y==y1)

             {

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

                     if(x1+dx[j]==t.x && y1+dy[j]==t.y) {ins(tot,id[x1][y1][j],t.sum);break;}

                 continue;

             }

             if(!vis[k.x][k.y]) vis[k.x][k.y]=,Q.push(k);

         }

     }

 }

 void bfs(int x0,int y0)

 {

     nd t,k;

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

     {

         t.x=x0+dx[i];

         t.y=y0+dy[i];

         if(!check(t)) continue;

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

         {

             if(t.x+dx[j]==x0 && t.y+dy[j]==y0) {ins(id[x0][y0][i],id[t.x][t.y][j],);break;}

         }

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

         memset(vis,,sizeof(vis));

         vis[t.x][t.y]=;

         t.sum=;

         Q.push(t);

         while(!Q.empty())

         {

             t=Q.front();Q.pop();

             for(int l=;l<=;l++)

             {

                 k.x=t.x+dx[l];

                 k.y=t.y+dy[l];

                 k.sum=t.sum+;

                 if(!check(k)) continue;

                 if(k.x==x0 && k.y==y0)

                 {

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

                             if(x0+dx[j]==t.x && y0+dy[j]==t.y) {if(i!=j) ins(id[x0][y0][i],id[x0][y0][j],t.sum);break;}

                     continue;

                 }

                 if(!vis[k.x][k.y]) vis[k.x][k.y]=,Q.push(k);

             }

         }

     }

 }

 int spfa(int st)

 {

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

     memset(dis,,sizeof(dis));

     memset(in,,sizeof(in));

     q.push(st);dis[st]=;in[st]=;

     while(!q.empty())

     {

         int x=q.front();in[x]=;q.pop();

         for(int i=first[x];i;i=a[i].next)

         {

             int y=a[i].y;

             if(dis[y]>dis[x]+a[i].d)

             {

                 dis[y]=dis[x]+a[i].d;

                 if(!in[y]) in[y]=,q.push(y);

             }

         }

     }

     int ans=INF;

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

         if(id[xed][yed][i]) ans=minn(ans,dis[id[xed][yed][i]]);

     if(ans<INF) return ans;

     return -;

 }

 int main()

 {

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

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

     freopen("puzzle.in","r",stdin);

     freopen("puzzle.out","w",stdout);

     int x,y,x0,y0,x1,y1,K;

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

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

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

             scanf("%d",&map[i][j]);

     tot=;len=;

     memset(first,,sizeof(first));

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

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

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

             {

                 x=i+dx[k];

                 y=j+dy[k];

                 if(x< || y< || x>n || y>m) continue;

                 if(map[i][j] && map[x][y])

                 {

                     id[i][j][k]=++tot;

                 }

             }

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

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

             if(map[i][j]) bfs(i,j);

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

     {

         scanf("%d%d%d%d%d%d",&x0,&y0,&x1,&y1,&xed,&yed);

         if(x1==xed && y1==yed) {printf("0\n");continue;}

         tot++;

         fd(x0,y0,x1,y1);

         printf("%d\n",spfa(tot));

     }

     return ;

 }

2014d1t1 石头剪刀布

模拟题。

 #include<cstdio>

 #include<cstdlib>

 #include<cstring>

 #include<cmath>

 #include<iostream>

 #include<algorithm>

 #include<set>

 using namespace std;

 const int N=;

 int n,l1,l2,a[N],b[N];

 int check(int x,int y)

 {

     if(x==y) return ;

     if(x== && (y== || y==)) return ;

     if(x== && (y== || y==)) return ;

     if(x== && (y== || y==)) return ;

     if(x== && (y== || y==)) return ;

     if(x== && (y== || y==)) return ;

     return ;

 }

 int main()

 {

     freopen("a.in","r",stdin);

     scanf("%d%d%d",&n,&l1,&l2);

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

     {

         scanf("%d",&a[i]);

     }

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

     {

         scanf("%d",&b[i]);

     }

     int j=,k=,ans1=,ans2=;

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

     {

         if(j==l1+) j=;

         if(k==l2+) k=;

         ans1+=check(a[j],b[k]);

         ans2+=check(b[k],a[j]);

         j++;k++;

     }

     printf("%d %d\n",ans1,ans2);

     return ;

 }

2014d1t2 联合权值

树上dfs乱搞。

 #include<cstdio>

 #include<cstdlib>

 #include<cstring>

 #include<cmath>

 #include<iostream>

 #include<algorithm>

 #include<set>

 using namespace std;

 const int N=,M=*,mod=;

 int n,m,len,ans_mx,ans_sum;

 int first[N],f[N],w[N],sum[N];

 struct node{

     int x,y,next;

 }a[M];

 int maxx(int x,int y){return x>y ? x:y;}

 void ins(int x,int y)

 {

     a[++len].x;a[len].y=y;

     a[len].next=first[x];first[x]=len;

 }

 void dfs(int x,int fa)

 {

     f[x]=fa;

     sum[x]=;

     int mx1=,mx2=;

     for(int i=first[x];i;i=a[i].next)

     {

         int y=a[i].y;

         if(y==fa) continue;

         sum[x]=(sum[x]+w[y])%mod;

         if(w[y]>mx1) mx2=mx1,mx1=w[y];

         else if(w[y]>mx2) mx2=w[y];

         dfs(y,x);

     }

     ans_mx=maxx(ans_mx,mx1*mx2);

 }

 void DFS(int x)

 {

     ans_sum=(ans_sum+w[x]*(((sum[f[x]]-w[x])%mod+mod)%mod)%mod)%mod;

     ans_sum=(ans_sum+*w[x]*w[f[f[x]]]%mod)%mod;

     ans_mx=maxx(ans_mx,w[x]*w[f[f[x]]]);

     for(int i=first[x];i;i=a[i].next)

     {

         int y=a[i].y;

         if(y==f[x]) continue;

         DFS(y);

     }

 }

 int main()

 {

     freopen("a.in","r",stdin);

     scanf("%d",&n);

     int x,y;

     len=;

     ans_mx=;ans_sum=;

     memset(f,,sizeof(f));

     memset(first,,sizeof(first));

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

     {

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

         ins(x,y);

         ins(y,x);

     }

     w[]=;

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

     {

         scanf("%d",&w[i]);

     }

     sum[]=w[];

     dfs(,);

     DFS();

     printf("%d %d\n",ans_mx,ans_sum);

     return ;

 }

2014d1t3 飞扬的小鸟

各种细节的dp

 #include<cstdio>

 #include<cstdlib>

 #include<cstring>

 #include<cmath>

 #include<iostream>

 #include<algorithm>

 #include<set>

 #include<queue>

 using namespace std;

 const int N=,M=,INF=(int)1e9;

 int n,m,t,sl[],s[][N],in[N],f[][N],sum[N],up[N],down[N],l[N],r[N];

 struct node{

     int x,l,r;

 }a[N];

 queue<int> q[];

 bool cmp(node x,node y){return x.x<y.x;}

 int minn(int x,int y){return x<y ? x:y;}

 int main()

 {

     freopen("a.in","r",stdin);

     freopen("a.out","w",stdout);

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

     sum[]=;

     memset(l,-,sizeof(l));

     memset(r,-,sizeof(r));

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

     {

         scanf("%d%d",&up[i],&down[i]);

         if(i->=) sum[i]=sum[i-]+down[i-];

     }

     up[n]=INF;down[n]=INF;

     // for(int i=0;i<n;i++) printf("sum %d = %d\n",i,sum[i]);

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

     {

         scanf("%d%d%d",&a[i].x,&a[i].l,&a[i].r);

         l[a[i].x]=a[i].l;

         r[a[i].x]=a[i].r;

     }

     sort(a+,a++t,cmp);

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

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

     sl[]=sl[]=;

     memset(in,,sizeof(in));

     for(int i=;i<=m;i++) f[][i]=f[][i]=INF;

     int x,y,now=,j=,ans=INF,mx=;

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

     {

         if(j<=t && a[j].r- < i-(sum[a[j].x]-sum[])) continue;

         f[][i]=;

         // printf("f 0 %d = %d\n",i,f[0][i]);

         s[][++sl[]]=i;

         q[].push(i);

     }

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

     {

         if(i!=)

         {

             now=-now;

             for(int k=;k<=sl[-now];k++)

             {

                 f[-now][s[-now][k]]=INF;

             }

             sl[-now]=;

         }

         while(j<=t && a[j].x<=i) j++;

         while(!q[now].empty())

         {

             x=q[now].front();q[now].pop();

             printf("f %d %d = %d\n",i,x,f[now][x]);

             mx=i;

             if(i==n) ans=minn(ans,f[now][x]);

             for(int k=;k<=((m-x)/up[i])+;k++)

             {

                 y=minn(x+k*up[i],m);

                 if(j<=t && (a[j].r- < y-(sum[a[j].x]-sum[i]))) continue;

                 if(l[i+]!=- && (y<=l[i+] || y>=r[i+])) continue;

                 f[-now][y]=minn(f[-now][y],f[now][x]+k);

                 if(!in[y])

                 {

                     in[y]=;

                     s[-now][++sl[-now]]=y;

                     q[-now].push(y);

                 }

             }

             y=x-down[i];

             if(y> && !(j<=t && (a[j].r- < y-(sum[a[j].x]-sum[i]))) && !(l[i+]!=- && (y<=l[i+] || y>=r[i+])))

             {

                 f[-now][y]=minn(f[-now][y],f[now][x]);

                 if(!in[y])

                 {

                     in[y]=;

                     s[-now][++sl[-now]]=y;

                     q[-now].push(y);

                 }

             }

         }

         for(int k=;k<=sl[-now];k++) in[s[-now][k]]=;

     }

     if(ans==INF)

     {

         printf("0\n");

         int k=;

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

         {

             if(a[i].x<=mx) k=i;

             else break;

         }

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

     }

     else

     {

         printf("1\n");

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

     }

     return ;

 }

2014 d2t1 无线网络发射器

枚举+树状数组

 #include<cstdio>

 #include<cstdlib>

 #include<cstring>

 #include<cmath>

 #include<iostream>

 #include<algorithm>

 #include<set>

 #include<queue>

 using namespace std;

 const int N=,M=,mx=;

 int l,n,c[N][N];

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

 {

     for(int i=x;i<=mx;i+=(i&(-i)))

         for(int j=y;j<=mx;j+=(j&(-j)))

             c[i][j]+=d;

 }

 int getsum(int x,int y)

 {

     int ans=;

     for(int i=x;i>=;i-=(i&(-i)))

         for(int j=y;j>=;j-=(j&(-j)))

             ans+=c[i][j];

     return ans;

 }

 int main()

 {

     freopen("a.in","r",stdin);

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

     int x,y,d;

     memset(c,,sizeof(c));

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

     {

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

         x++;y++;

         add(x,y,d);

     }

     int now,ans=,sum=;

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

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

         {

             now=getsum(i+l,j+l)-getsum(i-l-,j+l)-getsum(i+l,j-l-)+getsum(i-l-,j-l-);

             // if(now>20) printf("i = %d  j = %d  now = %d\n",i,j,now);

             if(now>ans) ans=now,sum=;

             else if(now==ans) sum++;

         }

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

     return ;

 }

2014d2t2 寻找道路

反向找一遍，然后spfa

 #include<cstdio>

 #include<cstdlib>

 #include<cstring>

 #include<cmath>

 #include<iostream>

 #include<algorithm>

 #include<set>

 #include<queue>

 using namespace std;

 const int N=,M=,INF=(int)1e9;

 int n,m,al,bl,af[N],bf[N],dis[N];

 bool c[N],vis[N],in[N];

 struct node{

     int x,y,next;

 }a[M],b[M];

 queue<int> q;

 void ins_a(int x,int y)

 {

     a[++al].x=x;a[al].y=y;

     a[al].next=af[x];af[x]=al;

 }

 void ins_b(int x,int y)

 {

     b[++bl].x=x;b[bl].y=y;

     b[bl].next=bf[x];bf[x]=bl;

 }

 void bfs(int st)

 {

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

     memset(vis,,sizeof(vis));

     q.push(st);vis[st]=;

     while(!q.empty())

     {

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

         for(int i=af[x];i;i=a[i].next)

         {

             int y=a[i].y;

             if(!vis[y])

             {

                 vis[y]=;

                 q.push(y);

             }

         }

     }

 }

 void spfa(int st)

 {

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

     memset(dis,,sizeof(dis));

     memset(in,,sizeof(in));

     q.push(st);dis[st]=;in[st]=;

     while(!q.empty())

     {

         int x=q.front();in[x]=;q.pop();

         for(int i=af[x];i;i=a[i].next)

         {

             int y=a[i].y;

             if(dis[y]>dis[x]+)

             {

                 dis[y]=dis[x]+;

                 if(!in[y]) in[y]=,q.push(y);

             }

         }

     }

 }

 int main()

 {

     freopen("a.in","r",stdin);

     int x,y,st,ed;

     al=;bl=;

     memset(af,,sizeof(af));

     memset(bf,,sizeof(bf));

     memset(c,,sizeof(c));

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

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

     {

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

         ins_a(y,x);

         ins_b(x,y);

     }

     scanf("%d%d",&st,&ed);

     bfs(ed);

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

     {

         if(i==ed || bf[i]) c[i]=;

         else c[i]=;

         for(int j=bf[i];j;j=b[j].next)

         {

             if(!vis[b[j].y]) {c[i]=;break;}

         }

     }

     al=;

     memset(af,,sizeof(af));

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

     {

         if(c[b[i].x] && c[b[i].y]) ins_a(b[i].x,b[i].y);

     }

     spfa(st);

     if(dis[ed]>=INF) printf("-1\n");

     else printf("%d\n",dis[ed]);

     return ;

 }

2014 d2t3 解方程

70分算法。mod几个质数。

 #include<cstdio>

 #include<cstdlib>

 #include<cstring>

 #include<cmath>

 #include<iostream>

 #include<algorithm>

 #include<set>

 #include<queue>

 using namespace std;

 typedef long long LL;

 const int N=,M=,S=,MX=;

 int n,m;

 struct node{

     int tmp,sl,s[M];

 }a[N];

 LL b[N],p[]={,,,,,,,,};//{0,2147483647,100000007,2013265921};

 bool c[S];

 char s[M];

 int minn(int x,int y){return x<y ? x:y;}

 LL cal_mod(node x,LL y)

 {

     LL now=,tmp=(LL)x.tmp;

     for(int i=;i<=x.sl;i++)

     {

         now=now*+(LL)x.s[i];

         if(now>=y) now%=y;

     }

     return now*tmp;

 }

 int main()

 {

     freopen("a.in","r",stdin);

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

     int sl;

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

     {

         scanf("%s",s);

         sl=strlen(s);

         a[i].sl=;

         if(s[]=='-')

         {

             a[i].tmp=-;

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

         }

         else

         {

             a[i].tmp=;

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

         }

     }

     int cnt=;

     memset(c,,sizeof(c));

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

     {

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

         {

             b[i]=cal_mod(a[i],p[k]);

             // printf("b %d = %lld\n",i,b[i]);

         }

         for(int i=;i<=minn(m,MX);i++)

         {

             if(!c[i]) continue;

             LL x=,now=;

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

             {

                 now=(now+b[j]*x%p[k])%p[k];

                 x=x*((LL)i)%p[k];

             }

             if(now) c[i]=;//ans[++cnt]=i;

         }

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

         {

             if(!c[i]) continue;

             if(!c[i%p[k]]) c[i]=;

         }

     }

     for(int i=;i<=m;i++) if(c[i]) cnt++;

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

     for(int i=;i<=m;i++) if(c[i]) printf("%d\n",i);

     return ;

 }

2015 d1t1 幻方

模拟题

 #include<cstdio>

 #include<cstdlib>

 #include<cstring>

 #include<cmath>

 #include<iostream>

 #include<algorithm>

 #include<set>

 using namespace std;

 const int N=;

 int n,a[N][N];

 int main()

 {

     freopen("a.in","r",stdin);

     scanf("%d",&n);

     int x,y,k=,lx=,ly=(n/)+;

     memset(a,,sizeof(a));

     a[][(n/)+]=;

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

     {

         if(lx== && ly!=n) x=n,y=ly+;

         if(lx!= && ly==n) x=lx-,y=;

         if(lx== && ly==n) x=lx+,y=ly;

         if(lx!= && ly!=n)

         {

             if(!a[lx-][ly+]) x=lx-,y=ly+;

             else x=lx+,y=ly;

         }

         a[x][y]=++k;

         lx=x;ly=y;

     }

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

     {

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

             printf("%d ",a[i][j]);

         printf("\n");

     }

     return ;

 }

2015 d1t2 信息传递

最重要的性质就是每个点只要一条出边。。

 #include<cstdio>

 #include<cstdlib>

 #include<cstring>

 #include<cmath>

 #include<iostream>

 #include<algorithm>

 #include<set>

 using namespace std;

 const int N=,INF=(int)1e9;

 int n,fa[N],d[N];

 int minn(int x,int y){return x<y ? x:y;}

 int findfa(int x)

 {

     if(fa[x]!=x)

     {

         int xx=fa[x];

         fa[x]=findfa(fa[x]);

         d[x]=d[x]+d[xx];

     }

     return fa[x];

 }

 int main()

 {

     freopen("a.in","r",stdin);

     scanf("%d",&n);

     int x,y,xx,yy,ans=INF;

     for(int i=;i<=n;i++) fa[i]=i,d[i]=;

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

     {

         x=i;

         scanf("%d",&y);

         xx=findfa(x);yy=findfa(y);

         if(xx==yy)

         {

             ans=minn(ans,d[x]+d[y]+);

         }

         else

         {

             fa[xx]=x;

             d[xx]=d[x];

             fa[x]=y;

             d[x]=;

         }

     }

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

     return ;

 }

2015d2t3 斗地主

搜索。然后看了别人代码用贪心。。

 #include<cstdio>

 #include<cstdlib>

 #include<cstring>

 #include<iostream>

 using namespace std;

 const int N=,S=,Inf=(int)1e9;

 int n,sum[N],ans;

 int getsum(int r[])

 {

     int c1=,c2=,c3=,c4=,cnt=;//cnt 带牌

     bool bk=;

     if(r[]==) bk=;

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

         if(r[i]==) c1++;

         if(r[i]==) c2++;

         if(r[i]==) c3++;

         if(r[i]==) c4++;

     }

     while(((!bk && c2>=) || (bk && c2->=)) && c4) c2-=,c4--,cnt++;//四带二对

     while(((!bk && c2) || (bk && c2->=)) && c3) c2--,c3--,cnt++;//三带一对

     while(c1>= && c4) c1-=,c4--,cnt++;//四带二单

     while(c2 && c4) c2--,c4--,cnt++;//四带二单

     while(c1 && c3) c1--,c3--,cnt++;//三带一单

     return cnt+c1+c2+c3+c4;//带牌+单牌+对牌+三牌+四牌

 }

 void dfs(int r[],int now)

 {

     int t=getsum(r);

     if(!ans || (ans && t+now<ans)) ans=t+now;

     if(ans && now>ans) return ;

     //三顺子

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

     {

         int cnt=;

         for(int j=i;j<=S;j++)

         {

             if(r[j]>=) cnt++;

             else break;

         }

         if(cnt>=)

         {

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

             {

                 for(int j=i;j<=i+l-;j++) r[j]-=;

                 dfs(r,now+);

                 for(int j=i;j<=i+l-;j++) r[j]+=;

             }

         }

     }

     //双顺子

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

     {

         int cnt=;

         for(int j=i;j<=S;j++)

         {

             if(r[j]>=) cnt++;

             else break;

         }

         if(cnt>=)

         {

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

             {

                 for(int j=i;j<=i+l-;j++) r[j]-=;

                 dfs(r,now+);

                 for(int j=i;j<=i+l-;j++) r[j]+=;

             }

         }

     }

     //单顺子

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

     {

         int cnt=;

         for(int j=i;j<=S;j++)

         {

             if(r[j]>=) cnt++;

             else break;

         }

         if(cnt>=)

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

         {

             for(int j=i;j<=i+l-;j++) r[j]--;

             dfs(r,now+);

             for(int j=i;j<=i+l-;j++) r[j]++;

         }

     }

 }

 int main()

 {

     freopen("a.in","r",stdin);

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

     int T;

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

     while(T--)

     {

         ans=;

         memset(sum,,sizeof(sum));

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

         {

             int x,y;

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

             if(x==) x=;

             else if(x>=) x--;

             sum[x]++;

         }

         dfs(sum,);

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

     }

     return ;

 }

2015 d2t1 跳石头

二分。

 #include<cstdio>

 #include<cstdlib>

 #include<cstring>

 #include<cmath>

 #include<iostream>

 #include<algorithm>

 #include<set>

 using namespace std;

 const int N=;

 int n,m,len,a[N];

 bool check(int d)

 {

     int sum=,last=;

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

     {

         if(a[i]-last<d) sum++;

         else last=a[i];

     }

     if(len-last<d) sum++;

     if(sum<=m) return ;

     return ;

 }

 int main()

 {

     freopen("a.in","r",stdin);

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

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

     {

         scanf("%d",&a[i]);

     }

     int l=,r=len,mid;

     while(l<r)

     {

         mid=(l+r+)/;

         if(check(mid)) l=mid;

         else r=mid-;

     }

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

     return ;

 }

2015d2t2 子串

四维dp。

 #include<cstdio>

 #include<cstdlib>

 #include<cstring>

 #include<cmath>

 #include<iostream>

 #include<algorithm>

 #include<set>

 using namespace std;

 const int N=,M=,mod=;

 int n,m,K,f[][M][M][];

 char a[N],b[N];

 void ad(int &x,int y){

     x=(x+y)%mod;

     return;

 }

 int main()

 {

     freopen("a.in","r",stdin);

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

     scanf("%s%s",a+,b+);

     memset(f,,sizeof(f));

     // f[0][0][0][0]=1;

     int x,now=,ans=;

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

     {

         now=-now;

         memset(f[-now],,sizeof(f[-now]));

         if(i==) f[now][][][]=;

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

             for(int k=;k<=K;k++)

                 for(int l=;l<=;l++)

                 {

                     x=f[now][j][k][l];

                     // printf("f %d %d %d %d = %d\n",i,j,k,l,x);

                     if(i==n && j==m && k==K) ad(ans,x);

                     if(x==) continue;

                     if(l==)

                     {

                         if(i+<=n && j+<=m && a[i+]==b[j+])

                         {

                             ad(f[-now][j+][k][],x);

                             ad(f[-now][j+][k+][],x);

                         }

                         ad(f[-now][j][k][],x);

                     }

                     else

                     {

                         if(i+<=n && j+<=m && a[i+]==b[j+]) ad(f[-now][j+][k+][],x);

                         ad(f[-now][j][k][],x);

                     }

                 }

     }

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

     return ;

 }

2015d2t3 运输计划

二分d，有k条路径比d大，找一条边是这k条路径的公共边让它减了之后满足条件。

 #include<cstdio>

 #include<cstdlib>

 #include<cstring>

 #include<cmath>

 #include<iostream>

 #include<algorithm>

 #include<set>

 using namespace std;

 const int N=,M=*,S=,D=;

 int n,m,len;

 int t[N],dep[N],dis[N],first[N],f[N][S];

 struct node{

     int x,y,d,next;

 }a[M];

 struct qnode{

     int x,y,z,d;

 }q[N];

 int maxx(int x,int y){return x>y ? x:y;}

 void ins(int x,int y,int d)

 {

     a[++len].x=x;a[len].y=y;a[len].d=d;

     a[len].next=first[x];first[x]=len;

 }

 void dfs(int x,int fa)

 {

     // printf("x = %d  fa = %d\n",x,fa);

     f[x][]=fa;

     dep[x]=dep[fa]+;

     for(int i=first[x];i;i=a[i].next)

     {

         int y=a[i].y;

         if(y==fa) continue;

         dis[y]=dis[x]+a[i].d;

         dfs(y,x);

     }

 }

 void lca_init()

 {

     for(int j=;j<=D;j++)

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

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

 }

 int lca_query(int x,int y)

 {

     if(dep[x]<dep[y]) swap(x,y);

     for(int i=D;i>=;i--)

     {

         if(dep[f[x][i]]>=dep[y]) x=f[x][i];

     }

     if(x==y) return x;

     for(int i=D;i>=;i--)

     {

         if(f[x][i]!=f[y][i]) x=f[x][i],y=f[y][i];

     }

     return f[x][];

 }

 void DFS(int x,int fa,int sum,int &dmx)

 {

     for(int i=first[x];i;i=a[i].next)

     {

         int y=a[i].y;

         if(y==fa) continue;

         DFS(y,x,sum,dmx);

         if(t[y]>=sum) dmx=maxx(dmx,a[i].d);

         t[x]+=t[y];

         t[y]=;

     }

 }

 bool check(int d)

 {

     int qmx=,sum=;

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

     {

         if(q[i].d>d)

         {

             t[q[i].x]++;

             t[q[i].y]++;

             t[q[i].z]-=;

             sum++;

             qmx=maxx(qmx,q[i].d);

         }

     }

     int dmx=;

     DFS(,,sum,dmx);

     if(qmx-dmx<=d) return ;

     return ;

 }

 int main()

 {

     freopen("a.in","r",stdin);

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

     int x,y,d;

     len=;

     memset(f,,sizeof(f));

     memset(t,,sizeof(t));

     memset(dep,,sizeof(dep));

     memset(dis,,sizeof(dis));

     memset(first,,sizeof(first));

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

     {

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

         ins(x,y,d);

         ins(y,x,d);

     }

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

         // printf("%d --> %d\n",a[i].x,a[i].y);

     dfs(,);

     lca_init();

     int l=,r=,mid;

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

     {

         scanf("%d%d",&q[i].x,&q[i].y);

         q[i].z=lca_query(q[i].x,q[i].y);

         q[i].d=dis[q[i].x]+dis[q[i].y]-*dis[q[i].z];

         r=maxx(r,q[i].d);

     }

     while(l<r)

     {

         mid=(l+r)/;

         if(check(mid)) r=mid;

         else l=mid+;

     }

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

     return ;

 }

巴特西

noip2012~2015刷题小记录

最新文章

热门文章