http://acm./contests/contest_show.php?cid=392
我们还是很水啊。。。。加油
感觉今天的题都挺难的，我和von一起组队做的，就出了两道题。郁闷啊。。
A:没看
B:前5道是von负责的，由于前几天做过一道优先队列的bfs所以von很快就1Y了。orz..赛后自己也敲了一下1Y：
代码：
View Code
#include <cstdio>
#include <cstring>
#include <iostream>
#include <queue>
#define maxn 507
using namespace std;
struct node
{
int x,y;
int num;
friend bool operator < (const node &a,const node &b)
{
return a.num > b.num;
}
};
int h,w,mark,sx,sy;
char str[maxn][maxn];
bool vt[maxn][maxn];
int f[4][2] = {{1,0},{-1,0},{0,1},{0,-1}};
priority_queue<node>q;
int bfs(int sx,int sy)
{
node p;
p.x = sx; p.y = sy;
p.num = 1;
while (!q.empty()) q.pop();
q.push(p);
vt[p.x][p.y] = true;
while (!q.empty())
{
node cur;
cur = q.top(); q.pop();
if (cur.x == 0 || cur.x == h -1 || cur.y == 0 || cur.y == w -1)
{
return cur.num;
}
for (int i = 0; i < 4; ++i)
{
p.x = cur.x + f[i][0];
p.y = cur.y + f[i][1];
if (p.x >= 0 && p.x < h && p.y >= 0 && p.y < w && !vt[p.x][p.y] && str[p.x][p.y] != '#')
{
vt[p.x][p.y] = true;
p.num = cur.num + 1;
if (str[p.x][p.y] == '@') p.num += mark;
q.push(p);
}
}
}
}
int main()
{
int i,j,t;
scanf("%d",&t);
while (t--)
{
memset(vt,false,sizeof(vt));
scanf("%d%d%d",&h,&w,&mark);
for (i = 0; i < h; ++i)
{
scanf("%s",str[i]);
for (j = 0; j < w; ++j)
{
if (str[i][j] == 'S')
{
sx = i; sy = j;
}
}
}
int ans = bfs(sx,sy);
printf("%d\n",ans);
}
return 0;
}
其他几道都木解出来。。。。。更新中。。。
G：一道博弈论的题目，一看到它就郁闷了，因为博弈论什么的都忘得差不多了。研究了很长时间还是没找出规律来。赛后问了问日华，再参考了一下代码才明白的。。
博弈论：1：sg函数解题。2：p/n分析找规律解题。这道题属于p/n分析找规律解题。
p必败点：其所有的后继点都是必胜点。n必胜点:其后继中存在必败点。。。。
分析1到k-1 在这个范围里面只能取一枚硬币，故有0--k-1 p,n,p,n,p,n.........当取得k时可以有两种取法1或者k能够到达0必败点所以k这点是必胜点。一次往后退规律。发现
当k为奇数时 所有的情况是0--s p,n,p,n,p,n.........
当k为偶数时有
0-k p,n,p,n,p,n......n,n
k+1 - 2*k+1 p,n,p,n,p,...n,n
......
贴一个日华的打表找规律的代码，orz
View Code
本题代码
View Code
J:开始没注意到这道题，看着有人a了这道就来看了，题很长可是题意很简单就是给你直角三角形的一条直角边，求最小的斜边和另一条直角边。。给的数据很大，两个循环枚举肯定TLE..
我就在那想三角形的性质：三边关系在枚举中剪枝行吗？ 不行。。又画了画图，看着斜边无限的增大，另一条直角边也无限的增大郁闷了。。
忽然就想到了z^2 - x^2 = y^2 可以把y^2分解成两个数的乘积，z+x = a; z - x = b; a>b&& z >x
View Code
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#define inf 0x7fffffff
using namespace std;
int main()
{
int N,i,a,b;
double ansx,ansy,z,x;
int t;
scanf("%d",&t);
while (t--)
{
bool flag = false;
ansx = inf;
ansy = inf;
scanf("%d",&N);
for (i = 1; i <= sqrt(1.0*N); ++i)
{
if (N%i == 0)
{
a = N/i;
b = i;
z = 1.0*(a + b)/2.0;
int tmp = (int)z;//z保证是大于0整数
if (tmp != z) continue;
x = z - min(a,b);
if (x >= 0)//x保证是大于0整数
{
flag = true;
if (ansx > x && ansy > z)
{
ansx = x; ansy = z;
}
}
}
}
if (flag)
printf("%.0lf %.0lf\n",ansx,ansy);
else
printf("IMPOSSIBLE\n");
}
return 0;
}
