重生之我回到了写P12417的前一秒

· · 题解

前记（题外）

一觉醒来我重生了。只见眼前出现了一道基础构造练习题，这一世，我要夺回属于我的一切。

确实是构造好题。提交次数和经历的分数都挺多的，反倒可以当游记了。

分数经历：14 \to 16 \to 33 \to 36 \to 63 \to 0 \to 100

共交了 34 次，起到了拉低通过率的作用。

对于存答案的方式

本来是用二维数组存的，需要一个变量记录答案总数。还是改成 vector< pair<int,int> > ans 更好。可以通过输出长度体现答案。

存储似乎定义函数更好：

inline void add(int x,int y)
{
    ans.push_back(make_pair(x,y));
}

输出答案（先输出长度）：

cout<<ans.size()<<"\n";
for(int i=0;i<ans.size();i++)
{
    cout<<ans[i].first<<' '<<ans[i].second<<"\n";
}

注意：每组数据请先清空。

14 pts

先看一眼子任务一，尝试先过一。

提供两种做法：

做法一：根据样例中 2 和 4 有解，3 无解可得：偶数有解，奇数无解。

做法二（证明）：最终的序列一定是由两两配对二次，奇数通过分割后必然存在奇数无法配对，故奇数无法成立。

16 pts

我还以为 O(n^2) 把每个都乘上一遍就好了，后来发现只有 n = 2 时成立。（

33 pts

发现当 n = 2 ^ k 时规律还挺好找的。

可以采取反复对半开分治的方法：

先将每 2 个数配对，在通过 2 次操作可以将四个数合并成一样的。然后再通过 4 操作将 8 个数合并直至合并出 2 ^ k 个一样的数。

void dfs(int l,int r)
{
    if(l==r-1)
    {
        add(l,r);
        return ;
    }
    int mid=(l+r)>>1;
    dfs(l,mid),dfs(mid+1,r);
    for(int i=l;i<=mid;i++) add(i,mid+i-l+1);
}

36 pts

由 33 pts 做法得到我们已经会了 2 ^ k 个数的合并，这时想到我如果会 2 ^ k + 2 就可以通过分治解决所有的 n。毕竟分来分去都是偶数，处理长度的二分之一进行奇数和偶数分讨即可。

然后尝试爆推 n = 10，不推 6 是因为太小了出不了规律。搞了两个小时的规律：

x,x,x,x,x,x,x,x,y,y

将前 6 个 x 与最后一个 y 配对：

xy,x^2y,x^3y,x^4y,x^5y,x^6y,x,x,y,x^6y

前 6 个首尾配对：

x^7y^2,x^7y^2,x^7y^2,x^7y^2,x^7y^2,x^7y^2,x,x,y,x^6y

采取 9 和 10，7 和 9 再 9 和 10。

x^7y^2,x^7y^2,x^7y^2,x^7y^2,x^7y^2,x^7y^2,x^7y^2,x^7y^2,x^7y^2,x^7y^2

然后得出了普遍规律：

当遇到一堆 x 和 2 个 y 时，将其分为两部分：p 个 x 为一部分，2 个 x 和 2 个 y 为一部分。将 p 个 x 都乘一遍最后一个 y，得到 xy,x^2y,\dots,x^py。采取首尾配对（有点像求和公式的推导），第一部分全部变成 x^{p+1}y^2。第二部分将最后两个先变成 x^py^2，再以一三二四配对得到 4 个 x^{p+1}y^2，这样整个序列都变成了 x^{p+1}y^2。

关于我为什么过不了子任务二，那是因为有部分合并写错了（

代码放在 63 pts 处。

63 pts

把 26 pts 调了一下，就是上面的思路。

void f(int l,int r)
{
    if(l==r-1)
    {
        add(l,r);
        return ;
    }
    if(l==r) return ;
    int len=r-l+1;
    if((len/2)%2==1)
    {
        int mid=(l+r)>>1;
        f(l,r-2),f(r-1,r);
        for(int i=l;i<=r-4;i++) add(i,r);
        for(int i=l;i<=(r-4)-(r-4-l+1)/2;i++) add(i,r-4+l-i);
        add(r-1,r),add(r-3,r-1),add(r-2,r);
    }
    else
    {
        int mid=(l+r)>>1;
        f(l,mid),f(mid+1,r);
        for(int i=l;i<=mid;i++) add(i,mid+i-l+1);
    }
}

0 pts

尝试重构。重构，重构！

每添加 2 个数就要把整个序列都扫一篇，还是太劣了。不过偶然间看到别人所说的互补使我有些思路。

还是和 63 pts 一样，爆推 n = 10。那就先不把前 8 个变成一样的。

a_1,a_2,a_3,a_4,a_5,a_6,a_7,a_8,a_9,a_{10}

像之前的分部分一样，将最后的 a_9,a_{10} 提出，以 a_1,a_2,\dots,a_{\frac{n-2}{2}} 也就是前 4 个为第一部分，剩下 \frac{n-2}{2} 个也就是 4 个分为第二部分。且将两部分通过 \frac{n-2}{2} 此操作变成一样。

注意：不需要把每个数变成一样浪费次数

第一部分正着过一遍 a_{10}，第二部分倒着过一遍 a_{10}。依次操作。

a_1a_{10},a_1a_2a_{10},a_1a_2a_3a_{10},a_1a_2a_3a_4a_{10} a_1a_2a_3a_4a_5a_6a_7a_8a_{10},a_1a_2a_3a_4a_6a_7a_8a_{10},a_1a_2a_3a_4a_7a_8a_{10},a_1a_2a_3a_4a_8a_{10}

赶紧简化第二部分：

a_1^2a_2^2a_3^2a_4^2a_{10},a_1a_2^2a_3^2a_4^2a_{10},a_1a_2a_3^2a_4^2a_{10},a_1a_2a_3a_4^2a_{10}

显然这个时候将第 i 个和第 (i+\frac{n}{2}) 个操作一遍是不一样的。

先看 a_1，第一个乘积为 a_1^3 但是后面都是 a_1^2，看来 a_1 先操作使得所有都是三次方。然后后面多出来的 a_2 至 a_{\frac{n-2}{2}} 都不会有多出来的三次方（其实是意外之举，效果出其不意）。

将先乘的与第一组最后一个操作，后面全部错位。

现在前 n-2 项就都是 a_1^3a_2^2a_3^2a_4^2a_{10}^2。后两项为 a_1^2a_2^2a_3^2a_4^2a_{10}^2，那我们开始时就把 a_1 和 a_{n-2} 操作一下，这样就不会少 a_1 了。

同理得 n 时答案。

解决了。。。吗？？

怎么是零分啊，啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊！

100 pts

样例过不了，特判 2,4。我果然不太聪明。