上午做了下昨天腾讯的比赛，感觉比前一天的难吧，只做出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 long
using 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 110
using 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 2100000000
using 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骑士问题
暂时未过，只会暴力，貌似会超时，以后再补。