Posted on | In ,

1

https://codeforces.com/problemset/problem/1358/C

最开始想到了棋盘走法问题，那个答案是C(n+m, m)，于是便想着把这道题区域中过对角线的部分中可能sum重复的走法剪掉，后来发现不可取，

image解法很巧妙，先选中sum最小的一种（沿着顶边和右边），接下来如果想扩大，只能把顶点向左下“内缩”，这样sum可以加一，同时我们知道最大的sum，在最小最大的这个区间中，每个sum均可以通过从最小sum缩若干次达到，所以sum不同的方案数就是这个区间的范围。“In order for us to come from the minimum to the maximum way, we must bend the way exactly 1 time per each cell of table (except for the cells of the minimum way). That is, the number of changes equals the number of cells not belonging to the minimum way”这是算最大最小差值的方法。

2

https://codeforces.com/contest/1359/problem/E

打完失眠过程中想出了正确结论。

一个序列是stable的当且仅当其中有一个元素是其余元素的公因数。然后我们就可以从1到大看每个数的倍数总量够k个的话，就可以从i及它的倍数中选k-1个构成稳定序列。求组合数用费马小定理的话是log(mod)复杂度，整体nlog(mod)。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
const int mod=998244353;
const int maxn=5e5+2;
ll fact[maxn];
void init(){
    fact[0]=1;
    for(int i=1;i<maxn;i++){
        fact[i]=fact[i-1]*i%mod;
    }
}
ll pow(ll x,int k){
    ll res=1;
    while(k){
        if(k&1)
            res=res*x%mod;
        x=(x*x)%mod;
        k>>=1;
    }
    return res;
}
ll rev(ll x,int p){ //费马小定理求逆元
    return pow(x,p-2)%mod;
}
ll c(int n,int m){  //C(n,m)
    ll res=0;
    try{
        res=fact[n]*rev(fact[m],mod)%mod*rev(fact[n-m],mod)%mod;
    }catch(exception e){
        cout<<n<<endl;
    }
    return res;
}

int main(){
    init();
    int n,k;
    cin>>n>>k;
    ll ans=0;
    for(int i=1;i<=n&&i*k<=n;i++){
        ll num=n/i;
        ans=(ans+c(num-1,k-1))%mod;
    }
    cout<<ans<<endl;
}

Posted on | In

记录脑筋急转弯

习惯

链式前向星需要memset head数组

记得特判

20校赛前一天的三角形

https://codeforces.com/contest/1355/problem/C

给三段区间，要求找出能构成三角形的向量的数目。乍一看要画图用线性规划……好麻烦就没写出来，出题人给的是另一种思路：想办法算出对于每个s（a+b<=s<=b+c），有多少对（x，y）的和等于s。这样一来我们就可以枚举z边，然后把当前和大于z的xy取法数目加在答案上。

第一步是个区间加，即对于所有x，把[x+b,x+c]这一段取法值加一，因为是离线的就不用线段树了，在区间首尾打标记然后维护当前点的取法即可，遍历一遍就赋值好了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
#include<bits/stdc++.h>
using namespace std;
#define ll long long

const int maxn=1e6+2;
ll ways[maxn];
int main(){
    ll a,b,c,d;
    cin>>a>>b>>c>>d;
    ll ans=0;
    for(int i=a;i<=b;i++){
        ways[i+b]+=1;
        ways[i+c+1]-=1;
    }
    ll tmp=0;
    for(int i=a+b;i<=b+c+1;i++){
        tmp+=ways[i];
        ways[i]=tmp;
    }
    assert(tmp==0);
    for(int i=b+c;i>c;i--){
        tmp+=ways[i];
        if(i<=d+1)
            ans+=tmp;
    }
    cout<<ans<<endl;
}

最大区间和beta

我们知道单纯求最大区间和可以用dp，在线性时间搞出来。这道题https://codeforces.com/contest/1359/problem/D要求我们求 减去区间最大值后的区间和 的最大值，增加了难度。

首先，我们可以用单调栈求出，对于每个点i，向左向右最远走到哪里可以不遇到比自己大的，这样我们可以确定下来点i可选的有效区间范围（即a[i]在这个范围中是最大值）。接下来我们只需要在这个区间中选择一个包含i的区间，可以用线段树维护前缀和的最大和最小值。在i左侧找到前缀和最小值，在i右侧找前缀和最大值，两者相减就是整体区间的最大值了。相减时还需要排除右边<=左边的情况。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
#include<bits/stdc++.h>
using namespace std;
#define lson (o<<1)
#define rson (o<<1|1)
#define inf 0x3f3f3f3f
const int maxn=1e5+2;

int n,a[maxn],sum[maxn];
int mn[maxn<<2],mx[maxn<<2];

void build(int o,int l,int r){
    if(l==r){
        mn[o]=mx[o]=sum[l];
        return;
    }
    int mid=(l+r)>>1;
    build(lson,l,mid);
    build(rson,mid+1,r);
    mn[o]=min(mn[lson],mn[rson]);
    mx[o]=max(mx[lson],mx[rson]);
}

int qu_mn(int o,int l,int r,int L,int R){
    if(l>=L&&r<=R){
        return mn[o];
    }
    int mid=(l+r)>>1;
    int res=inf;
    if(L<=mid){
        res=min(res,qu_mn(lson,l,mid,L,R));
    }
    if(R>mid){
        res=min(res,qu_mn(rson,mid+1,r,L,R));
    }
    return res;
}

int qu_mx(int o,int l,int r,int L,int R){
    if(l>=L&&r<=R){
        return mx[o];
    }
    int mid=(l+r)>>1;
    int res=-inf;
    if(L<=mid){
        res=max(res,qu_mx(lson,l,mid,L,R));
    }
    if(R>mid){
        res=max(res,qu_mx(rson,mid+1,r,L,R));
    }
    return res;
}

int l[maxn],r[maxn];    //记录每个点向左右走到哪为止不会遇到比自己大的,用单调栈求出
int main(){
    cin>>n;
    for(int i=1;i<=n;i++)
        cin>>a[i];
    sum[0]=0;
    for(int i=1;i<=n;i++){
        sum[i]=sum[i-1]+a[i];
    }
    stack<int> stk;
    for(int i=1;i<=n;i++){
        while(stk.size()&&a[stk.top()]<=a[i])
            stk.pop();
        if(stk.size()){
            l[i]=stk.top()+1;
        }else{
            l[i]=0;
        }
        stk.push(i);
    }
    while(stk.size()){
        stk.pop();
    }
    for(int i=n;i;i--){
        while(stk.size()&&a[stk.top()]<=a[i])
            stk.pop();
        if(stk.size()){
            r[i]=stk.top()-1;
        }else{
            r[i]=n;
        }
        stk.push(i);
    }
    build(1,0,n);
    int ans=0;
    for(int mnn,mxx,i=1;i<=n;i++){
        mnn=qu_mn(1,0,n,l[i],i);
        mxx=qu_mx(1,0,n,i,r[i]);
        if(mxx<=mnn)
            continue;
        ans=max(ans,mxx-mnn-a[i]);
    }
    cout<<ans<<endl;
}

数列翻转一下，再做dp

https://codeforces.com/contest/1366/problem/E

将当前要在a中找到的、每个subarray中的合法最小值称作目标数字。

直接从头开始线性遍历的话会遇到一个问题，就是你无法确定每个subarray中哪个数字是一定要选的，在存在连续一段目标数字的时候。而如果你把ab数组翻转一下，就会发现，遇到的第一个目标数字一定要选，如果不选的话，上一个subarray的最小值就会是它了。

并查集の新体验

https://codeforces.com/contest/1370/problem/E

分析题意得出，要做的就是求去重后的序列能拆分成多少个0101串（或1010），因为这样的串是可以一次处理完。

首先用序列自动机搞出来nxt数组，表示i及之后第一个0（1）元素的位置。然后从前向后贪心地选0101就行，有个问题就是选过的要标记vis，然后如果在找下一个元素时发现选过了，就要沿着nxt一直向下去找，这显然是n平方的。所以我们用了带路径压缩的并查集来处理。fa就表明，当当前元素不可用的时候，下一个要找谁。

https://codeforces.com/contest/1370/submission/84587433

路径压缩

1
2
3
int find(int x){
    return (fa[x]==x?x:fa[x]=find(fa[x]));
}

Posted on | In

二进制优化多重背包

裸的多重背包的复杂度是三次方的，因为在01背包的基础上需要对每种物品按数量逐个增加来测试。事实上大可不必这样，我们可以对于小于这个物品总数的所有二进制位和剩余部分挨个测试，这些测试足够组成原数量范围内的任意一个数，由于二进制位是刚好能表示“选与不选”的，因而也不能用更高进制（例如三进制还要去考虑选择的情况下是选1还是选2，没必要麻烦）。这样一来复杂度会降到nmlog(c)，大部分情况够用。

http://acm.hdu.edu.cn/showproblem.php?pid=2844

给一些面值的钱币，问能表示出几个1到m内的值。直接用多重背包即可，重量和价值相等，最后选dp[i]==i的那些。注意这道题的m可能是负的，所以判断输入要m|n，太阴了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;

const int maxm=1e5+10;
const int maxn=110;

int a[maxn],c[maxn],m,n;
int dp[maxm];
int main(){
    while(scanf("%d%d",&n,&m),m|n){
        for(int i=1;i<=n;i++)
            scanf("%d",a+i);
        for(int i=1;i<=n;i++)
            scanf("%d",c+i);
        memset(dp,0,sizeof(dp));
        int tmp;
        for(int i=1;i<=n;i++){
            int num=1;
            while(num<=c[i]){
                c[i]-=num;
                tmp=num*a[i];
                for(int k=m;k>=tmp;k--){
                    dp[k]=max(dp[k],dp[k-tmp]+tmp);
                }
                num<<=1;
            }
            if(c[i]>0){
                num=c[i];tmp=num*a[i];
                for(int k=m;k>=tmp;k--){
                    dp[k]=max(dp[k],dp[k-tmp]+tmp);
                }
            }
        }

        int ans=0;
        for(int i=1;i<=m;i++)
            if(dp[i]==i)
                ans++;
        printf("%d\n",ans);
    }
    return 0;
}

Posted on | In ,

//可做网络流和二分图模板

最大独立集是指一个图的点的最大子集，满足任意两点没有边直接相连。另一个相对的概念是最大团，在这个最大的子集中任意两点都有边直接相连，可以发现，补图的最大团就是原图的最大独立集。

在二分图中，|最大独立集|=n-|最大匹配|，这是因为首先有n-2*|最大匹配|个独立点，另外可以证明匹配中每条边可以选入一个点。

用dinic求最大匹配时，最后一次bfs的标记可以用来寻找最大独立集。我们称靠近起点一侧是左侧，另一侧为右侧。level>0的左侧点和level=0的右侧点就是一个最大独立集。这是一种优先选择左侧可行点的选法，不光有在最大匹配中未使用的那些，还有通过左右左“重获新生”的点，也就是，通过偶数次连边到达的左侧点，它保证没有边直接相连，直接相连的那些右侧点都因有效的level值而被pass了。右侧点只选那些不会干扰到这些政策的，即无法到达的那些。这里我们注意，可以到达的右侧点一定是已经使用过（它的出边已被消耗）的，要不然就会形成新的匹配了。

这一题又出现了蜜汁t，经大佬提醒数组开大了就好了。当越界不多时还是有效内存，所以不会报re，坑惨我了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
#include<bits/stdc++.h>
using namespace std;

const int maxn=5001;

struct edge{
    edge(){}
    edge(int _to,int _next,int _cap):to(_to),next(_next),cap(_cap){}
    int to,next;
    int cap;
}es[maxn*27*2];	//每个点最多连27个点，即27个bit各变一次
int head[maxn],cnt;
inline void add(int u,int v,int c){
    es[++cnt]=edge(v,head[u],c);
    head[u]=cnt;
}

int level[maxn],st,ed;
bool bfs(){
    queue<int> q;
    memset(level,0,sizeof(level));
    q.push(st);
    level[st]=1;
    while(!q.empty()){
        int u=q.front();
        q.pop();
        for(int v,i=head[u];i;i=es[i].next){
            v=es[i].to;
            if(!level[v]&&es[i].cap>0){
                level[v]=level[u]+1;
                q.push(v);
            }
        }
    }
    return level[ed]>0;
}

int cur[maxn];
int dfs(int x,int f){
    if(x==ed||f==0)
        return f;
    int res=0,tmp;
    for(int &i=cur[x];i;i=es[i].next){
        int v=es[i].to;
        if(level[v]==level[x]+1&&es[i].cap>0){
            tmp=dfs(v,min(f-res,es[i].cap));
            es[i].cap-=tmp;es[i^1].cap+=tmp;
            res+=tmp;
            if(res==f)
                break;
        }
    }
    if(!res)
        level[x]=0;
    return res;
}

int a[maxn];

int n,mark[maxn];
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        scanf("%d",a+i);
    }
    cnt=1;
    st=n+1,ed=n+2;
    for(int i=1;i<n;i++){
        for(int j=i+1;j<=n;j++){
            if(__builtin_popcount(a[i]^a[j])==1){
                if(__builtin_popcount(a[i])&1){
                    add(i,j,1);add(j,i,0);
                }else{
                    add(j,i,1);add(i,j,0);
                }
            }
        }
    }
    for(int i=1;i<=n;i++){
        if(__builtin_popcount(a[i])%2){
            add(st,i,1);add(i,st,0);
        }else{
            add(i,ed,1);add(ed,i,0);
        }
    }
    int ans=0;
    while(bfs()){
        for(int i=1;i<=n+2;i++)
            cur[i]=head[i];
        ans+=dfs(st,5000);
    }
    cout<<n-ans<<endl;
    for(int i=1;i<=n;i++){
        if(level[i]){
            if(__builtin_popcount(a[i])%2)
                printf("%d%c",a[i],i==n?'\n':' ');
        }else{
            if(__builtin_popcount(a[i])%2==0)
                printf("%d%c",a[i],i==n?'\n':' ');
        }
    }
}

Posted on | In

https://codeforces.com/problemset/problem/1348/F

题目大意，一队人排队，每个人能安排连续的一段位置[a,b]，问安排的方案是否唯一，如果不唯一，任意输出两种。

第一眼看上去直接用dinic求二分图匹配，然后发现数据量是2e5，感觉不太够，并且判唯一也不好做。看了题解发现这类问题其实有贪心的方案的。

我们首先目标是找出任一组合理安排，从1到n遍历位置安排人选，安排哪个人呢？a位于当前位置或左边，且b最小的那个。这样的人目前是最急需安排的，这种方案如果不行，那么就无法安排了。最小b可以通过一个multiset维护。同时我们不用担心这个最小b会比i小，因为前面已经安排了i-1个，如果第i大的b比i小则说明没有合法方案。

这样一来就找到了合法安排方案，接下来研究是否能找到第二种。我们可以证明，如果存在不止一种安排方案，那么必然有一种是仅仅交换两个人。可以交换两个人需要满足什么条件呢？设i和j可交换且posi<posj，那么需要aj<=posi&&posi<posj<=bi。这个条件很容易理解。具体实现可以通过线段树维护位置区间上a的区间最小值（依据第一种合法方案），每次仅需查询位于i+1,b区间上的人的a最小值，如果比i小，就说明它可以和i位置的人交换。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
#include<bits/stdc++.h>
using namespace std;

#define ll long long
const int maxn=2e5+2;
#define lson (o<<1)
#define rson (o<<1|1)
struct node1{
    int a,b,id;
    node1(){}
    node1(int _a,int _b,int _id):a(_a),b(_b),id(_id){}
    friend bool operator<(node1 x,node1 y){
        return x.a<y.a;
    }
}ns1[maxn],ns2[maxn];
struct node2{
    int b,id;
    node2(){}
    node2(int _b,int _id):b(_b),id(_id){}
    friend bool operator<(node2 x,node2 y){
        return x.b<y.b;
    }
};

int match[maxn],rnk[maxn];
int n;

int val[maxn<<2];   //存区间a的最小值
void build(int o,int l,int r){
    if(l==r){
        val[o]=ns2[rnk[l]].a;
        return ;
    }
    int mid=(l+r)/2;
    build(lson,l,mid);
    build(rson,mid+1,r);
    val[o]=min(val[lson],val[rson]);
}
int query(int o,int l,int r,int L,int R){
    if(l>=L&&r<=R){
        return val[o];
    }
    int mid=(l+r)/2;
    int res=1e9;
    if(L<=mid){
        res=min(res,query(lson,l,mid,L,R));
    }
    if(R>mid){
        res=min(res,query(rson,mid+1,r,L,R));
    }
    return res;
}

int main(){
    cin>>n;
    for(int i=1,a,b;i<=n;i++){
        cin>>a>>b;
        ns2[i]=ns1[i]=node1(a,b,i);
    }
    sort(ns1+1,ns1+n+1);
    multiset<node2> up;
    int p=1;
    for(int i=1;i<=n;i++){  //i是要待分配人的位置
        while(p<=n&&ns1[p].a<=i){
            up.insert(node2(ns1[p].b,ns1[p].id));
            p++;
        }
        auto it=up.begin();
        match[(*it).id]=i;  //match记录每个人去什么位置
        rnk[i]=(*it).id;       //rnk记录每个位置是谁
        up.erase(it);
    }
    bool f=true;
    int res[2]; //res记录哪两个位置上的人可以交换
    build(1,1,n);
    for(int i=1,b;i<n;i++){
        b=ns2[rnk[i]].b;
        if(b==i) continue;
        int tmp=query(1,1,n,i+1,b);
        if(tmp<=i){
            f=false;
            res[0]=i;
            for(int j=i+1;j<=b;j++){
                if(ns2[rnk[j]].a==tmp){
                    res[1]=j;
                    break;
                }
            }
            break;
        }
    }
    if(f){
        printf("YES\n");
        for(int i=1;i<=n;i++)
            printf("%d%c",match[i],(i==n?'\n':' '));
    }else{
        printf("NO\n");
        for(int i=1;i<=n;i++)
            printf("%d%c",match[i],(i==n?'\n':' '));
        swap(match[rnk[res[0]]],match[rnk[res[1]]]);
        for(int i=1;i<=n;i++)
            printf("%d%c",match[i],(i==n?'\n':' '));
    }
}

Posted on | In ,

https://ac.nowcoder.com/acm/contest/884/B

题目大意就是对于n个集合，每个集合最多32个unsigned int，给出m个询问问对于[l,r]的集合，是否都能各自通过异或得到x。很明显要维护区间线性基的交。

这道题我第一遍做的时候对线性基的理解还不是很深……当时误认为了求出的线性基都只有一个二进制位1，所以合并的时候就直接取与，然后就wa在了百分之六十。后来突然意识到有可能线性基的低位还有1存在，但并未考虑。后来上网查线性基取交的正确做法，给出的那套线代角度的证明实在看不懂，自己想了好久……这里用大白话给出我自己的直观理解。

我们首先要知道，线性基求交的本质是对于两个集合A、B和它们的基baseA、baseB，找到一组基使得既可以通过baseA表达，也可以通过baseB表达。一个通常的想法可以是，这个基脱胎于这两组基中的一组，比如我们对baseB挨个判断是否能被baseA表达，如果可以，这个基就是共有的。这里会有一个问题就是，baseB的低位1并未被完全清除，比如11和01，其实可以产生10这个基，于是我们修改表述为：要求选出baseB中的那些可以被baseA和baseB中低位基共同表达出来的基（等式转化一下就变成了，找出baseB中i和i以下某些基的异或和，这个异或和同样能被baseA表示）。

这里大部分人给出的做法是：在用baseA不断削减baseB中的某个基的同时，如果遇到削减不下去的情况，就把当前值增添到新baseA中（代码中为all），以待后续的基使用，同时记录下来削减到这个地步所需要的baseA（代码中为d），最终，如果某个baseB中的基，能够被一些baseA（在低位baseB的帮助下）削减至0，那么这些baseA的异或值就是一个合法新基，同样用到的baseBi和它的低位“帮手”的异或值也是这个。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
#include<bits/stdc++.h>
using namespace std;
#define lson (o<<1)
#define rson (o<<1|1)
#define ll long long
const int maxn=5e4+2;
const int maxp=32;
int n,m;

ll read(){
    ll x=0;char ch=getchar();
    while(ch<'0'||ch>'9'){ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x;
}
struct base{
    ll p[maxp];
    base(){ memset(p,0,sizeof(p));}
    void clr(){
        for(int i=maxp-1;i;i--){
            if(p[i]){
                for(int j=i-1;j>=0;j--){
                    if(p[j]&&(p[i]&(1ll<<j)))
                        p[i]^=p[j];
                }
            }
        }
    }
    bool check(ll x){
        for(int i=maxp-1;i>=0;i--){
            if(x&(1ll<<i)){
                if(p[i]) x^=p[i];
                else return false;
            }
        }
        return true;
    }
}initp[maxn],tree[maxn<<2];

void inst(ll x,base& bse){
    for(int i=maxp-1;i>=0;i--){
        if(x&(1ll<<i)){
            if(!bse.p[i]){
                bse.p[i]=x;
                break;
            }else
                x^=bse.p[i];
        }
        if(x==0)
            break;
    }
}

base d,all;
base merge(const base& a,const base& b){
    base res;
    d=a,all=a; //all装的是目前所有可用的低位基
    ll k;	//k是把baseBi和它的低位帮手削减至0所用到的baseA的异或和
    for(int i=0;i<maxp;i++){
        if(b.p[i]==0) continue;
        ll v=b.p[i];k=0;
        int j;
        for(j=i;j>=0;j--){
            if(((1ll<<j)&v)){
                if(all.p[j]>0){
                    v^=all.p[j];
                    k^=d.p[j];
                }else{
                    break;
                }
            }
        }
        if(!v)
            res.p[i]=k;
        else{
            all.p[j]=v;
            d.p[j]=k;
        }
    }
    return res;
}

/*
base merge(const base& a,const base& b){
    base res;
    for(int i=0;i<maxp;i++){
        if(b.p[i]==0)
            continue;
        ll v=b.p[i];
        for(int j=i;j>=0;j--){
            if((1ll<<j)&v){
                if(a.p[j]){
                    v^=a.p[j];
                }else{
                    break;
                }
            }
        }
        if(v==0)
            res.p[i]=b.p[i];
    }
    return res;
}
*/


void build(int o,int l,int r){
    if(l==r){
        tree[o]=initp[l];
        return;
    }
    int mid=(l+r)/2;
    build(lson,l,mid);
    build(rson,mid+1,r);
    tree[o]=merge(tree[lson],tree[rson]);
}
bool query(int o,int l,int r,int L,int R,ll x){
    if(l>=L&&r<=R){
        return tree[o].check(x);
    }
    bool f1=true,f2=true;
    int mid=(l+r)/2;
    if(L<=mid){
        f1=query(lson,l,mid,L,R,x);
    }
    if(R>mid){
        f2=query(rson,mid+1,r,L,R,x);
    }
    return f1&&f2;
}

int main(){
    scanf("%d%d",&n,&m);
    for(int i=1,k;i<=n;i++){
        scanf("%d",&k);ll x;
        for(int j=1;j<=k;j++){
            x=read();
            inst(x,initp[i]);
        }
        //initp[i].clr();
    }
    build(1,1,n);
    while(m--){
        int l,r;
        ll x;
        scanf("%d%d",&l,&r);x=read();
        printf(query(1,1,n,l,r,x)?"YES\n":"NO\n");
    }
}

其实我自己中间有一种想法就是，预先把所有基中能清理的低位1都清理掉，这样就不用考虑baseB的低位帮手的问题了（有了它也没用）使得merge函数极为简单（注释掉的那个），但后来想到，即使baseB都“净身”，也不排除会有必须和兄弟一起才能表示baseA的情况例如（baseB={1100,0011},baseA={1111}）。其实它们是可以共同表示1111这个数字，但在我那个算法中就漏掉了。

Posted on | In ,

树的直径即树上最长的一段路径，寻找它可以在O（n）内完成。

首先以任意一点为根做bfs，找到离根最远的点，它一定是直径的两点之一，再以它为根找最远的点，即直径的另一点。证明过程反证法即可。

https://ac.nowcoder.com/acm/contest/884/A

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
#include<bits/stdc++.h>
using namespace std;

//树直径模板
const int maxn=1e5+2;
struct edge{
    int to,next;
}es[maxn<<1];
int cnt,head[maxn];
inline void add(int x,int y){
    es[++cnt]=(edge){y,head[x]};
    head[x]=cnt;
}

int s[maxn];
int n,k;
int main(){
    cin>>n>>k;
    for(int i=1,x,y;i<=n-1;i++){
        cin>>x>>y;
        add(x,y);
        add(y,x);
    }
    for(int i=1;i<=k;i++)
        cin>>s[i];
    int dis[maxn];
    memset(dis,0,sizeof(dis));
    queue<int> q;
    q.push(1);
    dis[1]=1;
    while(!q.empty()){
        int u=q.front();
        q.pop();
        for(int i=head[u];i;i=es[i].next){
            int v=es[i].to;
            if(dis[v])
                continue;
            dis[v]=dis[u]+1;
            q.push(v);
        }
    }
    int a=1;
    for(int i=2;i<=k;i++){
        if(dis[s[i]]>dis[s[a]]){
            a=i;
        }
    }
    memset(dis,0,sizeof(dis));
    q.push(s[a]);
    dis[s[a]]=1;
    while(!q.empty()){
        int u=q.front();
        q.pop();
        for(int i=head[u];i;i=es[i].next){
            int v=es[i].to;
            if(dis[v])
                continue;
            dis[v]=dis[u]+1;
            q.push(v);
        }
    }
    int b=1;
    for(int i=2;i<=k;i++){
        if(dis[s[i]]>dis[s[b]])
            b=i;
    }
    int ans=dis[s[b]]/2;
    cout<<ans<<endl;
}

Posted on | In

https://ac.nowcoder.com/acm/contest/883/A

题目大意，给出一个无向图，设S(x)表示x的临近点集合，临近点即通过一条边直接相连的点。有两种操作，1是把边集合（读入顺序）从l到r的边状态反转（相连变断开，断开变相连），2是询问两个点的临近集是否相等。

这里首先涉及到的一个难点是如何表示临近集，我们采用异或哈希的方式，首先为所有点分配一个随机权值，这里用到了一个新版的随机函数

1
2
3
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
for(int i=1;i<=n;i++)
    val[i]=rng();

接下来我们把某个点的所有临近点的权值异或起来，作为它的临近集表示。异或哈希的大概原理是，原始权值在每个bit上01的概率相等，而异或过程对于每个bit产生01的概率也是等价的，所以能保证随机性。这个问题解决后，就能以O（1）时间判定临近集的相等。

接下来考虑如何维护翻转，一个简单的分块考虑是，对边集分块，最开始计算出每个块对每个点的影响（add数组）（O（m^1.5）），然后对于1操作，标记块的翻转，零碎的边直接计算出来；对于2操作，把所有翻转的块中对该点的影响都异或到现有答案上。这样两个操作的复杂度都是O（m^0.5），只可惜这样会超时，由于是多组数据，而我们在每组数据中都要对add数组进行整体清零，这个复杂度是m^0.5*n的，三四组数据估计就不行了。

所以考虑缩减add数组，我们发现，如果一个点的度数比较小，那么在计算它的临近集时可以挨个枚举相连的边，复杂度是和度数成正比的。因而我们考虑，只把度数大于sqrt（m）的点用add数组维护，这样的点总共不会超过2*sqrt（m）个。剩下的小点需要再维护一下零碎边的翻转性（e数组），同时块的翻转标记也会影响到它。

ps分块题的细节真的一不留神就写错……不过思路直接还是挺容易debug的

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
#include<bits/stdc++.h>
using namespace std;

const int maxn=1e5+2;
const int maxm=2e5+2;

#define ll long long
#define sz(x) (int)x.size()
ll val[maxn],s[maxn];
struct edge{
    int u,v;
}es[maxm];
typedef pair<int,int> pir;
vector<pir> g[maxn];
bool big[maxn];
int cnt,mp[maxn];
ll add[500][1000];
int pos[maxm],tot;
int tag[500],e[maxm];
int n,m,q,t;
string ans;
int main(){
    cin>>t;
    while(t--){
        cin>>n>>m;
        int block=sqrt(m);
        tot=0;
        for(int i=1;i<=m;i++){
            if((i-1)%block==0)
                tot++;
            pos[i]=tot;
        }
        for(int i=1;i<=n;i++)
            g[i].clear();
        for(int i=1;i<=m;i++){
            cin>>es[i].u>>es[i].v;
            g[es[i].u].push_back(pir(es[i].v,i));
            g[es[i].v].push_back(pir(es[i].u,i));
        }
        memset(big,0,sizeof(big));
        cnt=0;
        for(int i=1;i<=n;i++)
            if(sz(g[i])>block){
               big[i]=1;
               mp[i]=++cnt;
            }
        mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
        for(int i=1;i<=n;i++)
            val[i]=rng();


        for(int i=1;i<=tot;i++){
            for(int j=1;j<=cnt;++j)
                add[i][j]=0;
            for(int j=(i-1)*block+1;j<=min(m,i*block);j++){
                int u=es[j].u,v=es[j].v;
                if(big[u])
                    add[i][mp[u]]^=val[v];
                if(big[v])
                    add[i][mp[v]]^=val[u];
            }
        }

        for(int i=1;i<=tot;i++)
            tag[i]=1;
        memset(s,0,sizeof(s));
        memset(e,0,sizeof(e));
        cin>>q;
        ans="";
        while(q--){
            int opt;
            cin>>opt;
            if(opt==1){
                int l,r;
                cin>>l>>r;
                int lp=pos[l],rp=pos[r];
                if(lp<rp){
                    for(int i=lp+1;i<rp;i++)
                        tag[i]^=1;
                    for(int i=l;i<=block*lp;i++){
                        int u=es[i].u,v=es[i].v;
                        e[i]^=1;
                        if(big[u])
                            s[u]^=val[v];
                        if(big[v])
                            s[v]^=val[u];
                    }
                    for(int i=block*(rp-1)+1;i<=min(block*rp,r);i++){
                        int u=es[i].u,v=es[i].v;
                        e[i]^=1;
                        if(big[u])
                            s[u]^=val[v];
                        if(big[v])
                            s[v]^=val[u];
                    }
                }else{
                    for(int i=l;i<=r;i++){
                        int u=es[i].u,v=es[i].v;
                        e[i]^=1;
                        if(big[u])
                            s[u]^=val[v];
                        if(big[v])
                            s[v]^=val[u];
                    }
                }
            }else{
                int u,v;
                cin>>u>>v;
                ll valu=s[u],valv=s[v];
                if(big[u]){
                    for(int i=1;i<=tot;i++){
                        if(tag[i])
                            valu^=add[i][mp[u]];
                    }
                }else{
                    for(int i=0,id,to;i<sz(g[u]);i++){
                        id=g[u][i].second,to=g[u][i].first;
                        if(e[id]^tag[pos[id]]){
                            valu^=val[to];
                        }
                    }
                }
                if(big[v]){
                    for(int i=1;i<=tot;i++){
                        if(tag[i])
                            valv^=add[i][mp[v]];
                    }
                }else{
                    for(int i=0,id,to;i<sz(g[v]);i++){
                        id=g[v][i].second,to=g[v][i].first;
                        if(e[id]^tag[pos[id]]){
                            valv^=val[to];
                        }
                    }
                }
                if(valu==valv){
                    ans+='1';
                }else
                    ans+='0';
            }
        }
        cout<<ans<<endl;
    }
}
/*
1
5 4
1 2
1 3
4 2
4 3
3
2 1 4
1 1 1
2 1 2

*/

Posted on | In

https://ac.nowcoder.com/acm/contest/881/I

不得不说这题是真的难，看题解都差点没用理解。）

给定平面上若干（1e5）点，每个点ab两个权值，要求将其分为两组，a组的a权值和加b组的b权值和最大，划分条件转化一下就是，不能有a出现在b的右下，也就是要找到一条不降的折线，其上是a，其下是b。我们认为位于折线上的那些点属于b。

暴力dp是可做的，离散化xy并枚举每一列的划分点。考虑优化，认为dp[i]表示，加入i点后，如果折线的最后一个转折点是i，那么总和的最大值。它该怎么更新呢，对于点1~i-1，如果它们比i低，那折线就可以从它们那里拐过来，然后再加上b[i]；同时，再加入i点后，其余的dp值也需更新，比i高的折线会把i看作b，比i低的折线会把i看作a，分别加上这两个值即可。

这里我们注意到，已经用到了单点修改、区间加、询问区间最大值的操作，就果断线段树，将y离散化后在y上建立线段树，也就是dp数组是用线段树实现的。注意需要考虑x轴，这样一条会把所有点视为a的折线，建线段树的时候按1，1+tot范围去建立即可。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define lson (o<<1)
#define rson (o<<1|1)
const int maxn=1e5+4;
struct point{
    int x,y;
    ll a,b;
    friend bool operator<(const point& u,const point& v){
        if(u.x!=v.x){
            return u.x<v.x;
        }else
            return u.y>v.y;
    }
}ps[maxn];
int _y[maxn];

ll val[maxn<<2],lazy[maxn<<2];  //val维护线段树区间最大值,dp融入其中了

void build(int o,int l,int r){
    val[o]=0;
    lazy[o]=0;
    if(l==r)
        return ;
    int mid=(l+r)/2;
    build(lson,l,mid);
    build(rson,mid+1,r);
}
void pushup(int o){
    val[o]=max(val[lson],val[rson]);
}
void pushdown(int o){
    if(lazy[o]){
        val[lson]+=lazy[o];
        val[rson]+=lazy[o];
        lazy[lson]+=lazy[o];
        lazy[rson]+=lazy[o];
        lazy[o]=0;
    }
}
void update1(int o,int l,int r,int L,int R,ll add){
    //区间增加
    if(l>=L&&r<=R){
        val[o]+=add;
        lazy[o]+=add;
        return ;
    }
    pushdown(o);
    int mid=(l+r)/2;
    if(L<=mid){
        update1(lson,l,mid,L,R,add);
    }
    if(R>mid){
        update1(rson,mid+1,r,L,R,add);
    }
    pushup(o);
}
void update2(int o,int l,int r,int pos,ll x){
    //单点修改
    if(l==r){
        val[o]=max(x,val[o]);
        return;
    }
    pushdown(o);
    int mid=(l+r)/2;
    if(pos<=mid){
        update2(lson,l,mid,pos,x);
    }else{
        update2(rson,mid+1,r,pos,x);
    }
    pushup(o);
}
ll query(int o,int l,int r,int L,int R){
    if(l>=L&&r<=R){
        return val[o];
    }
    pushdown(o);
    int mid=(l+r)/2;
    ll res=0;
    if(L<=mid){
        res=max(res,query(lson,l,mid,L,R));
    }
    if(R>mid){
        res=max(res,query(rson,mid+1,r,L,R));
    }
    return res;
}

int n;
int main(){
    while(cin>>n){
        for(int i=1;i<=n;i++){
            cin>>ps[i].x>>ps[i].y>>ps[i].a>>ps[i].b;
            _y[i]=ps[i].y;
        }
        sort(_y+1,_y+n+1);
        int tot=unique(_y+1,_y+1+n)-_y-1;
        for(int i=1;i<=n;i++){
            ps[i].y=lower_bound(_y+1,_y+tot+1,ps[i].y)-_y+1;  //从2开始计数，1留给x轴
        }
        sort(ps+1,ps+1+n);
        build(1,1,tot+1);
        for(int i=1;i<=n;i++){
            ll dpi=query(1,1,tot+1,1,ps[i].y)+ps[i].b;
            update2(1,1,tot+1,ps[i].y,dpi);
            update1(1,1,tot+1,1,ps[i].y-1,ps[i].a);
            if(ps[i].y<tot+1)
                update1(1,1,tot+1,ps[i].y+1,tot+1,ps[i].b);

        }
        cout<<val[1]<<endl;
    }
}
/*
3
1 1 1 2
2 2 2 1
3 3 1 2

*/

Posted on | In

cdq分治，也叫时间分治，核心概念就是对于若干个操作和查询，维护每次操作在哪个时间段中有效。

https://ac.nowcoder.com/acm/contest/888/E?&headNav=acm

这道题中的size就是时间，我们维护某个size区间上点的连通状况（用并查集维护），进行查询时进入某个点则连上这个点上的边，退出它时把并查集再复原。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
#include<bits/stdc++.h>
using namespace std;
#define lson rt<<1
#define rson rt<<1|1
const int maxn=1e5+2;
int n,m;
int fa[maxn],h[maxn];
int fnd(int x){
    while(fa[x]!=x)
        x=fa[x];
    return x;
}
struct history{
    int x,y,preh;
};
vector<history> hs[maxn<<3];
int unite(int u,int v,int o){
    //在线段树的o点连上了uv边
    u=fnd(u);
    v=fnd(v);
    if(u==v)
        return 0;
    if(h[u]>h[v])
        swap(u,v);
    hs[o].push_back({u,v,h[v]});
    fa[u]=v;
    h[v]=max(h[u]+1,h[v]);
    return v;
}

void undo(int o){   //撤销线段树o点上的连边
    for(int i=0,x,y,preh;i<hs[o].size();i++){
        x=hs[o][i].x,y=hs[o][i].y,preh=hs[o][i].preh;
        fa[x]=x;h[y]=preh;
    }
    hs[o].clear();
}

struct node{
    int l,r;    //l..r分别代表以这个值开头的小区间，所以后面update时对于lr大区间添加的是l..r-1，这里存的r比实际区间右端点小1
    vector<int> es;
}tree[maxn<<3];

void build(int rt,int l,int r){ //build的意义是为每个节点设置管辖范围lr
    tree[rt].es.clear();
    tree[rt].l=l;
    tree[rt].r=r;
    if(l==r){
        return;
    }
    int mid=(l+r)/2;
    build(lson,l,mid);
    build(rson,mid+1,r);
}

void update(int L,int R,int rt,int u,int v){
    if(L<=tree[rt].l&&R>=tree[rt].r){
        tree[rt].es.push_back(u);
        tree[rt].es.push_back(v);
        return ;
    }
    int mid=(tree[rt].l+tree[rt].r)>>1;
    if(L<=mid){
        update(L,R,lson,u,v);
    }
    if(R>mid){
        update(L,R,rson,u,v);
    }
}

int ans,val[maxn<<1];

void dfs(int rt){
    for(int i=0;i<tree[rt].es.size();i+=2){
        unite(tree[rt].es[i],tree[rt].es[i+1],rt);
    }
    /*
    if(tree[rt].l==tree[rt].r){
        ans+=(fnd(1)==fnd(n)?val[tree[rt].l+1]-val[tree[rt].l]:0);
    }else{
        dfs(lson);
        dfs(rson);
    }
    */
    //和上面两种写法均可，本题这种快一些
    if(fnd(1)==fnd(n)){ //优先判通，上面的是只在叶节点判断
        ans+=val[tree[rt].r+1]-val[tree[rt].l]; //这个点的贡献是r-l个小区间的长度和，离散化中应该经常用这种技巧来算区间贡献，
        //这里这么来是因为线段树兄弟节点的lr不可等（刚好大1）所以要求l和r的意义要等价，如果就填lr则前r-l个点代表区间左端点，后面的r是多余的，所以我们干脆让每个值代表它作为左端点的那个区间
    }else if(tree[rt].l!=tree[rt].r){
        dfs(lson);
        dfs(rson);
    }
    undo(rt);
}

int u[maxn],v[maxn],l[maxn],r[maxn];
int main(){
    cin>>n>>m;
    int tot=0;
    for(int i=1;i<=m;i++){
        cin>>u[i]>>v[i]>>l[i]>>r[i];
    }
    for(int i=1;i<=m;i++){
        val[++tot]=l[i];
        val[++tot]=++r[i];
    }
    sort(val+1,val+tot+1);
    tot=unique(val+1,val+1+tot)-val-1;
    for(int i=1;i<=m;i++){
        l[i]=lower_bound(val+1,val+1+tot,l[i])-val;
        r[i]=lower_bound(val+1,val+1+tot,r[i])-val;
    }
    build(1,1,tot);
    for(int i=1;i<=n;i++)
        fa[i]=i;
    for(int i=1;i<=m;i++){
        update(l[i],r[i]-1,1,u[i],v[i]);    //意思是uv这条边在l到r-1（每段区间以左端点来代表）的小区间内都有效，
    }
    dfs(1);
    cout<<ans<<endl;
}