2017 9 1：
1、 1624: [Usaco2008 Open] Clear And Present Danger 寻宝之路
floyd最短路
#include<cstdio> #include<cstring> const int N=105,len=10000+9; int map[N][N]; int a[len]; int main() { int n,m; scanf("%d %d",&n,&m); for(int i=1;i<=m;i++) scanf("%d",&a[i]); for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) scanf("%d",&map[i][j]); for(int k=1;k<=n;k++) for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) if(map[i][k]+map[k][j]<map[i][j]) map[i][j]=map[i][k]+map[k][j]; long long ans=0; int last=1; for(int i=1;i<=m;i++) ans+=map[last][a[i]],last=a[i]; printf("%lld\n",ans); return 0; }
2、1648: [Usaco2006 Dec]Cow Picnic 奶牛野餐（看题解）
一道水题
然而我脑子短路了
竟然没想到怎么写
直接从每个牛的位置dfs一遍
标记一下每个点
然后再看哪些点被标记了K次就可以了
#include<cstdio> #include<cstring> const int K=107,N=1007,M=10005; int first[N],cow[K]; struct node { int to,next; }e[M]; int count[N]; int visit[N]; void dfs(int x) { visit[x]=1;count[x]++; for(int k=first[x];k;k=e[k].next) if(!visit[e[k].to]) dfs(e[k].to); } int main() { int k,n,m; scanf("%d %d %d",&k,&n,&m); for(int i=1;i<=k;i++) scanf("%d",&cow[i]); int u,v; int cnt=0; for(int i=1;i<=m;i++) { scanf("%d %d",&u,&v); e[++cnt].to=v;e[cnt].next=first[u];first[u]=cnt; } int sum=0; for(int i=1;i<=k;i++) { memset(visit,0,sizeof(visit)); dfs(cow[i]); } for(int i=1;i<=n;i++) if(count[i]==k) sum++; printf("%d\n",sum); return 0; }
3、1623: [Usaco2008 Open]Cow Cars 奶牛飞车
贪心
数据范围再大一些可以考虑二分找出符合条件的牛
刚开始cmp函数写错了
写成了min函数QAQ
#include<cstdio> #include<cstring> #include<algorithm> const int N=5*1e4+100; int si[N]; int sum[N]; bool cmp(int a,int b) { return a<b; } int main() { int n,m,d,l; scanf("%d %d %d %d",&n,&m,&d,&l); for(int i=1;i<=n;i++) { scanf("%d",&si[i]); if(si[i]<l) i--,n--; } std::sort(si+1,si+1+n,cmp); int k=1; int ans=0; for(int i=1;i<=n;i++) { while(si[i]-sum[k]*d<l&&i<=n) i++; if(i>n) break; sum[k]++; k++; if(k>m) k=1; ans++; } printf("%d\n",ans); return 0; }
4、1627: [Usaco2007 Dec]穿越泥地
随便打个bfs
每个点只会遍历一次
#include<cstdio> #include<cstring> const int N=1020; bool map[N][N]; bool bo[N][N]; const int len=1e6+5; int qu[len][3]; int x,y,n; int hh[4]={-1,0,0,1},ll[4]={0,1,-1,0}; int sth,stl;; int bfs() { int head=1,tail=2; qu[1][0]=sth,qu[1][1]=stl;qu[1][2]=0; while(head<=tail) { int rr=head++; if(head>len) head=0; // printf("std::%d %d %d\n",qu[rr][0],qu[rr][1],qu[rr][2]); if(qu[rr][0]==x&&qu[rr][1]==y) return qu[rr][2]; for(int i=0;i<4;i++) { int u=qu[rr][0]+hh[i],v=qu[rr][1]+ll[i]; if(!bo[u][v]&&!map[u][v]) { bo[u][v]=1; qu[tail][0]=u;qu[tail][1]=v;qu[tail++][2]=qu[rr][2]+1; if(tail>len) tail=0; } } } } int main() { scanf("%d %d %d",&x,&y,&n); x+=501,y+=501; sth=501,stl=501; int u,v; for(int i=1;i<=n;i++) { scanf("%d %d",&u,&v); map[u+501][v+501]=1; } printf("%d\n",bfs()); return 0; }
2017 9 2：
5、1682: [Usaco2005 Mar]Out of Hay 干草危机
最小生成树
很难受。。。
大水题WA了好几次
有一个地方m写成n了。。。。
#include<cstdio> #include<cstring> #include<algorithm> const int M=10000+17,N=2005; struct node { int to,c,from; }e[M]; int f[N]; int get(int v) { return f[v]==v?v:f[v]=get(f[v]); } int cnt; inline void insert(int u,int v,int c) { e[++cnt].from=u;e[cnt].to=v;e[cnt].c=c; } bool cmp(node a,node b) { return a.c<b.c; } int main() { int n,m; scanf("%d %d",&n,&m); int u,v,c; for(int i=1;i<=m;i++) { scanf("%d %d %d",&u,&v,&c); insert(u,v,c); } std::sort(e+1,e+1+m,cmp); for(int i=1;i<=n;i++) f[i]=i; int sum=0; for(int i=1;i<=m;i++) { int x=get(e[i].from),y=get(e[i].to); if(x!=y) { f[x]=y; sum++; if(sum==n-1) { printf("%d\n",e[i].c); return 0; } } } return 0; }6、3403: [Usaco2009 Open]Cow Line 直线上的牛
模拟
#include<cstdio> #include<cstring> const int len=100000*3+100; int qu[len]; inline char read() { char t=getchar(); while(t<'A'||t>'Z') t=getchar(); return t; } int main() { int s; scanf("%d",&s); int head=1e5+1,tail=1e5; int now=1; for(int i=1;i<=s;i++) { char t=read(); if(t=='A') { t=read(); if(t=='L') qu[--head]=now++; else qu[++tail]=now++; } else { int k;t=read(); scanf("%d",&k); if(t=='L') head+=k; else tail-=k; } } while(head<=tail) printf("%d\n",qu[head++]); return 0; }
7、3403: [Usaco2009 Open]Cow Line 直线上的牛
bfs
#include<cstdio> #include<cstring> const int M=50000+100,N=20005,len=1e5; struct node { int to,next; }e[M*2]; int first[N]; int dis[N]; int qu[len]; bool visit[N]; void bfs() { int head=1,tail=2; qu[1]=1; dis[1]=0;visit[1]=1; while(head<=tail) { int rr=qu[head++]; for(int k=first[rr];k;k=e[k].next) if(!visit[e[k].to]) { visit[e[k].to]=1; qu[tail++]=e[k].to; dis[e[k].to]=dis[rr]+1; } } } int main() { int n,m; scanf("%d %d",&n,&m); int cnt=0; int u,v; for(int i=1;i<=m;i++) { scanf("%d %d",&u,&v); e[++cnt].to=v;e[cnt].next=first[u];first[u]=cnt; e[++cnt].to=u;e[cnt].next=first[v];first[v]=cnt; } bfs(); int max=0,sum=0; for(int i=1;i<=n;i++) if(dis[i]>max) max=dis[i],sum=1; else if(dis[i]==max) sum++; for(int i=1;i<=n;i++) if(dis[i]==max) { printf("%d %d %d\n",i,dis[i],sum); return 0; } return 0; } ———————————————————————分割线——————————————————————————————写的这些题都好水啊。。。。。
准备弃坑
去写gold了，，，
2017 9 4：
没事闲的写一题
8、1606: [Usaco2008 Dec]Hay For Sale 购买干草
背包问题变形？
题意好像不是很清楚
我写的是完全背包
我看别人写的是01背包
不过我也过了。。。。
跑了300ms
不知道0ms的是怎么跑的 %%%
#include<cstdio> #include<cstring> #include<algorithm> int f[50000+19]; int a[5000+7]; int main() { int c,n; scanf("%d %d",&c,&n); for(int i=1;i<=n;i++) scanf("%d",&a[i]); f[0]=1; for(int i=1;i<=n;i++) for(int j=a[i];j<=c;j++) f[j]=std::max(f[j],f[j-a[i]]); for(int j=c;j>=0;j--) if(f[j]) { printf("%d\n",j); return 0; } return 0; }
9、1621: [Usaco2008 Open]Roads Around The Farm分岔路口
没事又写了一题
水。。
模拟，类似bfs
#include<cstdio> #include<cstring> const int len=1e6+5; int qu[len+5]; int main() { int n,k; scanf("%d %d",&n,&k); qu[1]=n; int head=1,tail=2; long long ans=0; while(head!=tail) { int rr=qu[head++];if(head==len) head=0; if(rr-k>0&&(rr-k)%2==0) { int tt=(rr-k)/2; qu[tail++]=tt; if(tail==len) tail=0; qu[tail++]=tt+k; if(tail==len) tail=0; } else ans++; } printf("%lld\n",ans); return 0; }2017 9 11：
10、1614: [Usaco2007 Jan]Telephone Lines架设电话线
随意一写竟然遇到一道难题QAQ
2017 10 14：
时光飞逝QAQ，已经过了一个月了
今天刚考完noip初赛QAQ，忐忑。。。
11、bzoj 1635: [Usaco2007 Jan]Tallest Cow 最高的牛
首先我们发现区间不可能相交（最多端点重叠或者区间包含）
那么我们可以刚开始就可以贪心地将所以牛都设为maxh
对于a can see b
我们只需将区间[ a+1,b-1 ] -1就可以了
注意去掉重复的关系
#include<cstdio> #include<cstring> int read() { int ans=0,f=1;char t=getchar(); while(t<'0'||t>'9') f=(t=='-'?-1:1),t=getchar(); while(t>='0'&&t<='9') ans=ans*10+t-'0',t=getchar(); return ans*f; } const int N=1e4+7; int ans[N]; struct node { int l,r; }e[N]; bool cmp(node a,node b) { if(a.l==b.l) return a.r<b.r; return a.l<b.l; } #include<algorithm> using std::sort; inline void swap(int &a,int &b) { int tmp=a;a=b,b=tmp; } int main() { int n=read(),k=read(),h=read(),m=read(); ans[1]=h; for(int i=1;i<=m;i++) { e[i].l=read(),e[i].r=read(); if(e[i].l>e[i].r) swap(e[i].l,e[i].r); } std::sort(e+1,e+1+m,cmp); for(int i=1;i<=m;i++) { if(e[i].l==e[i-1].l&&e[i].r==e[i-1].r) continue; ans[e[i].l+1]--;ans[e[i].r]++; } for(int i=1;i<=n;i++) ans[i]+=ans[i-1],printf("%d\n",ans[i]); return 0; }2017 10 23：
12、bzoj1610: [Usaco2008 Feb]Line连线游戏
#include<cstdio> #include<cstring> #include<algorithm> const int N=205; struct edgt { int x,y; }e[N]; struct node { double xie; }a[N*N]; const double eps=1e-10; inline bool cmp(node a,node b) { if(a.xie-b.xie<eps) return 1; return 0; } int qu[N]; int main() { int n; scanf("%d",&n); for(int i=1;i<=n;i++) scanf("%d %d",&e[i].x,&e[i].y); int sum=0,cnt=0; for(int i=1;i<=n;i++) for(int j=i+1;j<=n;j++) if(e[i].x!=e[j].x) a[++cnt].xie=(e[i].y-e[j].y)*1.0/(e[i].x-e[j].x); else sum=1; std::sort(a+1,a+1+cnt,cmp); for(int i=2;i<=cnt;i++) if(a[i].xie!=a[i-1].xie) sum++; printf("%d\n",sum+1); return 0; }
