JOISC 2018 题解 · 徐皓天

JOISC 2018

Day 1

道路建设

发现操作本质上是一个 $\text{access}$ ，LCT 维护即可，逆序对就把路径上的颜色块爬下来树状数组求就行了，时间复杂度 $\mathcal O(n \log^2 n)$ 。

const int N = 1e5 + 7;

struct LCT {
	int f[N], ch[N][2], s[N], z[N], a[N];
	#define lc ch[p][0]
	#define rc ch[p][1]
	#define upd(p) s[p] = s[ch[p][0]] + s[ch[p][1]] + 1
	#define get(p) (p == ch[f[p]][1])
	#define rev(p) v[p] ^= 1, swap(ch[p][0], ch[p][1])
	#define isrt(p) (ch[f[p]][0] != p && ch[f[p]][1] != p)
	inline void spd(int p) {
		if (z[p]) {
			if (lc) a[lc] = z[lc] = z[p];
			if (rc) a[rc] = z[rc] = z[p];
			z[p] = 0;
		}
	}
	inline void rot(int p) {
		int x = f[p], y = f[x], u = get(p), v = get(x), o = isrt(x);
		f[ch[p][u^1]] = x, ch[x][u] = ch[p][u^1];
		f[x] = p, ch[p][u^1] = x, upd(x), upd(p);
		if ((f[p] = y) && !o) ch[y][v] = p;
	}
	void pre(int p) {
		if (!isrt(p)) pre(f[p]);
		spd(p);
	}
	inline void splay(int p) {
		pre(p);
		for (int x = f[p]; !isrt(p); rot(p), x = f[p])
			if (!isrt(x)) rot(get(p) == get(x) ? x : p);
	}
	inline vector<pi> access(int p) {
		vector<pi> ret;
		int w = 0;
		for (int x = 0; p; p = f[x=p])
			splay(p), rc = x, upd(p),
			ret.pb(mp(a[p], s[p] - w)), w = s[p];
		return ret;
	}
	inline void link(int p, int x) {
		int w = a[x];
		splay(p), rc = x, f[x] = p, splay(x), upd(x), a[x] = z[x] = w;
	}
} lct;

struct BIT {
	vector<ll> c;
	inline BIT() {}
	inline BIT(int n) { c.resize(n); }
	inline void add(ui x, ll k) {
		while (x < c.size()) c[x] += k, x += x & -x;
	}
	inline ll ask(ui x) {
		ll k = 0;
		while (x) k += c[x], x -= x & -x;
		return k;
	}
};

int n, a[N];

int main() {
	rd(n);
	for (int i = 1; i <= n; i++) rd(a[i]), lct.a[i] = a[i];
	sort(a + 1, a + n + 1);
	int t = unique(a + 1, a + n + 1) - (a + 1);
	BIT c(t + 1);
	for (int i = 1; i <= n; i++)
		lct.a[i] = lower_bound(a + 1, a + t + 1, lct.a[i]) - a;
	lct.s[1] = 1;
	for (int i = 1, x, y; i < n; i++) {
		rd(x, y);
		auto ret = lct.access(x);
		ll ans = 0;
		for (pi o : ret)
			ans += o.se * c.ask(o.fi - 1), c.add(o.fi, o.se);
		print(ans);
		for (pi o : ret) c.add(o.fi, -o.se);
		lct.link(x, y);
	}
	return 0;
}

栅栏

咕。

帐篷

设 $f_{i,j}$ 表示 $i,j$ 的答案，转移枚举第一行怎么填即可，采用记搜写法，时间复杂度 $\mathcal O(n^2)$ 。

const int N = 3e3 + 7;
const modint inv2 = (modint)1 / 2;
modint f[N][N];
bool v[N][N];

inline modint F(int n, int m) {
	if (!n || !m) return 1;
	if (v[n][m]) return f[n][m];
	v[n][m] = 1;
	modint &k = f[n][m];
	k += F(n - 1, m);
	k += m * F(n - 1, m - 1) * 4;
	if (m >= 2) k += m * (m - 1) * inv2 * F(n - 1, m - 2);
	if (n >= 2) k += m * (n - 1) * F(n - 2, m - 1);
	return k;
}

int main() {
	int n, m;
	rd(n, m), print(F(n, m) - 1);
	return 0;
}

Day 2

修行

题意相当于求有多少 $1\sim n$ 的排列满足 $p_i > p_{i+1}$ 的 $i$ 恰好 $k-1$ 个。

转化为求概率，等价于 $n$ 个 $[0,1)$ 的随机变量 $a_{1\dots n}$ 满足 $a_i > a_{i+1}$ 的 $i$ 恰好 $k-1$ 个的概率。

考虑构造 $b_{i} = [a_{i-1} > a_i] + a_i - a_{i-1}$ ，其中 $b_1 = a_1$ ，即 $a$ 为 $b$ 的前缀和的小数部分。

于是问题转化为求 $k-1 \le \sum_{i=1}^n b_i < k$ 的概率，可以差分一下。

考虑容斥掉 $b_i \in [0,1)$ 的限制，于是问题变成 $n$ 个 $[0,+\infty)$ 的数之和 $< k$ 的概率，这个概率实际上等于 $\frac{k^n}{n!}$ 。

总时间复杂度 $\mathcal O(n \log n)$ 。

int n, k;

inline modint calc(int k) {
	modint ans = 0, o = 1;
	for (int i = 0; i < k; i++, o = -o)
		ans += o * binom(n, i) * ((modint)(k - i) ^ n);
	return ans;
}

int main() {
	rd(n, k), init(n);
	print(calc(k) - calc(k - 1));
	return 0;
}

路网服务

提答题，扔了。

最差记者 3

首先可以直接求出每个人的周期，即当 $i-1$ 走的长度不小于 $d_i$ 时， $i$ 将走 $i-1$ 所走的那么长。

于是 $d_i$ 为 $d_{i-1}$ 的倍数，则不同的 $d$ 只有 $\mathcal O(\log w)$ 个，则每次暴力求区间交即可，时间复杂度 $\mathcal O(q\log w)$ 。

const int N = 5e5 + 7;
int n, m, a[N];

int main() {
	rd(n, m), rda(a, n), a[0] = 1;
	vector<pi> p;
	p.pb(mp(1, 0));
	for (int i = 1; i <= n; i++) {
		if (a[i] % a[i-1]) a[i] = (a[i] / a[i-1] + 1) * a[i-1];
		if (a[i] == a[i-1]) ++p.back().se;
		else p.pb(mp(a[i], i));
	}
	for (int i = 1, t, l, r, ans, lst; i <= m; i++) {
		rd(t, l, r), ans = lst = 0;
		for (pi o : p) {
			int L = t / o.fi * o.fi - o.se, R = t / o.fi * o.fi - lst;
			ans += max(0, min(r, R) - max(l, L) + 1), lst = o.se + 1;
		}
		print(ans);
	}
	return 0;
}

Day 3

比太郎的聚会

对于这种询问中的某个量之和与 $n$ 同阶的题目，通常有三个做法：

如果是在树上，可以考虑虚树。
这个量只有 $\mathcal O(\sqrt n)$ 种，算过的保存下来就可以直接用。
这个量 $> \sqrt n$ 的只有 $\mathcal O(\sqrt n)$ 个，可以暴力； $\le \sqrt n$ 的通常可以预处理。

本题考虑第三个性质即可。

安全门

咕。

Day 4

糖

其实是经典题。

其实同样是个带悔贪心。

带悔贪心的解题方法：

算上反悔的代价之后用堆贪心。

模拟费用流。

首先贪心的选，当选择在 $i$ 之后， $i-1$ 和 $i+1$ 的位置要么同时选，要么同时不选，当同时选的时候就要撤销选择 $i$ ，因此我们可以将 $a_{i-1}+a_{i+1}-a_i$ 作为一个新的物品放入原本 $i$ 的位置，同时删掉 $i-1$ 和 $i+1$ 。

用链表和堆维护即可。

#define P pair<ll, int>
const int N = 2e5 + 7;
int n, m, l[N], r[N];
ll a[N], ans;
bool v[N];
priority_queue<P> q;

int main() {
	rd(n), m = (n + 1) >> 1, rda(a, n), a[0] = a[n+1] = -1e18, r[n+1] = n + 1;
	for (int i = 1; i <= n; i++)
		q.push(mp(a[i], i)), l[i] = i - 1, r[i] = i + 1;
	for (int i = 1; i <= m; i++) {
		while (v[q.top().se]) q.pop();
		int x = q.top().se;
		q.pop(), ans += a[x], print(ans);
		int L = l[x], R = r[x];
		v[L] = v[R] = 1, a[x] = a[L] + a[R] - a[x];
		l[x] = l[L], r[x] = r[R], r[l[x]] = x, l[r[x]] = x;
		if (L >= 1 && R <= n) q.push(mp(a[x], x));
	}
	return 0;
}

图书馆

考虑先通过最多 $n$ 次询问找到某一端，方法为询问 $[1,n] - i$ ，若答案为 $1$ 说明是某一端。

然后从这一端不断地找到与其相邻的下一个位置。考虑二分，假设我们现在要找到与位置 $p$ 相邻的某个位置，设可能的位置集合为 $S$ ，将其均匀的分为 $A,B$ 两个集合，然后询问 $A$ 和 $A + p$ 的答案，如果后者等于前者，说明 $A$ 中存在与 $p$ 相邻的位置，否则说明 $B$ 中存在与 $p$ 相邻的位置，然后二分下去即可。

询问复杂度为 $\mathcal O(n \log n)$ 。

int n;

inline int ask(vi p, int w = 0) {
	vi m(n);
	for (int x : p) m[x-1] = 1;
	if (w) m[w-1] = 1;
	return Query(m);
}

void Solve(int n) {
	srand(time(0) ^ n);
	::n = n;
	vi p(n);
	for (int i = 0; i < n; i++) p[i] = i + 1;
	random_shuffle(p.begin(), p.end());
	for (int i = 0; i < n; i++) {
		swap(p[0], p[i]);
		if (i == n - 1 || ask(vi(p.begin() + 1, p.end())) == 1) break;
	}
	for (int i = 0; i < n - 1; i++) {
		auto l = p.begin() + i + 1, r = p.end();
		while (l + 1 != r) {
			auto mid = l + ((r - l) >> 1);
			if (ask(vi(l, mid)) == ask(vi(l, mid), p[i])) r = mid;
			else l = mid;
		}
		swap(p[i+1], *l);
	}
	Answer(p);
}

野猪

咕。

Day 1

Day 2

Day 3

Day 4

评论