摘要：
在我做之前，我没想到会有这么多水˂Bzoj1599:[Usaco2008Oct]重石计数。。1#包含2数据、b、c；3英寸[100]；45intmain（）{6scanf；7for8for9for10t[i+j+k]++；11intans=0，ansx=0；12for13fans=t[i]，ansx=i；14printf；15return0；16}Bzoj1600:[Usaco2008Oct]建造围栏以形成四边形的充分必要条件是三条边的总和大于第四条边，也就是说，任何边都不超过总长度的一半，然后列举第二条切口在哪里。双方讨论了这种情况的贡献时间。O、 空间O网络上的解决方案似乎是背包，但那将是n^2=y）p[x]=y，ans+=e[i].w；37}3839printf；40返回0；41}Bzoj1602:[Usaco2008Oct]牧场步行模板问题，复习加倍=p[v][i]）35u=p[u][i]，v=p[v][i]；36返回p[u][0]；37}3839intmain（）{40scanf；41intu，v，g；42for43scanf，44adde；4546dfs；4748for{49scanf；50printf；51}52return0；53｝Bzoj1603：[美国2008年10月]脱粒机的顺序不会影响任何事情。那就直接来。。
做之前真是没想到有这么水>.<
但做了还是发上来吧>.<
就当是刷一刷AC量&1A率什么的>.<
Bzoj1599: [Usaco2008 Oct]笨重的石子
枚举。。
1 #include<cstdio> 2 int a,b,c; 3 int t[100]; 4 5 int main(){ 6 scanf("%d%d%d",&a,&b,&c); 7 for(int i=1;i<=a;i++) 8 for(int j=1;j<=b;j++) 9 for(int k=1;k<=c;k++) 10 t[i+j+k]++; 11 int ans=0,ansx=0; 12 for(int i=3;i<=a+b+c;i++) 13 if(t[i]>ans) ans=t[i],ansx=i; 14 printf("%d ",ansx); 15 return 0; 16 }
Bzoj1600: [Usaco2008 Oct]建造栅栏
组成四边形的充要条件是三边之和大于第四边
也就是任意一边不超过总长的一半(N边形也适用)
然后枚举一下第二次切在哪，两边讨论一下得出这种情况的贡献
时间O(n)，空间O(1)
网上的题解貌似都是背包，但那样就是n^2了。。
1 #include<cstdio> 2 #include<algorithm> 3 using namespace std; 4 int n,lim,ans; 5 6 int main(){ 7 scanf("%d",&n); 8 lim=(n+1)/2; 9 10 for(int i=2;i<=n-2;i++){ 11 int a=lim,b=i-lim,c=i+lim,d=n-lim; 12 a=min(i,a),c=min(n,c); 13 b=max(0,b),d=max(i,d); 14 ans+=(a-b-1)*(c-d-1); 15 } 16 printf("%d ",ans); 17 return 0; 18 }
Bzoj1601: [Usaco2008 Oct]灌水
这道题以前做了，新加一个点然后最小生成树。
1 #include<cstdio> 2 #include<algorithm> 3 using namespace std; 4 const int maxn=305; 5 6 int p[maxn]; 7 int find(int x){return p[x]==x?x:p[x]=find(p[x]);} 8 struct edge{ 9 int u,v,w; 10 bool operator <(const edge&a) 11 const {return w<a.w;} 12 }e[maxn*maxn+maxn]; 13 int n,k; 14 15 int main(){ 16 scanf("%d",&n); 17 for(int i=0;i<=n;i++) p[i]=i; 18 int w; 19 20 for(int i=1;i<=n;i++){ 21 scanf("%d",&w); 22 e[++k].u=0,e[k].v=i; 23 e[k].w=w; 24 } 25 for(int i=1;i<=n;i++) 26 for(int j=1;j<=n;j++){ 27 scanf("%d",&w); 28 e[++k].u=i,e[k].v=j; 29 e[k].w=w; 30 } 31 sort(e+1,e+k+1); 32 33 long long ans=0; 34 for(int i=1;i<=k;i++){ 35 int x=find(e[i].u),y=find(e[i].v); 36 if(x!=y) p[x]=y,ans+=e[i].w; 37 } 38 39 printf("%lld ",ans); 40 return 0; 41 }
Bzoj1602: [Usaco2008 Oct]牧场行走
模板题，复习倍增。
1 #include<cstdio> 2 #include<algorithm> 3 using namespace std; 4 const int maxn=1e3+5; 5 int n,q; 6 7 int head[maxn],e[maxn*2],w[maxn*2],nxt[maxn*2],k; 8 int adde(int u,int v,int g){ 9 e[++k]=v;w[k]=g;nxt[k]=head[u];head[u]=k; 10 e[++k]=u;w[k]=g;nxt[k]=head[v];head[v]=k; 11 } 12 int dep[maxn],dist[maxn],p[maxn][10]; 13 14 int dfs(int u){ 15 for(int i=1;i<10;i++) 16 p[u][i]=p[p[u][i-1]][i-1]; 17 for(int i=head[u];i;i=nxt[i]){ 18 int v=e[i]; 19 if(v==p[u][0]) continue; 20 dist[v]=dist[u]+w[i]; 21 dep[v]=dep[u]+1; 22 p[v][0]=u; 23 dfs(v); 24 } 25 } 26 27 int lca(int u,int v){ 28 if(dep[u]<dep[v]) swap(u,v); 29 int del=dep[u]-dep[v]; 30 for(int i=0;i<10;i++) 31 if(del&(1<<i)) u=p[u][i]; 32 if(u==v) return v; 33 for(int i=9;i>=0;i--) 34 if(p[u][i]!=p[v][i]) 35 u=p[u][i],v=p[v][i]; 36 return p[u][0]; 37 } 38 39 int main(){ 40 scanf("%d%d",&n,&q); 41 int u,v,g; 42 for(int i=1;i<n;i++) 43 scanf("%d%d%d",&u,&v,&g), 44 adde(u,v,g); 45 46 dfs(1); 47 48 for(int i=1;i<=q;i++){ 49 scanf("%d%d",&u,&v); 50 printf("%d ",dist[u]+dist[v]-2*dist[lca(u,v)]); 51 } 52 return 0; 53 }
Bzoj1603: [Usaco2008 Oct]打谷机
顺序并不会影响什么，然后直接来。。
1 #include<cstdio> 2 int n,a,b,c,ans; 3 int main(){ 4 scanf("%d",&n); 5 for(int i=1;i<n;i++){ 6 scanf("%d%d%d",&a,&b,&c); 7 ans^=c; 8 } 9 printf("%d ",ans); 10 return 0; 11 }
也不知道做这些题意义何在
然而玩水真是欢乐