2019杭电多校第一场

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;
}