NOI Online 能力测试 题解

不知道哪儿来的野鸡比赛。

序列

把每个位置看成一个点。

首先对于 $2$ 操作连边。

如果两个位置连通则意味着可以使一个位置 $+1$ 另一个位置 $-1$。

即对于一个连通块，我们可以在保证总和不变的情况下任意的加减，因此并查集将一个连通块缩成一个点。

再对于 $1$ 操作连边。

如果形成的图是二分图，则可以在保证左部点总和与右部点总和的差不变的情况下任意的加减。

如果形成的图不是二分图，则可以在保证总和奇偶性不变的情况下任意的加减。

const int N = 1e5 + 7;
int n, m, a[N], b[N], f[N], p[N], q[N], t, v[N];
ll s[N], c[3];
vi e[N];

int get(int x) {
	return x == f[x] ? x : (f[x] = get(f[x]));
}

inline bool dfs(int x, int k) {
	v[x] = k, c[k] += s[x];
	bool ok = 1;
	for (ui i = 0; i < e[x].size(); i++) {
		int y = e[x][i];
		if (v[y] == v[x]) ok = 0;
		if (!v[y] && !dfs(y, 3 - k)) ok = 0;
	}
	return ok;
}

inline bool solve() {
	rd(n), rd(m), rda(a, n), rda(b, n), t = 0;
	for (int i = 1; i <= n; i++) f[i] = i, s[i] = v[i] = 0, e[i].clear();
	for (int i = 1, o, x, y; i <= m; i++) {
		rd(o), rd(x), rd(y);
		if (o == 2) f[get(x)] = get(y);
		else p[++t] = x, q[t] = y;
	}
	for (int i = 1; i <= n; i++) s[get(i)] += b[i] - a[i];
	for (int i = 1; i <= t; i++) {
		int x = get(p[i]), y = get(q[i]);
		e[x].pb(y), e[y].pb(x);
	}
	for (int i = 1; i <= n; i++)
		if (get(i) == i && !v[i]) {
			c[1] = c[2] = 0;
			bool ok = dfs(i, 1);
			if (ok && c[1] != c[2]) return 0;
			if (!ok && ((c[1] ^ c[2]) & 1)) return 0;
		}
	return 1;
}

int main() {
	int T;
	rd(T);
	while (T--) prints(solve() ? "YES" : "NO");
	return 0;
}

冒泡排序

考虑冒泡排序一轮对逆序对的变化。

首先给出结论：假设原本在位置 $i$ 上的逆序对数为 $c_i$，冒泡排序一轮后，位置 $i$ 上的逆序对数变为 $\max(0, c_{i+1}-1)$。

相当于一个左移，减一，与 $0$ 取 $\max$ 的过程。

为什么呢？

冒泡排序一轮的本质，其实就是从第一个数开始，将其拿出来，放到它后面第一个比它大的数之前，然后将比它大的那个数拿出来，再往后放，以此类推。

假设我们拿出来的数原本的下标为 $i$，要放到下标为 $j$ 之前的位置，则 $(i,j)$ 这个里面的数全部往前移了一位，同时在它们上面的逆序对数少了一个。

而拿出来的数一定是逆序对数为 $0$ 的位置，否则前面一定有比它大的数，它就一定不会被拿出来。

因此左移，减一，与 $0$ 取 $\max$ 的过程就是逆序对数变化的过程。

有了这个结论，剩下的就好做了，用树状数组维护每个逆序对数的个数以及它们对答案的贡献即可。

const int N = 2e5 + 7;
int n, m, a[N], b[N], c[N];
ll s[N];

inline void add(int x, int k, ll w = 0) {
	while (x <= n) c[x] += k, s[x] += w, x += x & -x;
}

inline pair<int, ll> ask(int x) {
	int k = 0;
	ll w = 0;
	while (x) k += c[x], w += s[x], x -= x & -x;
	return mp(k, w);
}

int main() {
	rd(n), rd(m), rda(a, n);
	for (int i = 1; i <= n; i++)
		b[i] = ask(n).fi - ask(a[i]).fi, add(a[i], 1);
	for (int i = 1; i <= n; i++) c[i] = 0;
	for (int i = 1; i <= n; i++)
		if (b[i]) add(b[i], 1, b[i]);
	while (m--) {
		int o, x;
		rd(o), rd(x);
		if (o == 1) {
			if (a[x] < a[x+1]) {
				if (b[x]) add(b[x], -1, -b[x]);
				++b[x];
				if (b[x]) add(b[x], 1, b[x]);
			} else {
				if (b[x+1]) add(b[x+1], -1, -b[x+1]);
				--b[x+1];
				if (b[x+1]) add(b[x+1], 1, b[x+1]);
			}
			swap(a[x], a[x+1]), swap(b[x], b[x+1]);
		} else {
			if (x >= n) print(0);
			else {
				pair<int, ll> p1 = ask(n), p2 = ask(x);
				print(p1.se - p2.se - 1ll * (p1.fi - p2.fi) * x);
			}
		}
	}
	return 0;
}

最小环

对于询问 $k$，实际上是把整个长度为 $n$ 的环拆成 $\gcd(k,n)$ 个长度为 $\frac{n}{\gcd(k,n)}$ 个环。

因此预处理出每个可能的 $\gcd(k,n)$ 的答案，一共只有 $\sqrt(n)$ 个。

对于每个 $\gcd(k,n)$ 贪心地找到最优解，如何找见代码，至于为什么，我并不知道这并不重要。

const int N = 2e5 + 7;
int n, m, k, a[N];
ll ans[N];

int gcd(int x, int y) {
	return y ? gcd(y, x % y) : x;
}

inline ll calc(int x) {
	int c = n / x;
	ll ret = 0;
	for (int i = 1; i <= n; i += c) {
		int j = i + c - 1;
		for (int k = j - 2; k >= i; k--)
			ret += 1ll * a[k] * a[k+2];
		if (c == 1) ret += 1ll * a[i] * a[j];
		if (c > 1) ret += 1ll * a[i] * a[i+1] + 1ll * a[j-1] * a[j];
	}
	return ret;
}

int main() {
	rd(n), rd(m), rda(a, n);
	sort(a + 1, a + n + 1);
	for (int i = 1; i <= n; i++)
		if (!(n % i)) ans[i] = calc(i);
	while (m--) rd(k), print(ans[gcd(k,n)]);
	return 0;
}