2013腾讯编程马拉松第5场（3.25）部分题解
上午做了下昨天腾讯的比赛，感觉比前一天的难吧，只做出4道，最后一题老超时，晚上再看看吧，下面是我的代码+想法。
http://acm.hdu.edu.cn/showproblem.php?pid=4525
威威猫系列故事——吃鸡腿A:水题，设威威猫的原始体重为x，我们很容易就可以得到第n天威威猫的体重就是 (k1+k2)^n*x，然后就是与K比较了，当x>k时输出0，否则当（k1+k2）==0或-1或1，不然的话，我们依次求每一天威威猫的体重然后再和k比较即可，因为k可能很大，所以直接算(k1+k2)^n*x的话可能会与越界（超long long），所以我们换一种方式比较，改乘为除即可。下面是代码：
#include <iostream>#include <string.h>#include <stdio.h>#include <algorithm>#define ll long longusing namespace std;int main(){ //freopen("dd.txt","r",stdin); ll k,n,k1,k2; int ncase,x,time=1; scanf("%d",&ncase); while(ncase--) { printf("Case #%d: ",time++); scanf("%I64d%I64d%I64d%I64d",&n,&k1,&k2,&k); ll tmp=k1+k2,sum=0; for(int i=1;i<=n;i++) { scanf("%d",&x); sum+=x; } if(sum>k) printf("0\n"); else { if(tmp==1||tmp==-1||tmp==0) printf("inf\n"); else { int num=1,ans=0; k=k/sum; if(tmp<0) { tmp*=tmp; num=2; } long long t=1; while(1) { if(k/t<tmp) { ans+=num; break; } t*=tmp; ans+=num; } printf("%d\n",ans); } } } return 0;}
http://acm.hdu.edu.cn/showproblem.php?pid=4526
B：很简单的DP题，我们设dp[i][j]表示在第i辆过车后还剩j人时的最小花费，则若第i两车有x个座位，且它与前一辆车的时间间隔为t，则当第i辆车来时，我们可以选择不上,也就是 dp[i-1][j]+j*t,或者上m人（1<=m<=x），也就是
dp[i-1][j+m]+D+(j+m)*t,我们取它们中的最小值，这里要注意的是对于dp[i][j]有些j可能没有意义，也就是不可能达到，（比如前i辆车总共就y个座位，则我们不可能达到dp[i][n-y-1]等等）则我们一开始将所有的dp赋值为无穷大，
则更新的时候不会受到无效解的影响。初始化当然把dp[0][n]==0，我们最后求dp[k][0]。若dp[k][0]为无穷大则无解，否则输出dp[k][0]。代码如下：
#include <iostream>#include <string.h>#include <stdio.h>#include <algorithm>#define maxn 110using namespace std;int dp[maxn][maxn],sum[maxn];struct car{ int t; int num;}c[maxn];int min(int a,int b){ return a<b?a:b;}int max(int a,int b){ return a>b?a:b;}int main(){ //freopen("dd.txt","r",stdin); int ncase; scanf("%d",&ncase); while(ncase--) { int n,k,d,s,i,j; scanf("%d%d%d%d",&n,&k,&d,&s); memset(dp,1,sizeof(dp)); int inf=dp[0][0]; sum[0]=0; for(i=1;i<=k;i++) { scanf("%d%d",&c[i].t,&c[i].num); sum[i]=sum[i-1]+c[i].num; } dp[0][n]=0; c[0].t=0; for(i=1;i<=k;i++) { int tmp=max(0,n-sum[i]),num=c[i].num,t=c[i].t-c[i-1].t; for(j=n;j>=tmp;j--) { int m; dp[i][j]=min(dp[i-1][j]+j*t,dp[i-1][j+num]+t*(j+num)+d); for(m=1;m<num;m++) { dp[i][j]=min(dp[i][j],dp[i-1][j+m]+t*(j+m)+d); } } } if(dp[k][0]==inf) printf("impossible\n"); else printf("%d\n",dp[k][0]); } return 0;}http://acm.hdu.edu.cn/showproblem.php?pid=4527
小明系列故事——玩转十滴水C：
思路：模拟题，要注意两个水珠同时到达一个4级水珠的情况，我用广搜过的，反正就是根据题意模拟，没什么好说的。代码如下：
#include <iostream>#include <string.h>#include <stdio.h>#include <algorithm>#include <queue>using namespace std;int bo[7][7];int dir[4][2]={1,0,0,1,-1,0,0,-1};int vis[7][7];int check(int x,int y){ if(x<1||y<1||x>6||y>6) return 0; return 1;}void solve(int x,int y){ queue<int> q; bo[x][y]++; if(bo[x][y]>4) { vis[x][y]=0; q.push(x); q.push(y); q.push(0);//时间 q.push(-1);//方向 } int i; while(!q.empty()) { int xx=q.front();q.pop(); int yy=q.front();q.pop(); int tt=q.front();q.pop(); int d=q.front();q.pop(); if(d==-1) bo[xx][yy]=0; for(i=0;i<4;i++) { if(d!=-1&&d!=i) continue; int x1=xx+dir[i][0],y1=yy+dir[i][1]; if(check(x1,y1)) { if(bo[x1][y1]==0) { q.push(x1);q.push(y1);q.push(tt+1);q.push(i); } else if(bo[x1][y1]<4) { bo[x1][y1]++; } else if(bo[x1][y1]==4) { bo[x1][y1]++; vis[x1][y1]=tt+1; q.push(x1);q.push(y1);q.push(tt+1);q.push(-1); } else { if(tt+1<=vis[x1][y1]) bo[x1][y1]++; else { q.push(x1);q.push(y1);q.push(tt+1);q.push(i); } } } } }}int main(){ //freopen("dd.txt","r",stdin); while(scanf("%d",&bo[1][1])!=EOF) { int i,j,n,x,y; for(i=1;i<=6;i++) { for(j=1;j<=6;j++) { if(i==1&&j==1) continue; scanf("%d",&bo[i][j]); } } scanf("%d",&n); while(n--) { scanf("%d%d",&x,&y); memset(vis,-1,sizeof(vis)); solve(x,y); } for(i=1;i<=6;i++) { for(j=1;j<=6;j++) { if(j!=6) printf("%d ",bo[i][j]); else printf("%d",bo[i][j]); } printf("\n"); } printf("\n"); } return 0;}http://acm.hdu.edu.cn/showproblem.php?pid=4528
小明系列故事——捉迷藏D:搜索题，明显的宽度搜索，设dist[x][y][0]表示当前没看到大明和二明到达(x,y)时的最早时间，dp[x][y][1]表示看到大明没看到二明的最早时间，dp[x][y][2]表示看到二明而没看到大明的最早时间。我们首先预处理一下能看到大明和能看到二明的位置，然后就搜就是了。这里要注意的是我们不能穿过一个人，也就是我们要把大明和二明当做障碍物，具体看样例3。代码如下：
#include <iostream>#include <string.h>#include <stdio.h>#include <algorithm>#include <queue>#define maxn 110#define inf 2100000000using namespace std;int dir[4][2]={1,0,0,1,-1,0,0,-1};int n,m;char bo[maxn][maxn];int check(int x,int y){ if(x<1||y<1||x>n||y>m||bo[x][y]!='.') return 0; return 1;}int see[2][maxn][maxn];int dist[maxn][maxn][3];void init(int x,int y,int t){ int i; for(i=0;i<4;i++) { int xx=x+dir[i][0],yy=y+dir[i][1]; while(check(xx,yy)) { see[t][xx][yy]=1; xx+=dir[i][0]; yy+=dir[i][1]; } }}int bfs(int x,int y){ queue<int> q; dist[x][y][0]=0; int t,i; if(see[0][x][y]&&see[1][x][y]) return 0; q.push(x); q.push(y); q.push(0); while(!q.empty()) { int xx=q.front();q.pop(); int yy=q.front();q.pop(); int tt=q.front();q.pop(); int len=dist[xx][yy][tt]; //printf("%d %d\n",xx,yy); if(see[0][xx][yy]) { if(tt==2) return len; tt=1; } if(see[1][xx][yy]) { if(tt==1) return len; tt=2; } for(i=0;i<4;i++) { int x1=xx+dir[i][0],y1=yy+dir[i][1]; if(check(x1,y1)&&dist[x1][y1][tt]==-1) { dist[x1][y1][tt]=len+1; q.push(x1); q.push(y1); q.push(tt); } } } return inf;}int main(){ //freopen("dd.txt","r",stdin); int ncase,time=0; scanf("%d",&ncase); while(ncase--) { printf("Case %d:\n",++time); int t,i,j; scanf("%d%d%d",&n,&m,&t); for(i=1;i<=n;i++) scanf("%s",bo[i]+1); int sx,sy,x1,x2,y1,y2; memset(see,0,sizeof(see)); for(i=1;i<=n;i++) { for(j=1;j<=m;j++) { if(bo[i][j]=='D') x1=i,y1=j; if(bo[i][j]=='E') x2=i,y2=j; if(bo[i][j]=='S') { bo[i][j]='.'; sx=i,sy=j; } } } memset(dist,-1,sizeof(dist)); init(x1,y1,0); init(x2,y2,1); //printf("f"); int ans=bfs(sx,sy); if(ans>t) printf("-1\n"); else printf("%d\n",ans); } return 0;}
http://acm.hdu.edu.cn/showproblem.php?pid=4529
郑厂长系列故事——N骑士问题暂时未过，只会暴力，貌似会超时，以后再补。