BZOJ3687 简单题

/*
reference:
    https://www.cnblogs.com/zwfymqz/p/8696499.html
solution:
    我们先分析异或的性质，偶个相同的数异或起来就是零，奇数个异或起来就是那个数本身，
    所以我们只需要用bitset统计每个和出现了奇数次还是偶数次。每次新加入一个数x的时候，我们只需将bitset
    左移x位就可以表示加上x后的集合，然后与原来的bitset异或一下就可以更新。
    这是因为如果某元素之前出现过，这次又出现了，两次的值都为1，那么这个元素就出现了奇数次，异或起来就变成了0
    ；在两个bitset中只出现了一次，那么1异或0就变成了1；同理，两次都没出现结果也是0。
trigger:
    异或，就是对二进制每一位进行不进位操作
    bitset比DP的空间复杂度更优 
note:
    *bitset 和 异或操作 维护一个数的出现次数是奇数还是偶数 
date:
    2019.08.22
happy:
    体验一波二进制的强大，顺便练练bitset。
*/

bitset<200010>bit; 
int ans,sum,n;

signed main(){
    bit[0]=1;
    rd(n);
    rep(i,1,n){
        int x;rd(x);
        sum+=x;
        bit^=bit<<x;
    }
    dwn(i,sum,1){
        if(bit[i]&1)
            ans^=i;
    }
    printf("%d",ans);
    return 0;
}
/*
2
1 3
*/
//6

【前缀和 枚举顺序】P3131 [USACO16JAN]子共七Subsequences Summing to Sevens

/*
translation:
    n个数，分别是a[1...n]
    求一个最长的区间[x,y]，使得区间中的数(a[x...y])的和能被7整除。输出区间长度。若没有符合要求的区间，输出0。 
reference:
    
solution:
    (结论题，若sum[i]==sum[j] ，则sum[k]-sum[i]%7==0)
    用sum[i]表示前缀和%7的值，若存在i＜=j满足sum[j]=sum[i]，则区间(i,j]的和为7的倍数。
trigger:
    显然，这是一个前缀和问题， 
note:
    *
date:
    2019.08.22
happy:
    */

#define N 50010
#define M 

int first[7],sum[N],last[7]={INT_MIN},a[N];
int maxx=INT_MIN,n;

signed main(){
    rd(n);
    rep(i,1,n){
        rd(a[i]);
        sum[i]=(sum[i-1]+a[i])%7; 
    }
    dwn(i,n,1)//倒序枚举，保证最后一次更新时first最小 
        first[sum[i]]=i;
    rep(i,1,n)//正序枚举，保证最后一次更新时last最大 
        last[sum[i]]=i;
    rep(i,0,6){
        maxx=max(maxx,last[i]-first[i]);
    }
    printf("%lld",maxx);
    return 0;
}
/*
7
3
5
1
6
2
14
10
*/
//5

P1967 货车运输

/*
reference:
    
solution:
    首先，有一些边权比较小的边我们永远都不会取到，考虑把他们删掉，而整个图又要联通，
    那么就建一个最大生成树！两点之间的路径用lca维护，于是问题就转化为：
    在最大生成树的新图上跑lca，并同时维护这条路径的最小边权，最小边权也可以采用
    倍增的方法一道求出 
trigger:
    
note:
    *t=log2(n)+1 
date:
    2019.08.22
happy:
    
*/