挑战程序设计竞赛第二章练习题解
//poj1979
#include <iostream>
#include <sstream>
#include <fstream>
#include <string>
#include <map>
#include <vector>
#include <list>
#include <set>
#include <stack>
#include <queue>
#include <deque>
#include <algorithm>
#include <functional>
#include <iomanip>
#include <limits>
#include <new>
#include <utility>
#include <iterator>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cctype>
#include <cmath>
#include <ctime>
using namespace std;
const int INF = 0x3f3f3f3f;
const double PI = acos(-1.0);
int dx[] = {0, 1, 0, -1}, dy[] = {-1, 0, 1, 0};
const int maxn = 25;
int h, w;
char s[maxn][maxn];
int sx, sy;
bool range(int x, int y)
{
return x >= 0 && x < h && y >= 0 && y < w;
}
int dfs(int x, int y)
{
int ans = 1;
s[x][y] = '#';
for (int i = 0; i < 4; ++i)
if (range(x+dx[i], y+dy[i]) && s[x+dx[i]][y+dy[i]] == '.')
ans += dfs(x+dx[i], y+dy[i]);
return ans;
}
int main()
{
while (cin >> w >> h && (w || h))
{
for (int i = 0; i < h; ++i)
{
scanf("%s", s[i]);
for (int j = 0; j < w; ++j)
if (s[i][j] == '@')
{
sx = i;
sy = j;
}
}
cout << dfs(sx, sy) << endl;
}
return 0;
}
//poj3009
#include <iostream>
#include <sstream>
#include <fstream>
#include <string>
#include <map>
#include <vector>
#include <list>
#include <set>
#include <stack>
#include <queue>
#include <deque>
#include <algorithm>
#include <functional>
#include <iomanip>
#include <limits>
#include <new>
#include <utility>
#include <iterator>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cctype>
#include <cmath>
#include <ctime>
using namespace std;
const int INF = 0x3f3f3f3f;
const double PI = acos(-1.0);
int dx[] = {0, 1, 0, -1}, dy[] = {-1, 0, 1, 0};
const int maxn = 25;
int h, w;
int s[maxn][maxn];
int sx, sy;
bool range(int x, int y)
{
return x >= 0 && x < h && y >= 0 && y < w;
}
int dfs(int x, int y, int cur)
{
if (cur > 10)
return INF;
int ans = INF;
for (int i = 0; i < 4; ++i)
{
int tmpx = x + dx[i], tmpy = y + dy[i];
if (!range(tmpx, tmpy) || s[tmpx][tmpy] == 1)
continue;
while (range(tmpx, tmpy) && (!s[tmpx][tmpy] || s[tmpx][tmpy] == 3))
{
if (s[tmpx][tmpy] == 3)
return cur;
tmpx += dx[i];
tmpy += dy[i];
}
if (!range(tmpx, tmpy))
continue;
s[tmpx][tmpy] = 0;
ans = min(ans, dfs(tmpx-dx[i], tmpy-dy[i], cur+1));
s[tmpx][tmpy] = 1;
}
return ans;
}
int main()
{
while (cin >> w >> h && (w || h))
{
for (int i = 0; i < h; ++i)
for (int j = 0; j < w; ++j)
{
scanf("%d", &s[i][j]);
if (s[i][j] == 2)
{
s[i][j] = 0;
sx = i;
sy = j;
}
}
int ans = dfs(sx, sy, 1);
if (ans == INF)
ans = -1;
cout << ans << endl;
}
return 0;
}
//poj3669
#include <iostream>
#include <sstream>
#include <fstream>
#include <string>
#include <map>
#include <vector>
#include <list>
#include <set>
#include <stack>
#include <queue>
#include <deque>
#include <algorithm>
#include <functional>
#include <iomanip>
#include <limits>
#include <new>
#include <utility>
#include <iterator>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cctype>
#include <cmath>
#include <ctime>
using namespace std;
const int INF = 0x3f3f3f3f;
const double PI = acos(-1.0);
int dx[] = {0, 1, 0, -1, 0}, dy[] = {-1, 0, 1, 0, 0};
const int maxn = 400;
struct Point
{
int x, y, len;
};
int s[maxn][maxn], vis[maxn][maxn];
bool range(int x, int y)
{
return x >= 0 && y >= 0;
}
int bfs()
{
queue<Point> q;
q.push({0, 0, 0});
vis[0][0] = 1;
while (!q.empty())
{
Point p = q.front();
q.pop();
int x = p.x, y = p.y;
if (s[x][y] == INF)
return p.len;
if (s[x][y] <= p.len)
continue;
for (int i = 0; i < 5; ++i)
{
int tx = x + dx[i], ty = y + dy[i];
if (range(tx, ty) && !vis[tx][ty])
{
vis[tx][ty] = 1;
q.push({tx, ty, p.len+1});
}
}
}
return -1;
}
int main()
{
for (int i = 0; i < 400; ++i)
for (int j = 0; j < 400; ++j)
{
s[i][j] = INF;
vis[i][j] = 0;
}
int m;
cin >> m;
while (m--)
{
int x, y, t;
scanf("%d%d%d", &x, &y, &t);
for (int i = 0; i < 5; ++i)
if (range(x+dx[i], y+dy[i]) && s[x+dx[i]][y+dy[i]] > t)
s[x+dx[i]][y+dy[i]] = t;
}
cout << bfs() << endl;
return 0;
}
//poj2718
#include <iostream>
#include <sstream>
#include <fstream>
#include <string>
#include <map>
#include <vector>
#include <list>
#include <set>
#include <stack>
#include <queue>
#include <deque>
#include <algorithm>
#include <functional>
#include <iomanip>
#include <limits>
#include <new>
#include <utility>
#include <iterator>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cctype>
#include <cmath>
#include <ctime>
using namespace std;
const int INF = 0x3f3f3f3f;
const double PI = acos(-1.0);
int dx[] = {0, 1, 0, -1, 0}, dy[] = {-1, 0, 1, 0, 0};
const int maxn = 400;
int ans, n;
int num[10], vis[10];
void solve(int a)
{
int tmp[10], cnt = 0;
for (int i = 0; i < n; ++i)
if (!vis[i])
tmp[cnt++] = num[i];
do
{
if (!tmp[0] && cnt > 1)
continue;
int b = tmp[0];
for (int i = 1; i < cnt; ++i)
b = b * 10 + tmp[i];
ans = min(ans, abs(a-b));
} while (next_permutation(tmp, tmp+cnt));
}
void dfs(int cur, int res)
{
if (cur == n/2)
{
solve(res);
return;
}
for (int i = 0; i < n; ++i)
if (!vis[i])
{
if (!cur && !i && n > 2)
continue;
vis[i] = 1;
dfs(cur+1, res*10+num[i]);
vis[i] = 0;
}
}
int main()
{
int kase;
cin >> kase;
getchar();
while (kase--)
{
ans = INF;
memset(vis, 0, sizeof(vis));
char ch;
n = 0;
while (scanf("%c", &ch) == 1 && ch != '\n')
if (ch != ' ')
num[n++] = ch - '0';
dfs(0, 0);
cout << ans << endl;
}
return 0;
}
//poj3187
#include <iostream>
#include <sstream>
#include <fstream>
#include <string>
#include <map>
#include <vector>
#include <list>
#include <set>
#include <stack>
#include <queue>
#include <deque>
#include <algorithm>
#include <functional>
#include <iomanip>
#include <limits>
#include <new>
#include <utility>
#include <iterator>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cctype>
#include <cmath>
#include <ctime>
using namespace std;
const int INF = 0x3f3f3f3f;
const double PI = acos(-1.0);
int dx[] = {0, 1, 0, -1}, dy[] = {-1, 0, 1, 0};
const int maxn = 10000010;
int main()
{
int n, sum;
cin >> n >> sum;
int s[15];
for (int i = 0; i < n; ++i)
s[i] = i + 1;
do
{
int t[15];
for (int i = 0; i < n; ++i)
t[i] = s[i];
int tmp = n;
while (tmp-- > 1)
for (int i = 0; i < tmp; ++i)
t[i] += t[i+1];
if (t[0] == sum)
{
for (int i = 0; i < n-1; ++i)
printf("%d ", s[i]);
printf("%d\n", s[n-1]);
break;
}
} while (next_permutation(s, s+n));
return 0;
}
//poj3050
#include <iostream>
#include <sstream>
#include <fstream>
#include <string>
#include <map>
#include <vector>
#include <list>
#include <set>
#include <stack>
#include <queue>
#include <deque>
#include <algorithm>
#include <functional>
#include <iomanip>
#include <limits>
#include <new>
#include <utility>
#include <iterator>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cctype>
#include <cmath>
#include <ctime>
using namespace std;
const int INF = 0x3f3f3f3f;
const double PI = acos(-1.0);
int dx[] = {0, 1, 0, -1}, dy[] = {-1, 0, 1, 0};
const int maxn = 10000010;
int s[5][5];
set<int> m;
bool range(int x, int y)
{
return x >= 0 && x < 5 && y >= 0 && y < 5;
}
void dfs(int x, int y, int res, int cur)
{
if (cur == 5)
{
m.insert(res);
return;
}
for (int i = 0; i < 4; ++i)
{
int tx = x + dx[i], ty = y + dy[i];
if (range(tx, ty))
{
int tmp = res * 10 + s[tx][ty];
dfs(tx, ty, tmp, cur+1);
}
}
}
int main()
{
for (int i = 0; i < 5; ++i)
for (int j = 0; j < 5; ++j)
scanf("%d", &s[i][j]);
for (int i = 0; i < 5; ++i)
for (int j = 0; j < 5; ++j)
dfs(i, j, s[i][j], 0);
int ans = 0;
for (set<int>::iterator it = m.begin(); it != m.end(); ++it)
ans++;
cout << ans << endl;
return 0;
}
//poj2376
#include <iostream>
#include <sstream>
#include <fstream>
#include <string>
#include <map>
#include <vector>
#include <list>
#include <set>
#include <stack>
#include <queue>
#include <deque>
#include <algorithm>
#include <functional>
#include <iomanip>
#include <limits>
#include <new>
#include <utility>
#include <iterator>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cctype>
#include <cmath>
#include <ctime>
using namespace std;
const int INF = 0x3f3f3f3f;
const double PI = acos(-1.0);
int dx[] = {0, 1, 0, -1}, dy[] = {-1, 0, 1, 0};
const int maxn = 25010;
struct cow
{
int start, over;
bool operator < (const cow& b) const
{
if (start != b.start)
return start < b.start;
return over > b.over;
}
};
cow s[maxn];
int main()
{
int n, t;
scanf("%d%d", &n, &t);
for (int i = 0; i < n; ++i)
scanf("%d%d", &s[i].start, &s[i].over);
sort(s, s+n);
int ans = 0, last = 1, tmp = 0;
while (last <= t)
{
if (tmp == n || s[tmp].start > last)
break;
int tmplast = 0;
for (int i = tmp; i < n; ++i)
{
if (s[i].start > last)
{
tmp = i;
break;
}
if (tmplast < s[i].over)
tmplast = s[i].over;
tmp = i + 1;
}
ans++;
last = tmplast + 1;
}
if (last <= t)
ans = -1;
cout << ans << endl;
return 0;
}
//poj1328
#include <iostream>
#include <sstream>
#include <fstream>
#include <string>
#include <map>
#include <vector>
#include <list>
#include <set>
#include <stack>
#include <queue>
#include <deque>
#include <algorithm>
#include <functional>
#include <iomanip>
#include <limits>
#include <new>
#include <utility>
#include <iterator>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cctype>
#include <cmath>
#include <ctime>
using namespace std;
const int inf = 0x3f3f3f3f;
const double pi = acos(-1.0);
const double eps = 1e-8;
int dx[] = {0, 1, 0, -1}, dy[] = {-1, 0, 1, 0};
const int maxn = 25010;
struct island
{
double left, right;
bool operator < (const island& b) const
{
if (right != b.right)
return right < b.right;
return left > b.left;
}
};
int main()
{
int n, d, kase = 1;
while (scanf("%d%d", &n, &d) == 2 && (n || d))
{
island s[1010];
int can = 1;
for (int i = 0; i < n; ++i)
{
int x, y;
scanf("%d%d", &x, &y);
if (abs(y) > d)
{
can = 0;
continue;
}
s[i].left = x - sqrt(1.0*d*d-y*y);
s[i].right = x + sqrt(1.0*d*d-y*y);
}
if (!can)
{
printf("Case %d: -1\n", kase++);
continue;
}
sort(s, s+n);
int ans = 1;
island tmp = s[0];
for (int i = 1; i < n; ++i)
if (s[i].left > tmp.right)
{
++ans;
tmp = s[i];
}
printf("Case %d: %d\n", kase++, ans);
}
return 0;
}
算法码上来 文章被收录于专栏
公众号「算法码上来」。godweiyang带你学习算法，不管是编程算法，还是深度学习、自然语言处理算法都一网打尽，更有各种计算机新鲜知识和你分享。别急，算法码上来。
投递美团等公司10个岗位
哔哩哔哩公司氛围 95人发布