AtCoder Grand Contest 044 题解

AtCoder Grand Contest 044

Pay to Win

倒着考虑，记忆化搜索一下即可。

#define ll __int128
const int o[3] = {2,3,5};
const ll inf = 1e18;
ll n, a[3], d;
map<ll, ll> p;

inline ll f(ll x) {
	if (!x) return 0;
	if (p.find(x) != p.end()) return p[x];
	p[x] = d * x;
	for (int i = 0; i < 3; i++) {
		int k = o[i];
		if (!(x % k)) p[x] = min(p[x], f(x / k) + a[i]);
		else {
			int t = x % k;
			p[x] = min(p[x], f(x / k) + a[i] + t * d);
			p[x] = min(p[x], f(x / k + 1) + a[i] + (k - t) * d);
		}
	}
	return p[x];
}

inline void solve() {
	rd(n), rd(a[0], a[1], a[2]), rd(d);
	p.clear();
	print(f(n));
}

int main() {
	int T;
	rd(T);
	while (T--) solve(); 
	return 0;
}

Joker

直接暴力 01BFS 求最短路即可，即每次去掉一个数之后松弛周围需要松弛的点。

这样复杂度看上去是 $\mathcal O(n^4)$ 的，但是仔细分析之后会发现，由于每个点最短路最长也是 $\mathcal O(n)$ 的，而每次松弛必然会变短，因此每个点最多松弛 $\mathcal O(n)$ 次，总时间复杂度为 $\mathcal O(n^3)$ 。

const int N = 507;
const int dx[] = {1, -1, 0, 0};
const int dy[] = {0, 0, 1, -1};
int n, a[N*N], d[N][N], ans;
bool v[N][N];

inline void F(int z, int &x, int &y) {
	x = (z - 1) / n + 1, y = (z - 1) % n + 1;
}

int main() {
	rd(n), rda(a, n * n);
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= n; j++)
			d[i][j] = min(min(i, n + 1 - i), min(j, n + 1 - j)), v[i][j] = 1;
	for (int i = 1, x, y; i <= n * n; i++) {
		F(a[i], x, y);
		ans += --d[x][y], v[x][y] = 0;
		deque<pi> q;
		q.pb(mp(x, y));
		while (q.size()) {
			x = q.front().fi, y = q.front().se, q.pop_front();
			for (int o = 0; o < 4; o++) {
				int X = x + dx[o], Y = y + dy[o];
				if (X < 1 || X > n || Y < 1 || Y > n) continue;
				if (d[X][Y] > d[x][y] + v[X][Y]) {
					d[X][Y] = d[x][y] + v[X][Y];
					if (v[X][Y]) q.pb(mp(X, Y));
					else q.push_front(mp(X, Y));
				}
			}
		}
	}
	print(ans);
	return 0;
}

Strange Dance

基本上就是这题。

反向建 012Trie，S 操作就是交换所有点的 $1,2$ 子树，打个 lazy tag 即可；R 操作就是抽出一条从根开始的全 $2$ 链，将链上的 $0 \to 1$ ， $1 \to 2$ ， $2 \to 0$ 。

const int N = 6377292 + 7;
int n, m, trie[N][3], num[N], tot = 1, ans[N];
bool tag[N];
char s[N];

void build(int p, int d, int o, int x) {
	if (d == n) return num[p] = x, void();
	for (int i = 0; i < 3; i++)
		build(trie[p][i] = ++tot, d + 1, o * 3, x + i * o);
}

inline void spread(int p) {
	if (tag[p]) {
		swap(trie[p][1], trie[p][2]), tag[p] = 0;
		for (int i = 0; i < 3; i++) tag[trie[p][i]] ^= 1;
	}
}

void dfs(int p, int d, int o, int x) {
	if (d == n) return ans[num[p]] = x, void();
	spread(p);
	for (int i = 0; i < 3; i++)
		dfs(trie[p][i], d + 1, o * 3, x + i * o);
}

int main() {
	rd(n), build(1, 0, 1, 0), rds(s, m);
	for (int i = 1; i <= m; i++)
		if (s[i] == 'S') tag[1] ^= 1;
		else {
			int p = 1;
			for (int i = 0; i < n; i++, p = trie[p][0])
				spread(p),
				swap(trie[p][0], trie[p][1]),
				swap(trie[p][0], trie[p][2]);
		}
	dfs(1, 0, 1, 0);
	for (int i = 0, k = pow(3, n); i < k; i++)
		print(ans[i], " \n"[i==k-1]);
	return 0;
}

Guess the Password

交互题。

每次询问可以得到一个串与答案的最长公共子序列。

于是先搞出每个字符有多少个，然后把所有子序列归并起来即可。

const string str = "QWERTYUIOPASDFGHJKLZXCVBNMqwertyuiopasdfghjklzxcvbnm1234567890";
int n;
vector<string> ss;

inline int ask(const string& s) {
	cout << "? " << s << endl;
	int x;
	cin >> x;
	return x;
}

string merge(int l, int r) {
	if (l == r) return ss[l];
	int mid = (l + r) >> 1;
	string sl = merge(l, mid), sr = merge(mid + 1, r), s;
	for (int i = 0, j = 0, k = n - sl.size(); i <= (int)sl.size(); i++) {
		if (i == (int)sl.size()) {
			while (j < (int)sr.size()) s += sr[j++];
			break;
		}
		while (j < (int)sr.size() && ask(s + sr[j] + sl.substr(i)) == k - 1)
			s += sr[j++], --k;
		s += sl[i];
	}
	return s;
}

int main() {
	for (char c : str) {
		string s(128, c);
		int t = 128 - ask(s);
		if (t) ss.pb(s.substr(0, t));
		n += t;
	}
	string ans = merge(0, ss.size() - 1);
	cout << "! " << ans << endl;
	return 0;
}

Random Pawn

首先显然从 $a$ 最大值的位置断开。

发现跟这题很像，区别在于多了个 $b_i$ 。

即现在的式子为 $f_i = \max(a_i, \frac{f_{i-1} + f_{i+1}}{2} - b_i)$ 考虑找到 $c_{1\dots n}$ 满足 $c_i = \frac{c_{i-1}+c_{i+1}}{2} - b_i$ 。

则令 $g_i = f_i - c_i$ ， $v_i = a_i - c_i$ ，就变成了 $g_i = \max(v_i, \frac{g_{i-1} + g_{i+1}}{2})$ 就是上面那题了，求个凸包即可。

const int N = 2e5 + 7;
int n;
__int128 A[N], B[N], a[N], b[N], c[N];
ld ans;
vi s(1, 0);

inline bool pd(int i, int j, int k) {
	return (a[j] - a[i]) * (k - i) <= (a[k] - a[i]) * (j - i);
}

int main() {
	rd(n), rda(A, n), rda(B, n);
	int p = max_element(A + 1, A + n + 1) - A;
	for (int i = p; i <= n; i++) a[i-p] = A[i], b[i-p] = B[i];
	for (int i = 1; i <= p; i++) a[n-p+i] = A[i], b[n-p+i] = B[i];
	for (int i = 2; i <= n; i++)
		c[i] = 2 * (c[i-1] + b[i-1]) - c[i-2], a[i] -= c[i], ans += c[i];
	for (int i = 1; i <= n; i++) {
		while (s.size() > 1u && pd(s[s.size()-2], s.back(), i)) s.pop_back();
		s.pb(i);
	}
	for (ui i = 1; i < s.size(); i++) {
		int l = s[i-1], r = s[i];
		for (int k = l + 1; k < r; k++)
			ans += 1.0L * ((k - l) * a[r] + (r - k) * a[l]) / (r - l);
		ans += a[r];
	}
	printf("%.12Lf\n", ans / n);
	return 0;
}

Name-Preserving Clubs

咕。