Posted on | In ,

题目链接

给一个无向图，含边权，并定义这样一种三元组(u, v, t)满足：从u到v有一条路径且路径上的边权异或和为t。求所有三元组的t的和

  1. 我们对它逐步拆解分析，先考虑最简单的情况——如果这个图是一棵树。首先我们发现由于异或的特殊性，经过相同的边两次等价于没有经过，所以对于所有的点对(u, v)它有唯一的异或和dis(u, v) 且等于dis(u, root) ^ dis(v, root)，因为路径上重合的部分被异或掉了。这样的关系给了我们一个启示：可以一次计算出所有点到根的异或和（用dfs）。然后再用它来求两点间的异或和。

  2. 接下来我们向图中加入环，我们知道如果在一条边上“往返”，是对结果无影响的，所以对于该图中所有的环（重边也算），都可以随意地向(u, v)的基本路径中添加。相当于存在这样一个集合B，集合中是每个环完整一圈的异或和，我们可以从这个集合中任意取数并异或上1中的结果。

    因此我们可以去计算集合B的线性基。

  3. 进而我们需要考虑的是如何计算，由于点和边的数量级是1e5，如果遍历点对会超时，这个时候就需要找规律。最终是求和，我们按照二进制位去累加各种情况的贡献，对于第i位，去计数有多少点的深度值dep[i] = dis(i, root)在这一位上是1或0，分别是tot0和tot1，如果不考虑环，贡献值为tot0tot1\2^i。即最终有tot0*tot1对点的距离值的第i位是1，那就把它们加在一起。考虑环的话则，如果该位原本没有1，可以通过B的线性基来补充。具体公式在代码中。这样计算的复杂度是O(62*m)。

  4. 对于多个联通块，每发现一个联通块就单独计算它的贡献并累加。需即使清除记录的上个联通块的环。

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
#include<bits/stdc++.h>
using namespace std;

//https://codeforces.com/contest/724/problem/G

const int maxn=1e5+4;
const int maxm=4e5+4;
const int maxp=62;
const int mod=1e9+7;
#define ll long long
struct edge{
    int to,next;	//to是该边指向的点，next是该边的上一条边的下标
    ll val;
    edge(){ to=0,next=-1,val=0;}
}es[maxm];
int head[maxn]; //head[i]是i点发出的最后一条边的下标
int cnt;
int n,m;
ll base[maxp];

ll p[maxp];
int r;  //线性基数量
ll circle[maxm],dep[maxn];
int cir;

inline void add(int u,int v,ll t){
    es[cnt].to=v;
    es[cnt].val=t;
    es[cnt].next=head[u];	//next指向上个head
    head[u]=cnt++;	//当前加入的边是head
}

int cover[maxn];    //记录本次dfs覆盖了哪些点
int cntc;
void dfs(int u,int fa,ll cur){
    cover[cntc++]=u;
    //cur是当前点到根的异或和
    dep[u]=cur;

    for(int i=head[u];i!=-1;i=es[i].next){
        int v=es[i].to;
        if(es[i].to==fa)
            continue;
        if(dep[es[i].to]==-1){
            dfs(v,u,cur^es[i].val);
        }else{
            //重复到达某个点，说明有环，添加它的值
            circle[cir++]=dep[u]^dep[v]^es[i].val;
        }
    }
}

inline void linearBase(){
    memset(p,0,sizeof(p));
    r=0;
    for(int i=0;i<cir;i++){
        ll x=circle[i];
        for(int j=maxp-1;j>=0;j--){
            if(x&(1ll<<j)){
                if(!p[j]){
                    p[j]=x;
                    break;
                }
                x^=p[j];
            }
            if(!x) break;
        }
    }
    for(int i=0;i<maxp;i++)
        if(p[i]) r++;
}

ll ans;
inline void solve(){
    linearBase();
    int i,j;
    ll tot[2];
    for(i=0;i<maxp;i++){
        tot[0]=0,tot[1]=0;
        for(j=0;j<cntc;j++){
            if(dep[cover[j]]&(1ll<<i)) tot[1]++;
            else tot[0]++;
        }
        ll tmp=(tot[0]*(tot[0]-1)/2%mod+tot[1]*(tot[1]-1)/2)%mod;   //路径异或值该位同为1或0的对子数量
        bool f=false;   //true：存在一个线性基该位为1
        for(j=0;j<maxp;j++){
            if(p[j]&(1ll<<i)){
                f=true; break;
            }
        }
        if(f){
            tmp=(tmp*base[r-1]%mod)*base[i]%mod;    //线性基能带来2^(r-1)个2^i值
            ans=(ans+tmp)%mod;
        }
        tmp=tot[0]*tot[1]%mod;
        if(f){
            tmp=(tmp*base[r-1]%mod);	//在该位有线性基，所以只有一半的能做贡献
        }else{
            tmp=tmp*base[r]%mod;    //此时由于线性基该位为0，所以2^r个线性基全做贡献
        }
        tmp=tmp*base[i]%mod;
        ans=(ans+tmp)%mod;
    }
}

int main(){
    cin>>n>>m;
    int u,v;
    ll t;
    memset(head,-1,sizeof(head));
    for(int i=0;i<m;i++){
        scanf("%d%d%lld",&u,&v,&t);
        add(u,v,t);
        add(v,u,t);
    }
    base[0]=1;
    for(int i=1;i<maxp;i++) base[i]=(base[i-1]*2)%mod;
    memset(dep,-1,sizeof(dep));
    for(int i=1;i<=n;i++){
        if(dep[i]==-1){
            cntc=0; //清除上个联通块中的点
            cir=0;  //清除上个联通块中的环
            dfs(i,0,0);
            solve();
        }
    }
    cout<<ans%mod<<endl;
    return 0;
}

Posted on | In ,

​ 线性基类似于线性代数中的基向量，我们找一个整数集的线性基，实际上是找这样一个集合P，使得P中的元素互相异或运算得到的结果集和原集合相等。从二进制上看，最终我们期望得到

​ 1—–

​ 01—

​ 001-

这样的集合，同时也可以进一步将低位的0消去。

向原集合插入一个新数字

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
void inst(ll a){
    for(int i=61;i>=0;i--){
        if(a&(1ll<<i)){
            if(!p[i]){
                p[i]=a;
                break;
            }else{
                a^=p[i];
            }
        }
        if(a==0){
            //可以异或出0,会导致cnt比N小
            break;  //简单优化
        }
    }
}

询问第K大（线性基的值域第k大）

原理从二进制上看很直观，从小到大每个基有选与不选两种选择，将K看作二进制数，选取1位置的基即可，如果线性基能产生0则将k减1。

询问第k大的时候需要你把每个线性基的低位都清除

1
2
3
4
5
6
7
8
9
10
11
12
13
14
ll query(ll k){	//要求线性基已经整理成对角矩阵的形式
    if(cnt<N)	//结果集包含0
        k--;	//把0的次序去掉
    ll res=0;
    for(int i=0;i<=61;i++){
        //这个循环顺序无所谓
        if((k>>i)&1){
            if(rk[i]==-1)   //还没有这个基
                return -1;
            res^=p[rk[i]];  //rk标记第i个基的下标,其实应该是rk的逆映射（
        }
    }
    return res;
}

询问第k大例题：

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

...

int T,N,Q;
ll p[62],rk[62];	//p[i]表示2^i的基
int cnt;

...
    
int main(){
    cin>>T;
    for(int cse=1;cse<=T;cse++){
        memset(rk,-1,sizeof(rk));
        memset(p,0,sizeof(p));
        cnt=0;

        cin>>N;
        ll x;
        for(int i=0;i<N;i++){
            cin>>x;
            inst(x);
        }
        for(int i=0;i<=61;i++){
            if(p[i])
                rk[cnt++]=i;
        }
        for(int i=1;i<=61;i++){     //清除低位1
            for(int j=0;j<i;j++){
                if((1ll<<j)&p[i])
                    p[i]^=p[j];
            }
        }

        cin>>Q;
        cout<<"Case #"<<cse<<":\n";
        while(Q--){
            ll k;
            cin>>k;
            cout<<query(k)<<'\n';
        }
    }
    return 0;
}

Posted on | In

[toc]

A Blank

Blank

计数dp，长为n的数列，每个位置上四种数字选择，题目会给出m个限制条件，每个条件要求在[l,r]范围内有且仅有几种数字。要求给出所有合法方案数。

我们可以用dp来对每种数字上次出现的位置做情况讨论，例如用dp[x][y][z][w][len]来表示0123上次出现位置分别在xyzw、当前读取到第len个字符时共有多少种方案数。然后对于r=len的限制条件，我们查看在l之后出现过的数字种数是否符合要求，即xyzw中大于等于l的有几个。

优化：由于四个位置中必定有一个等于len，所以我们可以减少一个维度，令dp[x][y][z]表示较远出现的三个数字的位置，并且设定顺序，要求x>=y>=z。当且仅当=0时等号可能成立（均未出现过），不会出现两种数字占用同一个格子。

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
#include<vector>
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;

const int mod=998244353;
#define ll long long
int t;
const int maxn=110;
ll dp[maxn][maxn][maxn][2];
struct Condition{
    int l,x;
    Condition(int _l,int _x):l(_l),x(_x){}
};
vector<Condition> cons[maxn];

int main(){
    ios::sync_with_stdio(false);//关同步后不要再同时使用cin和scanf，会导致wa
    cin>>t;
    while(t--){
        int n,m;
        cin>>n>>m;
        //memset(dp,0,sizeof(dp));

        for(int i=0;i<=n;i++)
            cons[i].clear();
        for(int i=0;i<m;i++){
            int l,r,x;
            cin>>l>>r>>x;
            cons[r].push_back(Condition(l,x));
        }
        dp[0][0][0][0]=1;
        int cur=1,last=0;
        for(int i=1;i<=n;i++){
            for (int x=0;x<=i;x++){   //滚动所必须的清零操作
                for (int y=0;y<=x;y++){
                    for (int z=0;z<=y;z++){
                        dp[x][y][z][cur]=0;
                    }
                }
            }

            for(int x=0;x<i;x++){   //0代表未出现过，当且仅当=0时这三/两个变量可等
                for(int y=0;y<=x;y++){
                    for(int z=0;z<=y;z++){
                        dp[x][y][z][cur]+=dp[x][y][z][last];    //i-1
                        dp[i-1][y][z][cur]+=dp[x][y][z][last];  //x
                        dp[i-1][x][z][cur]+=dp[x][y][z][last];  //y
                        dp[i-1][x][y][cur]+=dp[x][y][z][last];  //z

                        dp[x][y][z][cur]%=mod;
                        dp[i-1][y][z][cur]%=mod;
                        dp[i-1][x][z][cur]%=mod;
                        dp[i-1][x][y][cur]%=mod;
                    }
                }
            }

            for(int j=0;j<cons[i].size();j++){
                int l=cons[i][j].l;
                int x=cons[i][j].x;
                for(int a=0;a<i;a++){
                    for(int b=0;b<=a;b++){
                        for(int c=0;c<=b;c++){
                            int type=1+(c>=l?1:0)+(b>=l?1:0)+(a>=l?1:0);
                            if(type!=x)
                                dp[a][b][c][cur]=0;
                        }
                    }
                }
            }
            swap(last,cur);
        }
        ll ans=0;
        for(int x=0;x<n;x++){
            for(int y=0;y<=x;y++){
                for(int z=0;z<=y;z++){
                    if(z==y&&z>0||y==x&&y>0)
                        continue;
                    ans=(ans+dp[x][y][z][last])%mod;
                }
            }
        }
        cout<<ans<<endl;
    }
    return 0;
}

B Operation

Operation

给出一列数。两种操作，对于区间[l,r]挑一些数得到最大的异或和并输出，以及在数列后面附加上一个新数字。

前缀线性基。

我们用p[n][i]中的p[n]表示到1~n个数形成的线性基，同时用pos[n][i]记录每个线性基需要用到的最左边的数的位置。这样在给定区间[l,r]时，我们对于线性基p[r]，判断其中的基的pos是否大于等于l，如果是则这个基是合法的。因此我们在建立线性基时如果遇到相同的有效位，优先采用靠后的那，同时在执行接下来的削减最高位的操作时，要注意它需要用到左边那个数做减数，所以此时pos指向左边那个数的位置。

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
#include<iostream>
#include<cstdio>

using namespace std;
const int maxn=5e5+4;
int n,m,T;

int p[maxn][31];
int pos[maxn][31];

void inst(int k,int x){
    //继承前面的线性基
    for(int i=0;i<=30;i++){
        p[k][i]=p[k-1][i];
        pos[k][i]=pos[k-1][i];
    }
    int tmpPos=k;
    //这里不能生成对角线的线性基，因为无法确定用了哪些基来消除低位0
    //只需要确保大于对应位全0即可，因为异或的一个重要性质是x^x=0，也就是超过一个的运算数是无意义的
    for(int i=30;i>=0;i--){
        if(x&(1<<i)){
            if(!p[k][i]){
                p[k][i]=x;
                pos[k][i]=tmpPos;
                break;
            }else{
                if(tmpPos>pos[k][i]){
                    swap(x,p[k][i]);		 //优先用靠右的
                    swap(tmpPos,pos[k][i]);  //如果未来去掉最高1的x可以作为线性基，则需要之前的k线性基，因为它是减数
                }
                x^=p[k][i];					 //削减最高位
            }
        }
    }
}

int main(){
    cin>>T;
    while(T--){
        scanf("%d%d",&n,&m);
        int x;
        for(int i=1;i<=n;i++){
            scanf("%d",&x);
            inst(i,x);
        }
        int ans=0;
        while(m--){
            int op;
            scanf("%d",&op);
            if(!op){
                int l,r;
                scanf("%d%d",&l,&r);
                l=(l^ans)%n+1;
                r=(r^ans)%n+1;
                if(l>r) swap(l,r);
                int res=0;
                for(int i=30;i>=0;i--){
                    if(pos[r][i]>=l&&((res^p[r][i])>res)) //大于则说明原本i位是0，否则一旦把它清掉肯定结果是变小的。
                        res^=p[r][i];
                }
                printf("%d\n",res);
                ans=res;
            }else{
                scanf("%d",&x);
                x^=ans;
                inst(++n,x);
            }
        }
    }
    return 0;
}

C Milk

Milk

这题是真的难……多部分dp的组合拼接，看别人的博客想了好久才理解。并且最后依然没有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
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
#include<iostream>
#include<cstdio>
#include<cstring>
#include<vector>

#include<algorithm>
using namespace std;
#define ll long long
#define inf 0x3f3f3f3f3f3f3f3f
const int maxn=1e4+4;
int t;
int n,m,k;

struct p{
    int r,c,val;
    p(){}
    p(int _r,int _c,int _val):r(_r),c(_c),val(_val){}
    friend bool operator<(const p& x, const p& y){
        return x.c<y.c;
    }
}ps[maxn];


vector<ll> solve_dp(const vector<p>& ms, int dest){
    //ms[0]是开始位置，dest是结束位置
    vector<ll> dp(ms.size(),inf);
    vector<ll> dp2(ms.size(),inf);
    dp2[0]=0;
    //dp2数组时刻保证距离的增长，即到i的距离，它只有在刚进行过更新时才有可能是有效的dp值,否则会有溢出的距离值
    dp[0]=(dest==-1?0:abs(ms[0].c-dest));
    for(int i=1;i<ms.size();i++){
        int len=ms[i].c-ms[i-1].c;  //到达本次新加入元素的距离
        for(int j=0;j<i;j++)    //注意下标
            dp2[j]+=len;
        for(int j=i;j>0;j--)
            dp2[j]=min(dp2[j],dp2[j-1]+ms[i].val);  //尝试用新元素更新
        for(int j=1;j<=i;j++){
            ll tmp=dp2[j]+(dest==-1?0:abs(ms[i].c-dest)); //刚选取最后一个最优元素时更新成功
            dp[j]=min(dp[j],tmp);
        }
    }
    return dp;
}

vector<ll> merge(const vector<ll>& a,const vector<ll>& b){
    vector<ll> c(a.size()+b.size()-1,inf);
    for(int i=0;i<a.size();i++){
        for(int j=0;j<b.size();j++){
            c[i+j]=min(c[i+j],a[i]+b[j]);
        }
    }
    return c;
}

ll ans[maxn];


int main(){
    cin>>t;
    while(t--){
        scanf("%d%d%d",&n,&m,&k);
        vector<int> disc;
        disc.push_back(1);  //必须考虑第一行
        for(int i=1;i<=k;i++){
            scanf("%d %d %d",&ps[i].r,&ps[i].c,&ps[i].val);
            disc.push_back(ps[i].r);
        }
        sort(disc.begin(),disc.end());
        int rows=unique(disc.begin(),disc.end())-disc.begin();
        disc.erase(disc.begin()+rows,disc.end());

        vector<p> lines[maxn];
        for(int i=0;i<=rows;i++)
            lines[i].clear();
        for(int i=1;i<=k;i++){
            int row=lower_bound(disc.begin(),disc.end(),ps[i].r)-disc.begin();
            lines[row].push_back(ps[i]);
            ans[i]=inf;
        }
        for(int i=0;i<rows;i++){
            sort(lines[i].begin(),lines[i].end());
        }

        vector<p> curL=lines[0];
        vector<ll> dp[2];

        curL.insert(curL.begin(),p(1,1,0));
        vector<ll> dp0=solve_dp(curL,-1);
        dp[0]=solve_dp(curL,(m+1)/2);
        for(int i=1;i<curL.size();i++)
            ans[i]=min(ans[i],dp0[i]);

        for(int i=1;i<rows;i++){
            curL=lines[i];
            p ept(disc[i],(m+1)/2,0);
            vector<p>::iterator split=lower_bound(curL.begin(),curL.end(),ept);
            vector<p> l=vector<p>(curL.begin(),split);
            vector<p> r=vector<p>(split,curL.end());

            l.push_back(ept);
            r.insert(r.begin(),ept);

            reverse(l.begin(),l.end());

            vector<ll> dpl[2];
            vector<ll> dpr[2];

            dpl[0]=solve_dp(l,-1);
            dpl[1]=solve_dp(l,(m+1)/2);
            dpr[0]=solve_dp(r,-1);
            dpr[1]=solve_dp(r,(m+1)/2);

            vector<ll> g1,g2;
            g1=merge(dpl[0],dpr[1]);
            g2=merge(dpl[1],dpr[0]);
            vector<ll> g(g1.size());    //本行不返回中点的dp值
            for(int i=1;i<g.size();i++){
                g[i]=min(g1[i],g2[i]);
                //g[i]+=(disc[i]-disc[i-1]);
            }

            g=merge(dp[(i-1)&1],g); //g是当前最优解
            dp[i&1]=merge(dp[(i-1)&1],merge(dpl[1],dpr[1]));

            for(int j=0;j<g.size();j++){
                dp[i&1][j]+=(disc[i]-disc[i-1]);
                ans[j]=min(ans[j],g[j]+=(disc[i]-disc[i-1]));    //只有在刚达到最优结果时才能更新成功
            }
        }
        for(int i=1;i<=k;i++)
            printf("%lld%c",ans[i],(i==k?'\n':' '));
    }
    return 0;
}

我觉得单独一个部分的dp就差不多够我做了。

F Typewriter

链接

给定一个字符串，用两种方法逐步构造它，可以在字符串后面以p代价附加任一字符，也可以复制已生成字符串的任一段子串到最后，代价q。求构造的最小代价。

后缀自动机+dp

dp[i]表示构造到第i位时的最小代价，显然满足dp[i]=min(dp[i-1]+p,dp[j]+q)，其中j+1到i的字符串可以从1到j的子串复制过来，同时我们可证明dp数组是一个不降序列，因此这里的j我们取最小的一个。

在对每一个dp[i]更新时，我们需维护这个j，实际上是在维护后缀自动机中的一个状态，首先这个状态代表的后缀要以s[i]结尾才是合法的，进而满足这个后缀集合中最长的一个要大于等于i-j，在此基础上它可以尽可能地向父亲跳，因为从父亲的next可能性更多。当某个状态没有通向s[i]的next时，我们需要再加入一个点，即执行extend(s[++j])。

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
#include<bits/stdc++.h>
//6583
using namespace std;
#define ll long long
const int maxn=2e5+2;
struct state{
    int len,link;
    int next[26];
};
inline int getnum(char ch){ return ch-'a';}
state st[maxn*4];
int sz,last;
ll dp[maxn];
void sam_init(){
    st[0].len=0;
    st[0].link=-1;
    sz=1;
    last=0;
}
void sam_extend(int ch){
    int cur=sz++;
    st[cur].len=st[last].len+1;
    int p=last;
    while(p!=-1&&!st[p].next[ch]){
        st[p].next[ch]=cur;
        p=st[p].link;
    }
    if(p==-1){
        st[cur].link=0;
    }else{
        int q=st[p].next[ch];
        if(st[p].len+1==st[q].len){
            //不修改pos
            st[cur].link=q;
        }else{                //考虑到q可能由其他拥有不同前缀的子串延申而来（更长）
            int clone=sz++;
            st[clone].len=st[p].len+1;
            memcpy(st[clone].next,st[q].next,sizeof(st[clone].next));
            st[clone].link=st[q].link;
            while(p!=-1&&st[p].next[ch]==q){
                st[p].next[ch]=clone;
                p=st[p].link;
            }
            st[q].link=st[cur].link=clone;
        }
    }
    last=cur;
}

char s[maxn];

int main(){
    ll p,q;
    while(~scanf("%s",s)){
        sam_init();
        cin>>p>>q;
        int len=strlen(s);
        for(int i=0;i<=len*2;i++){	//注意清零next
            memset(st[i].next,0,26*sizeof(int));
        }
        dp[0]=p;
        sam_extend(getnum(s[0]));
        int j=0;
        int cur=st[0].next[getnum(s[0])];    
        for(int i=1;i<len;i++){
            dp[i]=dp[i-1]+p;
            while(1){
                while(cur!=0&&st[st[cur].link].len>=i-j-1){
                    cur=st[cur].link;
                }
                if(st[cur].next[getnum(s[i])]){
                    cur=st[cur].next[getnum(s[i])];
                    break;
                }else{
                    sam_extend(getnum(s[++j]));
                }
            }
            dp[i]=min(dp[i],dp[j]+q);
        }
        cout<<dp[len-1]<<endl;
    }
    return 0;
}

I String

链接

给一个字符串，要求寻找长度为k、字典序最小的子序列，其中每个字母都要满足一个限定条件，即出现次数在[L,R]之间。

从0到k-1逐位贪心构造结果串，即对每一位从a到z尝试是否合法，合法则选用再看下一位。合法共需满足四个条件（看代码）。

用到了序列自动机，就是一个记录了每个位置后某个字母第一次出现在哪里的数组。

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
#include<bits/stdc++.h>
using namespace std;

const int maxn=1e5+4;
int nxt[maxn][26];
int now[26];
int l[26],r[maxn][26];  //l记录左边已选用的字符数量，r记录[r,n-1]中剩余各个字符的数量
int cond[26][2];
char s[maxn];
int k,n;
char ans[maxn];

void init(){
    n=strlen(s+1);
    memset(now,-1,sizeof(now));
    memset(r,0,sizeof(r));
    memset(l,0,sizeof(l));
    for(int i=n;~i;--i){    //这里下标必须是1到n，因为要用0作为起点
        for(int j=0;j<26;j++){
            nxt[i][j]=now[j];
            r[i][j]=r[i+1][j];
        }
        if(!i) break;
        now[s[i]-'a']=i;
        r[i][s[i]-'a']++;
    }
}

bool check(int pos,int ch,int cap){
    //check添加pos位置的ch字符是否可行，还剩cap个字符未添加

    l[ch]++;
    if(pos==-1){
        return false;   //如果已经没有ch字符
    }

    int need=0;
    for(int i=0;i<26;i++){  //剩余总量不能小于剩余必须的总和
        need+=max(0,cond[i][0]-l[i]);
    }
    if(need>cap)
        return false;

    for(int i=0;i<26;i++){  //已选的加上剩下所有可选的不能不够最低要求
        if(l[i]+r[pos+1][i]<cond[i][0])
            return false;
    }

    if(l[ch]>cond[ch][1])  //选上后不能超过
        return false;

    return true;
}

int main(){
    while(~scanf("%s%d",s+1,&k)){
        int L,R;
        for(int i=0;i<26;i++){
            scanf("%d%d",&L,&R);
            cond[i][0]=L;
            cond[i][1]=R;
        }
        init();
        int pos=0;
        bool f=true;
        for(int i=0;i<k;i++){
            if(!f) break;
            for(int j=0;j<26;j++){
                if(check(nxt[pos][j],j,k-i-1)){
                    ans[i]=j+'a';
                    pos=nxt[pos][j];
                    //l[j]++; //已经在check中加过了
                    break;
                }
                l[j]--;
                if(j==25){
                    f=false;
                }
            }
        }
        ans[k]=0;
        if(f) printf("%s\n",ans);
        else printf("-1\n");
    }
    return 0;
}

Posted on | In ,

模板题

树剖模板

这个题的需求是给定一棵树，操作支持区间修改和点查询，我们一样用线段树维护区间和实现区间查询。

三种操作I、D、Q分别是对于一条路径上的点增/减和询问某个点的当前值

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
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
//树剖（需求：区间修改，点查询）
//剖分结束后，线段树维护区间和
#include<iostream>
#include<cstdio>
#include<cstring>
#include<vector>
using namespace std;
#define ll long long
#define lson (rt<<1)
#define rson (rt<<1|1)
const int maxn=5e4+10;
int a[maxn];
int n,m,p;
struct{
    ll val,lazy;
}t[maxn<<2];

vector<int> e[maxn];
int dep[maxn];
int fa[maxn];
int siz[maxn];
int son[maxn];  //重儿子
int dfn[maxn];  //树上dfs序
int rnk[maxn];  //dfn的逆映射，用于建立线段树
int top[maxn];  //所在重链的头部

void pushup(int rt){
    t[rt].val=t[lson].val+t[rson].val;
}
void pushdown(int rt,int l,int r){
    if(t[rt].lazy!=0){
        int m=(l+r)/2;
        t[lson].val+=(m-l+1)*t[rt].lazy;
        t[rson].val+=(r-m)*t[rt].lazy;
        t[lson].lazy+=t[rt].lazy;
        t[rson].lazy+=t[rt].lazy;
        t[rt].lazy=0;
    }
    return ;
}

void build(int rt,int l,int r){
    t[rt].lazy=0;
    if(l==r){
        t[rt].val=a[rnk[l]];
        t[rt].lazy=0;
        return ;
    }
    int m=(l+r)/2;
    build(lson,l,m);
    build(rson,m+1,r);
    pushup(rt);
    return;
}
void update(int L,int R,int l,int r,int rt,int v){
    if(l>=L&&r<=R){
        t[rt].val+=(r-l+1)*v;
        t[rt].lazy+=v;
        return ;
    }
    pushdown(rt,l,r);
    int m=(l+r)/2;
    if(L<=m){
        update(L,R,l,m,lson,v);
    }
    if(R>m){
        update(L,R,m+1,r,rson,v);
    }
    pushup(rt);
}
long long query(int L,int R,int l,int r,int rt){
    if(l>=L&&r<=R){
        return t[rt].val;
    }
    pushdown(rt,l,r);
    int m=(l+r)/2;
    long long res=0LL;
    if(L<=m){
        res+=query(L,R,l,m,lson);
    }
    if(R>m){
        res+=query(L,R,m+1,r,rson);
    }
    return res;
}

void dfs1(int o,int from,int d){
    //第一遍处理fa、son、dep、siz
    siz[o]=1;
    dep[o]=d;
    fa[o]=from;
    for(int i=0;i<e[o].size();i++){
        int v=e[o][i];
        if(v==from)
            continue;
        dep[v]=dep[o]+1;
        dfs1(v,o,d+1);
        siz[o]+=siz[v];
        if(son[o]==-1||siz[v]>siz[son[o]]){
            son[o]=v;
        }
    }
}
int cnt;
void dfs2(int o,int t){	//t是当前重链最上面的点
    //第二遍处理dfn、top、rnk
    top[o]=t;
    dfn[o]=++cnt;
    rnk[dfn[o]]=o;
    if(son[o]!=-1){
        dfs2(son[o],t);
    }
    for(int i=0;i<e[o].size();i++){
        int v=e[o][i];
        if(v==fa[o]||v==son[o])
            continue;
        dfs2(v,v);	//轻儿子开启一条重链
    }
}

void solve(int x,int y,int v){	//每次更新一段重链
    int fx=top[x];
    int fy=top[y];
    while(fx!=fy){
        if(dep[fx]<dep[fy]){
            swap(fx,fy);
            swap(x,y);
        }
        update(dfn[fx],dfn[x],1,n,1,v);
        x=fa[fx];
        fx=top[x];
    }
    if(dep[x]>dep[y]){
        swap(x,y);
    }
    update(dfn[x],dfn[y],1,n,1,v);
}

int main(){
    while(cin>>n>>m>>p){	
        cnt=0;
        for(int i=1;i<=n;i++){
            scanf("%d",a+i);
            e[i].clear();
        }
        for(int i=0;i<m;i++){
            int u,v;
            scanf("%d%d",&u,&v);
            e[u].push_back(v);
            e[v].push_back(u);
        }
        memset(son,-1,sizeof(son));
        dfs1(1,-1,1);
        dfs2(1,1);
        build(1,1,n);
        while(p--){
            //这里最初读入字符出现了混乱，似乎不止一个空格？前面换行时有时无
            char cmd[5];
            scanf("%s",cmd);
            if(cmd[0]=='I'||cmd[0]=='D'){
                int x,y,v;
                scanf("%d%d%d",&x,&y,&v);
                if(cmd[0]=='D')
                    v=-v;
                solve(x,y,v);
            }else if(cmd[0]=='Q'){
                int q;
                scanf("%d",&q);
                cout<<query(dfn[q],dfn[q],1,n,1)<<endl;
            }
        }
    }
    return 0;
}

Posted on | In

例题洛谷一道题

线段树的讲解推荐博客

这道题唯一难点在于lazy标记的处理，因为涉及加和乘两种区间修改，需要考虑运算顺序。

板子：

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
#include<bits/stdc++.h>

using namespace std;
const int maxn=1e5;
#define lson (rt<<1)
#define rson (rt<<1|1)
//lazy_tag定义：记录当前节点的修改量，当前节点此时已完成修改，是这个算法区间修改复杂度优秀的核心
//这里add、mul分别是加和乘的lazy标记
int p;
int a[maxn];
struct{
    long long val,add,mul;
}t[maxn<<2];
//由子节点更新父节点的操作，区间合并
void pushup(int rt){
    t[rt].val=(t[lson].val+t[rson].val)%p;
}
//lazy标记下移，意味着子节点的值也要修改啦，先更新子节点的值，再补充修改它们的lazy标记
//这里我们规定计算顺序：先算乘法再加上add值，add相当于一个附加的offset，所以在更新乘法的lazy时，add标记同时也要乘上这个值。
//什么时候需要pushdown？上面提到的博客中很好地总结了：当接下来要用到当前区间的子区间时，需要把父节点之前存留的修改传下去
void pushdown(int rt,int l,int r){
    int m=(l+r)/2;
    t[lson].val=(t[lson].val*t[rt].mul%p+(m-l+1)*t[rt].add%p)%p;
    t[rson].val=(t[rson].val*t[rt].mul%p+(r-m)*t[rt].add%p)%p;
    t[lson].mul=(t[lson].mul*t[rt].mul)%p;
    t[rson].mul=(t[rson].mul*t[rt].mul)%p;
    t[lson].add=(t[lson].add*t[rt].mul%p+t[rt].add)%p;
    t[rson].add=(t[rson].add*t[rt].mul%p+t[rt].add)%p;
    t[rt].mul=1;
    t[rt].add=0;
    return ;
}
//bottom-up建树
void build(int l,int r,int rt){
    t[rt].add=0;
    t[rt].mul=1;
    if(l==r){
        t[rt].val=a[l-1];
    }else{
        int m=(l+r)/2;
        build(l,m,lson);
        build(m+1,r,rson);
        pushup(rt);
    }
    t[rt].val%=p;
    return ;
}
//top-down更新
void update_add(int L,int R,int l,int r,int rt,int v){
    if(l>=L&&r<=R){
        t[rt].add=(t[rt].add+v)%p;
        t[rt].val=(t[rt].val+(r-l+1)*v%p)%p;
        return;
    }
    pushdown(rt,l,r);
    int m=(l+r)/2;
    if(L<=m){
        update_add(L,R,l,m,lson,v);
    }
    //注意这个地方不能写成if-else，因为这两种情况可能同时出现，不是非此即彼的关系
    if(R>m){
        update_add(L,R,m+1,r,rson,v);
    }
    pushup(rt);
}

void update_mul(int L,int R,int l,int r,int rt,int v){
    if(l>=L&&r<=R){
        t[rt].mul=(t[rt].mul*v)%p;
        t[rt].add=(t[rt].add*v)%p;
        t[rt].val=(t[rt].val*v)%p;
        return;
    }
    pushdown(rt,l,r);
    int m=(l+r)/2;
    if(L<=m){
        update_mul(L,R,l,m,lson,v);
    }
    if(R>m){
        update_mul(L,R,m+1,r,rson,v);
    }
    pushup(rt);
}

long long query(int L,int R,int l,int r,int rt){
    if(l>=L&&r<=R){
        return t[rt].val;
    }
    pushdown(rt,l,r);
    int m=(l+r)/2;
    long long res=0LL;
    if(L<=m){
        res+=query(L,R,l,m,lson);
    }
    if(R>m){
        res+=query(L,R,m+1,r,rson);
    }
    return res%p;
}

int n,m;
int main(){
    cin>>n>>m>>p;
    for(int i=0;i<n;i++)
        scanf("%d",a+i);
    build(1,n,1);
    for(int i=0;i<m;i++){
        int flag;
        scanf("%d",&flag);
        if(flag==1){
            int L,R,v;
            scanf("%d%d%d",&L,&R,&v);
            update_mul(L,R,1,n,1,v);
        }else if(flag==2){
            int L,R,v;
            scanf("%d%d%d",&L,&R,&v);
            update_add(L,R,1,n,1,v);
        }else{
            int L,R;
            scanf("%d%d",&L,&R);
            cout<<query(L,R,1,n,1)<<endl;
        }
    }
    return 0;
}

Posted on | In

npm 安装

nodejs安装在了D盘，同时npm安装目录也设在了D盘，按照博客上教的方法设置即可

由于官网速度慢，想按照网友的方法设置镜像下载源，需要nrm这个工具，但由于某些原因npm安装一直卡在checking安装状态这一步（翻墙中）。这个时候从网上查到了一个方法：删掉C盘Roaming目录下的npm和npm-cache文件夹，但是可能是我更改了默认安装目录的原因，并未找到这两个文件夹。

最后的解决方法是，使用–registry=https://registry.npm.taobao.org先临时使用镜像站下载该工具，然后按照其他教程设置默认下载源为taobao即可

hexo提交免输入密码

设置ssh后，项目目录下_config.yml文件中的repository的地址写成git@github.com:格式

常用命令

ssh -T git@gitbub.com测试ssh连接

删除文章

hexo clean

删除本地md

hexo d -g

Posted on | In

Welcome to Hexo! This is your very first post. Check documentation for more info. If you get any problems when using Hexo, you can find the answer in troubleshooting or you can ask me on GitHub.

Quick Start

Create a new post

1
$ hexo new "My New Post"

More info: Writing

Run server

1
$ hexo server

More info: Server

Generate static files

1
$ hexo generate

More info: Generating

Deploy to remote sites

1
$ hexo deploy

More info: Deployment