CF Round #632

再次拉垮

A.构造

题意：给定n*m的棋盘

你对它染色黑或白

对于黑色B的而言，只要它存在白色相邻的格子，它就是满足条件的B'

对于白色的而言，只要它存在黑色相邻的格子，它就是满足条件的W'

构造一种染色方案，使得B'==W'+1，保证存在构造方案

思路：分情况

奇数直接B多W少，交替染色

偶数在交替染色的基础上，找到四个角中的一个，若他是W，把它改成B即可，这样这个B就一定不是B'(相邻一定的无W)

B.数学

给定一个a序列只有1,0,或-1组成，

你有以下的操作

给定b序列，问你可否经过上面的变换将a转化成b

思路：

只要是出现了1和-1，那么啥都可以表示

就是特判有点多，要细心举例，我wa了好几次（吃相难看）

例如

刚刷1，-1，满足否？

-1 1

-2 1

0的判断

-1 1

-1 0

C.前缀和，映射，数学

给定一个序列，现在问你有多少子序列，使得该子序列的所有子序列中不存在和为0的序列

如，｛1,2,-3｝是5个

In the first sample, the following subarrays are good: [1], [1,2], [2], [2,−3], [−3]. However, the subarray [1,2,−3] isn't good, as its subarray [1,2,−3] has sum of elements equal to 0.

思路：显然不考虑满足条件时，子序列总数量是n*(n+1)/2

接下来我们再剔除不满足条件的情况

我们可以通过前缀和与建立映射，可以知道每个和为零的子区段的始末

但是子区段之间可能有好多情况，包含，交叉，不交叉...

我们要是分析容斥性肯定不可能

但是我们可以换一种分类方法来考虑这道问题，即按照右端点情况进行分类

如果任意点x的位置n(下标为1开始计数)，那么以它为右端点的子区段的数量就是n

固定x位置，分析他的左端，我们一步一步把左端向左推。一旦说左端和右端包含了一段和为0的区段，那么你左端再怎么移动，他都是不满足条件的，换言之，当我们固定x时，无非是找到所有和为0的区段中最大的左端值

这样一来无论和为0的区段如何交叉，我们都不用管，我们只要每步去更新0区段里最大的左端值即可

代码：

#include<iostream>
#include<cstring>
#include<cstdio>
#include<map>
using namespace std;
#define INF 1e10+5
#define maxn 105
#define minn -105
#define ll long long int
#define ull unsigned long long int
#define uint unsigned int
int main()
{
    ll n,cur;
    map<ll,ll>ex;
    map<ll,ll>pos;
    ex[0]=1;
    pos[0]=0;
    cin>>n;
    ll ans=n*(n+1)/2;
    ll sum=0,curmax=0;
    for(ll i=1;i<=n;i++)
    {
        cin>>cur;
        sum+=cur;
        if(ex[sum])
        {
            curmax=max(curmax,pos[sum]+1);
        }
        ans-=curmax;
        pos[sum]=i,ex[sum]=1;
    }
    cout<<ans<<endl;
    return 0;
}