AtCoder Regular Contest 119 C - ARC Wrecker 2（同余定理+思维）

时间：2021-05-27 16:58:05 阅读：29 评论：0 收藏：0 [点我收藏+]

Problem Statement

There are $N$ buildings along the AtCoder Street, numbered $1$ through $N$ from west to east. Initially, Buildings $1, 2, \dots, N$ have the heights of $A_{1}, A_{2}, \dots, A_{N}$ , respectively.

Takahashi, the president of ARC Wrecker, Inc., plans to choose integers $l$ and $r$ $(1 \leq l < r \leq N)$ and make the heights of Buildings $l, l + 1, \dots, r$ all zero. To do so, he can use the following two kinds of operations any number of times in any order:

Set an integer $x$ $(l \leq x \leq r - 1)$ and increase the heights of Buildings $x$ and $x + 1$ by $1$ each.
Set an integer $x$ $(l \leq x \leq r - 1)$ and decrease the heights of Buildings $x$ and $x + 1$ by $1$ each. This operation can only be done when both of those buildings have heights of $1$ or greater.

Note that the range of $x$ depends on $(l, r)$ .

How many choices of $(l, r)$ are there where Takahashi can realize his plan?

Constraints

$2 \leq N \leq 300000$
$1 \leq A_{i} \leq 10^{9}$ $(1 \leq i \leq N)$
All values in input are integers.

Input

Input is given from Standard Input in the following format:

 $N$ 
 $A_{1}$   $A_{2}$   $\dots$   $A_{N}$

Output

Print the answer.

Sample Input 1 Copy

Copy

5
5 8 8 6 6

Sample Output 1 Copy

Copy

Takahashi can realize his plan for $(l, r) = (2, 3), (4, 5), (2, 5)$ .

For example, for $(l, r) = (2, 5)$ , the following sequence of operations make the heights of Buildings $2, 3, 4, 5$ all zero.

Decrease the heights of Buildings $4$ and $5$ by $1$ each, six times in a row.
Decrease the heights of Buildings $2$ and $3$ by $1$ each, eight times in a row.

For the remaining seven choices of $(l, r)$ , there is no sequence of operations that can realize his plan.

Sample Input 2 Copy

Copy

7
12 8 11 3 3 13 2

Sample Output 2 Copy

Copy

Takahashi can realize his plan for $(l, r) = (2, 4), (3, 7), (4, 5)$ .

For example, for $(l, r) = (3, 7)$ , the following figure shows one possible solution.

技术分享图片

Sample Input 3 Copy

Copy

10
8 6 3 9 5 4 7 2 1 10

Sample Output 3 Copy

Copy

Takahashi can realize his plan for $(l, r) = (3, 8)$ only.

Sample Input 4 Copy

Copy

14
630551244 683685976 249199599 863395255 667330388 617766025 564631293 614195656 944865979 277535591 390222868 527065404 136842536 971731491

Sample Output 4 Copy

Copy

题意：
有 n 个数，每次可以将 a[x],a[x+1] 同时 +1/-1 ，问存在多少区间同时减为 0

题解：
直觉告诉我用差分来做，然后模拟出来的结果时间复杂度都是 O(n^2)
直到看到了 hu_tao 大佬的讨论，一语惊醒，每次操作一定是将一个奇数位和偶数位同时操作，所以无论怎么变一个区间想要同时变为 0，那么这个区间上奇数位置和偶数位置的加和是相同的；
所以将奇数位置处的值置为负数，利用同余定理，就可以找到任意一个连续的子段加和为 0

const int N=1e6+5;
 
    int n, m, _;
    int i, j, k;
    ll a[N];
    map<ll,int> mp;

signed main()
{
    //IOS;
    while(~sd(n)){
        for(int i=1;i<=n;i++){
            sll(a[i]);
            if(i%2==0) a[i]=-a[i];
        }
        ll ans=0;
        mp[0]++;
        for(int i=1;i<=n;i++){
            a[i]+=a[i-1];
            if(mp[a[i]]) ans+=mp[a[i]];
            mp[a[i]]++;
        }
        pll(ans);
        mp.clear();
    }
    //PAUSE;
    return 0;
}

AtCoder Regular Contest 119 C - ARC Wrecker 2（同余定理+思维）

原文：https://www.cnblogs.com/Segment-Tree/p/14817521.html

踩

(0)

评论一句话评论（0）

分享档案

更多>

2021年09月23日 (328)
2021年09月24日 (313)
2021年09月17日 (191)
2021年09月15日 (369)
2021年09月16日 (411)
2021年09月13日 (439)
2021年09月11日 (398)
2021年09月12日 (393)
2021年09月10日 (160)
2021年09月08日 (222)