P7921 [Kubic] Division 题解

· · 题解

来水一发题解。个人感觉黑题有点虚高。

我们先猜测一下最终状态是什么。

设最终状态是 a_1, a_2, ..., a_n，且 a_1 \le a_2 \le... \le a_n。

那么很显然，这个状态成立当且仅当：

然后呢，就可以得到：

所以说必然不能有 a_1 = a_2 = a_3 或者 a_3 = a_4 = a_5 之类的。

相当于说只能满足每个数出现次数 \le 2 或者 1 + 3 的形式。

我们先只考虑全部 \le 2 的情况。

那么假设 a_n = k，那么显然 a_1 > \frac{k}{2} 的。

考虑填满后再删去一些数，那么先拿一个 k = 6 手玩一下。发现可以使减少和等于 0,4,5,6,8,9,10,11.....

最重要的特点是中间隔的是 1,2,3,7...

首先如果上面这样构造能构造的出来的话，必然是最优的且合法的（这个很好证吧）。

然后考虑把 1+3 的情况给塞回去，发现可以通过减少一个最小数，多一个另外的数来达到这个目的。

那么此时就可以除了 7 以外全部处理完了。

最后想想这个 7，手推一下可以想到放到下一次弄必然不劣。

那么就把这个 7 放到下面特判即可。

具体细节见代码。

Code：

/*
   长弓背负，仙女月鹫，
   梦中徐来，长夜悠悠。
   今宵共君，夜赏囃子，
   盼君速归，长夜悠悠。
   睡意袭我，眼阖梦徭，
   睡意袭我，意归襁褓。
   手扶卓揭，仙女水狃，
   盼君速归，长夜悠悠。
   今宵共君，戏于西楼，
   盼君速归，长夜悠悠。
   睡意袭我，涟锜池留，
   睡意袭我，意归海角。
                                      ——《ever17》
*/
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,tune=native")
#include <bits/stdc++.h>
using namespace std;
#define int long long
inline int read()
{
    int sum = 0, nega = 1;
    char ch = getchar();
    while (ch > '9'||ch < '0')
    {
        if (ch == '-') nega = -1;
        ch = getchar();
    }
    while (ch <= '9'&&ch >= '0') sum = sum * 10 + ch - '0', ch = getchar ();
    return sum * nega;
}
const int N = 1e5 + 9;
int n, pep, res;
int cnt[N]; 
queue<int> q;
int ansx[N], ansy[N];
inline int val(int x) {return x * (x + 1) / 2;}
signed main()
{
    n = read();
    for (int i = 1; i <= n; i++)
    {
        int p = i / 2;
        int v = (val(i) - val(p)) * 2;
        p++;
        if(v < n && n - v <= i - p)
        {
            for (int j = p; j <= i; j++) cnt[j] = 2;
            cnt[p]--, cnt[p + n - v]++;
            res = 0;
            for (int j = p; j <= i; j++)
                for (int k = 1; k <= cnt[j]; k++) 
                {
                    q.push(j); res += j;
                }
            while(!q.empty())
            {
                int x = q.front(); q.pop(); 
                if(q.empty()) break;
                int y = q.front(); q.pop();
                ansx[++pep] = x + y, ansy[pep] = x;
                q.push(x + y);
            }
            cout << pep << endl;
            for (int j = pep; j >= 1; j--) printf("%lld %lld\n", ansx[j], ansy[j]);
            return 0;
        } 
        if(v >= n && (v - n >= p || v - n == 0))
        {
        //  cout << v << " " << i << endl;
            if(v - n == i + 1 && i % 2 == 0) continue;
            for (int j = p; j <= i; j++) cnt[j] = 2;
            if(v - n == 0) ;
            else if(v - n <= i) cnt[v - n]--;
            else if(v - n <= i + p) cnt[p]--, cnt[v - n - p]--;
            else if(v - n <= i * 2) cnt[i]--, cnt[v - n - i]--;
            else if(v - n <= i * 2 + p) cnt[i]--, cnt[p]--, cnt[v - n - i - p]--;
            else cnt[i]--, cnt[i - 1]--, cnt[p] = 0;
            res = 0;
            for (int j = p; j <= i; j++)
                for (int k = 1; k <= cnt[j]; k++) 
                {
                    q.push(j); res += j;
                }
            if(res != n) continue;
            while(!q.empty())
            {
                int x = q.front(); q.pop(); 
                if(q.empty()) break;
                int y = q.front(); q.pop();
                ansx[++pep] = x + y, ansy[pep] = x;
                q.push(x + y);
            }
            cout << pep << endl;
            for (int j = pep; j >= 1; j--) printf("%lld %lld\n", ansx[j], ansy[j]);
            return 0;
        }
    }
    return 0;
}