P3540 [POI2012]SQU-Squarks

Alex_Wei · 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;
}