国庆 NOIP 模拟赛 Day 1

T1

挺简单的一道题，但是读题读了老半天。。

输入的是通关的顺序，并且因为每次选择的是满足条件的关卡中编号最小的，所以这个顺序一定是字典序最小的。把通关顺序划分为若干个递增块，每个递增块内各关卡的重要度是相同的。

然后可以算出各个块内每个位置的重要度，然后每个块内难度递增即可，但要注意重复。可以对每个位置维护一个指针，指向后面第一个没有选过的数。

# include <bits/stdc++.h>
using namespace std;
const int D = 1e5 + 7;
int n, cnt;
int x[D], p[D], d[D], pre[D];
int find (int x) {
	if (pre[x] == x) return x;
	return pre[x] = find (pre[x]);
}
int main () {
	freopen ("game.in", "r", stdin);
	freopen ("game.out", "w", stdout);
	cin >> n;
	for (int i = 1; i <= n; ++ i) cin >> x[i];
	for (int i = 1; i <= n; ++ i) {
		int l = i, r = i;
		d[x[r]] = ++ cnt;
		while (x[r + 1] == x[r] + 1) r ++, d[x[r]] = cnt;
		i = r;
	}
	for (int i = 1; i <= n; ++ i) pre[i] = i;
	for (int i = 1; i <= n; ++ i) {
		if (d[i] == d[i - 1]) {
			int tmp = find (d[i]);
			cout << tmp << " ";
			vis[tmp] = 1;
			pre[tmp] = tmp + 1;
		}
		else {
			cout << d[i] << " ";
			vis[d[i]] = 1;
			pre[d[i]] = d[i] + 1;
		}
	}
}

T2

30 pts

赛时打了一个线段树，维护区间 \(max\) 和 \(min\) ，然后找整块的，以为能多卡点分，然后跟暴力一个分……

# include <bits/stdc++.h>
using namespace std;
const int D = 5e5 + 7;
int n, m;
int h[D];
int mn[D << 2], mx[D << 2];
void pushup (int now) {
	mn[now] = min (mn[now << 1], mn[now << 1 | 1]);
	mx[now] = max (mx[now << 1], mx[now << 1 | 1]);
}
void build (int now, int l, int r) {
	if (l == r) {
		mx[now] = mn[now] = h[l];
		return;
	}
	int mid = l + r >> 1;
	build (now << 1, l, mid);
	build (now << 1 | 1, mid + 1, r);
	pushup (now);
}
void update (int now, int l, int r, int x, int c) {
	if (l == r) {
		mx[now] = mn[now] = c;
		return;
	}
	int mid = l + r >> 1;
	if (x <= mid) update (now << 1, l, mid, x, c);
	else update (now << 1 | 1, mid + 1, r, x, c);
	pushup (now);
}
int query (int now, int l, int r, int h) {
	if (mn[now] >= h) return 1;
	if (mx[now] < h) return 0;
	if (l == r) return 0;
	int mid = l + r >> 1;
	return query (now << 1, l, mid, h) + query (now << 1 | 1, mid + 1, r, h);
}
int main () {
	cin >> n >> m;
	for (int i = 1; i <= n; ++ i) cin >> h[i];
	build (1, 1, n);
	char opt; int l, r, x, las = 0;
	for (int i = 1; i <= m; ++ i) {
		cin >> opt;
		if (opt == 'Q') {
			cin >> x; x ^= las;
			las = query (1, 1, n, x);
			cout << las << "\n";
		}
		if (opt == 'C') {
			cin >> l >> r; l ^= las, r ^= las;
			update (1, 1, n, l, r);
		}
	}
}

100pts

就是维护高度，从前往后如果是瞬间增加的，就在线段树中将增加的这块区间+1，也就是当 \(a[i] > a[i - 1]\) 时，将 \(a[i - 1] ~ a[i]\) 区间 + 1，这样每个点就表示整个序列的这个高度上有几个突然增加的位置，也就是维护了山峰，然后查询的时候单点查询即可。

#include <bits/stdc++.h>
using namespace std;
const int D = 5e5 + 7;
int n, m;
int h[D];
int t[D << 2], lzy[D << 2];
void update(int now, int l, int r, int L, int R, int c) {
	if (L <= l && R >= r) {
		t[now] += (r - l + 1) * c;
		lzy[now]+=c;
		return;
	}
	int mid = l + r >> 1;
	if (L <= mid)
		update(now << 1, l, mid, L, R, c);
	if (R >= mid + 1)
		update(now << 1 | 1, mid + 1, r, L, R, c);
	t[now] = t[now << 1] + t[now << 1 | 1];
}
void add (int now, int l, int r, int z) {
	t[now] += (r - l + 1) * z;
}
void pushdown(int now, int l, int r) {
	int mid = l + r >> 1;
	add (now << 1, l, mid, lzy[now]);
	add (now << 1 | 1, mid + 1, r, lzy[now]);
	lzy[now << 1] += lzy[now];
	lzy[now << 1 | 1] += lzy[now];
	lzy[now] = 0;
}
int query(int now, int l, int r, int x) {
	if (l == r)
		return t[now];
	int mid = l + r >> 1, re = 0;
	pushdown(now, l, r);
	if (x <= mid)
		return query(now << 1, l, mid, x);
	else
		return query(now << 1 | 1, mid + 1, r, x);
}
int mx = 0;
void upd(int x, int y, int z) {
	if (h[x - 1] < y) {
		update(1, 1, 5e5, h[x - 1] + 1, y, z);
	}
	if (h[x + 1] > y) {
		update(1, 1, 5e5, y + 1, h[x + 1], z);
	}
}
int main() {
	cin >> n >> m;
	for (int i = 1; i <= n; ++i) {
		cin >> h[i];
	}
	for (int i = 1; i <= n; ++i) {
		if (h[i] != h[i - 1]) {
			update(1, 1, 5e5, h[i - 1] + 1, h[i], 1);
		}
	}
	int las = 0;
	for (int i = 1; i <= m; ++i) {
		char opt;
		cin >> opt;
		if (opt == 'Q') {
			int x;
			cin >> x;
			x ^= las;
			cout << (las = query(1, 1, 5e5, x)) << "\n";
		}
		if (opt == 'C') {
			int x, y;
			cin >> x >> y;
			x ^= las, y ^= las;
			upd(x, h[x], -1);
			h[x] = y; upd(x, h[x], 1);
		}
	}
}

T3

考虑怎么才能对答案产生贡献。

只有在符号后面加括号才能对答案加减，因为负负得正，所以考虑如何在负号后加括号。

如果在负号后面加括号，那负号后面的正号都会变成负号，负号都会变成正号。

但如果在后边的负号后面再加一个括号，那这个负号后面的正号变成负号后又变成了正号，负号相反。

所以负号后面如果又出现了负号，那第二个负号后面所有的符号都是可以任意改变的。

所以最优的方法是第二个负号后面都取绝对值。

但是有可能第一个负号与第二个负号之间正数过多，或者说和过大，那答案就不优了。

所以跳过这个负号，去下一个负号，按相同方法计算答案。