专栏文章

P10068 [CCO 2023] Line Town

EEuphoricStar
P10068题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@min3au2b
此快照首次捕获于
2025/12/01 19:52
3 个月前
此快照最后确认于
2025/12/01 19:52
3 个月前
查看原文
这题的特殊性质很有引导性，会了全部特殊性质基本就会正解了。
首先考虑 ∣ai∣|a_i| 互不相同怎么做。
发现一个数最后的符号只和它移动距离的奇偶性和原来的符号有关，并且最终序列的绝对值是先递减后递增。
那么自然考虑，按绝对值从大到小，在序列两端填数。设 fi,0/1f_{i, 0/1} 表示考虑了绝对值 ≥i\ge i 的数，序列左端填了偶数个 / 奇数个数，的最小交换次数。交换次数就是它在原序列中左边或右边（左边还是右边取决于它被填到最左边还是最右边）比它小的数的个数。时间复杂度 O(nlog⁡n)O(n \log n)，获得 725\frac{7}{25} 的高分。
再考虑 ∣ai∣≤1|a_i| \le 1 怎么做。容易想到枚举最终有 ii 个 00 换到最左边，但是这样仍然不好直接写出操作次数，因为交换就会变号比较麻烦。
那么有一个处理翻转相邻两位奇偶性的、比较经典的 trick 是翻转奇数位，到这题就是翻转奇数位的符号。这样的好处是操作变成直接交换相邻两个数，不用变号。
现在最终的状态形如 1,−1,⋯1,−1,0,⋯ ,0,−1,1,⋯ ,−1,11, -1, \cdots 1, -1, 0, \cdots, 0, -1, 1, \cdots, -1, 1，其中最后一位是 11 还是 −1-1 取决于 nn 的奇偶性。那么我们枚举了 ii 之后，序列中每一个 11 和 −1-1 的最终相对位置（在所有 ±1\pm 1 中是从左往右第几个）都能算出来。
那么算交换次数就是 ±1\pm 1 和 00 的交换次数，加上 ±1\pm 1 内部的交换次数。±1\pm 1 和 00 的交换次数等于一个 ±1\pm 1 左边或右边（左边还是右边取决于它被填到最左边还是最右边）00 的个数，±1\pm 1 内部的交换次数就是每个 ±1\pm 1 原来的相对位置减去最终的相对位置绝对值之和。
不难通过一些预处理做到 O(n)O(n)。拼上 ∣ai∣|a_i| 互不相同的做法，获得 2025\frac{20}{25} 的高分。
那么做到这一步其实可以发现正解就是上面两个做法拼起来。仍然是按 ∣ai∣|a_i| 从大到小 DP，设当前考虑的绝对值是 kk，把 kk 看成 11，−k-k 看成 −1-1，绝对值 <k< k 的数看成 00，然后套用 ∣ai∣≤1|a_i| \le 1 的做法即可。
实现时要特别小心奇偶性的处理。
最终总时间复杂度 O(nlog⁡n)O(n \log n)，但是除了离散化和计算每个数左边（和右边）比它小的数的个数时间复杂度是 O(nlog⁡n)O(n \log n) 之外，其他的部分都是 O(n)O(n) 的。
代码CPP
// Problem: P10068 [CCO 2023] Line Town
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P10068
// Memory Limit: 1024 MB
// Time Limit: 2000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>
#define pb emplace_back
#define fst first
#define scd second
#define mkp make_pair
#define mems(a, x) memset((a), (x), sizeof(a))

using namespace std;
using ll = long long;
using ull = unsigned long long;
using db = double;
using ldb = long double;
using pii = pair<int, int>;
using pll = pair<ll, ll>;

namespace IO {
	const int maxn = 1 << 20;
	
	char ibuf[maxn], *iS, *iT, obuf[maxn], *oS = obuf;

	inline char gc() {
		return (iS == iT ? iT = (iS = ibuf) + fread(ibuf, 1, maxn, stdin), (iS == iT ? EOF : *iS++) : *iS++);
	}

	template<typename T = int>
	inline T read() {
		char c = gc();
		T x = 0;
		bool f = 0;
		while (c < '0' || c > '9') {
			f |= (c == '-');
			c = gc();
		}
		while (c >= '0' && c <= '9') {
			x = (x << 1) + (x << 3) + (c ^ 48);
			c = gc();
		}
		return f ? ~(x - 1) : x;
	}
	
	inline int reads(char *s) {
		char c = gc();
		int len = 0;
		while (isspace(c)) {
			c = gc();
		}
		while (!isspace(c) && c != -1) {
			s[len++] = c;
			c = gc();
		}
		s[len] = '\0';
		return len;
	}
	
	inline string reads() {
		char c = gc();
		string s;
		while (isspace(c)) {
			c = gc();
		}
		while (!isspace(c) && c != -1) {
			s += c;
			c = gc();
		}
		return s;
	}

	inline void flush() {
		fwrite(obuf, 1, oS - obuf, stdout);
		oS = obuf;
	}
	
	struct Flusher {
		~Flusher() {
			flush();
		}
	} AutoFlush;

	inline void pc(char ch) {
		if (oS == obuf + maxn) {
			flush();
		}
		*oS++ = ch;
	}
	
	inline void write(char *s) {
		for (int i = 0; s[i]; ++i) {
			pc(s[i]);
		}
	}
	
	inline void write(const char *s) {
		for (int i = 0; s[i]; ++i) {
			pc(s[i]);
		}
	}

	template<typename T>
	inline void write(T x) {
		static char stk[64], *tp = stk;
		if (x < 0) {
			x = ~(x - 1);
			pc('-');
		}
		do {
			*tp++ = x % 10;
			x /= 10;
		} while (x);
		while (tp != stk) {
			pc((*--tp) | 48);
		}
	}
	
	template<typename T>
	inline void writesp(T x) {
		write(x);
		pc(' ');
	}
	
	template<typename T>
	inline void writeln(T x) {
		write(x);
		pc('\n');
	}
}

using IO::read;
using IO::reads;
using IO::write;
using IO::pc;
using IO::writesp;
using IO::writeln;

const int maxn = 500100;
const ll inf = 0x3f3f3f3f3f3f3f3fLL;

int n, a[maxn], lsh[maxn], tot, ls[maxn], rs[maxn], b[maxn], c[maxn], d[maxn];
ll f1[maxn], f2[maxn], f3[maxn], f4[maxn], pre[2][maxn], suf[2][maxn];
bool vis[maxn];
vector<int> ap[maxn];

namespace BIT {
	int c[maxn];
	
	inline void update(int x, int d) {
		for (int i = x; i <= tot; i += (i & (-i))) {
			c[i] += d;
		}
	}
	
	inline int query(int x) {
		int res = 0;
		for (int i = x; i; i -= (i & (-i))) {
			res += c[i];
		}
		return res;
	}
}

void solve() {
	n = read();
	for (int i = 1; i <= n; ++i) {
		a[i] = read();
		if (a[i] < 0) {
			a[i] = -a[i];
			vis[i] = 1;
		}
		lsh[++tot] = a[i];
	}
	sort(lsh + 1, lsh + tot + 1);
	tot = unique(lsh + 1, lsh + tot + 1) - lsh - 1;
	for (int i = 1; i <= n; ++i) {
		a[i] = lower_bound(lsh + 1, lsh + tot + 1, a[i]) - lsh;
		++b[a[i]];
	}
	for (int i = 1; i <= tot; ++i) {
		b[i] += b[i - 1];
	}
	for (int i = 1; i <= n; ++i) {
		ls[i] = BIT::query(a[i] - 1);
		rs[i] = b[a[i] - 1] - ls[i];
		BIT::update(a[i], 1);
	}
	mems(b, 0);
	for (int i = 1; i <= n; ++i) {
		if (vis[i] ^ (i & 1)) {
			a[i] = -a[i];
		}
		ap[abs(a[i])].pb(i);
	}
	ll f[2] = {0, inf};
	int r = n;
	for (int k = tot; k; --k) {
		if (lsh[k] == 0) {
			break;
		}
		ll g[2] = {inf, inf};
		int m1 = 0, m2 = 0, cnt = 0;
		for (int i : ap[k]) {
			++cnt;
			if (a[i] > 0) {
				b[++m1] = i;
				d[i] = cnt;
			} else {
				c[++m2] = i;
				d[i] = cnt;
			}
		}
		for (int i = 1; i <= m1; ++i) {
			f1[i] = f1[i - 1] + ls[b[i]];
			f2[i] = f2[i - 1] + rs[b[i]];
			b[i] = d[b[i]];
		}
		for (int i = 1; i <= m2; ++i) {
			f3[i] = f3[i - 1] + ls[c[i]];
			f4[i] = f4[i - 1] + rs[c[i]];
			c[i] = d[c[i]];
		}
		for (int j = 0; j <= 1; ++j) {
			for (int i = 1, p1 = 1, p2 = 1; i <= m1 + m2; ++i) {
				pre[j][i] = pre[j][i - 1];
				if ((j ^ i) & 1) {
					pre[j][i] += abs(b[p1++] - i);
				} else {
					pre[j][i] += abs(c[p2++] - i);
				}
			}
		}
		suf[0][m1 + m2 + 1] = suf[1][m1 + m2 + 1] = 0;
		for (int j = 0; j <= 1; ++j) {
			for (int i = m1 + m2, o = (r & 1) ^ j, p1 = m1, p2 = m2; i; --i, o ^= 1) {
				suf[j][i] = suf[j][i + 1];
				if (o) {
					suf[j][i] += abs(c[p2--] - i);
				} else {
					suf[j][i] += abs(b[p1--] - i);
				}
			}
		}
		for (int j = 0; j <= 1; ++j) {
			for (int i = 0; i <= m1 + m2; ++i) {
				int x = (i + 1) >> 1, y = (i >> 1);
				if (j) {
					swap(x, y);
				}
				int rx = m1 - x, ry = m2 - y;
				if (rx < 0 || ry < 0) {
					continue;
				}
				if ((r ^ j) & 1) {
					if (rx != ry && rx + 1 != ry) {
						continue;
					}
				} else {
					if (rx != ry && rx != ry + 1) {
						continue;
					}
				}
				g[(i & 1) ^ j] = min(g[(i & 1) ^ j], f[j] + ((((f1[x] + f3[y] + f2[m1] - f2[x] + f4[m2] - f4[y]) << 1) + pre[j][i] + suf[j][i + 1]) >> 1));
			}
		}
		f[0] = g[0];
		f[1] = g[1];
		r -= (int)ap[k].size();
	}
	writeln(min(f[0], f[1]) > 1e18 ? -1 : min(f[0], f[1]));
}

int main() {
	int T = 1;
	// scanf("%d", &T);
	while (T--) {
		solve();
	}
	return 0;
}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...