本文主要是介绍CSU Monthly 2012 Aug.，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
http://acm.csu.edu.cn/OnlineJudge/contest.php?cid=2026
这次参加比赛，结果就被完虐了
B题 我用的bfs ，随便写写竟然1A，我以为题目肯定还有我没有考虑到的情况
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>using namespace std;
const int maxn=100100;int degree[maxn],vis[maxn],head[maxn],tot,n,m;
struct Edge
{int u,v,next;
}e[maxn];
void addegde(int a,int b)
{e[tot].u=a,e[tot].v=b,e[tot].next=head[a],head[a]=tot++;
}
int que[maxn],dp[maxn];
int bfs()
{int l=0,r=0;que[r++]=1;memset(dp,-1,sizeof(dp));dp[1]=0;memset(vis,0,sizeof(vis));while(l<r){int u=que[l++];vis[u]=0;for(int i=head[u];i!=-1;i=e[i].next){int v=e[i].v;if(dp[v]==-1||dp[v]>dp[u]+degree[u]-1){dp[v]=dp[u]+degree[u]-1;if(!vis[v]) que[r++]=v,vis[v]=1;}}}return dp[n];
}
int main()
{int a,b;while(scanf("%d %d",&n,&m)==2){memset(head,-1,sizeof(head));memset(degree,0,sizeof(degree));tot=0;while(m--){scanf("%d%d",&a,&b);addegde(a,b);degree[a]++;}printf("%d\n",bfs());}return 0;
}
C题 我开始还以为是抽象成二分图，后来想想都不对，又以为是网络流，在保证最大流的前提下，费用最小，但是我不会建模……悲剧的只能自己yy了，题目的每个串都可以
抽象成4种不同的类型，分别是 小小 大大 小大 大小，然后贪心就可以了。1A
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>using namespace std;int x1,x2,x3,x4;
char word[1100];int main()
{int n;while(scanf("%d",&n)==1){x1=x2=x3=x4=0;int ans=0;for(int i=0;i<n;i++){scanf("%s",word);int cnt=0,len=strlen(word);for(int j=1;j<len;j++){bool pre=islower(word[j-1]);bool now=islower(word[j]);if(pre!=now) cnt++;}ans+=cnt;if(islower(word[0])&&islower(word[len-1])) x1++;else if(islower(word[0])&&!islower(word[len-1])) x2++;else if(!islower(word[0])&&islower(word[len-1])) x3++;else x4++;}//cout<<x1<<" "<<x2<<" "<<x3<<" "<<x4<<endl;//cout<<ans<<endl;if(x2) x2--;else ans++;if(x3>=x2){if(x3>x2+1) ans+=x3-x2-1;}elseans+=x2-x3;printf("%d\n",ans);}return 0;
}
G 题就是线段树加简单dp 的水题，用线段树来查找一段范围内的最大值就行了，1A
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>using namespace std;
const int maxn=100100;
const int inf=99999999;
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1int d[maxn];
struct Node
{int kind,v,happy;
}item[maxn];void update(int p,int val,int l,int r,int rt)
{if(l==r){d[rt]=max(d[rt],val);return;}int m=(l+r)>>1;if(p<=m) update(p,val,lson);else update(p,val,rson);d[rt]=max(d[rt<<1],d[rt<<1|1]);
}
int query(int L,int R,int l,int r,int rt)
{if(L<=l&&R>=r)return d[rt];int m=(l+r)>>1;int ret1=-1,ret2=-1;if(L<=m) ret1=query(L,R,lson);if(R>m) ret2=query(L,R,rson);return max(ret1,ret2);
}
int cmp(Node a,Node b)
{return a.kind < b.kind;
}
int main()
{int N,C,V;while(scanf("%d%d%d",&N,&C,&V)==3){for(int i=0;i<N;i++)scanf("%d%d%d",&item[i].kind,&item[i].v,&item[i].happy);sort(item,item+N,cmp);memset(d,-1,sizeof(d));int ans=-1,pre=0;/* for(int i=0;i<N;i++)cout<<item[i].kind<<" "<<item[i].v<<endl;cout<<endl;*/for(int i=0;i<N;i++)if(item[i].kind==item[pre].kind){if(item[i].v >= V ) continue;int Max=query(1,V-item[i].v,1,V,1);//cout<<Max<<endl;if(Max!=-1) ans=max(ans,Max+item[i].happy);}else{for(int j=pre;j<i;j++)if(item[j].v<V ) update(item[j].v,item[j].happy,1,V,1);pre=i;i--;}printf("%d\n",ans);}return 0;
}
H 题我真不知道贪心是否正确，就是每次浇水都选择最矮的那棵树浇水，抱着试试看的态度叫了，每次取最优值，竟然1A
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>using namespace std;
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
const int inf=99999999;
const int maxn=100010;
int height[maxn],rat[maxn],d[maxn<<2];void build(int l,int r,int rt)
{if(l==r){d[rt]=height[l];return;}int m=(l+r)>>1;build(lson);build(rson);d[rt]=min(d[rt<<1],d[rt<<1|1]);
}void update(int p,int val,int l,int r,int rt)
{if(l==r){d[rt]=val;return;}int m=(l+r)>>1;if(p<=m) update(p,val,lson);else update(p,val,rson);d[rt]=min(d[rt<<1],d[rt<<1|1]);
}
int query(int l,int r,int rt)
{if(l==r) return l;int m=(l+r)>>1;if(d[rt<<1]<=d[rt<<1|1]) return query(lson);else return query(rson);
}
int main()
{int N,K;while(scanf("%d %d",&N,&K)==2){int minp=1,maxp=1;for(int i=1;i<=N;i++){scanf("%d %d",&height[i],&rat[i]);if(height[i]>height[maxp]) maxp=i;if(height[i]<height[minp]) minp=i;}//cout<<minp<<" "<<maxp<<endl;build(1,N,1);int ans=height[maxp]-height[minp];for(int i=1;i<=K;i++){if(ans==0) break;height[minp]+=rat[minp];update(minp,height[minp],1,N,1);if(height[minp]>height[maxp]) maxp=minp;minp=query(1,N,1);ans=min(ans,height[maxp]-height[minp]);}printf("%d\n",ans);}return 0;
}
然后没做出来题目了，E题是比赛后写的，就是蛋疼的搜索+剪枝
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>using namespace std;
const int maxn=15;
const int inf=99999999;char map[maxn][maxn][maxn];
int fast[maxn][maxn][maxn],n,m,k;
int dir[][2]= {{0,1},{0,-1},{1,0},{-1,0}},qx[maxn*maxn*maxn],qy[maxn*maxn*maxn],qz[maxn*maxn*maxn];
bool vis[maxn][maxn][maxn];
int ans,best;bool isok(int x,int y,int z)
{if(x>=1&&x<=n&&y>=1&&y<=m&&z>=1&z<=m) return 1;return 0;
}
void bfs()
{memset(vis,0,sizeof(vis));int rr=0,l=0;for(int j=1; j<=m; j++)for(int r=1; r<=m; r++)if(map[1][j][r]=='U') qx[rr]=1,qy[rr]=j,qz[rr++]=r,fast[1][j][r]=1,vis[1][j][r]=1;//cout<<rr<<endl;while(l<rr){int curx=qx[l],cury=qy[l],curz=qz[l++],nx,ny,nz;for(int i=0; i<6; i++){if(i<4){nx=curx;ny=cury+dir[i][0];nz=curz+dir[i][1];}else if(i==4) nx=curx+1,ny=cury,nz=curz;else nx=curx-1,ny=cury,nz=curz;if(!isok(nx,ny,nz)) continue;if(i==4&&map[nx][ny][nz]!='U') continue;if(i==5&&map[nx][ny][nz]!='D') continue;if(!vis[nx][ny][nz]){vis[nx][ny][nz]=1;fast[nx][ny][nz]=fast[curx][cury][curz]+1;qx[rr]=nx,qy[rr]=ny,qz[rr++]=nz;}}}
}
void dfs(int x,int y,int z,int tim,int wealth)
{if(ans==best) return;if( n-tim/k+1<=x ) return;if(fast[x][y][z]+tim-1>=n*k) return;if(x==1&&map[1][y][z]=='U'){ans=max(ans,wealth);return;}vis[x][y][z]=1;int nx,ny,nz;for(int i=0; i<6; i++){if(i<4){nx=x;ny=y+dir[i][0];nz=z+dir[i][1];}else if(i==4) nx=x+1,ny=y,nz=z;else nx=x-1,ny=y,nz=z;if(!isok(nx,ny,nz)) continue;if(i==4&&map[x][y][z]!='D') continue;if(i==5&&map[x][y][z]!='U') continue;//cout<<nx<<" "<<ny<<" "<<nz<<" bug "<<endl;if(!vis[nx][ny][nz])dfs(nx,ny,nz,tim+1,wealth+ (map[nx][ny][nz]=='#') );}vis[x][y][z]=0;
}
int main()
{int sx,sy,sz;while(scanf("%d %d %d",&n,&m,&k)==3){best=0;for(int i=1; i<=n; i++)for(int j=1; j<=m; j++)for(int r=1; r<=m; r++){cin>>map[i][j][r];if(map[i][j][r]=='S') sx=i,sy=j,sz=r;fast[i][j][r]=inf;if(map[i][j][r]=='#') best++;}bfs();memset(vis,0,sizeof(vis));ans=-1;dfs(sx,sy,sz,0,0);printf("%d\n",ans);}return 0;
}
这篇关于CSU Monthly 2012 Aug.的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
