AtCoder Beginner Contest 246(current finish)

比赛链接：

https://atcoder.jp/contests/abc246

D - 2-variable Function

题目大意：

给一个 \(n\)，求出最小的 \(x\)，\(x\) 要满足以下两个条件：
1、\(x >= n\)
2、\(x = a^3 + a^2b + ab^2 + b ^ 3\)

思路：

因为 \(n\) 最大为 1e18，\(a\) 和 \(b\) 的最大值就是 1e6，所以想到二分。
先找出 \(a\)，然后二分枚举 \(b\)，就可以了。

代码：

#include 
using namespace std;
#define LL long long
LL n;
LL f(LL x, LL y){
	return (x + y) * (x * x + y * y);
}
int main(){
	cin >> n;
	LL ans = 1e18;
	for (LL i = 0; i <= 1000000; ++ i){
		LL l = 0, r = 1e6;
		while (l < r){
			LL mid = l + r >> 1;
			if (f(i, mid) >= n) r = mid;
			else l = mid + 1;
		}
		ans = min(ans, f(i, l));
	}
	cout << ans << "\n";
	return 0;
}

E - Bishop 2

题目大意：

\(n * n\) 的棋盘，'.' 表示该点上没有士兵，'#'表示该点上有一个士兵，告诉起点和终点，判断主教从起点走到终点最少几步。
移动的规则：从 \((i, j)\) 移动到 \((i \pm d, j \pm d)\) 需要满足移动的斜线上没有士兵。

思路：

因为每个点都有四种移动方式，按照四个方向 \(bfs\)。
若移动到这个点的方向与将要移动的方向一致时，显然，没必要再增加一步，因为原来的移动方式就可以直接抵达这个位置。
若方向不一致，说明是先移动到当前点，再通过一次移动向另一个方向进发。
通过双向队列来 \(bfs\)，\(bfs\) 的时候，每一新入队的点的距离肯定是当前距离 + 1。
所以当移动的方向一致的时候将新的点放入队头，因为距离不变，直到不能移动为止。方向不一致的时候，新的点放到队尾，距离要加 1。

代码：

#include 
using namespace std;
#define LL long long
const int N = 1510;
struct node{
	LL x, y, d;
};
char c;
LL n, sx, sy, ex, ey, v[N][N], dx[] = {-1, 1, -1, 1}, dy[] = {-1, -1, 1, 1}, d[N][N][4], f[N][N][4];
void bfs(){
	deque < node > q;
	memset ( d, 0x3f, sizeof d);
	for (int i = 0; i < 4; ++ i){
		LL nx = sx + dx[i], ny = sy + dy[i];
		if (nx < 1 || ny < 1 || nx > n || ny > n || v[nx][ny]) continue;
		q.push_back( {nx, ny, i});
		d[nx][ny][i] = 1;
	}
	while (q.size()){
		node t = q.front();
		q.pop_front();
		if (t.x == ex && t.y == ey){
			cout << d[ex][ey][t.d] << "\n";
			return;
		}
		if (f[t.x][t.y][t.d]) continue;
		f[t.x][t.y][t.d] = 1;
		LL cd = d[t.x][t.y][t.d];
		for (int i = 0; i < 4; ++ i){
			LL nx = t.x + dx[i], ny = t.y + dy[i];
			if (nx < 1 || ny < 1 || nx > n || ny > n || v[nx][ny]) continue;
			LL nd = cd;
			if (i != t.d) nd++;
			if (d[nx][ny][i] > nd){
				d[nx][ny][i] = nd;
				if (i == t.d) q.push_front({nx, ny, i});
				else q.push_back({nx, ny, i});
			}
		}
	}
	cout << "-1\n";
}
int main(){
	cin >> n >> sx >> sy >> ex >> ey;
	for (int i = 1; i <= n; ++ i){
		for (int j = 1; j <= n; ++ j){
			cin >> c;
			if (c == '#') v[i][j] = 1;
		}
	}
	bfs();
	return 0;
}