自动搬运

查看原文

来自洛谷，原作者为

	Alex_Wei **

搬运于2025-08-24 21:50:00，当前版本为作者最后更新于2021-12-19 22:32:18，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

*P3540 [POI2012]SQU-Squarks

POI 合集。

将给出的 $s_i$ 和要求的 $x_i$ 都从大到小排序，$s_1=x_1+x_2$，$s_2=x_1+x_3$，这一点显然。

先考虑已知一些数时，如何推出剩下来的数：假设 $x_1\sim x_r$ 已知，它们两两相加可以形成一些和 $t_j$，用可重集 $s$ 减去可重集 $t$，我们能得到一个最大数 $s_p$，它只能是 $x_1+x_{r+1}$ 的和，否则与 $s_p$ 的最大性违背。

因此，我们断言如果确定 $x_1$，那么可以在 $\mathcal{O}(n^2\log n)$ 的时间内得到整个 $x_i$：找到可重集 $s\backslash t$（$t$ 的定义如上）中最大的数 $s_p$，反推出 $x_{r+1}$，用 $x_{r+1}$ 与 $x_1\sim x_r$ 的和更新 $t$，再找到下一个最大的 $s_{p'}\in s\backslash t'$ 反推出 $x_{r+2}$，以此类推。根据 $s_p$ 的单调性可以用指针维护 $p$。$\log$ 由用 $x_{r+1}+x_i$ 通过 map 打标记产生（代码用了 priority_queue）。特别的，若求出的 $x_{r+1}\geq x_r$ 或 $x_{r+1}\leq 0$ 或 $t\nsubseteq S$ 则钦定的 $x_1$ 无解。

接下来考虑如何求 $x_1$：注意到 $x_2+x_3$ 仅有可能小于 $x_1+x_i\ (2\leq i\leq n)$，因此 $x_2+x_3$ 在从大到小排过序后的 $s$ 中下标不会超过 $n$。考虑直接枚举这个下标从而解出 $x_1,x_2$ 和 $x_3$。

综上，时间复杂度三方对数。由于大部分下标很快无解，因此常数非常小。

const int N = 300 + 5;
int n, m, a[N * N >> 1];
uint mp[N * N * 35];
void s(int x) {mp[x >> 5] |= 1u << (x & 31);}
bool query(int x) {return mp[x >> 5] >> (x & 31) & 1;}
vector <vint> ans;

int main(){
	cin >> n, m = n * (n - 1) >> 1;
	for(int i = 1; i <= m; i++) a[i] = read(), s(a[i]);
	sort(a + 1, a + m + 1), reverse(a + 1, a + m + 1);
	for(int i = 3; i <= n; i++) if(i == 3 || a[i] != a[i - 1]) {
		static int x[N], sum; sum = a[1] + a[2] + a[i];
		if(sum & 1) continue; x[1] = (sum >> 1) - a[i];
		if(x[1] < n) continue;
		priority_queue <int> q; bool ok = 1;
		for(int j = 2, p = 1; j <= n && ok; j++) {
			while(!q.empty() && q.top() == a[p]) q.pop(), p++;
			x[j] = a[p] - x[1];
			if(x[j] >= x[j - 1] || x[j] < 0) ok = 0;
			for(int k = 1; k < j && ok; k++) ok &= query(x[k] + x[j]), q.push(x[k] + x[j]); 
		} if(ok) {vint p; for(int j = n; j; j--) p.pb(x[j]); ans.pb(p);}
	}
	cout << ans.size() << endl, rev(ans);
	for(vint it : ans) {for(int p : it) cout << p << " "; cout << endl;}
	return flush(), 0;
}