USACO 补完（TJ）计划
Posted On 2018年9月28日
5279: [Usaco2018 Open]Disruption
树剖模板题
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 |
#include <cstdio> #include <algorithm> typedef long long ll; using namespace std; const int maxn=50000+10; char s[maxn*20],*c; inline int read() { int f=1,k=0; while (*c<'0'||*c>'9')c++;//++=='-'&&(f=-1); while (*c>='0'&&*c<='9')k=k*10+*c++-'0'; return k*f; } struct mc{int too,nxt;}e[maxn<<1]; struct mic{int delta;}t[maxn<<3]; struct zmc{int a,b,c;}E[maxn]; int A[maxn],B[maxn]; int last[maxn],fa[maxn],siz[maxn],dep[maxn],heavy[maxn],top[maxn],pos[maxn],tot; inline bool cmp(const zmc&a,const zmc&b){return a.c<b.c;} inline int min(const int a,const int b){return a<b?a:b;} void dfs(const int cur) { siz[cur]=1; for (int i=last[cur];i;i=e[i].nxt) if (e[i].too!=fa[cur]) fa[e[i].too]=cur, dep[e[i].too]=dep[cur]+1, dfs(e[i].too), siz[cur]+=siz[e[i].too], siz[heavy[cur]]<siz[e[i].too]&&(heavy[cur]=e[i].too); } void _dfs(const int cur,const int ancestor) { top[cur]=ancestor;pos[cur]=++tot; if (heavy[cur])_dfs(heavy[cur],ancestor); for (int i=last[cur];i;i=e[i].nxt) if (e[i].too!=fa[cur]&&e[i].too!=heavy[cur]) _dfs(e[i].too,e[i].too); } inline void down(const int cur) { if (t[cur].delta) { if (!t[cur<<1].delta)t[cur<<1].delta=t[cur].delta; else t[cur<<1].delta=min(t[cur<<1].delta,t[cur].delta); if (!t[cur<<1|1].delta)t[cur<<1|1].delta=t[cur].delta; else t[cur<<1|1].delta=min(t[cur<<1|1].delta,t[cur].delta); } t[cur].delta=0; } void update(const int cur,const int l,const int r,const int L,const int R,const int v) { if (L<=l&&r<=R)return(void)(!t[cur].delta&&(t[cur].delta=v)); down(cur); int mid=(l+r)>>1; if (L<=mid)update(cur<<1,l,mid,L,R,v); if (R>mid)update(cur<<1|1,mid+1,r,L,R,v); } int query(const int cur,const int l,const int r,const int pos) { if (l==r)return t[cur].delta; down(cur); int mid=(l+r)>>1; if (pos<=mid)return query(cur<<1,l,mid,pos); else return query(cur<<1|1,mid+1,r,pos); } signed main() { fread(c=s,1,sizeof(s),stdin); int n=read(),m=read(); for (int i=1,a,b;i<n;i++) A[i]=a=read(),B[i]=b=read(), e[i<<1].too=b,e[i<<1].nxt=last[a],last[a]=i<<1, e[i<<1|1].nxt=last[b],e[i<<1|1].too=a,last[b]=i<<1|1; dfs(1); _dfs(1,1); for (int i=1;i<=m;i++)E[i]=(zmc){read(),read(),read()}; sort(E+1,E+1+m,cmp); for (int i=1;i<=m;i++) { int a=E[i].a,b=E[i].b,c=E[i].c; while (top[a]!=top[b]) { if (dep[top[a]]<dep[top[b]])swap(a,b); update(1,1,n,pos[top[a]],pos[a],c); a=fa[top[a]]; } if (dep[a]>dep[b])swap(a,b); if (pos[a]+1<=pos[b]) update(1,1,n,pos[a]+1,pos[b],c); } for (int i=1,x;i<n;i++) x=query(1,1,n,max(pos[A[i]],pos[B[i]])),printf("%d\n",x?x:-1); } |
1722: [Usaco2006 Mar] Milk Team Select 产奶比赛
树形DP
令\(f[i][j][0/1]\)表示到第\(i\)个点有\(j\)对母子关系，取/不取
sb题调了半天TAT
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 |
#include <cstdio> #include <cstring> #include <vector> #include <cmath> #include <bitset> #include <set> #include <iostream> typedef long long ll; using namespace std; inline int read() { int f=1,k=0;char c=getchar(); 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=507; int n; int f[maxn][maxn][2],val[maxn]; int last[maxn]; struct mc{int too,nxt;}e[maxn]; inline int max(const int a,const int b){return a>b?a:b;} void dfs(const int cur) { f[cur][0][1]=val[cur];f[cur][0][0]=0; for (int i=last[cur];i;i=e[i].nxt) { dfs(e[i].too); for (int j=n-1;~j;j--) for (int k=0;k<=j;k++) { if (k-1>=0)f[cur][j][1]=max(f[cur][j][1],f[cur][j-k][1]+f[e[i].too][k-1][1]); f[cur][j][1]=max(f[cur][j][1],f[cur][j-k][1]+f[e[i].too][k][0]); f[cur][j][0]=max(f[cur][j][0],f[cur][j-k][0]+max(f[e[i].too][k][1],f[e[i].too][k][0])); } } } signed main() { memset(f,-23,sizeof(f)); n=read();int x=read(); for (int i=1;i<=n;i++) { val[i]=read(); int papa=read(); e[i].nxt=last[papa],last[papa]=i,e[i].too=i; } dfs(0); for (int i=n;~i;i--)if (f[0][i][0]>=x)return printf("%d\n",i),0; puts("-1"); } |
1828: [Usaco2010 Mar]balloc 农场分配
线段树维护贪心
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 |
#include <cstdio> #include <cstring> #include <algorithm> #include <cmath> #include <iostream> #include <cstdlib> using namespace std; typedef long long ll; inline int read() { int f=1,k=0;char c=getchar(); 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=1e5+100; struct mc{int l,r;}store[maxn]; inline bool cmp(const mc&a,const mc&b){return a.r<b.r||(a.r==b.r&&a.l>b.l);} int a[maxn]; struct zmc{int mn,delta;}t[maxn<<3]; inline void up(const int cur) { t[cur].mn=min(t[cur<<1].mn+t[cur<<1].delta,t[cur<<1|1].mn+t[cur<<1|1].delta); } inline void down(const int cur) { t[cur].mn+=t[cur].delta; t[cur<<1].delta+=t[cur].delta; t[cur<<1|1].delta+=t[cur].delta; t[cur].delta=0; } int query(const int l,const int r,const int L,const int R,const int cur) { if (L<=l&&r<=R)return t[cur].mn+t[cur].delta; down(cur); int mid=(l+r)>>1,ans=1e9; if (L<=mid)ans=query(l,mid,L,R,cur<<1); if (R>mid)ans=min(ans,query(mid+1,r,L,R,cur<<1|1)); return ans; } void update(const int l,const int r,const int L,const int R,const int cur,const int delta) { if (L<=l&&r<=R)return(void)(t[cur].delta+=delta); int mid=(l+r)>>1; down(cur); if (L<=mid)update(l,mid,L,R,cur<<1,delta); if (R>mid)update(mid+1,r,L,R,cur<<1|1,delta); up(cur); } signed main() { int n=read(),m=read(),ans=0; for (int i=1;i<=n;i++)a[i]=read(),update(1,n,i,i,1,a[i]); for (int i=1;i<=m;i++)store[i]=(mc){read(),read()}; sort(store+1,store+1+m,cmp); for (int i=1,now=1;i<=n;i++) { while (store[now].r==i&&now<=m) { int tmp=query(1,n,store[now].l,store[now].r,1); if (tmp)++ans,update(1,n,store[now].l,store[now].r,1,-1); ++now; } } printf("%d\n",ans); } |
1705: [Usaco2007 Nov]Telephone Wire 架设电话线
直接暴力DP
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 |
#include <cstdio> #include <cstring> #include <algorithm> #include <cmath> #include <iostream> using namespace std; inline int read() { int f=1,k=0;char c=getchar(); 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=1e5+100,up=100+5,inf=1e9; int f[maxn][up],h[maxn]; inline int max(const int a,const int b){return a>b?a:b;} inline int sqr(const int x){return x*x;} inline int abs(const int x){return x<0?-x:x;} inline int min(const int a,const int b){return a<b?a:b;} signed main() { int n=read(),c=read(),mx=0; for (int i=1;i<=n;i++)mx=max(mx,h[i]=read()); for (int i=h[1];i<=mx;i++)f[1][i]=sqr(h[1]-i); for (int i=2;i<=n;i++) for (int j=h[i];j<=mx;j++) { f[i][j]=inf; int sqrr=sqr(h[i]-j); for (int k=h[i-1];k<=mx;k++) f[i][j]=min(f[i][j],f[i-1][k]+sqrr+c*abs(j-k)); } int ans=inf; for (int i=h[n];i<=mx;i++)ans=min(ans,f[n][i]); printf("%d\n",ans); } |
1669: [Usaco2006 Oct]Hungry Cows饥饿的奶牛
LIS
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 |
#include <iostream> #include <cstdio> #include <algorithm> #include <vector> #include <bitset> using namespace std; typedef long long ll; inline ll read() { ll f=1,k=0;char c=getchar(); 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=5050; int a[maxn],f[maxn]; inline int max(const int a,const int b){return a>b?a:b;} signed main() { int n=read(),ans=1; for (int i=1;i<=n;i++) { a[i]=read(); f[i]=1; for (int j=1;j<i;j++) if (a[i]>a[j])f[i]=max(f[i],f[j]+1); ans=max(ans,f[i]); } printf("%d\n",ans); } |
1231: [Usaco2008 Nov]mixup2 混乱的奶牛
状压DP
令\(f[i][st]\)表示当前状态为\(st\)，最后一个数为\(val[i]\)的方案数
直接枚举转移即可
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 |
#include <iostream> #include <cstdio> #include <algorithm> #include <vector> #include <bitset> using namespace std; typedef long long ll; inline ll read() { ll f=1,k=0;char c=getchar(); 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=18; ll f[maxn][1<<maxn],a[maxn]; inline int ct(const int st) { int count=0; for (int i=0;i<=maxn;i++)if ((1<<i)&st)++count; return count; } inline int abs(const int x){return x<0?-x:x;} signed main() { int n=read(),k=read(); for (int i=1;i<=n;i++)a[i]=read(); for (int st=1;st<(1<<n);st++) for (int i=1;i<=n;i++) if ((1<<(i-1))&st) { int cnt=ct(st); if (cnt==1) f[i][st]=1; else for (int j=1;j<=n;j++) if ( ( (1<<(j-1))&st ) && (i!=j) && abs(a[j]-a[i])>k ) f[i][st]+=f[j][st^(1<<(i-1))]; } ll ans=0; for (int i=1;i<=n;i++)ans+=f[i][(1<<n)-1]; printf("%lld\n",ans); } |
1690: [Usaco2007 Dec]奶牛的旅行
分数规划
\(mid \leq \frac{\sum Point\ val_i }{\sum Edge \ val_j} \rightarrow \) \(mid \cdot (\sum Edge\ val_j) – \sum Point\ val_i \leq 0\)dfs判负环即可
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 |
#include <bitset> #include <cstring> #include <cstdio> #include <set> #include <iostream> #include <map> #include <algorithm> #include <cmath> using namespace std; typedef long long ll; inline int read() { int f=1,k=0;char c=getchar(); 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=5100<<2; const double eps=1e-3; int last[maxn],m,n,q[maxn],val[maxn]; bool f; double dist[maxn]; bitset<maxn>v; struct mc{int too,nxt,val;double coval;}e[maxn<<1]; void dfs(const int cur) { v[cur]=1; for (int i=last[cur];i&&!f;i=e[i].nxt) if (dist[e[i].too]>dist[cur]+e[i].coval) { if (v[e[i].too])return(void)(f=1); dist[e[i].too]=dist[cur]+e[i].coval; dfs(e[i].too); } v[cur]=0; } inline bool check() { f=0; for (int i=1;i<=n&&!f;i++)dfs(i); return f; } signed main() { n=read(),m=read(); for (int i=1;i<=n;i++)val[i]=read(); for (int i=1;i<=m;i++) { int a=read(),b=read(); e[i].too=b,e[i].nxt=last[a],last[a]=i; e[i].val=read(); } double l=1,r=1e4,mid; while (r-l>eps) { mid=(l+r)/2; for (int i=1;i<=m;i++)e[i].coval=mid*e[i].val-val[e[i].too]; v.reset(); memset(dist,0,sizeof(dist)); if (check())l=mid;else r=mid; } printf("%.2lf\n",l); } |
1711: [Usaco2007 Open]Dining吃饭
最大流
建模：
|
1 2 3 4 5 6 7 8 9 10 11 12 |
int S=F+D+1;T=F+D+2; for (int i=1;i<=F;i++)add(S,i,1); for (int i=1;i<=D;i++)add(i+F,T,1); for (int i=1;i<=n;i++) { int a=read(),b=read(),now=F+D+2+i,noww=F+D+2+n+i; for (int i=1;i<=a;i++) add(read(),now,1); add(now,noww,1); for (int i=1;i<=b;i++) add(noww,read()+F,1); } |
Total:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 |
#include <bitset> #include <cstring> #include <cstdio> #include <set> #include <iostream> #include <map> #include <algorithm> #include <cmath> using namespace std; typedef long long ll; inline int read() { int f=1,k=0;char c=getchar(); 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=110000,inf=1e9; struct mc{int too,nxt,val;}e[maxn]; int last[maxn],tot=1,T; int q[maxn],level[maxn]; inline void add(const int a,const int b,const int val) { ++tot; e[tot].too=b,e[tot].nxt=last[a],last[a]=tot;e[tot].val=val; ++tot; e[tot].too=a,e[tot].nxt=last[b],last[b]=tot;e[tot].val=0; } inline bool bfs(const int s,const int t) { memset(level,0,sizeof(level)); int front=1,rear=1; q[front]=s;level[s]=1; while (front<=rear) { int now=q[front++]; for (int i=last[now];i;i=e[i].nxt) if (e[i].val>0&&!level[e[i].too]) level[e[i].too]=level[now]+1,q[++rear]=e[i].too; } return level[t]; } int dfs(const int cur,int flow) { if (cur==T)return flow; int co=0; for (int i=last[cur],tmp;i;i=e[i].nxt) if (e[i].val>0&&(level[cur]+1==level[e[i].too])) { tmp=dfs(e[i].too,min(flow,e[i].val)); e[i].val-=tmp; e[i^1].val+=tmp; flow-=tmp; co+=tmp; } return co; } signed main() { int n=read(),F=read(),D=read(); int S=F+D+1;T=F+D+2; for (int i=1;i<=F;i++)add(S,i,1); for (int i=1;i<=D;i++)add(i+F,T,1); for (int i=1;i<=n;i++) { int a=read(),b=read(),now=F+D+2+i,noww=F+D+2+n+i; for (int i=1;i<=a;i++) add(read(),now,1); add(now,noww,1); for (int i=1;i<=b;i++) add(noww,read()+F,1); } int ans=0; while (bfs(S,T))ans+=dfs(S,inf); printf("%d\n",ans); } |
2442: [Usaco2011 Open]修剪草坪
令\(f[i][0/1]0/1\)表示不取/取\(i\)的最大值
易得方程：
|
1 2 3 |
for (int j=i-1;j>=0&&j+k>=i;j--) f[i][1]=max(f[j][0]+sum[i]-sum[j],f[i][1]); f[i][0]=max(f[i-1][1],f[i-1][0]); |
线段树维护\(f[i][0]-sum[i]\)即可
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 |
#include <bitset> #include <cstring> #include <cstdio> #include <set> #include <iostream> #include <map> #include <algorithm> using namespace std; typedef long long ll; inline int read() { int f=1,k=0;char c=getchar(); 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=100000+100; const ll inf=1ll<<60; struct mc{ll mx;}t[maxn<<3]; int a[maxn]; ll sum[maxn],f[maxn][2]; ll query(const int l,const int r,const int L,const int R,const int cur) { if (L<=l&&r<=R)return t[cur].mx; int mid=(l+r)>>1;ll ans=-inf; if (L<=mid)ans=query(l,mid,L,R,cur<<1); if (R>mid)ans=max(ans,query(mid+1,r,L,R,cur<<1|1)); return ans; } void update(const int l,const int r,const int cur,const int pos,const ll C) { if (l==r)return (void)(t[cur].mx=C); int mid=(l+r)>>1; if (pos<=mid)update(l,mid,cur<<1,pos,C); else update(mid+1,r,cur<<1|1,pos,C); t[cur].mx=max(t[cur<<1].mx,t[cur<<1|1].mx); } signed main() { int n=read(),k=read(); for (int i=1;i<=n;i++)sum[i]=sum[i-1]+(a[i]=read()); for (int i=1;i<=n;i++) { f[i][1]=query(0,n,max(0,i-k),i-1,1)+sum[i]; f[i][0]=max(f[i-1][1],f[i-1][0]); update(0,n,1,i,f[i][0]-sum[i]); } printf("%lld\n",max(f[n][1],f[n][0])); } |
1725: [Usaco2006 Nov]Corn Fields牧场的安排
状压DP
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 |
#include <bitset> #include <cstring> #include <cstdio> #include <set> #include <iostream> #include <map> #include <algorithm> using namespace std; typedef unsigned long long ull; inline int read() { int f=1,k=0;char c=getchar(); 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 total=1ll<<13,maxn=14; int f[2][total],n,m; bitset<maxn>mp[maxn]; inline bool ok(const int st,const int now,const int p) { for (int i=0;i<m;i++) if ( ((1<<i)&now) && ( ((1<<i)&st) || !mp[p][i+1] || (i&&((1<<(i-1))&now)) || (i!=m-1&&((1<<(i+1))&now)) ) )return 0; return 1; } signed main() { n=read(),m=read(); for (int i=1;i<=n;i++) for (int j=1;j<=m;j++)mp[i][j]=read(); f[0][0]=1; for (int i=1;i<=n;i++) { memset(f[i&1],0,sizeof(f[i&1])); for (int st=0;st<=(1<<m)-1;st++) for (int now=0;now<=(1<<m)-1;now++) if (ok(st,now,i))f[i&1][now]+=f[(i&1)^1][st]; } int ans=0; for (int i=0;i<=(1<<m)-1;i++)(ans+=f[n&1][i])%=100000000; printf("%d\n",ans); } |
1717: [Usaco2006 Dec]Milk Patterns 产奶的模式
二分+Hash
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 |
#include <bitset> #include <cstring> #include <cstdio> #include <set> #include <iostream> #include <map> #include <algorithm> using namespace std; typedef unsigned long long ull; inline int read() { int f=1,k=0;char c=getchar(); 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; } map<ull,int>sum; const ull BASE=1000000+7; const int maxn=20000+100; inline int max(const int a,const int b){return a>b?a:b;} ull Hash[maxn],base[maxn],front[maxn],a[maxn]; inline ull get(const int l,const int r){return front[l]*(Hash[r]-Hash[l-1]);} signed main() { int n=read(),k=read(); for (int i=1;i<=n;i++)a[i]=read(); front[1]=base[n]=1; for (int i=2;i<=n;i++)front[i]=front[i-1]*BASE; for (int i=n-1;i;i--)base[i]=base[i+1]*BASE; for (int i=1;i<=n;i++)Hash[i]=Hash[i-1]+base[i]*a[i]; int l=0,r=n,mid; while (l<r) { sum.clear(); mid=((l+r)>>1)+1; int mx=0;ull tmp; for (int i=1;i+mid-1<=n;i++) tmp=get(i,i+mid-1),tmp=++sum[tmp],(tmp>mx)&&(mx=tmp); if (mx>=k)l=mid;else r=mid-1; } printf("%d\n",l); } |
1633: [Usaco2007 Feb]The Cow Lexicon 牛的词典
直接上最暴力的DP即可（不要想太多…）
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 |
#include <iostream> #include <cstdio> #include <algorithm> #include <cstring> using namespace std; typedef long long ll; typedef unsigned long long ull; inline int read() { int f=1,k=0;char c=getchar(); 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; } inline int max(const int&a,const int&b){return a>b?a:b;} inline int min(const int&a,const int&b){return a<b?a:b;} const int maxn=610,up=602; char s[maxn],p[maxn][30]; int cd[maxn],f[maxn]; signed main() { int n=read(),len=read(); scanf("%s",s+1); for (int i=1;i<=n;i++) scanf("%s",p[i]+1),cd[i]=strlen(p[i]+1); for (int i=1;i<=len;i++) { f[i]=i; for (int j=1;j<=n;j++) { int pos,Len=cd[j],cnt=0; for (pos=i;pos;pos--) { if (p[j][Len]==s[pos])Len--; else cnt++; if (!Len)break; } if (!Len)f[i]=min(f[i],f[pos-1]+cnt); } } printf("%d\n",f[len]); } |
1672: [Usaco2005 Dec]Cleaning Shifts 清理牛棚
DIJ建模
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 |
#include <bits/stdc++.h> using namespace std; inline int read() { register int f=1,k=0;register char c=getchar(); 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=(100000+10)<<1; struct mc{int nxt,too,val;}e[maxn<<3]; int last[maxn],dist[maxn],T,m; bitset<maxn>vis; priority_queue<pair<int,int>,vector<pair<int,int> >,greater<pair<int,int> > >q; inline int dij() { memset(dist,0x3f,sizeof(dist)); q.push(make_pair(0,m));dist[m]=0; while (!q.empty()) { register int now=q.top().second;q.pop(); if (vis[now])continue;vis[now]=1; for (register int i=last[now];i;i=e[i].nxt) if (dist[e[i].too]>dist[now]+e[i].val) { dist[e[i].too]=dist[now]+e[i].val; if (!vis[e[i].too])q.push(make_pair(dist[e[i].too],e[i].too)); } } return printf("%d\n",dist[T]>1e9?-1:dist[T]); } int main() { int n=read();m=read();T=read()+1; for (register int i=1,a,b;i<=n;i++) a=read(),b=read()+1,e[i].val=read(),e[i].too=b,e[i].nxt=last[a],last[a]=i; for (register int ii=m,a,b,i=n+10;ii<=T;i++,ii++) a=ii+1,b=ii,e[i].too=b,e[i].too=b,e[i].nxt=last[a],last[a]=i; dij(); } |
1682: [Usaco2005 Mar]Out of Hay 干草危机
Kruskal
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 |
#include <bits/stdc++.h> using namespace std; inline int read() { register int f=1,k=0;register char c=getchar(); 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=20000+10; struct mc{int x,y,val;}e[maxn]; int fa[maxn]; int gf(const int x){return fa[x]==x?x:fa[x]=gf(fa[x]);} inline bool cmp(const mc&a,const mc&b){return a.val<b.val;} int main() { int n=read(),m=read(),ans=0,cnt=1; for (register int i=1;i<=m;i++) e[i].x=read(),e[i].y=read(),e[i].val=read(); for (register int i=1;i<=n;i++)fa[i]=i; sort(e+1,e+1+m,cmp); for (register int i=1,a,b;i<=m;i++) { a=gf(e[i].x),b=gf(e[i].y); if (a!=b)fa[a]=b,ans=max(ans,e[i].val),cnt++; } printf("%d\n",ans); } |
1628: [Usaco2007 Demo]City skyline
单调栈
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 |
#include <cstdio> using namespace std; inline int read() { register int f=1,k=0;register char c=getchar(); 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=50010; int st[maxn]; int main() { int n=read(),w=read(),ans=0,top=0; for (register int i=1,y;i<=n;i++) { read();y=read(); while (top&&st[top]>y)--top; if (st[top]!=y)ans++,st[++top]=y; } printf("%d\n",ans); } |
1627: [Usaco2007 Dec]穿越泥地
bfs
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 |
#include<bits/stdc++.h> using namespace std; inline int read() { register int f=1,k=0;register char c=getchar(); 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=10010,dx[]={0,0,1,-1},dy[]={1,-1,0,0}; bitset<1015>mp[1015],vis[1015]; int qx[1015*1015],qy[1005*1015],t[1015*1015]; int main() { int x=read(),y=read(),n=read(),X=502,Y=502; for (register int i=1,x;i<=n;i++)x=read(),mp[x+502][read()+502]=1; x+=502,y+=502; register int front=1,rear=1;qx[1]=X;qy[1]=Y;t[1]=0;vis[X][Y]=1; while (front<=rear) { if (qx[front]==x&&qy[front]==y)return printf("%d\n",t[front]),0; for (register int i=0,xx,yy;i<=3;i++) { xx=qx[front]+dx[i];yy=qy[front]+dy[i]; if (xx&&yy&&xx<=1002&&yy<=1002&&!vis[xx][yy]&&!mp[xx][yy]) vis[xx][yy]=1,t[++rear]=t[front]+1,qx[rear]=xx,qy[rear]=yy; } front++; } } |
1624: [Usaco2008 Open] Clear And Present Danger 寻宝之路
Floyd
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 |
#include<bits/stdc++.h> using namespace std; inline int read() { register int f=1,k=0;register char c=getchar(); 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=105; int store[10010],dist[maxn][maxn]; int main() { int n=read(),m=read(); for (register int i=1;i<=m;i++)store[i]=read(); for (register int i=1;i<=n;i++) for (register int j=1;j<=n;j++)dist[i][j]=read(); for (register int k=1;k<=n;k++) for (register int i=1;i<=n;i++) for (register int j=1;j<=n;j++) dist[i][j]=min(dist[i][j],dist[i][k]+dist[k][j]); long long ans=0; for (register int i=2;i<=m;i++) ans+=dist[store[i-1]][store[i]]; ans+=dist[1][store[1]]+dist[store[m]][n]; printf("%lld\n",ans); } |
1640: [Usaco2007 Nov]Best Cow Line 队列变换
模拟+贪心
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 |
#include<bits/stdc++.h> using namespace std; inline int read() { register int f=1,k=0;register char c=getchar(); 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=2000+100; char s[maxn]; inline bool judge(const int l,const int r) { for (register int i=l;i<(l+r)/2;i++) if (s[i]<s[r-(i-l)])return 1; else if (s[r-(i-l)]<s[i])return 0; return 0; } int main() { int n=read(); for (register int i=1;i<=n;i++) while ((s[i]=getchar())<'A'||s[i]>'Z'); for (register int i=1,front=1,rear=n;i<=n;i++) putchar(s[front]<s[rear]||judge(front,rear)?s[front++]:s[rear--]),!(i%80)&&putchar('\n'); } |
1651: [Usaco2006 Feb]Stall Reservations 专用牛棚
差分
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 |
#include<bits/stdc++.h> using namespace std; inline int read() { register int f=1,k=0;register char c=getchar(); 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=1e6+100; int cf[maxn],l[maxn],r[maxn]; int main() { int n=read(),ans=0; for (register int i=1;i<=n;i++)cf[read()]++,cf[read()+1]--; for (register int i=1;i<=1e6+1;i++) cf[i]+=cf[i-1],cf[i]>ans&&(ans=cf[i]); printf("%d\n",ans); } |
1679: [Usaco2005 Jan]Moo Volume 牛的呼声
推式子
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 |
#include<bits/stdc++.h> using namespace std; inline int read() { register int f=1,k=0;register char c=getchar(); 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=10005; int pos[maxn]; long long sum[maxn]; int main() { int n=read();long long ans=0; for (register int i=1;i<=n;i++)pos[i]=read(); sort(pos+1,pos+1+n); for (register int i=2;i<=n;i++) ans+=1ll*(pos[i]-pos[i-1])*(i-1)*(n-i+1)*2; printf("%lld\n",ans); } |
1646: [Usaco2007 Open]Catch That Cow 抓住那只牛
bfs
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 |
#include<bits/stdc++.h> using namespace std; inline int read() { register int f=1,k=0;register char c=getchar(); 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=1000000,inf=2139062143; int q[maxn],minn[maxn]; int main() { register int n=read(),k=read(),front=1,rear=1;q[1]=n; memset(minn,0x7f,sizeof(minn));minn[n]=0; while (front<=rear) { if (q[front]==k)return printf("%d\n",minn[k]),0; if (q[front]<=max(n,k)&&(minn[q[front]<<1]==inf)) q[++rear]=q[front]<<1,minn[q[front]<<1]=minn[q[front]]+1; if (q[front]-1>=0&&minn[q[front]-1]==inf) q[++rear]=q[front]-1,minn[q[front]-1]=minn[q[front]]+1; if (q[front]+1<=k&&minn[q[front]+1]==inf) q[++rear]=q[front]+1,minn[q[front]+1]=minn[q[front]]+1; ++front; } } |
1657: [Usaco2006 Mar]Mooo 奶牛的歌声
单调栈
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 |
#include<bits/stdc++.h> using namespace std; inline int read() { register int f=1,k=0;register char c=getchar(); 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=50010; int h[maxn],v[maxn],st[maxn],sum[maxn]; int main() { int n=read(),top=0; for (register int i=1;i<=n;i++)h[i]=read(),v[i]=read(); for (register int i=1;i<=n;i++) { while (top&&h[st[top]]<h[i])sum[i]+=v[st[top--]]; st[++top]=i; } top=0; for (register int i=n;i;i--) { while (top&&h[st[top]]<h[i])sum[i]+=v[st[top--]]; st[++top]=i; } register int ans=0; for (register int i=1;i<=n;i++)ans=max(ans,sum[i]); printf("%d\n",ans); } |
1677: [Usaco2005 Jan]Sumsets 求和
递推
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 |
#include<bits/stdc++.h> using namespace std; inline int read() { register int f=1,k=0;register char c=getchar(); 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=1e6+100; const long long MOD=1e9; long long f[maxn]; int main() { int n=read(); f[0]=1; for (register int i=1;i<=n;i++) if (i&1)f[i]=f[i-1]; else f[i]=f[i-1]+f[i>>1],(f[i]%=MOD); printf("%lld\n",f[n]%MOD); } |
1660: [Usaco2006 Nov]Bad Hair Day 乱发节
单调栈
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 |
#include<bits/stdc++.h> using namespace std; inline int read() { register int f=1,k=0;register char c=getchar(); 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=80100; int st[maxn],n,a[maxn]; int main() { n=read();long long ans=0,top=0; for (register int i=1;i<=n;i++)a[i]=read(); for (register int i=1;i<=n;i++) { while (top&&st[top]<=a[i])--top; ans+=top; st[++top]=a[i]; } printf("%lld\n",ans); } |
1636: [Usaco2007 Jan]Balanced Lineup
RMQ
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 |
#include <cstdio> #include <cmath> #include <iostream> using namespace std; struct io{ char op[1<<23],*s; io() { fread(s=op,1,sizeof op,stdin); } inline int read() { register int u=0,f=1; while(*s<48||*s>'9')*s=='-'&&(f=-1),s++; while(*s>32)u=u*10+*s++-48; return u*f; } inline char getchar(){return *s++;} }ip; #define read ip.read #define getchar ip.getchar inline int max(int a,int b) { return a>b?a:b; } inline int min(int a,int b) { return a<b?a:b; } const int maxn=50010; int mi[maxn][17],mx[maxn][17],n,q,a,b; int main() { n=read();q=read(); register int lg=log(n)/log(2); for (register int i=1;i<=n;i++) mi[i][0]=mx[i][0]=read(); for (register int j=1;j<=lg;j++) for (register int i=1;i<=n-(1<<j)+1;i++) { register int tmp=i+(1<<(j-1)); mi[i][j]=min(mi[i][j-1],mi[tmp][j-1]); mx[i][j]=max(mx[i][j-1],mx[tmp][j-1]); } for (register int i=1;i<=q;i++) { a=read();b=read(); lg=log(b-a+1)/log(2); printf("%d\n",max(mx[a][lg],mx[b-(1<<lg)+1][lg])-min(mi[a][lg],mi[b-(1<<lg)+1][lg])); } } |
1621: [Usaco2008 Open]Roads Around The Farm分岔路口
模拟
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 |
#include<bits/stdc++.h> using namespace std; inline int read() { register int f=1,k=0;register char c=getchar(); 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; } int q[1000000]; int main() { register int n=read(),k=read(),ans=0,front=1,rear=1;q[1]=n; while (front<=rear) { if (q[front]>k&&(q[front]-k)/2*2+k==q[front]) q[++rear]=(q[front]-k)/2,q[++rear]=(q[front]-k)/2+k; else ans++; front++; } printf("%d\n",ans); } |
1611: [Usaco2008 Feb]Meteor Shower流星雨
bfs
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 |
#include<bits/stdc++.h> using namespace std; inline int read() { register int f=1,k=0;register char c=getchar(); 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=50100,dx[]={0,0,1,-1,0},dy[]={1,-1,0,0,0},inf=2139062143; int eta[310][310],qx[310*310*10],qy[310*310*10],minn[310][310]; int main() { int m=read(),ans=2e9; memset(eta,0x7f,sizeof(eta)); memset(minn,0x7f,sizeof(minn)); for (register int i=1,x,y,X,Y,T;i<=m;i++) { x=read(),y=read(),T=read(); for (register int j=0;j<=4;j++) { X=x+dx[j],Y=y+dy[j]; if (X>=0&&Y>=0) eta[X][Y]=min(eta[X][Y],T); } } register int front=1,rear=1;qx[1]=qy[1]=0;minn[0][0]=0; while (front<=rear) { if (eta[qx[front]][qy[front]]==inf) ans=min(ans,minn[qx[front]][qy[front]]); for (register int i=0,x,y;i<=3;i++) { x=qx[front]+dx[i];y=qy[front]+dy[i]; if (x>=0&&y>=0&&minn[x][y]==inf&&x<=301&&y<=301 &&minn[qx[front]][qy[front]]<eta[x][y]-1) minn[x][y]=minn[qx[front]][qy[front]]+1,qx[++rear]=x,qy[rear]=y; } ++front; } printf("%d\n",ans==2e9?-1:ans); } |
1626: [Usaco2007 Dec]Building Roads 修建道路
Kruskal
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 |
#include<bits/stdc++.h> using namespace std; inline int read() { register int f=1,k=0;register char c=getchar(); 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=1100; struct mc{double dis;int x,y;}e[maxn*maxn]; int x[maxn],y[maxn],fa[maxn]; inline double abs(const int a,const int b) { return sqrt(1ll*(x[a]-x[b])*(x[a]-x[b])+1ll*(y[a]-y[b])*(y[a]-y[b])); } int gf(const int x){return fa[x]==x?x:fa[x]=gf(fa[x]);} inline bool cmp(const mc&a,const mc&b){return a.dis<b.dis;} int main() { int n=read(),m=read(),tot=0; for (register int i=1;i<=n;i++)x[i]=read(),y[i]=read(),fa[i]=i; for (register int i=1;i<=n;i++) for (register int j=i+1;j<=n;j++) e[++tot]=(mc){abs(i,j),i,j}; for (register int i=1;i<=m;i++)fa[gf(read())]=gf(read()); sort(e+1,e+1+tot,cmp); double ans=0; for (register int i=1,a,b;i<=tot;i++) if ((a=gf(e[i].x))!=(b=gf(e[i].y)))fa[a]=b,ans+=e[i].dis; printf("%.2lf\n",ans); } |
1616: [Usaco2008 Mar]Cow Travelling游荡的奶牛
方案DP
令\(f[t][i][j]\)表示\(t\)时\((i,j)\)的方案数
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 |
#include<bits/stdc++.h> using namespace std; inline int read() { register int f=1,k=0;register char c=getchar(); 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=207,dx[]={1,-1,0,0},dy[]={0,0,1,-1}; int f[maxn][maxn][maxn],mp[maxn][maxn]; char s[200]; int main() { int n=read(),m=read(),T=read(); for (register int i=1;i<=n;i++) { scanf("%s",s+1); for (register int j=1;j<=m;j++)mp[i][j]=(s[j]=='.'); } int x=read(),y=read(),X=read(),Y=read(); f[0][x][y]=1; for (register int t=1;t<=T;t++) for (register int i=1;i<=n;i++) for (register int j=1;j<=m;j++) for (register int k=0,xx,yy;k<=3;k++) { xx=i+dx[k],yy=j+dy[k]; if (mp[xx][yy])f[t][i][j]+=f[t-1][xx][yy]; } printf("%d\n",f[T][X][Y]); } |
1625: [Usaco2007 Dec]宝石手镯
01背包DP
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 |
#include<bits/stdc++.h> using namespace std; inline int read() { register int f=1,k=0;register char c=getchar(); 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=15000; int f[maxn],w[maxn],d[maxn]; int main() { int n=read(),m=read(); for (register int i=1;i<=n;i++) w[i]=read(),d[i]=read(); for (register int i=1;i<=n;i++) { for (register int j=m-w[i];j;j--) if (f[j])f[j+w[i]]=max(f[j+w[i]],f[j]+d[i]); f[w[i]]=max(f[w[i]],d[i]); } int ans=0; for (register int i=1;i<=m;i++)ans=max(ans,f[i]); printf("%d\n",ans); } |
1609: [Usaco2008 Feb]Eating Together麻烦的聚餐
求两次最长不降子序列即可（正反）
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 |
#include<bits/stdc++.h> using namespace std; inline int read() { register int f=1,k=0;register char c=getchar(); 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=30100; int sum[maxn],n,a[maxn]; inline void update(int x,const int mx) { for(;x<=n;x+=x&-x)sum[x]=max(sum[x],mx); } inline int query(int x) { register int ans=0; for (;x;x-=x&-x)ans=max(ans,sum[x]); return ans; } int main() { n=read();int ans=0; for (register int i=1;i<=n;i++)a[i]=read(); for (register int i=1,x;i<=n;i++) update(a[i],x=query(a[i])+1),x>ans&&(ans=x); ans=n-ans; for (register int i=1;i<=n;i++)sum[n-i+1]=a[i]; for (register int i=1;i<=n;i++)a[i]=sum[i]; memset(sum,0,sizeof(sum)); int tmp=0; for (register int i=1,x;i<=n;i++) update(a[i],x=query(a[i])+1),x>tmp&&(tmp=x); ans=min(ans,n-tmp); printf("%d\n",ans); } |
1674: [Usaco2005]Part Acquisition
最短路
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 |
#include <bits/stdc++.h> using namespace std; struct io{ char op[1<<24],*s; io() { fread(s=op,1,sizeof op,stdin); } inline int read() { register int u=0,f=1; while(*s<48||*s>'9')*s=='-'&&(f=-1),s++; while(*s>32)u=u*10+*s++-48; return u*f; } inline char getchar(){return *s++;} }ip; #define read ip.read #define getchar ip.getchar const int maxn=50000+100,inf=2139062143; struct mc{int too,nxt,val;}e[maxn<<1]; int last[maxn],dist[maxn]; bitset<maxn>vis; priority_queue<pair<int,int>,vector<pair<int,int> >,greater<pair<int,int> > >q; inline void dij() { q.push(make_pair(0,1));dist[1]=0; while (!q.empty()) { register int cur=q.top().second;q.pop(); if (vis[cur])continue;vis[cur]=1; for (register int i=last[cur];i;i=e[i].nxt) if (dist[e[i].too]>dist[cur]+e[i].val) { dist[e[i].too]=dist[cur]+e[i].val; q.push(make_pair(dist[e[i].too],e[i].too)); } } } int main() { int n=read(),m=read(); memset(dist,0x7f,sizeof(dist)); for (register int i=1,a,b;i<=n;i++) a=read(),b=read(),e[i].too=b,e[i].nxt=last[a],last[a]=i,e[i].val=1; dij(); printf("%d\n",dist[m]==inf?-1:dist[m]+1); } |
1635: [Usaco2007 Jan]Tallest Cow 最高的牛
差分
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 |
#include <bits/stdc++.h> using namespace std; struct io{ char op[1<<20],*s; io() { fread(s=op,1,sizeof op,stdin); } inline int read() { register int u=0,f=1; while(*s<48||*s>'9')*s=='-'&&(f=-1),s++; while(*s>32)u=u*10+*s++-48; return u*f; } inline char getchar(){return *s++;} }ip; #define read ip.read #define getchar ip.getchar const int maxn=10010; struct as{int l,r;}ask[maxn]; int cf[maxn]; inline bool cmp(const as&a,const as&b){return a.l<b.l||(a.l==b.l&&a.r<b.r);} int main() { int n=read(),i=read(),h=read(),r=read(); for (register int i=1;i<=r;i++) ask[i].l=read(),ask[i].r=read(),ask[i].l>ask[i].r&&(swap(ask[i].l,ask[i].r),1); sort(ask+1,ask+1+r,cmp); for (register int i=1;i<=r;i++) if (ask[i].l!=ask[i-1].l||(ask[i].l==ask[i-1].l&&ask[i].r!=ask[i-1].r)) cf[ask[i].l+1]--,cf[ask[i].r]++; for (register int i=1;i<=n;i++) printf("%d\n",(cf[i]+=cf[i-1])+h); } |
1619: [Usaco2008 Nov]Guarding the Farm 保卫牧场
sort后bfs
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 |
#include <bits/stdc++.h> using namespace std; struct io{ char op[1<<25],*s; io() { fread(s=op,1,sizeof op,stdin); } inline int read() { register int u=0,f=1; while(*s<48||*s>'9')*s=='-'&&(f=-1),s++; while(*s>32)u=u*10+*s++-48; return u*f; } inline char getchar(){return *s++;} }ip; #define read ip.read #define getchar ip.getchar const int maxn=707,dx[]={1,-1,0,0,-1,1,1,-1},dy[]={0,0,1,-1,-1,1,-1,1}; int mp[maxn][maxn],vis[maxn][maxn],x[maxn*maxn],y[maxn*maxn], posx[maxn*maxn],posy[maxn*maxn],pos[maxn*maxn]; inline bool cmp(const int&a,const int&b) { return mp[posx[a]][posy[a]]>mp[posx[b]][posy[b]]; } int main() { int n=read(),m=read(),tot=0; for (register int i=1;i<=n;i++) for (register int j=1;j<=m;j++) mp[i][j]=read(),posx[(i-1)*m+j]=i,posy[(i-1)*m+j]=j, pos[(i-1)*m+j]=(i-1)*m+j; sort(pos+1,pos+1+n*m,cmp); for (register int i=1,front,rear;i<=n*m;i++) if (mp[posx[pos[i]]][posy[pos[i]]]&&!vis[posx[pos[i]]][posy[pos[i]]]) { front=rear=1;x[1]=posx[pos[i]],y[1]=posy[pos[i]];++tot; while (front<=rear) { for (register int k=0,X,Y;k<=7;k++) { X=x[front]+dx[k],Y=y[front]+dy[k]; if (X>=1&&X<=n&&Y>=1&&Y<=m&&mp[X][Y]<=mp[x[front]][y[front]] &&!vis[X][Y]) vis[X][Y]=tot,x[++rear]=X,y[rear]=Y; } ++front; } } printf("%d\n",tot); } |
1613: [Usaco2008 Jan]Running贝茜的晨练计划
DP
\(f[i][j]\)表示第\(i\)分钟，疲惫值为\(j\)的最远距离
\(f[i][0]=max(f[i-1][0],f[i-j][j])\)\(f[i][j]=f[i-1][j-1]+Di\)
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 |
#include <bits/stdc++.h> using namespace std; struct io{ char op[1<<22],*s; io() { fread(s=op,1,sizeof op,stdin); } inline int read() { register int u=0,f=1; while(*s<48||*s>'9')*s=='-'&&(f=-1),s++; while(*s>32)u=u*10+*s++-48; return u*f; } inline char getchar(){return *s++;} }ip; #define read ip.read #define getchar ip.getchar const int maxn=10010; int f[maxn][505],d[maxn]; int main() { int n=read(),m=read(); for (register int i=1;i<=n;i++)d[i]=read(); for (register int i=1;i<=n;i++) { f[i][0]=max(f[i][0],f[i-1][0]); for (register int j=0,mi=m<i?m:i;j<=mi;j++) f[i][0]=max(f[i-j][j],f[i][0]); for (register int j=1;j<=m;j++) f[i][j]=max(f[i][j],f[i-1][j-1]+d[i]); } printf("%d\n",f[n][0]); } |
1600: [Usaco2008 Oct]建造栅栏
DP
1.构成四边形的条件：三边之和大于第四边，故每条边不超过\(n/2\)，即\(mxlen=n/2-1\)
2.总的方案数，可从最后一条边考虑起，最后一条边有多少种情况，再依次加上前面得出的结果
令\(f[i][j]\)表示划分到第\(i\)块，总长为\(j\)的方案数
\(f[i][j]=Σf[i-1][j-k]\)其中，\(k\)表示第\(i\)块的长度，满足\(1<=k<=min(mxlen,j)\)
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 |
#include <bits/stdc++.h> using namespace std; struct io{ char op[100],*s; io() { fread(s=op,1,sizeof op,stdin); } inline int read() { register int u=0,f=1; while(*s<48||*s>'9')*s=='-'&&(f=-1),s++; while(*s>32)u=u*10+*s++-48; return u*f; } inline char getchar(){return *s++;} }ip; const int maxn=2507; int f[5][maxn]; int main() { int n=ip.read(); f[0][0]=1; for (register int i=1,mxlen=(n+1)/2-1;i<=4;i++) for (register int j=0;j<=n;j++) for (register int k=1,up=mxlen<j?mxlen:j;k<=up;k++) f[i][j]+=f[i-1][j-k]; printf("%d\n",f[4][n]); } |
5142: [Usaco2017 Dec]Haybale Feast
二分
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 |
#include <bits/stdc++.h> using namespace std; struct io{ char op[1<<23],*s; io() { fread(s=op,1,sizeof op,stdin); } inline int read() { register int u=0,f=1; while(*s<48||*s>'9')*s=='-'&&(f=-1),s++; while(*s>32)u=u*10+*s++-48; return u*f; } inline char getchar() { return *s++; } inline long long readll() { register int f=1;register long long k=0;register char c=getchar(); 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; } }ip; #define read ip.read #define getchar ip.getchar #define readll ip.readll const int maxn=100010; int n,f[maxn],s[maxn]; long long m; inline bool ok(const int mid) { register long long tmp=0; for (register int i=1;i<=n;i++) { if (s[i]>mid)tmp=0;else tmp+=f[i]; if (tmp>=m)return 1; } return 0; } int main() { n=read();m=readll();register int mx=0; for (register int i=1;i<=n;i++)f[i]=read(),s[i]=read(),s[i]>mx&&(mx=s[i]); register int l=0,r=mx,mid; while (l<r) { mid=( |