1666: [Usaco2006 Oct]Another Cow Number Game 奶牛的数字游戏

模拟

1 #include 
      
        2 inline int read() 3 { 4     register int f=1,c=getchar(),k=0; 5     while (c<'0'||c>'9')c=='-'&&(f=-1),c=getchar(); 6     while (c>='0'&&c<='9')k=k*10+c-'0',c=getchar(); 7     return k*f; 8 } 9 int n,ans;10 int main()11 {12     n=read();13     while (n!=1)14         if (n&1)n=n*3+1,ans++;else n=n>>1,ans++;15     printf("%d\n",ans);16 }
      

1576: [Usaco2009 Jan]安全路经Travel

1 #include 
      
         2 #include 
       
          3 #include 
        
           4 inline void swap(int &a,int &b)  5 {  6     register int tmp=b;  7     b=a;a=tmp;  8 }  9 inline int read() 10 { 11     register int k=0,c=getchar(),f=1; 12     while (c<'0'||c>'9')c=='-'&&(f=-1),c=getchar(); 13     while (c>='0'&&c<='9')k=k*10+c-'0',c=getchar(); 14     return k*f; 15 } 16 const int maxn=500000+100,inf=1<<30; 17 struct edg{ 18     int x,too,del,nxt; 19 }edge[maxn]; 20 struct qaq{ 21     int dis,pos; 22 }; 23 struct mc{ 24     int a,b,len; 25 }e[maxn]; 26 bool v[maxn],used[maxn]; 27 int vis[maxn]; 28 int n,m,tot,tot2,a,b,c,dist[maxn],last[maxn],h[maxn]; 29 int fq[maxn],eg[maxn],fa[maxn]; 30 std::priority_queue
         
          q; 31 bool operator<(qaq a,qaq b){
    return a.dis>b.dis;} 32 inline void add(int a,int b,int c) 33 { 34     edge[++tot].nxt=last[a]; 35     last[a]=tot; 36     edge[tot].too=b; 37     edge[tot].x=a; 38     edge[tot].del=c; 39 } 40 inline bool cmp(mc a,mc b) 41 { 42     return a.len
          
           edge[i].del+dist[now]) 58             { 59                 dist[edge[i].too]=dist[now]+edge[i].del; 60                 fq[edge[i].too]=now; 61                 eg[edge[i].too]=i; 62                 if (!v[edge[i].too]) 63                 { 64                     v[edge[i].too]=1; 65                     q.push((qaq){dist[edge[i].too],edge[i].too}); 66                 } 67             } 68         } 69         v[now]=0; 70     } 71 } 72 int main() 73 { 74     tot=1; 75     n=read();m=read(); 76     for (register int i=1;i<=n;i++)fa[i]=i; 77     for (register int i=1;i<=m;i++)a=read(),b=read(),c=read(),add(a,b,c),add(b,a,c); 78     spfa(); 79     for (register int i=1;i<=n;i++)used[eg[i]]=used[eg[i]^1]=1; 80     for (register int i=1;i<=tot;i++) 81     if (!used[i]) 82     { 83         e[++tot2].a=edge[i].x;e[tot2].b=edge[i].too; 84         e[tot2].len=edge[i].del+dist[edge[i].x]+dist[edge[i].too]; 85     } 86     std::sort(e+1,e+tot2+1,cmp); 87     for(register int i=1;i<=tot2;i++) 88     { 89         register int a=e[i].a,b=e[i].b,f1=gf(a),f2=gf(b),lasta=0,lastb=0; 90         while (f1!=f2) 91         { 92             if (dist[a]
          
         
        
       
      

1708: [Usaco2007 Oct]Money奶牛的硬币

完全背包

#include 
      
       #define ll long long inline int read(){    register int c=getchar(),k=0,f=1;    while (c<'0'||c>'9')c=='-'&&(f=-1),c=getchar();    while (c>='0'&&c<='9')k=k*10+c-'0',c=getchar();    return k*f; } const int maxn=10000+10;ll f[maxn];int n,v,cur;int main(){    v=read();n=read();    f[0]=1;    for (register int i=1;i<=v;i++)    {        cur=read();        for (register int j=cur;j<=n;j++)        f[j]+=f[j-cur];    }    printf("%lld\n",f[n]);}
      

1699: [Usaco2007 Jan]Balanced Lineup排队

裸RMQ

1 #include 
      
        2 #include 
       
         3 #include 
        
          4 using namespace std; 5 inline int read() 6 { 7     register int c=getchar(),f=1,k=0; 8     while (c<'0'||c>'9')c=='-'&&(f=-1),c=getchar(); 9     while (c>='0'&&c<='9')k=k*10+c-'0',c=getchar();10     return k*f;11 } 12 inline int max(int a,int b)13 {14     return a>b?a:b;15 }16 inline int min(int a,int b)17 {18     return a
        
       
      

1715: [Usaco2006 Dec]Wormholes 虫洞

SPFA判负环

1 #include 
      
        2 #include 
       
         3 inline int read() 4 { 5     register int f=1,c=getchar(),k=0; 6     while(c<'0'||c>'9')c=='-'&&(f=-1),c=getchar(); 7     while(c>='0'&&c<='9')k=k*10+c-'0',c=getchar(); 8     return k*f; 9 }10 const int maxn=6300*2,inf=1<<30;11 bool vis[maxn];12 int m,n,a,b,c,tot,w,last[maxn],to[maxn],nxt[maxn],del[maxn],dist[maxn],q[maxn],cnt[maxn];13 bool spfa(int s)14 {15     memset(cnt,0,sizeof(cnt));16     memset(vis,0,sizeof(vis));17     for (register int i=1;i<=n;i++)18     dist[i]=inf;19     register int front=1,rear=1;20     dist[s]=0;21     q[1]=s;22     vis[s]=1;23     while(front<=rear)24     {25         cnt[q[front]]++;26         if (cnt[q[front]]>n)return 0;27         for (register int i=last[q[front]];i;i=nxt[i])28         if (dist[q[front]]+del[i]
       
      

1753: [Usaco2005 qua]Who's in the Middle

裸sort

1 #include 
      
        2 #include 
       
         3 inline int read() 4 { 5     register int f=1,c=getchar(),k=0; 6     while (c<'0'||c>'9')c=='-'&&(f=-1),c=getchar(); 7     while (c>='0'&&c<='9')k=k*10+c-'0',c=getchar(); 8     return k*=f; 9 }10 const int maxn=1e4+1;11 int n,a[maxn];12 int main()13 {14     n=read();15     for (register int i=1;i<=n;i++)16     a[i]=read();17     std::sort(a+1,a+1+n);18     printf("%d\n",a[n/2+1]);19 }
       
      

1755: [Usaco2005 qua]Bank Interest

模拟

1 #include 
      
        2 inline int read() 3 { 4     register int f=1,c=getchar(),k=0; 5     while (c<'0'||c>'9')c=='-'&&(f=-1),c=getchar(); 6     while (c>='0'&&c<='9')k=k*10+c-'0',c=getchar(); 7     return k*f; 8 } 9 int main()10 {11     register int r,y;12     register double tmp,tmp1;13     r=read();tmp=read();y=read();14     tmp1=(double)r/100;15     while(y--)16     tmp*=1+tmp1;17     printf("%d\n",(int)tmp);18 }
      

3408: [Usaco2009 Oct]Heat Wave 热浪

SPFA

卡不动了QAQ

1 #include 
      
        2 inline void read(int &k) 3 { 4     register int f=1,c=getchar();k=0; 5     while(c<'0'||c>'9')c=='-'&&(f=-1),c=getchar(); 6     while(c>='0'&&c<='9')k=k*10+c-'0',c=getchar(); 7     k*=f; 8 } 9 const int maxn=6300*2;10 int m,n,a,b,c,tot,s,t,last[maxn],to[maxn],nxt[maxn],del[maxn],dist[maxn],q[maxn];11 int main()12 {13     read(n);read(m);read(s);read(t);14     for (register int i=1;i<=m;i++)15     {16         read(a);read(b);read(c);17         nxt[++tot]=last[a];18         last[a]=tot;19         to[tot]=b;20         del[tot]=c;21         nxt[++tot]=last[b];22         last[b]=tot;23         to[tot]=a;24         del[tot]=c;25     }26     for (register int i=1;i<=n;i++)27     dist[i]=1<<30;28     register int front=1,rear=1;29     dist[s]=0;30     q[1]=s;31     while(front<=rear)32     {33         for (register int i=last[q[front]];i;i=nxt[i])34         if (dist[q[front]]+del[i]
      

1724: [Usaco2006 Nov]Fence Repair 切割木板

堆（同合并果子）

1 #include 
      
        2 #include 
       
         3 #define ll long long  4 std::priority_queue
        
         
          ,std::greater
          
            >q; 5 inline int read() 6 { 7     register int c=getchar(),f=1,k=0; 8     while (c<'0'||c>'9')c=='-'&&(f=-1),c=getchar(); 9     while (c>='0'&&c<='9')k=k*10+c-'0',c=getchar();10     return k*f;11 }12 const int maxn=20100;13 long long n,a,ans; 14 int main()15 {16     n=read();17     register int a,b;18     for (register int i=1;i<=n;i++)19     a=read(),q.push(a);20     for (register int i=1;i
          
         
        
       
      

4094: [Usaco2013 Dec]Optimal Milking

线段树（维护4最值）

1 #include 
      
        2 #include 
       
         3 using namespace std; 4 #define ll long long  5 inline int max(int a,int b) 6 { 7     return a>b?a:b; 8 } 9 inline int read()10 {11     register int c=getchar(),f=1,k=0;12     while (c<'0'||c>'9')c=='-'&&(f=-1),c=getchar();13     while (c>='0'&&c<='9')k=k*10+c-'0',c=getchar();14     return k*f;15 }16 const int maxn=50000+100;17 struct node{18     int l,r,clr,cl,cr,cnone;19 }tree[maxn*8];20 ll ans;21 int f[maxn],m,d,n,a[maxn],x,y;22 inline void pushup(int x)23 {24 //    25     tree[x].clr=max(tree[x<<1].cl+tree[x<<1|1].cr,max(tree[x<<1].clr+tree[x<<1|1].cr,tree[x<<1].cl+tree[x<<1|1].clr));26     tree[x].cl=max(tree[x<<1].cl+tree[x<<1|1].cl,max(tree[x<<1].cl+tree[x<<1|1].cnone,tree[x<<1].clr+tree[x<<1|1].cnone));27     tree[x].cr=max(tree[x<<1].cr+tree[x<<1|1].cr,max(tree[x<<1].cnone+tree[x<<1|1].cr,tree[x<<1].cnone+tree[x<<1|1].clr));28     tree[x].cnone=max(tree[x<<1].cr+tree[x<<1|1].cnone,max(tree[x<<1].cnone+tree[x<<1|1].cl,tree[x<<1].cnone+tree[x<<1|1].cnone));29 30 }31 void build(int l,int r,int cur)32 {33     tree[cur].l=l;tree[cur].r=r;34     if (l==r)35     {36         tree[cur].clr=read();37         return;38     }39     register int mid=(l+r)>>1;40     build(l,mid,cur<<1);41     build(mid+1,r,cur<<1|1);42     pushup(cur);43 }44 void update(int x,int y,int cur)45 {46 //    cout << x<<" "<
        
         << " "<
         
          <
          
           >1;48     if (tree[cur].l==x&&tree[cur].r==x){tree[cur].clr=y;return;}else if (x<=mid)update(x,y,cur<<1);else update(x,y,cur<<1|1);49     pushup(cur);50 }51 int main()52 {53     n=read();d=read();54     build(1,n,1);55     for (register int i=1;i<=d;i++)56     {57         x=read(),y=read(),update(x,y,1);58         ans+=max(tree[1].clr,max(tree[1].cl,max(tree[1].cr,tree[1].cnone)));59     }60     printf("%lld\n",ans);61 }
          
         
        
       
      

3407: [Usaco2009 Oct]Bessie's Weight Problem 贝茜的体重问题

背包

1 #include 
      
        2 inline int max(int a,int b) 3 { 4     return a>b?a:b; 5 } 6 inline int read() 7 { 8     register int f=1,c=getchar(),k=0; 9     while (c<'0'||c>'9')c=='-'&&(f=-1),c=getchar();10     while (c>='0'&&c<='9')k=k*10+c-'0',c=getchar();11     return k*f;12 } 13 int d,f[45000*3],m;14 int main()15 {16     d=read();m=read();register int cur;17     for (register int i=1;i<=m;i++)18     {19         cur=read();20         for (register int j=d;j>=cur;j--)21         f[j]=max(f[j],f[j-cur]+cur);22     }23     printf("%d\n",f[d]);24 }
      

1012: [JSOI2008]最大数maxnumber

单标记线段树

1 #include 
      
        2 #define ll long long 3 inline int max(int a,int b) 4 { 5     return a>b?a:b; 6 } 7 inline int read() 8 { 9     register int f=1,c=getchar(),k=0;10     while (c<'0'||c>'9')c=='-'&&(f=-1),c=getchar();11     while (c>='0'&&c<='9')k=k*10+c-'0',c=getchar();12     return k*f;13 } 14 const int maxn=200010,inf=1<<30;15 struct node{16     int l,r,delta;17 }tree[maxn*16];18 int m,d,last,cu,tot;19 void build(int l,int r,int cur)20 {21     tree[cur].l=l;tree[cur].r=r;22     tree[cur].delta=-inf;23     if (l==r)return;24     register int mid=(l+r)>>1;25     build(l,mid,cur<<1);26     build(mid+1,r,cur<<1|1);27 }28 void update(int x,int c,int cur)29 {30     if (tree[cur].l==x&&tree[cur].r==x)31     {32         tree[cur].delta=c;33         return;34     }35     register int mid=(tree[cur].l+tree[cur].r)>>1;36     if (x<=mid)update(x,c,cur<<1);else update(x,c,cur<<1|1);37     tree[cur].delta=max(tree[cur<<1|1].delta,tree[cur<<1].delta);38 }39 int query(int l,int r,int cur)40 {41     if (l<=tree[cur].l&&tree[cur].r<=r)return tree[cur].delta;42     register int ans=-inf,mid=(tree[cur].l+tree[cur].r)>>1;43     if (l<=mid)ans=query(l,r,cur<<1);44     if (r>mid)ans=max(ans,query(l,r,cur<<1|1));45     return ans;46 }47 int main()48 {49     m=read();d=read();50     build(1,m,1);51     for(register int i=1;i<=m;i++)52         if (getchar()=='A')cu=read(),update(++tot,(last+cu)%d,1);53         else cu=read(),printf("%d\n",last=query(tot-cu+1,tot,1));54 }
      

1370: [Baltic2003]Gang团伙

并查集

(题意贼坑：敌人的朋友不是敌人！！！）（坑我WA了4次QAQ

1 #include 
      
        2 #include 
       
         3 inline int read() 4 { 5     register int f=1,c=getchar(),k=0; 6     while (c<'0'||c>'9')c=='-'&&(f=-1),c=getchar(); 7     while (c>='0'&&c<='9')k=k*10+c-'0',c=getchar(); 8     return k*f; 9 }10 const int maxn=5000*2+100;11 int fa[maxn],n,m,a,b,be[maxn];12 int gf(int now)13 {14     return fa[now]==now?now:fa[now]=gf(fa[now]);15 } 16 int main()17 {18     n=read();m=read();19     for (register int i=1;i<=(n<<1);i++)fa[i]=i;20     register int ans=0;21     for (register int i=1;i<=m;i++)22     {23         if (getchar()=='E')a=read(),b=read(),fa[gf(a)]=gf(b+n),fa[gf(b)]=gf(a+n);24         else a=read(),b=read(),fa[gf(a)]=gf(b);25     }26     for (register int i=1;i<=n;i++)27     be[i]=gf(i);28     std::sort(be+1,be+1+n);29     for (register int i=1;i<=n;i++)30     if (be[i]!=be[i-1])ans++;31     printf("%d\n",ans);32 }
       
      

1572: [Usaco2009 Open]工作安排Job

堆+sort

1726: [Usaco2006 Nov]Roadblocks第二短路

SPFA分类更新

1 #include 
      
        2 #include 
       
         3 #include 
        
          4 #define ll long long 5 using namespace std; 6 inline int min(int a,int b) 7 { 8     return a
         
          '9')c=='-'&&(f=-1),c=getchar();14     while (c>='0'&&c<='9')k=k*10+c-'0',c=getchar();15     return k*f;16 }17 const int maxn=101000*2,inf=1<<30;18 struct edge{19     int x,too,nxt,co;20 //    bool operator<(const edge&a)const{return this->co>a.co;}21 }e[maxn];22 int q[maxn];23 bool vis[maxn];24 int n,r,last[maxn],dist[maxn],dist2[maxn];25 //priority_queue
          
           q;26 inline void spfa()27 {28     dist[1]=0;29     register int h=0,t=1;30     q[1]=1;31     while (h!=t)32     {33         if (++h==maxn)h=0;34         register int now=q[h];35         vis[now]=1;36         for (register int i=last[now];i;i=e[i].nxt)37         {38             register bool flag=0;register int tmp=dist[now]+e[i].co;39             if (tmp
           
            dist[e[i].too]&&tmp
           
          
         
        
       
      

4511: [Usaco2016 Jan]Subsequences Summing to Sevens

桶

1 #include 
      
        2 #define ll long long 3 inline ll read() 4 { 5     register int f=1,k=0;register char c=getchar(); 6     while (c<'0'||c>'9')c=='-'&&(f=-1),c=getchar(); 7     while (c>='0'&&c<='9')k=k*10+c-'0',c=getchar(); 8     return k*f; 9 }10 inline ll max(ll a,ll b){
    return a>b?a:b;}11 const int maxn=50010;12 ll a[maxn],sum[maxn],t[10],ans;13 int main()14 {15     register int n=read();16     for (register int i=1;i<=n;i++)a[i]=read(),sum[i]=(sum[i-1]+a[i])%7;17     for (register int i=1;i<=n;i++)if (t[sum[i]])ans=max(i-t[sum[i]],ans);else t[sum[i]]=i;18     printf("%lld\n",ans);19 }