ExfJoe's Blog

这场状态还行，这次A相对难度来说算我做的最快的了。不过B题不会，C题m码成n算法细节还想错了直接FST，幸好最后没弃疗rush出了D，保住一波rating。

感觉这场题目质量一般，虽然B这类型题目我确实不会做。

A。根据题意你会发现，对于一个$a_i$，如果相邻两个位置中有某一个数与它相等，那这个位置是永远不会变的。因此这个序列就长成了这样：SSS + 10101 + SSS + 01010 + SSSSS + 1010 + SSSS... 也就是不动点把整个序列分为好几块，每一块都是01交替出现的，同时容易发现每一块左右两个端点经过一次变换后也会固定不动了，因此我们可以前后各扫一遍确定每个位置的变换次数。

#include <bits/stdc++.h>

typedef long long ll;
typedef unsigned int u32;
typedef unsigned long long ull;
typedef long double LD;
typedef std::pair<int, int> PII;
typedef std::vector<int> VI;

#define ST first
#define ND second
#define pb push_back
#define mp std::make_pair
#define ALL(x) x.begin(), x.end()
#define REP(i, a, b) for (int i = (a); i < (b); ++i)
#define PER(i, a, b) for (int i = (a); i > (b); --i)
#define FOR(i, a, b) for (int i = (a); i <= (b); ++i)
#define ROF(i, a, b) for (int i = (a); i >= (b); --i)
	
inline int read()
{
	static char ch;
	bool sgn = false;
	while (ch = getchar(), ch < '0' || ch > '9') if (ch == '-') sgn = true;
	int res = ch - 48;
	while (ch = getchar(), ch >= '0' && ch <= '9') res = res * 10 + ch - 48;
	return sgn ? -res : res;
}

const int N = 5e5 + 5;
int n, a[N], num[N];
bool b[N];

int main()
{
	n = read();
	FOR(i, 1, n) a[i] = read();
	b[1] = b[n] = true;
	REP(i, 2, n)
	{
		if (a[i - 1] == a[i] || a[i + 1] == a[i])
			b[i] = true;
	}
	
	int cur = 0, ans = 0;
	FOR(i, 1, n)
	{
		if (b[i]) cur = 0;
		else num[i] = ++cur;
	}
	cur = 0;
	ROF(i, n, 1)
	{
		if (b[i]) cur = 0;
		else num[i] = std::min(num[i], ++cur);
		ans = std::max(ans, num[i]);
	}
	printf("%d\n", ans);
	FOR(i, 1, n)
		printf("%d ", num[i] & 1 ? a[i] ^ 1 : a[i]);
	return 0;
}

B。开题的时候发现什么相对速度，停课狗表示这是什么鬼= =。考试的时候还以为是与风速的相对速度。

我的做法是先分类讨论：

1.假设前$t$秒内能到达，那么我一定是沿起点到终点的这条直线行走的，因此我们可以在$[0,t]$内二分答案。

2.若前$t$秒内无法到达，此时前$t$秒内就不一定是沿原起点到终点的直线行走，而有可能需要走偏一点利用两段不同的风速来缩短时间。那么我们可以更改一下起点，也就是$(x,y)$->$(x + (v_x - w_x) * t, y + (v_y - w_y) * t)$，然后全程都按照$w$的风速，沿新起点到终点的直线行走。因此依然可以二分答案。根据更改的式子可以发现前$t$秒按$w$风速行走，可以看成未更改起点前按$v$风速行走，所以这个做法是对的。

#include <bits/stdc++.h>

typedef long long ll;
typedef unsigned int u32;
typedef unsigned long long ull;
typedef long double LD;
typedef std::pair<int, int> PII;
typedef std::vector<int> VI;

#define ST first
#define ND second
#define pb push_back
#define mp std::make_pair
#define ALL(x) x.begin(), x.end()
#define REP(i, a, b) for (int i = (a); i < (b); ++i)
#define PER(i, a, b) for (int i = (a); i > (b); --i)
#define FOR(i, a, b) for (int i = (a); i <= (b); ++i)
#define ROF(i, a, b) for (int i = (a); i >= (b); --i)
	
inline int read()
{
	static char ch;
	bool sgn = false;
	while (ch = getchar(), ch < '0' || ch > '9') if (ch == '-') sgn = true;
	int res = ch - 48;
	while (ch = getchar(), ch >= '0' && ch <= '9') res = res * 10 + ch - 48;
	return sgn ? -res : res;
}

double sx, sy, ex, ey, V, T, vx, vy, wx, wy;

inline double sqrDist(const double &lx, const double &ly, const double &rx, const double &ry)
{
	return (rx - lx) * (rx - lx) + (ry - ly) * (ry - ly);
}

inline double norm(const double &lx, const double &ly, const double &rx, const double &ry)
{
	return sqrt(sqrDist(lx, ly, rx, ry));
}

int main()
{
	sx = read(); sy = read();
	ex = read(); ey = read();
	V = read(); T = read();
	vx = read(); vy = read();
	wx = read(); wy = read();
	
	double cx = sx + vx * T, cy = sy + vy * T;
	if (norm(cx, cy, ex, ey) <= V * T)
	{
		double l = 0, r = T;
		FOR(i, 1, 200)
		{
			double mid = (l + r) / 2;
			cx = mid * vx + sx, cy = mid * vy + sy;
			if (norm(cx, cy, ex, ey) <= mid * V)
				r = mid;
			else
				l = mid;
		}
		printf("%.8lf\n", l);
	}
	else
	{
		sx += (vx - wx) * T, sy += (vy - wy) * T;
		double l = T, r = 1e10;
		FOR(i, 1, 1000)
		{
			double mid = (l + r) / 2;
			cx = mid * wx + sx, cy = mid * wy + sy;
			if (norm(cx, cy, ex, ey) <= mid * V)
				r = mid;
			else
				l = mid;
		}
		printf("%.8lf\n", l);
	}
	return 0;
}

C。本来是道很简单的题不过赛中的细节没考虑好。我们对三个国家分别做最短路求出他们要与某个点联通所要花费的最小代价(因为通过国家时代价为0，因此不能简单的BFS)。之后枚举一个交汇点求下总代价，注意交汇点为空地与为国家领土的代价有细节区别。

#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <queue>

#define REP(i, a, b) for (int i = (a); i < (b); ++i)
#define PER(i, a, b) for (int i = (a); i > (b); --i)
#define FOR(i, a, b) for (int i = (a); i <= (b); ++i)
#define ROF(i, a, b) for (int i = (a); i >= (b); --i)

const int N = 1000, INF = 0x1A1A1A1A;
int n, m, dist[4][N][N];
char s[N + 5][N + 5];
int dir[4][2] = {{0, -1}, {0, 1}, {1, 0}, {-1, 0}};
struct node
{
	int dist, x;
	node() {}
	node(const int &_dist, const int &_x) :
		dist(_dist), x(_x) {}
	bool operator < (const node &rhs) const
	{
		return dist > rhs.dist;
	}
};
std::priority_queue<node> PQ;

inline bool canGo(const int &x, const int &y)
{
	return x >= 0 && x < n && y >= 0 && y < m && s[x][y] != '#';
}

inline int Cost(const int &x, const int &y)
{
	return s[x][y] == '.' ? 1 : 0;
}

inline void Dijkstra(const int &d)
{
	while (!PQ.empty())
		PQ.pop();
	memset(dist[d], INF, sizeof(dist[d]));
	
	REP(i, 0, n) REP(j, 0, m)
		if (s[i][j] - '1' == d)
		{
			dist[d][i][j] = 0;
			PQ.push(node(0, i * N + j));
		}
	while (!PQ.empty())
	{
		node Top = PQ.top();
		PQ.pop();
		int x = Top.x / N, y = Top.x % N;
		if (dist[d][x][y] != Top.dist)
			continue;
		REP(k, 0, 4)
		{
			int u = x + dir[k][0], v = y + dir[k][1];
			if (canGo(u, v) && dist[d][x][y] + Cost(u, v) < dist[d][u][v])
				PQ.push(node(dist[d][u][v] = dist[d][x][y] + Cost(u, v), u * N + v));
		}
	}
}

int main()
{
	scanf("%d%d", &n, &m);
	REP(i, 0, n)
		scanf("%s", s[i]);
	REP(k, 0, 3)
		Dijkstra(k);
	
	int ans = INF;
	REP(i, 0, n) REP(j, 0, m)
		if (s[i][j] != '#')
			ans = std::min(ans, dist[0][i][j] + dist[1][i][j] + dist[2][i][j] - (s[i][j] == '.') * 2);
	if (ans == INF)
		puts("-1");
	else
		printf("%d\n", ans);
	return 0;
}

D题比较简单，因此整体来说这场ABCD难度要远低于其他Round。

注意到$n<=150$，并且两个士兵重复交换没有意义，因此最多交换$\mathrm{C}_n^2$次，这样我们可以直接DP了。

$f_{i,j,k}$表示前$i$个士兵中我已经选择了$j$个士兵为最终的前$K$个士兵，用了$k$次的交换的情况下最大的和。转移方程显然。空间上用滚动数组。复杂度O(n^4)。

#include <bits/stdc++.h>

typedef long long ll;
typedef unsigned int u32;
typedef unsigned long long ull;
typedef long double LD;
typedef std::pair<int, int> PII;
typedef std::vector<int> VI;

#define ST first
#define ND second
#define pb push_back
#define mp std::make_pair
#define ALL(x) x.begin(), x.end()
#define REP(i, a, b) for (int i = (a); i < (b); ++i)
#define PER(i, a, b) for (int i = (a); i > (b); --i)
#define FOR(i, a, b) for (int i = (a); i <= (b); ++i)
#define ROF(i, a, b) for (int i = (a); i >= (b); --i)
	
inline int read()
{
	static char ch;
	bool sgn = false;
	while (ch = getchar(), ch < '0' || ch > '9') if (ch == '-') sgn = true;
	int res = ch - 48;
	while (ch = getchar(), ch >= '0' && ch <= '9') res = res * 10 + ch - 48;
	return sgn ? -res : res;
}

const int N = 151;
ll f[2][N][N * N / 2];
int n, m, S, q[N];
	
int main()
{
	n = read(); m = read(); S = read();
	S = std::min(S, n * (n - 1) / 2);
	FOR(i, 1, n)
		q[i] = read();
	memset(f, -1, sizeof(f));
	
	int cur = 0, nxt = 1;
	ll ans = 0x7fffffffffffffffll;
	f[cur][0][0] = 0;
	FOR(i, 1, n)
	{
		FOR(j, 0, m) FOR(k, 0, S)
			if (f[cur][j][k] != -1)
			{
				if (k + (i - j - 1) <= S && j != m)
					if (f[nxt][j + 1][k + i - j - 1] == -1 || f[cur][j][k] + q[i] < f[nxt][j + 1][k + i - j -1])
						f[nxt][j + 1][k + i - j - 1] = f[cur][j][k] + q[i];
				if (f[nxt][j][k] == -1 || f[nxt][j][k] > f[cur][j][k])
					f[nxt][j][k] = f[cur][j][k];
			}
		FOR(j, 0, m) FOR(k, 0, S)
			f[cur][j][k] = -1;
		std::swap(cur, nxt);
	}
	FOR(i, 0, S) if (f[cur][m][i] != -1)
		ans = std::min(ans, f[cur][m][i]);
	std::cout << ans;
	return 0;
}

E还没看题，以后填坑。