0718 测试题解

有一道原题，有点难受。所以 300。

出题人也是真厉害……不说了。

下发的题解非常的弱智，有很多地方几乎是错的……太难受了。

所以决定写这篇。

gnsi

（其实是sign，绝+1）

重心有一个结论：三点 -> （横坐标的平均值，纵坐标的平均值）

所以可以很轻易的找到上下界来判断。

quencese

傻逼计数

考虑递推的式子，设 $f_{t, i}$ 表示第 $t$ 次最后一个数是 $i$ 的可能数：

$$f_{t, i} = \sum_{j = 1}^{\lfloor \sqrt i \rfloor} f_{t + 1, i} $$

又由于实际上 $t$ 据说在 $10$ 次左右就只剩下了 $1$，也就是说，$\forall (t_1, t_2) (f_{t_1, i} = f_{t_2, i})$。

所以只保留 $i$ 这一维，向上推即可。

这是 $O(n \sqrt n)$ 的，显然不够优秀，所以考虑优化。

看式子，长得像前缀和，于是利用前缀和优化：

设 $g_i = \sum_{j = 1}^{i} f_j$。

于是有 $f_i = g_{\lfloor \sqrt i \rfloor}$。

两者稍微合并一下：

$$g_i = sum_{j = 1}^{i} g_{\lfloor \sqrt j \rfloor} $$

很明显，这里可以用类似数论分块的方法求和即可。

大概的复杂度是：

$$T(n) = \sqrt n T(\sqrt n) + O(\sqrt n) $$

我不清楚这个东西复杂度到底是什么，但是很明显的是，非常的迅速，大概是在 $O(\sqrt n)$ 左右。

这是核心代码：

using lint = long long;
lint calc(lint x) {
    if (g.get(x))
        return g.get(x);
    if (x == 1) return 1;

    lint v = 0;
    for (lint i = 1; i * i <= x; ++i) {
        lint r = min(x + 1, (i + 1) * (i + 1));
        v += calc(i) * (r - i * i) % mod;
        v %= mod;
    }

    g.set(x, v);
    return v;
}

trolcon

弱智 DP 题，根本做不来。

很明显的结论是最多只需要合并三次，所以考虑用合并的次数作为状态之一，找到最小的支配集大小：

设 $f_{i, k}$ 表示考虑到第 $i$ 个线段，合并的 $k$ 次时，最小的支配集大小。

定义 $last_i$ 表示第 $i$ 条线段左侧右端点最大的线段（不相交）。

$conj_i$ 表示与第 $i$ 条线段相交的线段中左端点最小的线段。$conj^k_i$ 就是嵌套几层下去……

于是可以有转移方程：

$$f_{i, k} = \min{ f_{last_i, k} + 1, \min_{t = 0}^{k} (f_{conj^{t + 1}_i, k - t} + 1}) $$

看着头皮发麻 QwQ

那么问题在于如何维护 $last_i$ 和 $conj_i$……这可以用 set 进行维护。

考虑根据当前考虑的区间的左端点分成三个部分：完全在左边（按照右端点排序），包含了左端点（按照左端点排序），完全在右边。

然后类似于单调栈的思路不断弹出即可。

#include <iostream>
#include <algorithm>
#include <vector>
#include <array>
#include <set>

using namespace std;
const int N = 1e5 + 7;

struct LR {
	int l, r, i;
} segs[N];

struct cmpByR {
	bool operator() (const LR &lhs, const LR &rhs) {
		return lhs.r > rhs.r;
	}
}; 

struct cmpByL {
	bool operator() (const LR &lhs, const LR &rhs) {
		return lhs.l < rhs.l;
	}
};

set<LR, cmpByL> all, rs, ms;
set<LR, cmpByR> ls;

const int M = N * 30, INF = 1e9 + 7;

int last[N], conj[N];
int f[N][4];

int main() {
	freopen("trolcon.in", "r", stdin);
	freopen("trolcon.out", "w", stdout);
	
	cin.tie(0)->sync_with_stdio(false);
	
	int n; cin >> n;
	for (int l, r, i = 1; i <= n; ++i) {
		cin >> l >> r;
		all.insert({l, r, i});
		rs.insert({l, r, i});
	}

	int maxk = 0, ending = 1;
	for (auto it : all) {
		int x = it.l;
		while (!ms.empty() && ms.begin()->r < x) {
			ls.insert(*ms.begin());
			ms.erase(ms.begin());
		}
		
		while (!rs.empty() && rs.begin()->l <= x) {
			ms.insert(*rs.begin());
			rs.erase(rs.begin());
		}
		
		int i = ending = it.i, lst = ls.size() ? ls.begin()->i : 0, cont = ms.size() ? ms.begin()->i : 0;
		last[i] = lst, conj[i] = cont;
		for (int t = 0; t <= 3; ++t) {
			f[i][t] = f[lst][t] + 1;
			for (int k = 0, con = cont; k <= t; ++k, con = conj[con]) {
				f[i][t] = min(f[i][t], f[last[con]][t - k] + 1);
			}
			
			maxk = max(maxk, f[i][t]);
		}
	}
	
	if (maxk <= 1)
		return cout << "-1" << '\n', 0;
	for (int k = 1; k <= 3; ++k) {
		if (f[ending][k] < f[ending][0]) {
			cout << k << '\n';
			return 0;
		}
	}
	
	cout << "ROCKYOU" << '\n';
	return 0;
}

doog

利用矩阵有结合律以及没有交换律，以及矩阵的逆的性质即可。