P6842 Strip 题解

· · 题解

题意简述

对一个长度为 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;
}