自动搬运

查看原文

来自洛谷，原作者为

	LG086 我想要说的前人们都说过了。

搬运于2025-08-24 22:24:30，当前版本为作者最后更新于2024-11-16 22:53:33，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

题意简述

对一个长度为 $n$ 的纸条进行 $k$ 次折叠，每次在 $a_i$ 所在的位置折叠，问纸条长度是多少。

注意到 $n$ 有不超过 $18$ 个整数位，所以应该使用 long long 类型进行运算。

以一个例子引入。

我们假设 $n=5,k=3$，每次折叠的位置分别为 $\{3,4,1\}$，则原纸条上每个端点的数字为 $\{0,1,2,3,4,5\}$。计算每次折叠的结果。

1. 对 $3$ 所在的位置进行折叠，得到 $\{3,(2;4),(1;5),0\}$。
2. 对 $4$ 所在的位置折叠，得到 $\{(2;4),(1;3;5),0\}$。
3. 对 $1$ 所在的位置折叠，得到 $\{(1;3;5),(0;2;4)\}$。
4. 此时纸条上有 $2$ 个端点，得到答案 $ans=1$。

基本思路

使用 $last$ 数组存储本次折叠前的，每一次折叠的数字的位置。根据本次折叠前的，每一次折叠的数字的位置，可以推算出本次折叠的数字所在的位置。

使用 $l,r$ 记录纸条的左右端点，使用 $ans$ 计算纸条长度。

因为每次向左折与向右折本质上是一样的，而且每次向右折可以保证 $l,r$ 会越来越大，所以可以统一向右折叠。
接着判断折叠位置是否偏右，使用 $a=\max(a,last_i-a)$ 更新折叠的位置。

为什么更新方式是 $a=\max(a,last_i-a)$？
以折叠二次为例，假设本次折叠位置的数字为 $k$，第一次折叠的位置是 $last$。那么我们可以得到 $\{last,(last+1;last-1),(last+2;last-2),\dots\}$。在 $2\times last$ 的位置，$0$ 恰好在该位置上。于是推出 $2\times last-k$ 的位置上的数字为 $k$。

更新 $r=\max(r,2\times a-1)$，并计算当前 $ans$。由于折叠后 $l=a$，所以只考虑右端点到 $a$ 的距离，所以 $ans=r-a$。

最后输出 $ans$，完成。

示例代码

#include<iostream>
#define LG086 main
using namespace std;
using ll = long long;
const int N = 1e4+5;
ll n,k,last[N];
int LG086(){
	ios::sync_with_stdio(0);
	cin.tie(0);cout.tie(0);
	cin>>n>>k;
	ll l=0,r=n,ans=n;
	for(ll _(1),a;_<=k;_++){
		cin>>a;
		for(int i(1);i<_;i++)
			a=max(a,2*last[i]-a);
		last[_]=a;r=max(r,a*2-l);
		ans=r-a;l=a;
	}
	cout<<ans;
	return 0;
}