【刷题记录】BZOJ-USACO

2023-10-09 18:38:46

接下来要滚去bzoj刷usaco的题目辣=v=在博客记录一下刷题情况，以及存一存代码咯。加油！

1.【bzoj1597】[Usaco2008 Mar]土地购买

 #include<cstdio>

 #include<algorithm>

 #include<cstring>

 using namespace std;

 const int N=;

 int n,cnt,q[N];

 long long x[N],y[N],f[N];

 struct node{long long x,y;}a[N];

 bool cmp(node a,node b){return a.x==b.x?a.y<b.y:a.x<b.x;}

 long long read()

 {

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

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

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

     return x*f;

 }

 double slope(int k,int j){return (double)(f[j]-f[k])/(y[k+]-y[j+]);}

 int main()

 {

     n=read();

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

         a[i].x=read(),a[i].y=read();

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

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

     {

         while(cnt&&a[i].y>=y[cnt])cnt--;

         x[++cnt]=a[i].x;y[cnt]=a[i].y;

     }

     int l=,r=;

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

     {

         while(l<r&&slope(q[l],q[l+])<x[i])l++;

         int t=q[l];

         f[i]=f[t]+y[t+]*x[i];

         while(l<r&&slope(q[r-],q[r])>slope(q[r],i))r--;

         q[++r]=i;

     }

     printf("%lld",f[cnt]);

     return ;

 }

斜率优化dp

2.【bzoj1607】[Usaco2008 Dec]Patting Heads 轻拍牛头

 #include<cstdio>

 #include<algorithm>

 #include<cstring>

 const int N=1e5+;

 using namespace std;

 int n,mx,a[N],c[N*],ans[N*];

 int read()

 {

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

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

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

     return x*f;

 }

 int main()

 {

     n=read();

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

         a[i]=read(),c[a[i]]++,mx=max(mx,a[i]);

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

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

             ans[j]+=c[i];

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

         printf("%d\n",ans[a[i]]-);

     return ;

 }

筛法

3.【bzoj1610】[Usaco2008 Feb]Line连线游戏

 #include<cstdio>

 #include<algorithm>

 #include<cstring>

 #include<cmath>

 using namespace std;

 const int N=1e6+;

 int n,ans,cnt,x[],y[];

 double q[N];

 int read()

 {

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

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

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

     return x*f;

 }

 int main()

 {

     n=read();

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

         x[i]=read(),y[i]=read();

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

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

         {

             if(x[i]==x[j])ans=;

             else q[++cnt]=1.0*(y[j]-y[i])/(x[j]-x[i]);

         }

     sort(q+,q+cnt+);

     if(cnt>=)ans++;

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

         if(fabs(q[i]-q[i-])>1e-)ans++;

     printf("%d",ans);

     return ;

 }

计算几何

4.【bzoj1609】[Usaco2008 Feb]Eating Together麻烦的聚餐

 #include<cstdio>

 #include<algorithm>

 #include<cstring>

 #define ll long long

 using namespace std;

 const int N=3e4+;

 const int inf=0x3f3f3f3f;

 int n,a[N],dp[N][],ans=inf;

 int read()

 {

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

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

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

     return x*f;

 }

 int main()

 {

     n=read();

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

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

     dp[][]=dp[][]=dp[][]=;

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

     {

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

         {

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

                 dp[i][j]=min(dp[i][j],dp[i-][k]);

             if(j!=a[i])dp[i][j]++;

         }

     }

     for(int i=;i<=;i++)ans=min(ans,dp[n][i]);

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

     dp[n+][]=dp[n+][]=dp[n+][]=;

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

     {

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

         {

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

                 dp[i][j]=min(dp[i][j],dp[i+][k]);

             if(j!=a[i])dp[i][j]++;

         }

     }

     for(int i=;i<=;i++)ans=min(ans,dp[][i]);

     printf("%d",ans);

     return ;

 }

普通dp

5.【bzoj1669】[Usaco2007 Jan]Balanced Lineup排队

 #include<cstdio>

 #include<algorithm>

 #include<cstring>

 #include<cmath>

 #define ll long long

 using namespace std;

 const int N=5e4+;

 const int inf=0x3f3f3f3f;

 int n,q,l,r,mx[N][],mn[N][];

 int read()

 {

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

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

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

     return x*f;

 }

 int rmq(int l,int r)

 {

     int a=log(r-l+)/log();

     int mxx=max(mx[l][a],mx[r-(<<a)+][a]);

     int mnn=min(mn[l][a],mn[r-(<<a)+][a]);

     return mxx-mnn;

 }

 int main()

 {

     n=read();q=read();

     for(int i=;i<=n;i++)mx[i][]=mn[i][]=read();

     int a=log(n)/log();

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

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

         {

             mx[j][i]=mx[j][i-];

             mx[j][i]=max(mx[j][i],mx[j+(<<(i-))][i-]);

             mn[j][i]=mn[j][i-];

             mn[j][i]=min(mn[j][i],mn[j+(<<(i-))][i-]);

         }

     while(q--)

     {

         l=read();r=read();

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

     }

     return ;

 }

RMQ-ST

6.【bzoj1606】[Usaco2008 Dec]Hay For Sale 购买干草

 #include<cstdio>

 #include<algorithm>

 #include<cstring>

 #include<cmath>

 #define ll long long

 using namespace std;

 const int inf=0x3f3f3f3f;

 int c,h,v[],dp[];

 int read()

 {

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

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

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

     return x*f;

 }

 int main()

 {

     c=read();h=read();

     for(int i=;i<=h;i++)v[i]=read();

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

         for(int j=c;j>=v[i];j--)

             dp[j]=max(dp[j],dp[j-v[i]]+v[i]);

     printf("%d",dp[c]);

     return ;

 }

背包dp

7.【bzoj1625】 [Usaco2007 Dec]宝石手镯

 #include<cstdio>

 #include<algorithm>

 #include<cstring>

 #include<cmath>

 #define ll long long

 using namespace std;

 const int inf=0x3f3f3f3f;

 int n,m,v[],d[],dp[];

 int read()

 {

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

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

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

     return x*f;

 }

 int main()

 {

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

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

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

         for(int j=m;j>=v[i];j--)

             dp[j]=max(dp[j],dp[j-v[i]]+d[i]);

     printf("%d",dp[m]);

     return ;

 }

背包dp

8.【bzoj1617】[Usaco2008 Mar]River Crossing渡河问题

 #include<cstdio>

 #include<algorithm>

 #include<cstring>

 #include<cmath>

 #define ll long long

 using namespace std;

 const int inf=0x3f3f3f3f;

 int n,m[],dp[];

 int read()

 {

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

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

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

     return x*f;

 }

 int main()

 {

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

     dp[]=;

     n=read();m[]=read();

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

         m[i]=read()+m[i-];

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

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

             dp[i]=min(dp[i],dp[j]+m[i-j]+m[]);

     printf("%d",dp[n]-m[]);

     return ;

 }

普通dp

9.【bzoj1612】[Usaco2008 Jan]Cow Contest奶牛的比赛

 #include<cstdio>

 #include<algorithm>

 #include<cstring>

 #include<cmath>

 #define ll long long

 using namespace std;

 const int inf=0x3f3f3f3f;

 int n,m,a,b,ans,l[],r[];

 bool map[][];

 int read()

 {

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

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

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

     return x*f;

 }

 int main()

 {

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

     while(m--)

     {

         a=read();b=read();

         map[a][b]=true;

         r[a]++;l[b]++;

     }

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

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

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

                 if(map[i][k]&&map[k][j]&&!map[i][j])

                     map[i][j]=true,r[i]++,l[j]++;

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

         if(l[i]+r[i]==n-)ans++;

     printf("%d",ans);

     return ;

 }

Floyd

10.【bzoj1614】[Usaco2007 Jan]Telephone Lines架设电话线

 #include<cstdio>

 #include<algorithm>

 #include<cstring>

 #include<cmath>

 #define ll long long

 using namespace std;

 const int inf=0x3f3f3f3f;

 int n,m,k,u,v,w,cnt,ans=-;

 int first[],dis[],q[];

 bool f[];

 struct edge{int to,next,w;}e[];

 int read()

 {

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

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

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

     return x*f;

 }

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

 {

     cnt++;e[cnt].next=first[u];first[u]=cnt;

     e[cnt].to=v;e[cnt].w=w;

 }

 bool check(int x)

 {

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

     int h=,t=;

     dis[]=;q[]=;f[]=true;

     while(h!=t)

     {

         u=q[h++];f[u]=false;if(h>)h=;

         for(int i=first[u];i;i=e[i].next)

         {

             v=e[i].to;

             if(e[i].w>x)w=;

             else w=;

             if(dis[v]>dis[u]+w)

             {

                 dis[v]=dis[u]+w;

                 if(!f[v])

                 {

                     f[v]=true;q[t++]=v;

                     if(t>)t=;

                 }

             }

         }

     }

     return dis[n]<=k;

 }

 int main()

 {

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

     while(m--)

     {

         u=read();v=read();w=read();

         insert(u,v,w);insert(v,u,w);

     }

     int l=,r=;

     while(l<=r)

     {

         int mid=(l+r)>>;

         if(check(mid))ans=mid,r=mid-;

         else l=mid+;

     }

     printf("%d",ans);

     return ;

二分+SPFA

11.【bzoj1601】[Usaco2008 Oct]灌水

 #include<cstdio>

 #include<algorithm>

 #include<cstring>

 #define ll long long

 using namespace std;

 const int inf=0x3f3f3f3f;

 const int N=1e5+;

 struct edge{int a,b,w;}e[N];

 int n,w,cnt,ans,f[];

 int read()

 {

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

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

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

     return x*f;

 }

 void ins(int a,int b,int w){e[++cnt].a=a;e[cnt].b=b;e[cnt].w=w;}

 int find(int t){return f[t]==t?t:f[t]=find(f[t]);}

 bool cmp(edge a,edge b){return a.w<b.w;}

 int main()

 {

     n=read();

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

         ins(,i,read()),f[i]=i;

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

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

             {ins(i,j,read());if(i==j)cnt--;}

     sort(e+,e+cnt+,cmp);

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

     {

         int x=find(e[i].a),y=find(e[i].b);

         if(x==y)continue;

         ans+=e[i].w;f[x]=y;

     }

     printf("%d",ans);

     return ;

 }

最小生成树

12.【bzoj1602】[Usaco2008 Oct]牧场行走

 #include<cstdio>

 #include<algorithm>

 #include<cstring>

 #define ll long long

 using namespace std;

 const int inf=0x3f3f3f3f;

 const int N=1e3+;

 struct edge{int next,to,w;}e[N*];

 int n,cnt,u,v,w,q,first[N],deep[N],di[N],x[N][];

 int read()

 {

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

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

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

     return x*f;

 }

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

 {

     cnt++;e[cnt].next=first[u];first[u]=cnt;

     e[cnt].to=v;e[cnt].w=w;

 }

 void dfs(int k)

 {

     for(int i=;(<<i)<=deep[k];i++)

         x[k][i]=x[x[k][i-]][i-];

     for(int i=first[k];i;i=e[i].next)

     {

         if(deep[e[i].to])continue;

         x[e[i].to][]=k;

         deep[e[i].to]=deep[k]+;

         di[e[i].to]=di[k]+e[i].w;

         dfs(e[i].to);

     }

 }

 int lca(int ri,int rj)

 {

     if(deep[ri]<deep[rj])swap(ri,rj);

     int d=deep[ri]-deep[rj];

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

         if((<<i)&d)ri=x[ri][i];

     if(ri==rj)return ri;

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

         if((<<i)<=deep[rj]&&x[ri][i]!=x[rj][i])

             ri=x[ri][i],rj=x[rj][i];

     return x[ri][];

 }

 int main()

 {

     n=read();q=read();

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

     {

         u=read();v=read();w=read();

         ins(u,v,w);ins(v,u,w);

     }

     deep[]=;dfs();

     while(q--)

     {

         u=read();v=read();

         printf("%d\n",di[u]+di[v]-*di[lca(u,v)]);

     }

     return ;

 }

LCA

13.【bzoj1613】[Usaco2007 Jan]Running贝茜的晨练计划

 #include<cstdio>

 #include<algorithm>

 #include<cstring>

 #define ll long long

 using namespace std;

 const int inf=0x3f3f3f3f;

 const int N=1e4+;

 int n,m,v,f[N][];

 int read()

 {

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

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

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

     return x*f;

 }

 int main()

 {

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

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

     {

         v=read();

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

         {

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

             if(i+j<=n)f[i+j][]=max(f[i+j][],f[i][j]);

         }

         f[i][]=max(f[i-][],f[i][]);

     }

     printf("%d",f[n][]);

     return ;

 }

普通dp

14.【bzoj1230】[Usaco2008 Nov]lites 开关灯

 #include<cstdio>

 #include<algorithm>

 #include<cstring>

 #define ll long long

 #define l(x) x<<1

 #define r(x) x<<1|1

 using namespace std;

 const int inf=0x3f3f3f3f;

 const int N=1e5+;

 int n,m,p,L,R,ans,num[N*],rev[N*];

 int read()

 {

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

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

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

     return x*f;

 }

 void up(int x)

 {

     num[x]=num[l(x)]+num[r(x)];

 }

 void crev(int x,int l,int r)

 {

     num[x]=(r-l+)-num[x];

     rev[x]^=;

 }

 void start(int x,int l,int r)

 {

     int mid=(l+r)>>;

     if(rev[x])

     {

         crev(l(x),l,mid);

         crev(r(x),mid+,r);

         rev[x]=;

     }

 }

 void change(int x,int l,int r)

 {

     if(l!=r)start(x,l,r);

     if(L<=l&&R>=r){crev(x,l,r);return;}

     int mid=(l+r)>>;

     if(L<=mid)change(l(x),l,mid);

     if(R>mid)change(r(x),mid+,r);

     if(l!=r)up(x);

 }

 void ask(int x,int l,int r)

 {

     if(l!=r)start(x,l,r);

     if(L<=l&&R>=r)

     {

         ans+=num[x];

         return;

     }

     int mid=(l+r)>>;

     if(L<=mid)ask(l(x),l,mid);

     if(R>mid)ask(r(x),mid+,r);

 }

 int main()

 {

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

     while(m--)

     {

         p=read();L=read();R=read();

         if(p==)change(,,n);

         else

         {

             ans=;

             ask(,,n);

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

         }

     }

     return ;

 }

线段树

15.【bzoj1600】[Usaco2008 Oct]建造栅栏

 #include<cstdio>

 #include<algorithm>

 #include<cstring>

 #define ll long long

 using namespace std;

 const int inf=0x3f3f3f3f;

 const int N=;

 int n,mx,f[N][];

 int read()

 {

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

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

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

     return x*f;

 }

 int main()

 {

     n=read();

     mx=(n+)/-;f[][]=;

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

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

             for(int k=;k<=min(j,mx);k++)

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

     printf("%d",f[n][]);

     return ;

 }

普通dp

16.【bzoj1603】[Usaco2008 Oct]打谷机

 #include<cstdio>

 #include<algorithm>

 #include<cstring>

 #define ll long long

 using namespace std;

 const int inf=0x3f3f3f3f;

 const int N=1e3+;

 int n,u,v,w,cnt,r[N],first[N];

 bool f[N];

 struct edge{int to,next,w;}e[N*];

 int read()

 {

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

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

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

     return x*f;

 }

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

 {

     cnt++;e[cnt].next=first[u];first[u]=cnt;

     e[cnt].to=v;e[cnt].w=w;

 }

 void dfs(int x)

 {

     f[x]=true;

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

     {

         if(f[e[i].to])continue;

         r[e[i].to]=r[x]^e[i].w;

         dfs(e[i].to);

     }

 }

 int main()

 {

     n=read();

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

     {

         u=read();v=read();w=read();

         ins(u,v,w);ins(v,u,w);

     }

     dfs();

     printf("%d",r[n]);

     return ;

 }

DFS

17.【bzoj1599】[Usaco2008 Oct]笨重的石子

 #include<cstdio>

 #include<algorithm>

 #include<cstring>

 #define ll long long

 using namespace std;

 const int inf=0x3f3f3f3f;

 int s1,s2,s3,s[],ans,mn;

 int read()

 {

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

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

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

     return x*f;

 }

 int main()

 {

     s1=read();s2=read();s3=read();

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

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

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

                 s[i+j+k]++;

     for(int i=;i<=s1+s2+s3;i++)

         if(s[i]>mn)mn=s[i],ans=i;

     printf("%d",ans);

     return ;

 }

枚举

18.【bzoj1692】[Usaco2007 Dec]队列变换

 #include<cstdio>

 #include<cstring>

 #include<algorithm>

 #define long long LL

 using namespace std;

 const int N=;

 int n,m,l,r,cnt,t1[N],t2[N],sa[N],c[N],rk[N];

 char s[N];

 void build()

 {

     int *x=t1,*y=t2;

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

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

     for(int i=n-;i>=;i--)sa[--c[x[i]]]=i;

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

     {

         int p=;

         for(int i=n-k;i<n;i++)y[p++]=i;

         for(int i=;i<n;i++)if(sa[i]>=k)y[p++]=sa[i]-k;

         memset(c,,sizeof(c));

         for(int i=;i<n;i++)c[x[y[i]]]++;

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

         for(int i=n-;i>=;i--)sa[--c[x[y[i]]]]=y[i];

         swap(x,y);

         p=;x[sa[]]=;

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

             x[sa[i]]=y[sa[i-]]==y[sa[i]]&&y[sa[i-]+k]==y[sa[i]+k]?p-:p++;

         if(p>=n)break;

         m=p;

     }

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

 }

 int main()

 {

     scanf("%d",&n);

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

     {

         s[i]=getchar();

         while(s[i]<'A'||s[i]>'Z')s[i]=getchar();

     }

     for(int i=;i<n;i++)t1[i]=t1[n*-i]=s[i]-'A'+;

     n=(n+)<<;m=;build();

     n=(n>>)-;l=;r=n-;

     while(l<=r)

     {

         if(rk[n*-r]<rk[l])printf("%c",s[r--]);

         else printf("%c",s[l++]);

         cnt++;

         if(cnt==)printf("\n"),cnt=;

     }

     return ;

 }

后缀数组+贪心

19.【bzoj1666】[Usaco2006 Oct]Another Cow Number Game 奶牛的数字游戏

 #include<cstdio>

 #include<cstring>

 #include<algorithm>

 #define LL long long

 using namespace std;

 LL n,ans;

 int read()

 {

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

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

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

     return x*f;

 }

 int main()

 {

     scanf("%lld",&n);

     while(n!=)

     {

         if(n%)n=n*+;

         else n/=;

         ans++;

     }

     printf("%lld",ans);

     return ;

 }

模拟

20.【bzoj1717】[Usaco2006 Dec]Milk Patterns 产奶的模式

 #include<cstdio>

 #include<cstring>

 #include<algorithm>

 #define LL long long

 using namespace std;

 const int N=;

 int cnt=,n,m,k,ans;

 int que[N],s[N],rk[N],hei[N],t1[N],t2[N],c[N],sa[N];

 struct node{int v,pos;}q[N];

 int read()

 {

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

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

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

     return x*f;

 }

 bool cmp(node a,node b){return a.v<b.v;}

 void build()

 {

     int *x=t1,*y=t2;

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

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

     for(int i=n-;i>=;i--)sa[--c[x[i]]]=i;

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

     {

         int p=;

         for(int i=n-k;i<n;i++)y[p++]=i;

         for(int i=;i<n;i++)if(sa[i]>=k)y[p++]=sa[i]-k;

         memset(c,,sizeof(c));

         for(int i=;i<n;i++)c[x[y[i]]]++;

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

         for(int i=n-;i>=;i--)sa[--c[x[y[i]]]]=y[i];

         swap(x,y);

         p=;x[sa[]]=;

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

             x[sa[i]]=y[sa[i-]]==y[sa[i]]&&y[sa[i-]+k]==y[sa[i]+k]?p-:p++;

         if(p>=n)break;

         m=p;

     }

 }

 void get_height()

 {

     int k=;

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

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

     {

         if(k)k--;

         int j=sa[rk[i]-];

         while(s[i+k]==s[j+k])k++;

         hei[rk[i]]=k;

     }

 }

 int main()

 {

     n=read();k=read();

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

         q[i].pos=i,q[i].v=read();

     sort(q,q+n,cmp);

     t1[q[].pos]=;

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

     {

         if(q[i].v!=q[i-].v)t1[q[i].pos]=++cnt;

         else t1[q[i].pos]=cnt;

     }

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

     n++;m=cnt+;build();

     get_height();

     int h=,t=;k--;

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

     {

         while(h<=t&&que[h]<=i-k)h++;

         while(h<=t&&hei[i]<=hei[que[t]])t--;

         que[++t]=i;

         if(i>=k)ans=max(ans,hei[que[h]]);

     }

     printf("%d",ans);

     return ;

 }

后缀数组

21.【bzoj1724】[Usaco2006 Nov]Fence Repair 切割木板

 #include<cstdio>

 #include<cstring>

 #include<algorithm>

 #include<queue>

 #define LL long long

 using namespace std;

 const int N=;

 int n;

 LL sum,ans;

 priority_queue<LL,vector<LL>,greater<LL> >q;

 LL read()

 {

     LL x=,f=;char c=getchar();

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

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

     return x*f;

 }

 int main()

 {

     n=read();

     for(int i=;i<=n;i++)q.push(read());

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

     {

         sum=q.top();q.pop();

         sum+=q.top();q.pop();

         ans+=sum;q.push(sum);

     }

     printf("%lld",ans);

     return ;

 }

优先队列

22.【bzoj1572】[Usaco2009 Open]工作安排Job

 #include<cstdio>

 #include<cstring>

 #include<algorithm>

 #include<queue>

 #define LL long long

 using namespace std;

 const int N=;

 int n,cnt;

 LL ans,sum;

 struct node{int d;LL p;}a[N];

 priority_queue<LL,vector<LL>,greater<LL> >q;

 LL read()

 {

     LL x=,f=;char c=getchar();

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

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

     return x*f;

 }

 bool cmp(node a,node b){return a.d<b.d;}

 int main()

 {

     n=read();

     for(int i=;i<=n;i++)a[i].d=read(),a[i].p=read();

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

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

     {

         if(cnt<a[i].d)

         {

             ans+=a[i].p;

             q.push(a[i].p);

             cnt++;

         }

         else

         {

             sum=q.top();

             if(sum>=a[i].p)continue;

             q.pop();

             ans=ans-sum+a[i].p;

             q.push(a[i].p);

         }

     }

     printf("%lld",ans);

     return ;

 }

优先队列

23.【bzoj1726】[Usaco2006 Nov]Roadblocks第二短路

 #include<cstdio>

 #include<cstring>

 #include<algorithm>

 #include<queue>

 #define LL long long

 using namespace std;

 const int inf=0x3f3f3f3f;

 int n,m,cnt,a,b,d,s,sum,ans=inf;

 int first[],q[],d1[],d2[];

 bool f[];

 struct edge{int from,to,next,w;}e[];

 int read()

 {

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

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

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

     return x*f;

 }

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

 {

     e[++cnt].to=v;e[cnt].from=u;e[cnt].w=w;

     e[cnt].next=first[u];first[u]=cnt;

 }

 void spfa(int s,int d[])

 {

     int h=,t=;

     memset(q,,sizeof(q));

     memset(f,,sizeof(f));

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

     q[h]=s;f[s]=true;d[s]=;

     while(h!=t)

     {

         int u=q[h++];f[u]=false;if(h>)h=;

         for(int i=first[u];i;i=e[i].next)

         {

             int v=e[i].to;

             if(d[u]+e[i].w<d[v])

             {

                 d[v]=d[u]+e[i].w;

                 if(!f[v])

                 {

                     if(d[v]<d[q[h]]){h--;if(h<)h=;q[h]=v;}

                     f[v]=true;q[t++]=v;

                     if(t>)t=;

                 }

             }

         }

     }

 }

 int main()

 {

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

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

     {

         a=read();b=read();d=read();

         ins(a,b,d);ins(b,a,d);

     }

     spfa(,d1);spfa(n,d2);

     sum=d1[n];

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

     {

         s=e[i<<].w+d1[e[i<<].from]+d2[e[i<<].to];

         if(s<ans&&s>sum)ans=s;

         s=e[i<<].w+d2[e[i<<].from]+d1[e[i<<].to];

         if(s<ans&&s>sum)ans=s;

     }

     printf("%d",ans);

     return ;

 }

SPFA

24.【bzoj1579】[Usaco2009 Feb]Revamping Trails 道路升级

 #include<cstdio>

 #include<cstring>

 #include<algorithm>

 #include<queue>

 #define LL long long

 using namespace std;

 const int N=;

 const LL inf=1e15;

 int n,m,k,cnt,a,b,w,first[N];

 LL dis[N][];

 struct edge{int to,next;LL w;}e[];

 struct node

 {

     int p,k;LL w;

     bool operator < (const node& t)const{return w>t.w;}

 };

 priority_queue<node>q;

 int read()

 {

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

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

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

     return x*f;

 }

 void ins(int u,int v,LL w)

 {

     e[++cnt].to=v;e[cnt].w=w;

     e[cnt].next=first[u];first[u]=cnt;

 }

 void dijkstra()

 {

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

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

             dis[i][j]=inf;

     q.push((node){,,});

     while(!q.empty())

     {

         node t=q.top();q.pop();

         int u=t.p,kk=t.k;

         if(dis[u][kk]!=t.w)continue;

         if(u==n){dis[n][k]=t.w;break;}

         for(int i=first[u];i;i=e[i].next)

         {

             int v=e[i].to;

             if(dis[v][kk]>t.w+e[i].w)

             {

                 dis[v][kk]=t.w+e[i].w;

                 q.push((node){v,kk,dis[v][kk]});

             }

             if(kk<k&&dis[v][kk+]>t.w)

             {

                 dis[v][kk+]=t.w;

                 q.push((node){v,kk+,dis[v][kk+]});

             }

         }

     }

 }

 int main()

 {

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

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

     {

         a=read();b=read();w=read();

         ins(a,b,w);ins(b,a,w);

     }

     dijkstra();

     printf("%lld",dis[n][k]);

     return ;

 }

分层图+Dijkstra

25.【bzoj1711】[Usaco2007 Open]Dining吃饭

 #include<cstdio>

 #include<cstring>

 #include<algorithm>

 #define LL long long

 using namespace std;

 const int N=;

 int n,f,d,t,fi,di,ans,cnt=,S,T;

 int cur[N],first[N],dis[N],q[];

 struct edge{int to,next,flow;}e[];

 int read()

 {

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

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

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

     return x*f;

 }

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

 {

     e[++cnt].to=v;e[cnt].flow=w;

     e[cnt].next=first[u];first[u]=cnt;

 }

 void init()

 {

     n=read();f=read();d=read();

     S=;T=f+n+n+d+;

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

         ins(f+i,f+n+i,),ins(f+n+i,f+i,);

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

         ins(S,i,),ins(i,S,);

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

         ins(f+n+n+i,T,),ins(T,f+n+n+i,);

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

     {

         fi=read();di=read();

         while(fi--)

         {

             t=read();

             ins(t,f+i,),ins(f+i,t,);

         }

         while(di--)

         {

             t=read();

             ins(f+n+i,f+n+n+t,),ins(f+n+n+t,f+n+i,);

         }

     }

 }

 bool bfs()

 {

     memset(dis,-,sizeof(dis));

     int head=,tail=;

     q[head]=S;dis[S]=;

     while(head!=tail)

     {

         int u=q[head++];if(head>)head=;

         for(int i=first[u];i;i=e[i].next)

         {

             int v=e[i].to;

             if(dis[v]!=-||!e[i].flow)continue;

             dis[v]=dis[u]+;

             q[tail++]=v;if(tail>)tail=;

         }

     }

     return dis[T]>-;

 }

 int dfs(int u,int a)

 {

     if(u==T||a==)return a;

     int f,flow=;

     for(int& i=cur[u];i;i=e[i].next)

     {

         int v=e[i].to;

         if(dis[v]==dis[u]+&&(f=dfs(v,min(e[i].flow,a)))>)

         {

             e[i].flow-=f;e[i^].flow+=f;

             flow+=f;a-=f;if(a==)break;

         }

     }

     return flow;

 }

 int main()

 {

     init();

     while(bfs())

     {

         for(int i=S;i<=T;i++)cur[i]=first[i];

         ans+=dfs(S,(int)1e9);

     }

     printf("%d",ans);

     return ;

 }

网络流

26.【bzoj1690】 [Usaco2007 Dec]奶牛的旅行

 #include<cstdio>

 #include<cstring>

 #include<algorithm>

 #define LL long long

 using namespace std;

 const int N=;

 int n,m,a,b,ww,cnt;

 int first[N],w[N];

 double dis[N];

 bool f[N],flag;

 struct edge{int to,next,w;double v;}e[];

 int read()

 {

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

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

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

     return x*f;

 }

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

 {

     e[++cnt].to=v;e[cnt].w=w;

     e[cnt].next=first[u];first[u]=cnt;

 }

 void spfa(int u)

 {

     if(flag)return;

     f[u]=true;

     for(int i=first[u];i;i=e[i].next)

     {

         int v=e[i].to;

         if(dis[u]+e[i].v<dis[v])

         {

             if(f[v]){flag=true;return;}

             dis[v]=dis[u]+e[i].v;

             spfa(v);

         }

     }

     f[u]=false;

 }

 bool check(double x)

 {

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

         for(int j=first[i];j;j=e[j].next)

             e[j].v=e[j].w*x-w[e[j].to];

     flag=false;

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

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

     {

         spfa(i);

         if(flag)return true;

     }

     return false;

 }

 int main()

 {

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

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

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

     {

         a=read();b=read();ww=read();

         ins(a,b,ww);

     }

     double l=,r=,mid;

     while(r-l>0.001)

     {

         mid=(l+r)/;

         if(check(mid))l=mid;

         else r=mid;

     }

     printf("%.2lf",l);

     return ;

 }

SPFA+01分数规划

27.【bzoj1708】[Usaco2007 Oct]Money奶牛的硬币

 #include<cstdio>

 #include<cstring>

 #include<algorithm>

 #define LL long long

 using namespace std;

 const int N=;

 LL n,m,v[],dp[];

 LL read()

 {

     LL x=,f=;char c=getchar();

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

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

     return x*f;

 }

 int main()

 {

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

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

     dp[]=;

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

         for(int j=v[i];j<=m;j++)

             dp[j]+=dp[j-v[i]];

     printf("%lld",dp[m]);

     return ;

 }

完全背包

28.【bzoj1725】[Usaco2006 Nov]Corn Fields牧场的安排

 #include<cstdio>

 #include<cstring>

 #include<algorithm>

 #define LL long long

 using namespace std;

 const int N=<<;

 const int mod=;

 int n,m,mx,x,ans,mp[],f[][N];

 int read()

 {

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

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

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

     return x*f;

 }

 int main()

 {

     n=read();m=read();mx=(<<m)-;

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

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

         {

             x=read();

             mp[i]=(mp[i]<<)+x;

         }

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

         if((i&(i>>))==&&(mp[]|i)==mp[])f[][i]=;

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

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

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

                 if((k&(k>>))==&&(j&k)==&&(mp[i]|k)==mp[i])

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

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

         ans=(ans+f[n][i])%mod;

     printf("%d",ans);

     return ;

 }

状压dp

29.【bzoj1827】[Usaco2010 Mar]gather 奶牛大集会

 #include<cstdio>

 #include<cstring>

 #include<algorithm>

 #define LL long long

 using namespace std;

 const int N=1e5+;

 int n,a,b,v,sum,cnt,first[N],w[N],size[N];

 LL ans,dis[N];

 bool f[N];

 struct edge{int to,next,w;}e[N<<];

 int read()

 {

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

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

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

     return x*f;

 }

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

 {e[++cnt]=(edge){v,first[u],w};first[u]=cnt;}

 int dfs1(int x)

 {

     f[x]=true;

     ans+=dis[x]*w[x];

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

         if(!f[e[i].to])

         {

             dis[e[i].to]=dis[x]+e[i].w;

             size[x]+=dfs1(e[i].to);

         }

     size[x]+=w[x];

     return size[x];

 }

 void dfs2(int x)

 {

     f[x]=true;

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

     {

         if(f[e[i].to]||sum-size[e[i].to]>size[e[i].to])continue;

         ans+=((LL)sum-size[e[i].to]*)*e[i].w;

         dfs2(e[i].to);

     }

 }

 int main()

 {

     n=read();

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

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

     {

         a=read();b=read();v=read();

         ins(a,b,v);ins(b,a,v);

     }

     dfs1();sum=size[];

     memset(f,,sizeof(f));dfs2();

     printf("%lld",ans);

     return ;

 }

贪心

30.【bzoj2442】[Usaco2011 Open]修剪草坪

 #include<cstdio>

 #include<cstring>

 #include<algorithm>

 #define LL long long

 using namespace std;

 const int N=1e5+;

 int n,k,h,t,v[N],q[N];

 LL sum,ans=1e15,f[N];

 int read()

 {

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

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

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

     return x*f;

 }

 int main()

 {

     n=read();k=read();

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

         v[i]=read(),sum+=v[i];

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

     {

         f[i]=f[q[h]]+v[i];

         while(h<=t&&f[q[t]]>f[i])t--;

         q[++t]=i;

         while(h<=t&&i-q[h]>k)h++;

     }

     for(int i=max(,n-k);i<=n;i++)

         ans=min(ans,f[i]);

     printf("%lld",sum-ans);

     return ;

 }

单调队列优化dp

31.【bzoj1576】[Usaco2009 Jan]安全路经Travel

 #include<cstdio>

 #include<cstring>

 #include<algorithm>

 #include<queue>

 using namespace std;

 const int N=1e5+;

 int n,m,a,b,w,cnt,tot;

 int first[N],dis[N],fa[N],f[N],deep[N],ans[N];

 struct edge{int from,to,next,w;}e[N*],ee[N*];

 struct node

 {

     int id,w;

     bool operator < (const node& t)const{return w>t.w;}

 };

 priority_queue<node>q;

 int read()

 {

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

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

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

     return x*f;

 }

 void ins(int u,int v,int w){e[++cnt]=(edge){u,v,first[u],w};first[u]=cnt;}

 bool cmp(edge a,edge b){return a.w<b.w;}

 int find(int t){return f[t]==t?t:f[t]=find(f[t]);}

 void dijkstra()

 {

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

     dis[]=;deep[]=;q.push((node){,});

     while(!q.empty())

     {

         node t=q.top();q.pop();

         int u=t.id;

         if(dis[u]!=t.w)continue;

         for(int i=first[u];i;i=e[i].next)

         {

             int v=e[i].to;

             if(dis[v]>dis[u]+e[i].w)

             {

                 dis[v]=dis[u]+e[i].w;

                 deep[v]=deep[u]+;

                 fa[v]=u;

                 q.push((node){v,dis[v]});

             }

         }

     }

 }

 int main()

 {

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

     for(int i=;i<=n;i++)f[i]=i,ans[i]=-;

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

     {

         a=read();b=read();w=read();

         ins(a,b,w);ins(b,a,w);

     }

     dijkstra();

 //  for(int i=1;i<=n;i++)printf("[%d] [dis]%d [deep]%d [fa]%d\n",i,dis[i],deep[i],fa[i]);

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

     {

         a=e[i].from;b=e[i].to;

         if(deep[a]>deep[b])swap(a,b);

         if(dis[a]+e[i].w==dis[b])continue;

         ee[++tot]=(edge){a,b,,dis[a]+dis[b]+e[i].w};

     }

     sort(ee+,ee+tot+,cmp);

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

     {

         a=ee[i].from;b=ee[i].to;

         while(a!=b)

         {

             if(deep[a]<deep[b])swap(a,b);

             if(ans[a]==-)ans[a]=ee[i].w-dis[a];

             a=f[a]=find(fa[a]);

         }

     }

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

     return ;

 }

并查集+dijkstra

32.【bzoj1592】[Usaco2008 Feb]Making the Grade 路面修整

 #include<cstdio>

 #include<algorithm>

 #include<cstring>

 #include<cstdlib>

 #define LL long long

 using namespace std;

 const int N=;

 int n,sum,w[N],v[N],ans[N];

 int read()

 {

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

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

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

     return x*f;

 }

 bool cmp(int a,int b){return a>b;}

 int main()

 {

     n=read();

     for(int i=;i<=n;i++)v[i]=w[i]=read();

     sort(v+,v+n+);

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

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

         {

             ans[j]+=abs(w[i]-v[j]);

             if(j>)ans[j]=min(ans[j],ans[j-]);

         }

     sum=ans[n];

     memset(ans,,sizeof(ans));

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

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

         {

             ans[j]+=abs(w[i]-v[j]);

             if(j>)ans[j]=min(ans[j],ans[j-]);

         }

     sum=min(sum,ans[n]);

     printf("%d",sum);

     return ;

 }

普通dp

33.【bzoj1782】[Usaco2010 Feb]slowdown 慢慢游

 #include<cstdio>

 #include<algorithm>

 #include<cstring>

 #define LL long long

 using namespace std;

 const int N=;

 int n,a,b,cnt,tot,p;

 int first[N],l[N],r[N],t[N<<];

 struct edge{int to,next;}e[N<<];

 int read()

 {

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

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

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

     return x*f;

 }

 void ins(int u,int v){e[++cnt]=(edge){v,first[u]};first[u]=cnt;}

 void dfs(int u)

 {

     l[u]=++tot;

     for(int i=first[u];i;i=e[i].next)

         if(!l[e[i].to])dfs(e[i].to);

     r[u]=++tot;

 }

 int lowbit(int x){return x&(-x);}

 void insert(int x,int p)

 {

     while(x<=*n)

     {

         t[x]+=p;

         x+=lowbit(x);

     }

 }

 int query(int x)

 {

     int ans=;

     while(x){ans+=t[x];x-=lowbit(x);}

     return ans;

 }

 int main()

 {

     n=read();

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

     {

         a=read();b=read();

         ins(a,b);ins(b,a);

     }

     dfs();

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

     {

         p=read();

 //      printf("\n%d %d\n",l[p],r[p]);

         printf("%d\n",query(l[p]));

         insert(l[p],);insert(r[p],-);

     }

     return ;

 }

dfs序+树状数组

34.【bzoj1715】[Usaco2006 Dec]Wormholes 虫洞

 #include<cstdio>

 #include<algorithm>

 #include<cstring>

 #define LL long long

 using namespace std;

 const int N=;

 int T,n,m,w,a,b,t,cnt,first[N],dis[N];

 bool flag,f[N];

 struct edge{int to,next,v;}e[N*];

 int read()

 {

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

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

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

     return x*f;

 }

 void ins(int u,int v,int w){e[++cnt]=(edge){v,first[u],w};first[u]=cnt;}

 void spfa(int u)

 {

     if(flag)return;

     f[u]=true;

     for(int i=first[u];i;i=e[i].next)

     {

         int v=e[i].to;

         if(dis[u]+e[i].v<dis[v])

         {

             if(f[v]){flag=true;return;}

             dis[v]=dis[u]+e[i].v;

             spfa(v);

         }

     }

     f[u]=false;

 }

 int main()

 {

     T=read();

     while(T--)

     {

         memset(first,,sizeof(first));

         memset(f,,sizeof(f));

         n=read();m=read();w=read();

         cnt=;flag=false;

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

         {

             a=read();b=read();t=read();

             ins(a,b,t);ins(b,a,t);

         }

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

         {

             a=read();b=read();t=read();

             ins(a,b,-t);

         }

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

         {

             spfa(i);

             if(flag)break;

         }

         if(flag)printf("YES\n");

         else printf("NO\n");

     }

     return ;

 }

SPFA

35.【bzoj1596】[Usaco2008 Jan]电话网络

 #include<cstdio>

 #include<algorithm>

 #include<cstring>

 #define LL long long

 using namespace std;

 const int N=1e4+;

 int n,a,b,ans,cnt,first[N],fa[N];

 bool f[N];

 struct edge{int to,next;}e[N<<];

 int read()

 {

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

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

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

     return x*f;

 }

 void ins(int u,int v){e[++cnt]=(edge){v,first[u]};first[u]=cnt;}

 void dfs(int x)

 {

     bool flag=false;

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

     {

         int v=e[i].to;

         if(fa[v])continue;

         fa[v]=x;

         dfs(v);

         if(f[v])flag=true;

     }

     if(!flag&&!f[fa[x]]&&!f[x])f[fa[x]]=true,ans++;

 }

 int main()

 {

     n=read();

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

     {

         a=read();b=read();

         ins(a,b);ins(b,a);

     }

     fa[]=;dfs();

     printf("%d",ans);

     return ;

 }

贪心

36.【bzoj1571】[Usaco2009 Open]滑雪课Ski

 #include<cstdio>

 #include<algorithm>

 #include<cstring>

 #define LL long long

 using namespace std;

 const int N=1e4+;

 int T,k,n,cnt=;

 int g[],f[];

 struct lesson{int m,l,a;}c[];

 struct snow{int c,d;}s[N];

 int read()

 {

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

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

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

     return x*f;

 }

 bool cmp1(snow a,snow b){return a.c<b.c;}

 bool cmp2(lesson a,lesson b){return a.m<b.m;}

 int main()

 {

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

     T=read();k=read();n=read();

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

         c[i].m=read(),c[i].l=read(),c[i].a=read();

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

         s[i].c=read(),s[i].d=read();

     sort(s+,s+n+,cmp1);

     sort(c+,c+k+,cmp2);

     c[].m=;c[].l=;c[].a=;

     c[++k].m=T;c[k].l=;c[k].a=0x3f3f3f3f;

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

     {

         while(cnt<=n&&s[cnt].c<=i)g[i]=min(g[i],s[cnt++].d);

         g[i]=min(g[i],g[i-]);

     }

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

     {

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

         {

             if(c[j].a>=c[i].a||c[j].m+c[j].l>c[i].m)continue;

             f[i]=max(f[i],f[j]+(c[i].m-c[j].m-c[j].l)/g[c[j].a]);

         }

     }

     printf("%d",f[k]);

     return ;

 }

普通dp

37.【bzoj1770】[Usaco2009 Nov]lights 燈

 #include<cstdio>

 #include<algorithm>

 #include<cstring>

 #include<cmath>

 using namespace std;

 int n,m,u,v,ans,sum,f[][],p[];

 int read()

 {

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

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

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

     return x*f;

 }

 void gauss()

 {

     int t;

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

     {

         for(t=i;t<=n;t++)if(f[t][i])break;

         if(t>n)continue;

         if(t!=i)

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

                 swap(f[i][j],f[t][j]);

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

             if(f[k][i])

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

                     f[k][j]^=f[i][j];

     }

 }

 void dfs(int x)

 {

     if(sum>=ans)return;

     if(!x){ans=sum;return;}

     if(f[x][x])

     {

         int t=f[x][n+];

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

             t^=f[x][i]*p[i];

         p[x]=t;

         if(t)sum++;

         dfs(x-);

         if(t)sum--;

     }

     else

     {

         p[x]=;dfs(x-);

         p[x]=;sum++;dfs(x-);sum--;

     }

 }

 int main()

 {

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

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

     {

         u=read();v=read();

         f[u][v]=f[v][u]=;

     }

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

         f[i][i]=f[i][n+]=;

     gauss();

     ans=0x3f3f3f3f;sum=;

     dfs(n);

     printf("%d",ans);

     return ;

 }

高斯消元

38.【bzoj1593】[Usaco2008 Feb]Hotel 旅馆

 #include<cstdio>

 #include<cstring>

 #include<algorithm>

 #define l(x) x<<1

 #define r(x) x<<1|1

 using namespace std;

 const int N=2e5+;

 int n,m,f,p,q;

 struct node{int l,r,m,lm,rm,sum,tag;}t[N];

 int read()

 {

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

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

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

     return x*f;

 }

 void up(int x)

 {

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

     if(t[l(x)].m==t[l(x)].sum)t[x].lm=t[l(x)].sum+t[r(x)].lm;

     else t[x].lm=t[l(x)].lm;

     if(t[r(x)].m==t[r(x)].sum)t[x].rm=t[r(x)].sum+t[l(x)].rm;

     else t[x].rm=t[r(x)].rm;

     t[x].m=max(t[l(x)].m,t[r(x)].m);

     t[x].m=max(t[x].m,t[l(x)].rm+t[r(x)].lm);

 }

 void dn(int x)

 {

     int f=t[x].tag;t[x].tag=;

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

     if(f==)

     {

         t[l(x)].lm=t[l(x)].rm=t[l(x)].m=t[l(x)].sum;

         t[r(x)].lm=t[r(x)].rm=t[r(x)].m=t[r(x)].sum;

         t[l(x)].tag=t[r(x)].tag=;

     }

     if(f==)

     {

         t[l(x)].lm=t[l(x)].rm=t[l(x)].m=;

         t[r(x)].lm=t[r(x)].rm=t[r(x)].m=;

         t[l(x)].tag=t[r(x)].tag=;

     }

 }

 void build(int x,int l,int r)

 {

     t[x].lm=t[x].rm=t[x].m=t[x].sum=r-l+;

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

     if(l==r)return;

     int mid=(l+r)>>;

     build(l(x),l,mid);build(r(x),mid+,r);

 }

 void change(int x,int a,int b,int f)

 {

     dn(x);

     int l=t[x].l,r=t[x].r,mid=(l+r)>>;

     if(a==l&&b==r)

     {

         if(f==)t[x].lm=t[x].rm=t[x].m=t[x].sum;

         else t[x].lm=t[x].rm=t[x].m=;

         t[x].tag=f;

         return;

     }

     if(mid>=b)change(l(x),a,b,f);

     else if(mid<a)change(r(x),a,b,f);

     else

     {

         change(l(x),a,mid,f);

         change(r(x),mid+,b,f);

     }

     up(x);

 }

 int ask(int x,int w)

 {

     dn(x);

     int l=t[x].l,r=t[x].r,mid=(l+r)>>;

     if(l==r)return l;

     if(t[l(x)].m>=w)return ask(l(x),w);

     if(t[l(x)].rm+t[r(x)].lm>=w)return mid-t[l(x)].rm+;

     if(t[r(x)].m>=w)return ask(r(x),w);

 }

 int main()

 {

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

     build(,,n);

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

     {

         f=read();

         if(f==)

         {

             p=read();

             if(t[].m<p)printf("0\n");

             else

             {

                 q=ask(,p);

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

                 change(,q,q+p-,);

             }

         }

         else

         {

             p=read();q=read();

             change(,p,p+q-,);

         }

     }

     return ;

 }

线段树

39.【bzoj1668】[Usaco2006 Oct]Cow Pie Treasures 馅饼里的财富

 #include<cstdio>

 #include<cstring>

 #include<algorithm>

 using namespace std;

 const int N=;

 const int inf=0x3f3f3f3f;

 int r,c,mp[N][N],f[N][N];

 int read()

 {

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

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

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

     return x*f;

 }

 int main()

 {

     r=read();c=read();

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

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

         {

             mp[i][j]=read();

             f[i][j]=-inf;

         }

     f[][]=mp[][];

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

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

         {

             if(j>)f[j][i]=max(f[j][i],f[j-][i-]);

             f[j][i]=max(f[j][i],f[j][i-]);

             if(j<r)f[j][i]=max(f[j][i],f[j+][i-]);

             f[j][i]+=mp[j][i];

         }

     printf("%d",f[r][c]);

     return ;

 }

普通dp

40.【bzoj1604】[Usaco2008 Open]Cow Neighborhoods 奶牛的邻居

 #include<cstdio>

 #include<cstring>

 #include<algorithm>

 #include<set>

 #define LL long long

 using namespace std;

 const int N=1e5+;

 const LL inf=1e15;

 int n,c,x,y,ans,h=,f[N],sum[N];

 struct node{LL x,y;int id;}a[N];

 multiset <node> s;

 set <node>::iterator it;

 int read()

 {

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

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

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

     return x*f;

 }

 int find(int t){return f[t]==t?t:f[t]=find(f[t]);}

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

 bool operator < (node a,node b){return a.y<b.y;}

 void change(int x,int y)

 {

     int xx=find(x),yy=find(y);

     if(xx!=yy)ans--,f[xx]=yy;

 }

 int main()

 {

     n=read();c=read();ans=n;

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

     {

         x=read();y=read();f[i]=i;

         a[i].x=x+y;a[i].y=x-y;a[i].id=i;

     }

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

     s.insert((node){,-inf,});

     s.insert((node){,inf,});

     s.insert(a[]);

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

     {

         while(a[i].x-a[h].x>c)s.erase(s.find(a[h++]));

         it=s.lower_bound(a[i]);

         node xx=*it,yy=*--it;

         if(xx.y-a[i].y<=c)change(xx.id,a[i].id);

         if(a[i].y-yy.y<=c)change(yy.id,a[i].id);

         s.insert(a[i]);

     }

     printf("%d ",ans);ans=;

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

     for(int i=;i<=n;i++)ans=max(ans,sum[i]);

     printf("%d",ans);

     return ;

 }

并查集+平衡树

41.【bzoj1691】[Usaco2007 Dec]挑剔的美食家

 #include<cstdio>

 #include<algorithm>

 #include<cstring>

 #include<set>

 #define LL long long

 using namespace std;

 const int N=1e5+;

 int n,m,cnt=;

 LL ans;

 struct node{int x,y;}a[N],b[N];

 multiset <int> s;

 multiset <int> :: iterator t;

 int read()

 {

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

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

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

     return x*f;

 }

 bool cmp(node a,node b){return a.y>b.y;}

 int main()

 {

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

     for(int i=;i<=n;i++)a[i].x=read(),a[i].y=read();

     for(int i=;i<=m;i++)b[i].x=read(),b[i].y=read();

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

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

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

     {

         while(b[cnt].y>=a[i].y&&cnt<=m)s.insert(b[cnt++].x);

         t=s.lower_bound(a[i].x);

         if(t!=s.end())

         {

             ans+=*t;

             s.erase(t);

         }

         else

         {

             printf("-1");

             return ;

         }

     }

     printf("%lld",ans);

     return ;

 }

平衡树+贪心

42.【bzoj1697】[Usaco2007 Feb]Cow Sorting牛排序

 #include<cstdio>

 #include<algorithm>

 #include<cstring>

 #define LL long long

 using namespace std;

 const int N=1e4+;

 int n,t,mn=1e6;

 LL ans;

 bool f[N];

 struct node{int num,pos,id;}a[N];

 int read()

 {

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

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

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

     return x*f;

 }

 bool cmp1(node a,node b){return a.num<b.num;}

 bool cmp2(node a,node b){return a.pos<b.pos;}

 int main()

 {

     n=read();

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

         a[i].num=read(),a[i].pos=i,mn=min(mn,a[i].num);

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

     for(int i=;i<=n;i++)a[i].id=i;

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

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

     {

         if(f[i])continue;

         int mnn=a[i].num,sum=a[i].num,cnt=;

         f[i]=true;t=a[i].id;

         while(!f[t])

         {

             mnn=min(mnn,a[t].num);

             sum+=a[t].num;

             f[t]=true;cnt++;

             t=a[t].id;

         }

         ans+=min(sum+1ll*(cnt-)*mnn,sum+mnn+1ll*(cnt+)*mn);

 //      printf("%d %d %d\n",sum,mnn,cnt);

     }

     printf("%lld",ans);

     return ;

 }

置换

43.【bzoj1589】[Usaco2008 Dec]Trick or Treat on the Farm 采集糖果

 #include<cstdio>

 #include<algorithm>

 #include<cstring>

 #define LL long long

 using namespace std;

 const int N=1e5+;

 int n,head=,tail,cnt;

 int to[N],in[N],s[N],q[N],ans[N];

 bool f[N];

 int read()

 {

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

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

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

     return x*f;

 }

 int main()

 {

     n=read();

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

         to[i]=read(),in[to[i]]++;

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

         if(!in[i])s[++tail]=i,f[i]=true;

     while(head<=tail)

     {

         int h=s[head++];in[to[h]]--;

         if(!in[to[h]])s[++tail]=to[h],f[to[h]]=true;

     }

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

     {

         if(f[i])continue;

         int t=to[i];cnt=;

         f[i]=true;q[++cnt]=i;

         while(!f[t])

             f[t]=true,q[++cnt]=t,t=to[t];

         for(int j=;j<=cnt;j++)ans[q[j]]=cnt;

     }

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

         ans[s[i]]=ans[to[s[i]]]+;

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

         printf("%d\n",ans[i]);

     return ;

 }

拓扑排序

44.【bzoj1574】[Usaco2009 Jan]地震损坏Damage

 #include<cstdio>

 #include<algorithm>

 #include<cstring>

 #define LL long long

 using namespace std;

 const int N=3e4+;

 int n,m,c,u,v,w,ans,cnt;

 int first[N];

 bool del[N],f[N];

 struct edge{int to,next;}e[N*];

 int read()

 {

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

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

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

     return x*f;

 }

 void ins(int u,int v){e[++cnt]=(edge){v,first[u]};first[u]=cnt;}

 void delet(int x)

 {

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

         del[e[i].to]=true;

 }

 void dfs(int x)

 {

     ans--;f[x]=true;

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

         if(!f[e[i].to]&&!del[e[i].to])dfs(e[i].to);

 }

 int main()

 {

     ans=n=read();m=read();c=read();

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

     {

         u=read();v=read();

         ins(u,v);ins(v,u);

     }

     for(int i=;i<=c;i++)delet(read());

     dfs();

     printf("%d",ans);

     return ;

 }

dfs+贪心

45.【bzoj1828】[Usaco2010 Mar]balloc 农场分配

 #include<cstdio>

 #include<algorithm>

 #include<cstring>

 #define LL long long

 #define l(x) x<<1

 #define r(x) x<<1|1

 using namespace std;

 const int N=1e5+;

 int n,m,sum,ans,L,R,mn[N*],add[N*];

 struct node{int l,r;}a[N];

 int read()

 {

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

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

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

     return x*f;

 }

 bool cmp(node a,node b){return a.r==b.r?a.l>b.l:a.r<b.r;}

 void up(int x){mn[x]=min(mn[l(x)],mn[r(x)]);}

 void dn(int x,int l,int r)

 {

     int mid=(l+r)>>;

     mn[l(x)]+=add[x];add[l(x)]+=add[x];

     mn[r(x)]+=add[x];add[r(x)]+=add[x];

     add[x]=;

 }

 void build(int x,int l,int r)

 {

     if(l==r){mn[x]=read();return;}

     int mid=(l+r)>>;

     build(l(x),l,mid);

     build(r(x),mid+,r);

     if(l!=r)up(x);

 }

 void change(int x,int l,int r)

 {

     if(l!=r)dn(x,l,r);

     if(L<=l&&R>=r){mn[x]--;add[x]--;return;}

     int mid=(l+r)>>;

     if(L<=mid)change(l(x),l,mid);

     if(R>mid)change(r(x),mid+,r);

     if(l!=r)up(x);

 }

 void ask(int x,int l,int r)

 {

     if(l!=r)dn(x,l,r);

     if(L<=l&&R>=r){ans=min(ans,mn[x]);return;}

     int mid=(l+r)>>;

     if(L<=mid)ask(l(x),l,mid);

     if(R>mid)ask(r(x),mid+,r);

 }

 int main()

 {

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

     build(,,n);

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

         a[i].l=read(),a[i].r=read();

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

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

     {

         ans=1e9;L=a[i].l;R=a[i].r;ask(,,n);

         if(!ans)continue;

         sum++;change(,,n);

     }

     printf("%d",sum);

     return ;

 }

线段树+贪心

46.【bzoj1709】[Usaco2007 Oct]Super Paintball超级弹珠

 #include<cstdio>

 #include<algorithm>

 #include<cstring>

 #define LL long long

 using namespace std;

 const int N=1e2+;

 int n,k,ans;

 int row[N],line[N],left[N*],right[N*],map[N][N];

 int read()

 {

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

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

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

     return x*f;

 }

 int main()

 {

     n=read();k=read();

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

         map[read()][read()]++;

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

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

         {

             row[i]+=map[i][j];

             line[j]+=map[i][j];

         }

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

     {

         int x=i,y=;

         while(x<=n&&y<=n)left[n-i+]+=map[x++][y++];

     }

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

     {

         int x=,y=i;

         while(x<=n&&y<=n)left[n+i-]+=map[x++][y++];

     }

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

     {

         int x=i,y=n;

         while(x<=n&&y>=)right[n-i+]+=map[x++][y--];

     }

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

     {

         int x=,y=i;

         while(x<=n&&y>=)right[n+n-i]+=map[x++][y--];

     }

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

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

         {

             int tmp=;

             tmp+=row[i]-map[i][j];

             tmp+=line[j]-map[i][j];

             tmp+=left[n+j-i]-map[i][j];

             tmp+=right[*n-j-i+]-map[i][j];

 //          printf("[%d %d] [left]%d %d [right]%d %d\n",i,j,n-j+i,left[n+j-i],2*n-j-i+1,right[2*n-j-i+1]);

             if(tmp+map[i][j]==k)ans++;

         }

     printf("%d",ans);

 /*  for(int i=1;i<=n;i++)printf("[%d] %d\n",i,row[i]);

     for(int i=1;i<=n;i++)printf("[%d] %d\n",i,line[i]);

     for(int i=1;i<=2*n-1;i++)printf("[%d] %d\n",i,left[i]);

     for(int i=1;i<=2*n-1;i++)printf("[%d] %d\n",i,right[i]);*/

     return ;

 }

枚举

47.【bzoj1584】[Usaco2009 Mar]Cleaning Up 打扫卫生

 #include<cstdio>

 #include<algorithm>

 #include<cstring>

 #include<cmath>

 #define LL long long

 using namespace std;

 const int N=4e4+;

 int n,m,a[N],f[N],pre[N],pos[N],cnt[N];

 int read()

 {

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

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

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

     return x*f;

 }

 int main()

 {

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

     m=(int)(sqrt(n));

     for(int i=;i<=n;i++)a[i]=read(),f[i]=i;

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

     {

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

             if(pre[a[i]]<=pos[j])cnt[j]++;

         pre[a[i]]=i;

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

             if(cnt[j]>j)

             {

                 int t=pos[j]+;

                 while(pre[a[t]]>t)t++;

                 pos[j]=t;cnt[j]--;

             }

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

             f[i]=min(f[i],f[pos[j]]+j*j);

     }

     printf("%d",f[n]);

     return ;

 }

神奇のdp

48.【bzoj1707】[Usaco2007 Nov]tanning分配防晒霜

 #include<cstdio>

 #include<algorithm>

 #include<cstring>

 #define LL long long

 using namespace std;

 const int N=;

 int n,m,ans,id;

 struct cow{int mx,mn;}c[N];

 struct spf{int spf,cov;}s[N];

 int read()

 {

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

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

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

     return x*f;

 }

 bool cmp1(cow a,cow b){return a.mx<b.mx;}

 bool cmp2(spf a,spf b){return a.spf<b.spf;}

 int main()

 {

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

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

         c[i].mn=read(),c[i].mx=read();

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

         s[i].spf=read(),s[i].cov=read();

     sort(c+,c+n+,cmp1);

     sort(s+,s+m+,cmp2);

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

     {

         id=-;

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

             if(s[j].spf>=c[i].mn&&s[j].spf<=c[i].mx&&s[j].cov>){id=j;break;}

         if(id==-)continue;

         ans++;s[id].cov--;

     }

     printf("%d",ans);

     return ;

 }

贪心

49.【bzoj1754】[Usaco2005 qua]Bull Math

 #include<cstdio>

 #include<algorithm>

 #include<cstring>

 #define LL long long

 using namespace std;

 const int N=;

 char s[N];

 int lena,lenb,len,a[N],b[N],ans[N];

 int main()

 {

     scanf("%s",s+);

     lena=strlen(s+);

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

     scanf("%s",s+);

     lenb=strlen(s+);

     for(int i=lenb;i>=;i--)b[i]=s[lenb-i+]-'';

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

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

             ans[i+j-]+=b[i]*a[j];

     len=lena+lenb+;

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

         if(ans[i]>)ans[i+]+=ans[i]/,ans[i]%=;

     while(len>&&!ans[len])len--;

     for(int i=len;i>=;i--)printf("%d",ans[i]);

     return ;

 }

高精度

50.【bzoj1706】[usaco2007 Nov]relays 奶牛接力跑

 #include<cstdio>

 #include<algorithm>

 #include<cstring>

 #define LL long long

 using namespace std;

 const int N=;

 int n,t,s,e,cnt,x,y,w,id[N*];

 struct node

 {

     int map[N][N];

     node(){memset(map,0x3f,sizeof(map));}

 }m,ans;

 int read()

 {

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

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

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

     return x*f;

 }

 int get_id(int x){return id[x]?id[x]:id[x]=++cnt;}

 node operator * (node a,node b)

 {

     node c;

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

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

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

                 c.map[i][j]=min(c.map[i][j],a.map[i][k]+b.map[k][j]);

     return c;

 }

 int main()

 {

     n=read();t=read();s=read();e=read();

     s=get_id(s);e=get_id(e);

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

     {

         w=read();x=read();y=read();

         x=get_id(x);y=get_id(y);

         m.map[x][y]=m.map[y][x]=min(m.map[x][y],w);

     }

     bool f=false;

     for(int p=;p<=n;p<<=,m=m*m)

         if(p&n)

         {

             if(!f)ans=m,f=true;

             else ans=ans*m;

         }

     printf("%d",ans.map[s][e]);

     return ;

 }

Floyd+矩阵乘法

51.【bzoj1753】[Usaco2005 qua]Who's in the Middle

 #include<cstdio>

 #include<algorithm>

 #include<cstring>

 #define LL long long

 using namespace std;

 const int N=;

 int n,a[N];

 int read()

 {

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

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

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

     return x*f;

 }

 int main()

 {

     n=read();

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

     sort(a+,a+n+);

     printf("%d",a[(n+)>>]);

     return ;

 }

模拟

52.【bzoj1710】[Usaco2007 Open]Cheappal 廉价回文

 #include<cstdio>

 #include<algorithm>

 #include<cstring>

 #define LL long long

 using namespace std;

 const int N=;

 const int inf=0x3f3f3f3f;

 int n,m,t,p[],f[N][N],ans=inf;

 char s[N],ch[];

 int read()

 {

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

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

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

     return x*f;

 }

 int main()

 {

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

     scanf("%s",s+);

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

     {

         scanf("%s",ch);

         t=ch[]-'a';

         p[t]=read();

         p[t]=min(p[t],read());

     }

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

     f[][]=;

     f[][]=p[s[]-'a'];

     f[][]=p[s[n]-'a'];

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

     {

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

         {

             t=inf;

             if(i&&j&&s[i]==s[n-j+])t=f[i-][j-];

             if(i)t=min(t,f[i-][j]+p[s[i]-'a']);

             if(j)t=min(t,f[i][j-]+p[s[n-j+]-'a']);

             f[i][j]=min(f[i][j],t);

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

         }

     }

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

     {

         ans=min(ans,f[i][n-i]);

         ans=min(ans,f[i][n-i-]);

     }

     printf("%d",ans);

     return ;

 }

区间dp

53.【bzoj1598】[Usaco2008 Mar]牛跑步

 #include<cstdio>

 #include<algorithm>

 #include<cstring>

 #define LL long long

 using namespace std;

 const int N=;

 const int inf=0x3f3f3f3f;

 int n,m,k,x,y,d,cnt,aa,bb;

 int c[],first[N],f[N][];

 struct edge{int to,next,w;}e[N*];

 int read()

 {

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

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

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

     return x*f;

 }

 void ins(int u,int v,int w){e[++cnt]=(edge){v,first[u],w};first[u]=cnt;}

 void check(int a,int b,int w)

 {

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

     cnt=;aa=bb=;

     while(cnt<k)

     {

         if(f[a][aa]<f[b][bb]+w)c[++cnt]=f[a][aa++];

         else c[++cnt]=f[b][bb++]+w;

     }

     for(int i=;i<=k;i++)f[a][i]=c[i];

 }

 int main()

 {

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

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

     {

         x=read();y=read();d=read();

         ins(y,x,d);

     }

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

     f[n][]=;

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

         for(int j=first[i];j;j=e[j].next)

             check(i,e[j].to,e[j].w);

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

         if(f[][i]>=inf)printf("-1\n");

         else printf("%d\n",f[][i]);

     return ;

 }

k短路

54.【bzoj2060】[Usaco2010 Nov]Visiting Cows 拜访奶牛

 #include<cstdio>

 #include<algorithm>

 #include<cstring>

 using namespace std;

 const int N=5e4+;

 int n,cnt,x,y,first[N],f[N][];

 bool vis[N];

 struct edge{int to,next;}e[N*];

 int read()

 {

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

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

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

     return x*f;

 }

 void ins(int u,int v){e[++cnt]=(edge){v,first[u]};first[u]=cnt;}

 void dfs(int x)

 {

     vis[x]=true;f[x][]=;

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

     {

         int to=e[i].to;

         if(vis[to])continue;

         dfs(to);

         f[x][]+=f[to][];

         f[x][]+=max(f[to][],f[to][]);

     }

 }

 int main()

 {

     n=read();

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

     {

         x=read();y=read();

         ins(x,y);ins(y,x);

     }

     dfs();

     printf("%d",max(f[][],f[][]));

     return ;

 }

树形dp

55.【bzoj1741】[Usaco2005 nov]Asteroids 穿越小行星群

 #include<cstdio>

 #include<algorithm>

 #include<cstring>

 using namespace std;

 const int N=1e3+;

 const int inf=0x3f3f3f3f;

 int n,k,cnt=,x,y,S,T,ans;

 int first[N],dis[N],q[N],cur[N];

 struct edge{int to,next,flow;}e[];

 int read()

 {

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

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

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

     return x*f;

 }

 void ins(int u,int v,int flow){e[++cnt]=(edge){v,first[u],flow};first[u]=cnt;}

 bool bfs()

 {

     memset(dis,-,sizeof(dis));

     int head=,tail=;

     q[head]=S;dis[S]=;

     while(head!=tail)

     {

         int u=q[head++];if(head>)head=;

         for(int i=first[u];i;i=e[i].next)

         {

             int v=e[i].to;

             if(dis[v]!=-||!e[i].flow)continue;

             dis[v]=dis[u]+;

             q[tail++]=v;if(tail>)tail=;

         }

     }

     return dis[T]>-;

 }

 int dfs(int u,int a)

 {

     if(u==T||a==)return a;

     int f,flow=;

     for(int& i=cur[u];i;i=e[i].next)

     {

         int v=e[i].to;

         if(dis[v]==dis[u]+&&(f=dfs(v,min(e[i].flow,a)))>)

         {

             e[i].flow-=f;e[i^].flow+=f;

             flow+=f;a-=f;if(a==)break;

         }

     }

     return flow;

 }

 int main()

 {

     n=read();k=read();

     S=;T=*n+;

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

     {

         x=read();y=read();

         ins(x,y+n,inf);ins(y+n,x,);

     }

     for(int i=;i<=n;i++)ins(S,i,),ins(i,S,);

     for(int i=;i<=n;i++)ins(i+n,T,),ins(T,i+n,);

     while(bfs())

     {

         for(int i=S;i<=T;i++)cur[i]=first[i];

         ans+=dfs(S,inf);

     }

     printf("%d",ans);

     return ;

 }

网络流

56.【bzoj1578】[Usaco2009 Feb]Stock Market 股票市场

 #include<cstdio>

 #include<algorithm>

 #include<cstring>

 using namespace std;

 int s,d,m,map[][],f[];

 int read()

 {

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

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

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

     return x*f;

 }

 int main()

 {

     s=read();d=read();m=read();

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

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

             map[i][j]=read();

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

     {

         memset(f,,sizeof(f));

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

             for(int k=map[j][i];k<=m;k++)

                 f[k]=max(f[k],f[k-map[j][i]]+map[j][i+]-map[j][i]);

         m+=f[m];

     }

     printf("%d",m);

     return ;

 }

背包dp

57.【bzoj1703】[Usaco2007 Mar]Ranking the Cows 奶牛排名

 #include<cstdio>

 #include<algorithm>

 #include<cstring>

 #include<bitset>

 using namespace std;

 bitset<> f[];

 int n,m,x,y,ans;

 int read()

 {

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

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

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

     return x*f;

 }

 int main()

 {

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

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

         x=read(),y=read(),f[x][y]=true;

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

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

             if(f[j][i])f[j]|=f[i];

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

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

             if(!f[i][j]&&!f[j][i])ans++;

     printf("%d",ans);

     return ;

 }

Floyd传递闭包

58.【bzoj2199】[Usaco2011 Jan]奶牛议会

 #include<cstdio>

 #include<algorithm>

 #include<cstring>

 #define LL long long

 using namespace std;

 const int inf=0x3f3f3f3f;

 const int N=;

 const char s[]={'?','Y','N'};

 struct edge{int to,next;}e[N*];

 int n,m,a,b,c,d,cnt,first[N],ans[N];

 bool vis[N],p,q;

 char ch;

 int read()

 {

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

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

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

     return x*f;

 }

 char get()

 {

     char ch=getchar();

     while(ch!='Y'&&ch!='N')ch=getchar();

     return ch;

 }

 void insert(int u,int v){e[++cnt]=(edge){v,first[u]};first[u]=cnt;}

 void dfs(int x)

 {

     vis[x]=true;

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

         if(!vis[e[i].to])dfs(e[i].to);

 }

 bool check(int x)

 {

     memset(vis,,sizeof(vis));

     dfs(x);

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

         if(vis[i]&&vis[i+n])return false;

     return true;

 }

 int main()

 {

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

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

     {

         a=read();ch=get();

         if(ch=='Y')b=a+n;

         else b=a,a=b+n;

         c=read();ch=get();

         if(ch=='Y')d=c+n;

         else d=c,c=d+n;

         insert(b,c);insert(d,a);

     }

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

     {

         p=check(i);q=check(i+n);

         if(!p&&!q){printf("IMPOSSIBLE");return ;}

         if(p&&q)ans[i]=;

         else if(p)ans[i]=;

         else ans[i]=;

     }

     for(int i=;i<=n;i++)putchar(s[ans[i]]);

     return ;

 }

2-SAT

59.【bzoj1702】[Usaco2007 Mar]Gold Balanced Lineup 平衡的队列

 #include<cstdio>

 #include<algorithm>

 #include<cstring>

 #include<map>

 #define LL long long

 #define UL unsigned long long

 using namespace std;

 const int N=1e5+;

 const int hash=;

 int n,k,cnt,x,ans,f[N][];

 int read()

 {

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

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

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

     return x*f;

 }

 map<UL,int>m;

 int search(int t)

 {

     UL sum=;

     for(int i=;i<=k;i++)sum=sum*hash+1LL*f[t][i];

     if(!m[sum]&&sum)m[sum]=t;

     return m[sum];

 }

 int main()

 {

     n=read();k=read();

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

     {

         cnt=;x=read();

         for(;x;x>>=)f[i][++cnt]=x&;

         for(int j=;j<=k;j++)f[i][j]+=f[i-][j];

     }

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

     {

         for(int j=;j<=k;j++)f[i][j]-=f[i][];

         ans=max(ans,i-search(i));

     }

     printf("%d",ans);

     return ;

 }

哈希

60.【bzoj1734】[Usaco2005 feb]Aggressive cows 愤怒的牛

 #include<cstdio>

 #include<algorithm>

 #include<cstring>

 #define LL long long

 using namespace std;

 const int inf=0x3f3f3f3f;

 const int N=1e5+;

 int n,c,ans,a[N];

 int read()

 {

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

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

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

     return x*f;

 }

 bool check(int x)

 {

     int sum=,last=a[];

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

         if(a[i]-last>=x)last=a[i],sum++;

     return sum>=c;

 }

 void work()

 {

     int l=,r=a[n]-a[],mid;

     while(l<=r)

     {

         mid=(l+r)>>;

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

         else r=mid-;

     }

 }

 int main()

 {

     n=read();c=read();

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

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

     printf("%d",ans);

     return ;

 }

二分

61.【bzoj1585】[Usaco2009 Mar]Earthquake Damage 2 地震伤害

 #include<cstdio>

 #include<algorithm>

 #include<cstring>

 #define LL long long

 using namespace std;

 const int N=;

 const int inf=0x3f3f3f3f;

 int n,m,k,x,y,cnt=,ans,S,T;

 int dis[N],first[N],cur[N],q[N];

 bool f[N];

 struct edge{int to,next,flow;}e[N*];

 int read()

 {

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

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

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

     return x*f;

 }

 void ins(int u,int v,int flow){e[++cnt]=(edge){v,first[u],flow};first[u]=cnt;}

 bool bfs()

 {

     memset(dis,-,sizeof(dis));

     int head=,tail=;

     q[head]=S;dis[S]=;

     while(head!=tail)

     {

         int u=q[head++];if(head>)head=;

         for(int i=first[u];i;i=e[i].next)

         {

             int v=e[i].to;

             if(dis[v]!=-||!e[i].flow)continue;

             dis[v]=dis[u]+;

             q[tail++]=v;if(tail>)tail=;

         }

     }

     return dis[T]>-;

 }

 int dfs(int u,int a)

 {

     if(u==T||a==)return a;

     int f,flow=;

     for(int& i=cur[u];i;i=e[i].next)

     {

         int v=e[i].to;

         if(dis[v]==dis[u]+&&(f=dfs(v,min(e[i].flow,a)))>)

         {

             e[i].flow-=f;e[i^].flow+=f;

             flow+=f;a-=f;if(a==)break;

         }

     }

     return flow;

 }

 int main()

 {

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

     S=;T=*n+;

     ins(,T,inf);ins(T,,);

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

     {

         x=read();y=read();

         ins(x+n,y,inf);ins(y,x+n,);

         ins(y+n,x,inf);ins(x,y+n,);

     }

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

     {

         x=read();f[x]=true;

         ins(S,x,inf);ins(x,S,inf);

     }

     ins(,+n,inf);ins(+n,,);

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

     {

         if(f[i])ins(i,i+n,inf),ins(i+n,i,);

         else ins(i,i+n,),ins(i+n,i,);

     }

     while(bfs())

     {

         for(int i=S;i<=T;i++)cur[i]=first[i];

         ans+=dfs(S,inf);

     }

     printf("%d",ans);

     return ;

 }

网络流

62.【bzoj1704】[Usaco2007 Mar]Face The Right Way 自动转身机

 #include<cstdio>

 #include<algorithm>

 #include<cstring>

 #define LL long long

 using namespace std;

 const int N=;

 int n,cnt,K,M=,d[N],c[N];

 void read()

 {

     char ch=getchar();

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

     {

         while(ch!='F'&&ch!='B')ch=getchar();

         if(ch=='F')d[i]=;

         else d[i]=;

         ch=getchar();

     }

     for(int i=n;i;i--)d[i]-=d[i-];

 }

 int main()

 {

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

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

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

     {

         int m=,sum=;bool f=true;

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

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

         {

             sum+=c[i];

             if(c[i]%==)continue;

             if(i+k->n){f=false;break;}

             c[i]++;c[i+k]--;sum++;m++;

         }

         if(f&&m<M)M=m,K=k;

     }

     printf("%d %d",K,M);

     return ;

 }

枚举+贪心

63.【bzoj1718】[Usaco2006 Jan] Redundant Paths 分离的路径

 #include<cstdio>

 #include<algorithm>

 #include<cstring>

 #define LL long long

 using namespace std;

 const int N=;

 const int M=;

 int n,m,x,y,cnt=,T,top,C,ans;

 int ind[N],first[N],low[N],dfn[N],col[N],st[N],pos[N];

 bool f[M*];

 struct edge{int from,to,next;}e[M*];

 int read()

 {

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

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

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

     return x*f;

 }

 void ins(int u,int v){e[++cnt]=(edge){u,v,first[u]};first[u]=cnt;}

 int min(int a,int b){return a<b?a:b;}

 void tarjan(int x)

 {

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

     st[++top]=x;pos[x]=top;

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

     {

         int to=e[i].to;

         if(f[i^])continue;

         f[i]=true;

         if(!dfn[to])tarjan(to),low[x]=min(low[x],low[to]);

         else low[x]=min(low[x],dfn[to]);

     }

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

         for(C++;top>=pos[x];top--)col[st[top]]=C;

 }

 int main()

 {

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

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

     {

         x=read();y=read();

         ins(x,y);ins(y,x);

     }

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

         if(!dfn[i])tarjan(i);

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

         if(col[e[i].from]!=col[e[i].to])

             ind[col[e[i].from]]++,ind[col[e[i].to]]++;

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

         if(ind[i]==)ans++;

     printf("%d",(ans+)>>);

     return ;

 }

tarjan

64.【bzoj1700】[Usaco2007 Jan]Problem Solving 解题

 #include<cstdio>

 #include<algorithm>

 #include<cstring>

 #define LL long long

 using namespace std;

 const int N=;

 int n,m,ans,sum1[N],sum2[N],f[N][N];

 int read()

 {

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

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

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

     return x*f;

 }

 int main()

 {

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

     f[][]=;

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

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

         sum1[i]=sum1[i-]+read(),sum2[i]=sum2[i-]+read();

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

     {

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

         {

             if(sum1[k]-sum1[k-i]>m)continue;

             for(int j=;j<=k-i;j++)

             {

                 if(sum1[k]-sum1[k-i]+sum2[k-i]-sum2[k-i-j]>m)continue;

                 f[k][i]=min(f[k][i],f[k-i][j]+);

 //              printf("%d %d %d   %d %d\n",k,i,f[k][i],k-i,j);

             }

         }

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

             if(sum2[k]-sum2[k-i]<=m)f[k][]=min(f[k][],f[k][i]+);

     }

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

     ans=f[n][]+;

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

         if(sum2[n]-sum2[n-i]<=m)ans=min(ans,f[n][i]+);

     printf("%d",ans);

     return ;

 }

普通dp

65.【bzoj1778】[Usaco2010 Hol]Dotp 驱逐猪猡

 #include<cstdio>

 #include<algorithm>

 #include<cstring>

 #define LL long long

 using namespace std;

 const int N=;

 const int M=1e5+;

 int n,m,p,q,cnt,x,y;

 int first[N],ind[N];

 double f[N][N];

 struct edge{int to,next;}e[M];

 int read()

 {

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

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

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

     return x*f;

 }

 void ins(int u,int v){e[++cnt]=(edge){v,first[u]};first[u]=cnt;}

 int main()

 {

     n=read();m=read();p=read();q=read();

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

         x=read(),y=read(),ins(x,y),ins(y,x),ind[x]++,ind[y]++;

     f[][n+]=;

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

     {

         f[i][i]=;

         for(int j=first[i];j;j=e[j].next)

             f[i][e[j].to]-=(-1.0*p/q)/ind[e[j].to];

     }

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

     {

         int now=i;

         for(int j=i+;j<=n;j++)if(f[j][i]>f[now][i])now=j;

         if(now!=i)for(int j=i+;j<=n;j++)swap(f[i][j],f[now][j]);

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

             for(int k=n+;k>=i;k--)

                 f[j][k]-=f[j][i]/f[i][i]*f[i][k];

     }

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

     {

         for(int j=i+;j<=n;j++)f[i][n+]-=f[i][j]*f[j][n+];

         f[i][n+]/=f[i][i];

     }

     for(int i=;i<=n;i++)printf("%.9lf\n",f[i][n+]*p/q);

     return ;

 }

高斯消元+概率dp

66.【bzoj1776】[Usaco2010 Hol]cowpol 奶牛政坛

 #include<cstdio>

 #include<algorithm>

 #include<cstring>

 #define LL long long

 using namespace std;

 const int N=2e5+;

 int n,k,rt,cnt,p;

 int a[N],first[N],deep[N],id[N],depth[N],ans[N],x[N][];

 struct edge{int to,next;}e[N];

 int read()

 {

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

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

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

     return x*f;

 }

 void ins(int u,int v){e[++cnt]=(edge){v,first[u]};first[u]=cnt;}

 void dfs(int k)

 {

     for(int i=;(<<i)<=deep[k];i++)

         x[k][i]=x[x[k][i-]][i-];

     for(int i=first[k];i;i=e[i].next)

     {

         x[e[i].to][]=k;

         deep[e[i].to]=deep[k]+;

         dfs(e[i].to);

     }

 }

 int lca(int ri,int rj)

 {

     if(deep[ri]<deep[rj])swap(ri,rj);

     int d=deep[ri]-deep[rj];

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

         if((<<i)&d)ri=x[ri][i];

     if(ri==rj)return ri;

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

         if((<<i)<=deep[rj]&&x[ri][i]!=x[rj][i])

             ri=x[ri][i],rj=x[rj][i];

     return x[ri][];

 }

 int main()

 {

     n=read();k=read();

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

     {

         a[i]=read();p=read();

         if(!p)rt=i;else ins(p,i);

     }

     deep[rt]=;dfs(rt);

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

         if(deep[i]>depth[a[i]])id[a[i]]=i,depth[a[i]]=deep[i];

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

     {

         if(i==id[a[i]])continue;

         int lc=lca(i,id[a[i]]);

         ans[a[i]]=max(ans[a[i]],deep[i]+deep[id[a[i]]]-*deep[lc]);

     }

     for(int i=;i<=k;i++)printf("%d\n",ans[i]);

     return ;

 }

LCA

67.【bzoj1731】[Usaco2005 dec]Layout 排队布局

 #include<cstdio>

 #include<algorithm>

 #include<cstring>

 #define LL long long

 using namespace std;

 const int N=;

 const int M=3e4+;

 const int inf=-;

 int n,ml,md,a,b,w,cnt;

 int first[N],dis[N];

 bool f,vis[N];

 struct edge{int to,next,w;}e[M];

 int read()

 {

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

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

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

     return x*f;

 }

 void ins(int u,int v,int w){e[++cnt]=(edge){v,first[u],w};first[u]=cnt;}

 void dfs(int x)

 {

     vis[x]=true;

     for(int i=first[x];i&&!f;i=e[i].next)

     {

         int to=e[i].to;

         if(dis[to]<dis[x]+e[i].w)

         {

             dis[to]=dis[x]+e[i].w;

             if(vis[to]){f=;return;}

             else dfs(to);

         }

     }

     vis[x]=false;

 }

 int main()

 {

     n=read();ml=read();md=read();

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

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

     {

         a=read();b=read();w=read();

         if(a>b)swap(a,b);ins(b,a,-w);

     }

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

     {

         a=read();b=read();w=read();

         if(a>b)swap(a,b);ins(a,b,w);

     }

     memset(dis,,sizeof(dis));

     dis[n]=;dfs(n);

     if(f)printf("-1");

     else if(dis[]==inf)printf("-2");

     else printf("%d",-dis[]);

     return ;

 }

差分约束

68.【bzoj1755】[Usaco2005 qua]Bank Interest

 #include<cstdio>

 #include<algorithm>

 #include<cstring>

 #define LL long long

 using namespace std;

 int r,m,y;

 double p,ans;

 int read()

 {

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

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

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

     return x*f;

 }

 int main()

 {

     r=read();m=read();y=read();

     p=+1.0*r/;ans=m;

     for(int i=;i<=y;i++)ans=ans*p;

     printf("%lld",(LL)ans);

     return ;

 }

模拟

69.【bzoj1705】[Usaco2007 Nov]Telephone Wire 架设电话线

 #include<cstdio>

 #include<algorithm>

 #include<cstring>

 #define LL long long

 using namespace std;

 const int inf=0x3f3f3f3f;

 const int N=1e5+;

 const int M=;

 int n,c,a[N],f[M],up[M],dn[M];

 int read()

 {

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

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

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

     return x*f;

 }

 int main()

 {

     n=read();c=read();

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

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

         if(i<a[])f[i]=inf;

         else f[i]=(i-a[])*(i-a[]);

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

     {

         int t=inf;

         for(int j=;j;j--)up[j]=t=min(t,f[j]+j*c);

         t=inf;

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

         {

             dn[j]=t=min(t,f[j]-j*c);

             f[j]=inf;

         }

         for(int j=a[i];j<=;j++)

             f[j]=min(dn[j]+j*c,up[j]-j*c)+(j-a[i])*(j-a[i]);

     }

     int ans=inf;

     for(int i=;i<=;i++)ans=min(ans,f[i]);

     printf("%d",ans);

     return ;

 }

奇怪のdp

70.【bzoj2200】[Usaco2011 Jan]道路和航线

 #include<cstdio>

 #include<algorithm>

 #include<cstring>

 #include<queue>

 #define LL long long

 using namespace std;

 const int inf=0x3f3f3f3f;

 const int N=;

 const int M=;

 int n,mr,mp,S,cnt,tot,u,v,w,C,head,tail;

 int first[N],FIRST[N],id[N],color[N],dis[N],ind[N],Q[N];

 bool vis[N],f[N],mark[M];

 struct edge{int to,next,w;}e[M];

 struct path{int from,to,next,w;}E[M];

 struct node{int d,id;bool operator < (const node& a)const{return a.d<d;}};

 priority_queue<node>q[N];

 int read()

 {

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

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

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

     return x*f;

 }

 void ins(int u,int v,int w){e[++cnt]=(edge){v,first[u],w};first[u]=cnt;}

 void INS(int u,int v,int w){E[++tot]=(path){u,v,FIRST[u],w};FIRST[u]=tot;}

 void dfs(int x)

 {

     color[x]=C;

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

         if(!color[e[i].to])dfs(e[i].to);

 }

 void search(int x)

 {

     vis[x]=f[color[x]]=true;

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

         if(!vis[e[i].to])search(e[i].to);

 }

 void find(int x)

 {

     vis[x]=true;

     for(int i=FIRST[x];i;i=E[i].next)

     {

         int to=E[i].to,now=color[to];

         dis[to]=min(dis[to],dis[x]+E[i].w);

 //      printf("to:%d dis:%d\n",to,dis[to]);

         q[now].push((node){dis[to],to});

         ind[now]--;if(!ind[now])Q[tail++]=now;

     }

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

         if(!mark[i]&&!vis[e[i].to])find(e[i].to);

 }

 int main()

 {

     n=read();mr=read();mp=read();S=read();

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

         u=read(),v=read(),w=read(),ins(u,v,w),ins(v,u,w);

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

         if(!color[i])id[++C]=i,dfs(i);

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

     {

         u=read(),v=read(),w=read();

         ins(u,v,w),mark[cnt]=true;INS(u,v,w);

     }

     search(S);

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

         if(f[color[E[i].from]]&&f[color[E[i].to]])ind[color[E[i].to]]++;

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

     dis[S]=;memset(vis,,sizeof(vis));

     Q[tail++]=color[S];q[color[S]].push((node){,S});

     while(head!=tail)

     {

         int x=Q[head++];

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

         {

             node t=q[x].top();u=t.id;q[x].pop();

             if(dis[t.id]!=t.d)continue;

 //          printf("u:%d\n",u);

             for(int i=first[u];i;i=e[i].next)

                 if(!mark[i]&&dis[e[i].to]>dis[u]+e[i].w)

                     dis[e[i].to]=dis[u]+e[i].w,q[x].push((node){dis[e[i].to],e[i].to});

         }

         find(id[x]);

     }

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

         if(dis[i]>=inf)printf("NO PATH\n");

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

     return ;

 }

dijkstra+拓扑排序

71.【bzoj1575】[Usaco2009 Jan]气象牛Baric

 #include<cstdio>

 #include<algorithm>

 #include<cstring>

 #define LL long long

 using namespace std;

 const int N=;

 const int inf=0x3f3f3f3f;

 int n,e,a[N],w[N][N],f[N][N];

 int read()

 {

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

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

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

     return x*f;

 }

 int abs(int a){return a>?a:-a;}

 int main()

 {

     n=read();e=read();

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

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

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

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

             {

                 if(i==)w[i][j]+=*abs(a[j]-a[k]);

                 else if(j==n+)w[i][j]+=*abs(a[k]-a[i]);

                 else w[i][j]+=abs(*a[k]-a[i]-a[j]);

             }

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

     f[][]=;w[][n+]=inf;

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

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

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

                 if(k>=j-)f[i][j]=min(f[i][j],f[k][j-]+w[k][i]);

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

         if(f[n+][i]<=e)

         {printf("%d %d\n",i-,f[n+][i]);break;}

     return ;

 }

普通dp

72.【bzoj1774】[Usaco2009 Dec]Toll 过路费

 #include<cstdio>

 #include<algorithm>

 #include<cstring>

 #define LL long long

 using namespace std;

 const int N=;

 const int inf=0x3f3f3f3f;

 int n,m,q,x,y,w,s,t,c[N],f[N][N],g[N][N];

 struct node{int c,id;}a[N];

 int read()

 {

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

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

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

     return x*f;

 }

 bool cmp(node a,node b){return a.c<b.c;}

 int main()

 {

     n=read();m=read();q=read();

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

         c[i]=a[i].c=read(),a[i].id=i;

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

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

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

             if(i!=j)f[i][j]=f[j][i]=g[i][j]=g[j][i]=inf;

             else g[i][j]=c[i];

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

         x=read(),y=read(),w=read(),f[x][y]=f[y][x]=min(f[x][y],w);

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

     {

         int k=a[now].id;

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

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

             {

                 f[i][j]=f[j][i]=min(f[i][j],f[i][k]+f[k][j]);

                 g[i][j]=g[j][i]=min(g[i][j],f[i][j]+max(a[now].c,max(c[i],c[j])));

             }

     }

     while(q--)

     {

         s=read();t=read();

         printf("%d\n",g[s][t]);

     }

     return ;

 }

奇怪のFloyd

73.【bzoj1914】[Usaco2010 OPen]Triangle Counting 数三角形

 #include<cstdio>

 #include<algorithm>

 #include<cstring>

 #define LL long long

 using namespace std;

 const int N=1e5+;

 const int inf=0x3f3f3f3f;

 int n,x,y;

 LL ans,now,to;

 struct node{int x,y,id;double t;}a[N];

 int read()

 {

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

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

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

     return x*f;

 }

 bool cmp(node a,node b){return a.id==b.id?a.t>b.t:a.id<b.id;}

 int main()

 {

     n=read();

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

     {

         a[i].x=x=read();a[i].y=y=read();

         if(x)a[i].t=1.0*y/x;

         else a[i].t=-inf;

         if(x>&&y>=)a[i].id=;

         else if(x>=&&y<)a[i].id=;

         else if(x<&&y<=)a[i].id=;

         else a[i].id=;

     }

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

     ans=1ll*n*(n-)*(n-)/;now=;to=;

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

     {

         now--;

         while(1ll*a[i].x*a[to].y<1ll*a[to].x*a[i].y)

         {

             now++;to++;

             if(to>n)to-=n;

         }

         ans-=now*(now-)/;

 //      printf("%.3lf %lld %lld %lld\n",a[i].t,now,to,ans);

     }

     printf("%lld",ans);

     return ;

 }

计算几何

74.【bzoj1577】[Usaco2009 Feb]庙会捷运Fair Shuttle

 #include<cstdio>

 #include<cstring>

 #include<algorithm>

 #include<queue>

 using namespace std;

 const int N=8e4+;

 int n,m,st,ed,num,c,cnt,now,ans,first[N];

 bool f[N];

 struct edge{int ed,num,next;}e[N];

 struct node1

 {

     int id,ed,num;

     bool operator <(const node1&x)const{return x.ed<ed;}

 };

 priority_queue<node1>q1;

 struct node2

 {

     int id,ed,num;

     bool operator <(const node2&x)const{return x.ed>ed;}

 };

 priority_queue<node2>q2;

 int read()

 {

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

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

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

     return x*f;

 }

 void ins(int u,int v,int w){e[++cnt]=(edge){v,w,first[u]};first[u]=cnt;}

 void push(int id,int ed,int num){q1.push((node1){id,ed,num});q2.push((node2){id,ed,num});}

 int main()

 {

     m=read();n=read();c=read();

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

         st=read(),ed=read(),num=read(),ins(st,ed,num);

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

     {

         while(!q1.empty())

         {

             node1 t=q1.top();

             if(t.ed>i)break;

             if(!f[t.id]){q1.pop();continue;}

             now-=t.num;ans+=t.num;

             f[t.id]=false;q1.pop();

         }

         for(int j=first[i];j;j=e[j].next)

         {

             f[j]=true;now+=e[j].num;

             push(j,e[j].ed,e[j].num);

         }

         while(now>c)

         {

             node2 t=q2.top();

             if(!f[t.id]){q2.pop();continue;}

             if(t.num>now-c)

             {

                 q2.pop();f[t.id]=false;

                 t.num-=now-c;now=c;

                 push(++cnt,t.ed,t.num);

                 f[cnt]=true;break;

             }

             q2.pop();f[t.id]=false;now-=t.num;

         }

     }

     printf("%d",ans);

     return ;

 }

堆+贪心

75.【bzoj3940】[Usaco2015 Feb]Censoring

不会AC自动机…… 留坑待填QAQ（已经懒得填了）

76.【bzoj1783】[Usaco2010 Jan]Taking Turns

 #include<cstdio>

 #include<cstring>

 #include<algorithm>

 #include<queue>

 #define LL long long

 using namespace std;

 const int N=7e5+;

 int n,a[N];

 LL f[][N];

 int read()

 {

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

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

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

     return x*f;

 }

 int main()

 {

     n=read();

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

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

     {

         f[][i]=f[][i+];

         f[][i]=f[][i+];

         if(f[][i]+a[i]>=f[][i])

         {

             f[][i]=f[][i]+a[i];

             f[][i]=f[][i+];

         }

     }

     printf("%lld %lld",f[][],f[][]);

     return ;

 }

博弈论

77.【bzoj1590】[Usaco2008 Dec]Secret Message 秘密信息

 #include<cstdio>

 #include<cstring>

 #include<algorithm>

 #include<queue>

 #define LL long long

 using namespace std;

 const int N=5e5+;

 int n,m,len,cnt,ans;

 int a[N],c[N][],w[N],sum[N];

 int read()

 {

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

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

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

     return x*f;

 }

 void ins(int now,int p)

 {

     if(p>len){sum[now]++;w[now]++;return;}

     if(!c[now][a[p]])c[now][a[p]]=++cnt;

     ins(c[now][a[p]],p+);

     sum[now]=w[now];

     if(c[now][])sum[now]+=sum[c[now][]];

     if(c[now][])sum[now]+=sum[c[now][]];

 }

 void dfs(int now,int p)

 {

     if(p>len){ans+=sum[now];return;}

     if(now)ans+=w[now];

     if(!c[now][a[p]])return;

     dfs(c[now][a[p]],p+);

 }

 int main()

 {

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

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

     {

         len=read();

         for(int j=;j<=len;j++)a[j]=read();

         ins(,);

     }

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

     {

         len=read();ans=;

         for(int j=;j<=len;j++)a[j]=read();

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

     }

     return ;

 }

trie

78.【bzoj2097】[Usaco2010 Dec]Exercise 奶牛健美操

 #include<cstdio>

 #include<algorithm>

 #include<cstring>

 #define LL long long

 using namespace std;

 const int N=1e5+;

 int n,m,u,v,cnt,l,r,mid,ans,sum,tot;

 int s[N],first[N],f[N];

 struct edge{int to,next;}e[N<<];

 int read()

 {

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

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

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

     return x*f;

 }

 void ins(int u,int v){e[++cnt]=(edge){v,first[u]};first[u]=cnt;}

 void dfs(int x,int fa)

 {

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

         if(e[i].to!=fa)dfs(e[i].to,x);

     f[x]=;tot=;

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

         if(e[i].to!=fa)s[++tot]=f[e[i].to];

     sort(s+,s+tot+);

     for(int i=tot;i;i--)

         if(s[i]+s[i-]>mid)sum++;

         else{f[x]+=s[i];break;}

 }

 int main()

 {

     n=read();m=read();l=;r=n;

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

         u=read(),v=read(),ins(u,v),ins(v,u);

     while(l<=r)

     {

         mid=(l+r)>>;

         sum=;dfs(,);

         if(sum<=m)ans=mid,r=mid-;

         else l=mid+;

     }

     printf("%d",ans);

     return ;

 }

二分+贪心

79.【bzoj1663】[Usaco2006 Open]赶集

 #include<cstdio>

 #include<algorithm>

 #include<cstring>

 #define LL long long

 using namespace std;

 const int N=4e2+;

 int n,ans,f[N],map[N][N];

 struct node{int t,id;}a[N];

 int read()

 {

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

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

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

     return x*f;

 }

 bool cmp(node a,node b){return a.t<b.t;}

 int main()

 {

     n=read();

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

         a[i].t=read(),a[i].id=i;

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

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

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

             map[i][j]=read();

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

     {

         if(map[][a[i].id]<=a[i].t)f[i]=;

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

             if(a[j].t+map[a[j].id][a[i].id]<=a[i].t&&f[j]+>f[i])

                 f[i]=f[j]+;

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

     }

     printf("%d",ans);

     return ;

 }

普通dp

80.【bzoj1696】[Usaco2007 Feb]Building A New Barn新牛舍

 #include<cstdio>

 #include<algorithm>

 #include<cstring>

 #define LL long long

 using namespace std;

 const int N=1e4+;

 const int inf=0x3f3f3f3f;

 const int xx[]={,,-,};

 const int yy[]={-,,,};

 int n,ans=inf,tmp,num,x[N],y[N];

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

 int read()

 {

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

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

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

     return x*f;

 }

 int ab(int a){return a>?a:-a;}

 bool check(int x,int y)

 {

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

         if(a[i].x==x&&a[i].y==y)return false;

     return true;

 }

 int work(int x,int y)

 {

     int sum=;

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

         sum+=ab(x-a[i].x)+ab(y-a[i].y);

     return sum;

 }

 int main()

 {

     n=read();

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

     {

         a[i].x=x[i]=read();

         a[i].y=y[i]=read();

     }

     sort(x+,x+n+);sort(y+,y+n+);

     if(n&)

     {

         int X=x[(n>>)+],Y=y[(n>>)+];

         if(check(X,Y))printf("%d 1",work(X,Y));

         else

         {

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

             {

                 tmp=work(X+xx[i],Y+yy[i]);

                 if(tmp<ans)ans=tmp,num=;

                 else if(tmp==ans)num++;

             }

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

         }

     }

     else

     {

         int X1=x[n>>],Y1=y[n>>],X2=x[(n>>)+],Y2=y[(n>>)+];

         num=(X2-X1+)*(Y2-Y1+);

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

             if(a[i].x>=X1&&a[i].x<=X2&&a[i].y>=Y1&&a[i].y<=Y2)num--;

         printf("%d %d",work(X1,Y1),num);

     }

     return ;

 }

中位数+乱搞

81.【bzoj1594】[Usaco2008 Jan]猜数游戏

 #include<cstdio>

 #include<cstring>

 #include<algorithm>

 #define LL long long

 using namespace std;

 const int N=1e6+;

 int n,m,l,r,ans=,mid,f[N];

 struct node{int l,r,w;}a[N],b[N];

 int read()

 {

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

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

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

     return x*f;

 }

 bool cmp(node a,node b){return a.w>b.w;}

 int find(int t){return f[t]==t?t:f[t]=find(f[t]);}

 bool check(int x)

 {

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

     for(int i=;i<=x;i++)b[i]=a[i];

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

     int l1=b[].l,l2=b[].l,r1=b[].r,r2=b[].r;

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

     {

         if(b[i].w<b[i-].w)

         {

             if(find(l1)>r1)return false;

             for(int j=f[l2];j<=r2;j=f[j])

                 find(j),f[j]=find(j+);

             l1=l2=b[i].l;r1=r2=b[i].r;

         }

         else

         {

             l1=max(l1,b[i].l);l2=min(l2,b[i].l);

             r1=min(r1,b[i].r);r2=max(r2,b[i].r);

             if(r1<l1)return false;

         }

     }

     if(find(l1)>r1)return false;

     return true;

 }

 int main()

 {

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

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

         a[i].l=read(),a[i].r=read(),a[i].w=read();

     l=;r=m+;

     while(l<=r)

     {

         mid=(l+r)>>;

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

         else r=mid-;

     }

     printf("%d",ans>=m?:ans+);

     return ;

 }

二分+并查集

82.【bzoj1583】[Usaco2009 Mar]Moon Mooing 哞哞叫

 #include<cstdio>

 #include<cstring>

 #include<algorithm>

 #define LL long long

 using namespace std;

 const int N=4e6+;

 LL c,n,a1,b1,c1,a2,b2,c2,n1,n2,cnt,l,r,q[N];

 int main()

 {

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

     scanf("%lld%lld%lld",&a1,&b1,&c1);

     scanf("%lld%lld%lld",&a2,&b2,&c2);

     q[++cnt]=c;l=r=;n1=a1*c/c1+b1;n2=a2*c/c2+b2;

     while(cnt<n)

     {

         if(n1<n2)

         {

             if(n1!=q[cnt])q[++cnt]=n1;

             n1=q[++l]*a1/c1+b1;

         }

         else

         {

             if(n2!=q[cnt])q[++cnt]=n2;

             n2=q[++r]*a2/c2+b2;

         }

     }

     printf("%lld",q[n]);

     return ;

 }

模拟

83.【bzoj1742】[Usaco2005 nov]Grazing on the Run 边跑边吃草

 #include<cstdio>

 #include<cstring>

 #include<algorithm>

 #define LL long long

 using namespace std;

 const int N=1e3+;

 int n,p,pos[N],fl[N][N],fr[N][N];

 int read()

 {

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

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

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

     return x*f;

 }

 int ab(int a){return a>?a:-a;}

 int main()

 {

     n=read();p=read();

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

     sort(pos+,pos+n+);

     for(int i=;i<=n;i++)fl[i][i]=fr[i][i]=n*ab(pos[i]-p);

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

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

         {

             int j=i+num-,now=n-j+i;

             fl[i][j]=min(fl[i+][j]+now*(pos[i+]-pos[i]),fr[i+][j]+now*(pos[j]-pos[i]));

             fr[i][j]=min(fl[i][j-]+now*(pos[j]-pos[i]),fr[i][j-]+now*(pos[j]-pos[j-]));

         }

     printf("%d",min(fl[][n],fr[][n]));

     return ;

 }

未来dp

84.【bzoj1751】[Usaco2005 qua]Lake Counting

 #include<cstdio>

 #include<cstring>

 #include<algorithm>

 #define LL long long

 using namespace std;

 const int N=1e2+;

 const int xx[]={-,,,-,,-,,};

 const int yy[]={-,-,-,,,,,};

 int n,m,ans,X,Y;

 bool map[N][N],f[N][N];

 char s[N];

 int read()

 {

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

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

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

     return x*f;

 }

 void dfs(int x,int y)

 {

     f[x][y]=true;

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

     {

         X=x+xx[i];Y=y+yy[i];

         if(X<||X>n||Y<||Y>m)continue;

         if(map[X][Y]&&!f[X][Y])dfs(X,Y);

     }

 }

 int main()

 {

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

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

     {

         scanf("%s",s+);

         for(int j=;j<=m;j++)if(s[j]=='W')map[i][j]=true;

     }

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

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

         {

             if(!map[i][j]||f[i][j])continue;

             ans++;dfs(i,j);

         }

     printf("%d",ans);

     return ;

 }

dfs

85.【bzoj1775】[Usaco2009 Dec]Vidgame 电视游戏问题

 #include<cstdio>

 #include<cstring>

 #include<algorithm>

 #define LL long long

 using namespace std;

 const int N=;

 const int M=1e5+;

 int n,m,P,G,w,v,f[N][M],g[N][M];

 int read()

 {

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

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

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

     return x*f;

 }

 int main()

 {

     memset(f,,sizeof(f));

     memset(g,,sizeof(g));

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

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

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

     {

         P=read();G=read();

         for(int j=;j<=m;j++)f[i][j]=max(f[i-][j],g[i-][j]);

         for(int j=P;j<=m;j++)g[i][j]=max(f[i-][j-P],g[i-][j-P]);

         while(G--)

         {

             w=read();v=read();

             for(int j=m;j>=w;j--)g[i][j]=max(g[i][j],g[i][j-w]+v);

         }

     }

     printf("%d\n",max(f[n][m],g[n][m]));

     return ;

 }

普通dp

码农公寓

相关文章