[ARC119C] ARC Wrecker 2

jnyz2021109122116 · 2023-01-17 10:39:56 · 题解

Part 0

本题思考过程是最重要的，而解法很显然。

题意：选定一个区间 (l,r)，使这个区间内任意相邻两座楼房的高度同时加 1 或减 1，要求使区间内所有楼房的高度都变为 0。请求出有多少个满足要求的区间。

Ps：下文称高度加 1 为“增加”，高度减 1 为“削减”。

Part 1

我们先从最简单的情况开始分析。

• 当区间长度为 2 时，当且仅当两座楼高度相等时满足要求。
• 当区间长度为 3 时，我们知道：对于两端的楼房，其操作必定为“削减”，这就要求中间楼房的高度恰好等于两端楼房的高度和。
• 当区间长度为 4 时,我们设四座楼房的高度分别为 a\ \ b\ \ c\ \ d

  对两端的楼房“削减”后变成

  0\ \ b-a\ \ c-d\ \ 0

  是不是有点眼熟？我们把它变成了情况1。令

  b-a=c-d

  可得

  a+c=b+d
• 当区间长度为 5 时，设五座楼房的高度分别为 a\ \ b\ \ c\ \ d\ \ e

  同理，对两端的楼房“削减”后变成

  0\ \ b-a\ \ c\ \ d-e\ \ 0

  梅开二度，我们把它变成了情况2。令

  c=(b-a)+(d-e)

  可得

  a+c+e=b+d

总结一下，我们发现了啥？

• 对于任意长度大于等于 2 的区间，都可以把它变成前 2 种情况。
• 对于一个合法区间，其奇数位置上楼房的高度和必定等于偶数位置上楼房的高度和。

那有同学就要问了：万一有的楼高度不够减怎么办？ 我们大可放心“减”，上面的讨论已经包含可能出现的高度为负的情况。毕竟对负高度楼房来说，“增加”即“削减”。

Part 3

我们现在知道了这一结论，不妨把奇数或偶数位置上楼房的高度乘以 -1，于是区间和就变成了 0！

我翻开算法书一查，这代码没有年代，歪歪斜斜的每页上都写着“我是蒟蒻”几个字。我横竖睡不着，仔细看了半夜，才从字缝里看出字来，满本都写着三个字是“前缀和”！

设前缀和数组为 a_i，对于合法区间 (l,r)，a_{l-1}=a_r。也就是说，如果前缀和数组中出现两个相同的数字，那么就对应一个合法区间。
那出现三个甚至更多怎么办？——排列组合
怎样记录数字出现的次数？——Map

Tips：

• long long
• 不要忘记前缀和数组第一项为 0。

Talk is cheap,show me the code.

#include<bits/stdc++.h>
#define ll long long
using namespace std;

ll n,sum,ans; 
unordered_map<ll,int> v;
int main(){
    cin>>n;
    v[0]=1;
    for(int i=1;i<=n;i++){
        sum+=read()*(i%2? 1:-1);//省略快读
        ans+=v[sum]++;
    }
    cout<<ans<<'\n';
    return 0;
}