蛋疼啊，本次只做出了一道题目。。。渣爆了。。。
妈蛋，，卡题之夜。。比赛结果是1道题，比赛完哗啦哗啦出4道题。。
A acdream1191 Dragon Maze
题意： 给一个迷宫，给出入口坐标和出口坐标，要求从入口到出口的步数尽可能少，如果有多种方案，则要求获得的分数尽可能多，获得的分数为经过的方格的数字之和
思路： bfs求最小步数，每走一步更新一下走到这个格子的最大权值
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int INF = 1e9;
const double eps = 1e-;
const int N = ;
int cas = ; const int dx[] = {,,-,};
const int dy[] = {-,,,}; int g[N][N],w[N][N];
int dep[N][N],exitdep;
bool vis[N][N];
int n,m;
int enx,eny,exx,exy;
int ans; inline bool inside(int x,int y)
{
return x>= && x<n && y>= && y<m;
} void bfs()
{
exitdep = INF;
ans = ;
memset(vis,,sizeof(vis));
memset(w,,sizeof(w));
queue<pii> que;
vis[enx][eny]=;
que.push(make_pair(enx,eny));
dep[enx][eny]=;
w[enx][eny]=g[enx][eny];
while(!que.empty())
{
int x = que.front().first;
int y = que.front().second;
que.pop();
if(dep[x][y]>exitdep) continue;
if(x==exx && y==exy)
{
//ans = max(ans,w[x][y]);
exitdep = dep[x][y];
}
for(int i=;i<;i++)
{
int nx = x+dx[i];
int ny = y+dy[i];
if(!vis[nx][ny] || dep[nx][ny]==dep[x][y]+)
w[nx][ny]=max(w[nx][ny],w[x][y]+g[nx][ny]);
if(vis[nx][ny] || g[nx][ny]==- || !inside(nx,ny)) continue;
vis[nx][ny]=;
dep[nx][ny]=dep[x][y]+;
que.push(make_pair(nx,ny));
}
}
} void run()
{
scanf("%d%d",&n,&m);
int i,j;
scanf("%d%d%d%d",&enx,&eny,&exx,&exy);
for(i=;i<n;i++)
for(j=;j<m;j++)
scanf("%d",&g[i][j]);
bfs();
printf("Case #%d: ",cas++);
if(exitdep==INF) puts("Mission Impossible.");
else printf("%d\n",w[exx][exy]);
} int main()
{
#ifdef LOCAL
freopen("case.txt","r",stdin);
#endif
int _;
scanf("%d",&_);
while(_--)
run();
return ;
}
B acdream1207 qj的寻找爱情之旅
题意：有一个数量为n的序列，给出第一项，求第n项最小的时候是多少，要求满足
① H[i] = (H[i−1] + H[i+1])/2 − 1, 其中 1 < i < N
② Hi ≥ 0
思路： 容易推出 H[i] = 2*H[i-1] - H[i-2] + 2 由于H[1] 题目给出，所以只要知道H[2]就可以一个个推到H[n]，我开始的时候暴力了一下，发现规律，当H[2]小的时候，后面会有某一个数不满足Hi>=0的条件，当H[2]大于某个界限的时候，就会满足Hi>=0而且H[2]越大H[n]就越大，所以只要当H[2]=界限的时候H[n]就是所求最小值 ， 然后就容易想到二分H[2]
坑点： 18行那里，如果我写成h[i]<-eps就wa，写成h[i]<0就AC了，浮点数一直很蛋疼啊。。 以后涉及浮点的话就多尝试一下吧。。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int INF = 1e9;
const double eps = 1e-;
const int N = ;
int cas = ; double h[N],ans;
int n; bool solve()
{
for(int i=;i<=n;i++)
{
h[i]=*h[i-]-h[i-]+;
if(h[i]<)
return ;
}
return ;
} void bs()
{
double l,r;
l=0.0;
r=h[];
while(r-l>eps)
{
h[] = (l+r)/2.0;
if(solve())
{
r=h[];
ans = min(ans,h[n]);
}
else
l=h[];
}
} int main()
{
#ifdef LOCAL
// freopen("case.txt","r",stdin);
#endif
cin>>n>>h[];
ans = 2e9;
bs();
printf("%.2lf\n",ans);
return ;
}
C acdream1208 qj的奇怪宝具
题意：有一串环形柱子，每个柱子有两个值，左边和右边两个值，而且相邻的两个柱子，前面一个柱子的右值是后面一个珠子的左值，两个珠子聚合的时候会获得能量，获得的能力如下计算：设前一个珠子的左值为a，右值（也是后一个珠子的左值）为b，后一个珠子的右值为c，则这两个聚合后获得能量为a*b*c。求能获得的最大能量。
思路：典型的区间dp，矩阵连乘模型，不过这里是环状。解决方法也不难想：把链子复制一份到后面，求一次区间dp，然后答案就是dp[i][i+n-1], 1<=i<=n中的最大值
坑点：OJ问题，如果用多case输入模式就wa，单case就AC
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int INF = 1e9;
const double eps = 1e-;
const int N = ;
int cas = ; int dp[N][N];
int ans;
int a[N],n; void next()
{
int i;
int t=a[];
for(i=;i<n;i++)
a[i]=a[i+];
a[n]=t;
a[n+]=a[];
} void get_dp()
{
memset(dp,,sizeof(dp));
for(int i=;i+<=*n+;i++)
dp[i][i+]=a[i]*a[i+]*a[i+];
int t;
for(int len=;len<=n;len++)
{
for(int i=;i<=*n;i++)
{
int j=i+len;
for(int k=i;k<j;k++)
{
t=dp[i][k]+dp[k+][j]+a[i]*a[k+]*a[j+];
if(t>dp[i][j])
dp[i][j]=t;
}
}
}
} void run()
{
int i;
for(i=;i<=n;i++)
{
scanf("%d",&a[i]);
a[i+n]=a[i];
}
ans = ;
a[*n+]=a[];
get_dp();
for(i=;i+n-<=*n;i++)
ans = max(ans,dp[i][i+n-]);
printf("%d\n",ans);
} int main()
{
#ifdef LOCAL
freopen("case.txt","r",stdin);
#endif
// while(scanf("%d",&n)!=EOF)
scanf("%d",&n);
run();
return ;
}
D acdream1209 qj的招待会
题意：有一些点，用大写字母或者小写字母表示，大写字母表示这个点上有人，小写表示没人。再给出一些有权边，题目求有人的点到qj所在的点的最短距离是多少
思路：改造一下dij就过了吧，在dij的循环里，如果当前点是一个有人点，直接就可以输出答案了
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int INF = 1e9;
const double eps = 1e-;
const int N = ;
int cas = ; // http://acm.zju.edu.cn/mdj2014/contestInfo.do?contestId=2 int id[];
void pre()
{
char c;
for(c=;c<;c++)
if(c>='A' && c<='Z') id[c]=c-'A';
else id[c]=c-'a'+;
} int n=id['z']+;
int m;
int first[N];
int d[N];
bool done[N];
int g[N][N]; void dij(int s)
{
for(int i=;i<n;i++)
d[i]=INF;
d[s]=;
priority_queue<pii,vector<pii>,greater<pii> > q;
memset(done,,sizeof(done));
q.push(make_pair(d[s],s));
while(!q.empty())
{
pii u=q.top(); q.pop();
int x = u.second;
// cout<<x<<endl;
if(x< && x!=id['Z'])
{
printf("%c %d\n",x+'A',d[x]);
return;
}
if(done[x]) continue;
done[x]=;
for(int v=;v<n;v++)
{
if(g[x][v]==- || x==v) continue;
if(d[v]>d[x]+g[x][v])
{
d[v]=d[x]+g[x][v];
q.push(make_pair(d[v],v));
}
}
}
} int cnt; void run()
{
char s1[],s2[];
int i,a,b,c;
cnt=;
memset(g,-,sizeof(g));
for(i=;i<m;i++)
{
scanf("%s%s%d",s1,s2,&c);
a=id[s1[]];
b=id[s2[]];
if(g[a][b]==- || g[a][b]>c)
{
g[a][b]=g[b][a]=c;
}
}
dij(id['Z']);
} int main()
{
#ifdef LOCAL
freopen("case.txt","r",stdin);
#endif
pre();
n=id['z']+;
// cout<<"n="<<n<<endl;
while(scanf("%d",&m)!=EOF)
run();
return ;
}
E 题目都还没看。。看心情补吧。。