专栏文章

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

PPyrf_uqcat
P12417题解参与者 12已保存评论 11

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
11 条
当前快照
1 份
快照标识符
@mip2ogql
此快照首次捕获于
2025/12/03 05:10
3 个月前
此快照最后确认于
2025/12/03 05:10
3 个月前
查看原文

前记（题外）

一觉醒来我重生了。只见眼前出现了一道基础构造练习题，这一世，我要夺回属于我的一切。
确实是构造好题。提交次数和经历的分数都挺多的，反倒可以当游记了。
分数经历：14→16→33→36→63→0→10014 \to 16 \to 33 \to 36 \to 63 \to 0 \to 100
共交了 34 次，起到了拉低通过率的作用。

对于存答案的方式

本来是用二维数组存的，需要一个变量记录答案总数。还是改成 vector< pair<int,int> > ans 更好。可以通过输出长度体现答案。
存储似乎定义函数更好：
CPP
inline void add(int x,int y)
{
    ans.push_back(make_pair(x,y));
}
输出答案（先输出长度）：
CPP
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(n2)O(n^2) 把每个都乘上一遍就好了，后来发现只有 n=2n = 2 时成立。（

33 pts

发现当 n=2kn = 2 ^ k 时规律还挺好找的。
可以采取反复对半开分治的方法：
先将每 22 个数配对，在通过 22 次操作可以将四个数合并成一样的。然后再通过 44 操作将 88 个数合并直至合并出 2k2 ^ k 个一样的数。
CPP
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 做法得到我们已经会了 2k2 ^ k 个数的合并，这时想到我如果会 2k+22 ^ k + 2 就可以通过分治解决所有的 nn。毕竟分来分去都是偶数，处理长度的二分之一进行奇数和偶数分讨即可。
然后尝试爆推 n=10n = 10，不推 66 是因为太小了出不了规律。搞了两个小时的规律：
x,x,x,x,x,x,x,x,y,yx,x,x,x,x,x,x,x,y,y
将前 66 个 xx 与最后一个 yy 配对：
xy,x2y,x3y,x4y,x5y,x6y,x,x,y,x6yxy,x^2y,x^3y,x^4y,x^5y,x^6y,x,x,y,x^6y
前 66 个首尾配对：
x7y2,x7y2,x7y2,x7y2,x7y2,x7y2,x,x,y,x6yx^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。
x7y2,x7y2,x7y2,x7y2,x7y2,x7y2,x7y2,x7y2,x7y2,x7y2x^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
然后得出了普遍规律：
当遇到一堆 xx 和 22 个 yy 时，将其分为两部分：pp 个 xx 为一部分，22 个 xx 和 22 个 yy 为一部分。将 pp 个 xx 都乘一遍最后一个 yy，得到 xy,x2y,…,xpyxy,x^2y,\dots,x^py。采取首尾配对（有点像求和公式的推导），第一部分全部变成 xp+1y2x^{p+1}y^2。第二部分将最后两个先变成 xpy2x^py^2，再以一三二四配对得到 44 个 xp+1y2x^{p+1}y^2，这样整个序列都变成了 xp+1y2x^{p+1}y^2。
关于我为什么过不了子任务二，那是因为有部分合并写错了（
代码放在 63 pts 处。

63 pts

把 26 pts 调了一下，就是上面的思路。
CPP
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

尝试重构。重构，重构！
每添加 22 个数就要把整个序列都扫一篇，还是太劣了。不过偶然间看到别人所说的互补使我有些思路。
还是和 63 pts 一样，爆推 n=10n = 10。那就先不把前 88 个变成一样的。
a1,a2,a3,a4,a5,a6,a7,a8,a9,a10a_1,a_2,a_3,a_4,a_5,a_6,a_7,a_8,a_9,a_{10}
像之前的分部分一样，将最后的 a9,a10a_9,a_{10} 提出，以 a1,a2,…,an−22a_1,a_2,\dots,a_{\frac{n-2}{2}} 也就是前 44 个为第一部分，剩下 n−22\frac{n-2}{2} 个也就是 44 个分为第二部分。且将两部分通过 n−22\frac{n-2}{2} 此操作变成一样。
注意：不需要把每个数变成一样浪费次数
第一部分正着过一遍 a10a_{10}，第二部分倒着过一遍 a10a_{10}。依次操作。
a1a10,a1a2a10,a1a2a3a10,a1a2a3a4a10a_1a_{10},a_1a_2a_{10},a_1a_2a_3a_{10},a_1a_2a_3a_4a_{10}
a1a2a3a4a5a6a7a8a10,a1a2a3a4a6a7a8a10,a1a2a3a4a7a8a10,a1a2a3a4a8a10a_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}
赶紧简化第二部分：
a12a22a32a42a10,a1a22a32a42a10,a1a2a32a42a10,a1a2a3a42a10a_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}
显然这个时候将第 ii 个和第 (i+n2)(i+\frac{n}{2}) 个操作一遍是不一样的。
先看 a1a_1，第一个乘积为 a13a_1^3 但是后面都是 a12a_1^2，看来 a1a_1 先操作使得所有都是三次方。然后后面多出来的 a2a_2 至 an−22a_{\frac{n-2}{2}} 都不会有多出来的三次方（其实是意外之举，效果出其不意）。
将先乘的与第一组最后一个操作，后面全部错位。
现在前 n−2n-2 项就都是 a13a22a32a42a102a_1^3a_2^2a_3^2a_4^2a_{10}^2。后两项为 a12a22a32a42a102a_1^2a_2^2a_3^2a_4^2a_{10}^2，那我们开始时就把 a1a_1 和 an−2a_{n-2} 操作一下，这样就不会少 a1a_1 了。
同理得 nn 时答案。
解决了。。。吗？？
怎么是零分啊，啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊！

100 pts

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

评论

共 11 条评论，欢迎与作者交流。

正在加载评论...