2021 杭电多校 7 题解

发表于 | 评论数： | 阅读次数：
Solved A B C D E F G H I J K L
11/12 Ø . O O O O O O O O O O
  • O for passing during the contest
  • Ø for passing after the contest
  • ! for attempted but failed
  • · for having not attempted yet

比赛链接

这场比赛的 A 题比较有趣，记录一下。

A

题目描述

给一个长度为 $n\le 1e5$ 的串 $S$，和常数 $k\le 1e5$。要求构造一个串 $T$ 满足：

  1. $|S|=|T|$；
  2. $T$ 字典序不小于 $S$；
  3. 任意字母出现次数为 $k$ 的因数；
  4. $T$ 是所有满足上述条件中字典序最小的。

$T\le 32$ 组数据， $\sum |S|\le 1e6$，时限 10s。

解题思路

由于 $T$ 要求字典序最小，考虑二分与 $S$ 第一个不同的位置。如果可以构造，则右移左端点；否则左移右端点。check 的时候，使用 bitset 加速背包并记录位置即可。问题在于到底是对于什么条件二分，这个条件一定要有单调性。

下面是比赛记录，正解在最后

场上最初想的是，既然考虑可行性，就先不考虑字典序要求比 $S$ 大这个条件，直接判断从哪个位置开始往后可能有解，顺便求出来答案：在 $[1,x]$ 与 $S$ 相同， $x+1$ 位是某个元素，后面是一串类似 aaaaabbbbbcccdd 的递增序列。。这个的复杂度是对的，$O(26d(k)\frac{n}{32}\log n)$。但是考虑 5 6 zzzzz 的情况，应当无解。于是假了。

改了一下想法后，先枚举下一位填什么，对于下一位填 $c$ 可行的这些位置，可行性具有单调性。这样确实是正确的，但复杂度 $O(26^2d(k)\frac{n}{32}\log n)=O(26^2n\log n)$，太大了。

TLE代码

点击
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
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<queue>
#include<map>
#include<set>
#include<cmath>
#include<vector>
#include<cassert>
#include<ctime>
#include<bitset>
#include<functional>
typedef long long ll;
using namespace std;
#define pii pair<int,int>
#define pll pair<ll,ll>
#define pil pair<int,ll>
#define pli pair<ll,int>
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define N 100010
char s[N],t[N],ans[N],res[N];
int n,k;
vector<int>fac;
void init(){
    int i;
    fac.clear();
    for(i=1;i*i<=k;i++){
        if(k%i==0){
            fac.pb(i);
            if(i*i!=k)fac.pb(k/i);
        }
    }
    fac.pb(0);
    sort(fac.begin(),fac.end());
}
int num[26],ind[26],rem[26];
int check(int x,int ch){
    // [0, x] same with s
    int i,j,c;
    memset(num,0,sizeof(num));
    memset(rem,0,sizeof(rem));
    for(i=1;i<=x;i++){
        t[i]=s[i];
        num[s[i]-'a']++;
    }
    int sum=n-x;
    for(i=0;i<26;i++){
        auto it=lower_bound(fac.begin(),fac.end(),num[i]);
        if(it==fac.end())return 0;
        ind[i]=it-fac.begin();
        int nxt=*it;
        sum-=nxt-num[i];
        rem[i]=nxt-num[i];
        num[i]=nxt;
    }
    if(sum<0)return 0;
    
    // construct sum
    if(x==n)return sum==0;
    
    ++x;
    t[x]=ch+'a';
    memset(num,0,sizeof(num));
    memset(rem,0,sizeof(rem));
    for(i=1;i<=x;i++)num[t[i]-'a']++;
    sum=n-x;
    for(i=0;i<26;i++){
        auto it=lower_bound(fac.begin(),fac.end(),num[i]);
        if(it==fac.end())return 0;
        ind[i]=it-fac.begin();
        int nxt=*it;
        sum-=nxt-num[i];
        rem[i]=nxt-num[i];
        num[i]=nxt;
    }
    if(sum<0)return 0;
    
    bitset<N>bs[26];bs[25].reset();
    bs[25][0]=1;
    for(i=24;i>=0;i--){
        bs[i].reset();
        for(j=ind[i];j<fac.size();j++)bs[i]|=(bs[i+1]<<(fac[j]-num[i]));
    }
    if(!bs[0][sum])return 0;
    
    int cur=sum;
    for(i=0;i<26;i++){
        for(j=fac.size()-1;j>=ind[i];j--){
            if(cur-(fac[j]-num[i])>=0&&bs[i+1][cur-(fac[j]-num[i])]){
                cur-=fac[j]-num[i];
                rem[i]+=fac[j]-num[i];
                break;
            }
        }
    }
    assert(!cur);
    
    cur=x+1;
    for(i=0;i<26;i++)for(j=0;j<rem[i];j++)t[cur++]=i+'a';
    t[cur]='\0';
    assert(cur-1==n);
    assert(t[x]>s[x]);
    strcpy(ans+1,t+1);
    return 1;
}
int main(){
    int T,i,j;
    scanf("%d",&T);
    while(T--){
        scanf("%d%d",&n,&k);
        init();
        scanf("%s",s+1);
        res[1]='z'+1;res[2]='\0';
        if(check(n,0)){
            printf("%s\n",s+1);
            continue;
        }
        vector<int>v[27];
        for(i=1;i<=n;i++)for(j=s[i]-'a'+1;j<26;j++)v[j].pb(i);
        for(i=0;i<26;i++){
            int L=0,R=v[i].size();
            ans[1]='z'+1;ans[2]='\0';
            while(L<R){
                int mid=(L+R)>>1;
                if(check(v[i][mid]-1,i))L=mid+1;
                else R=mid;
            }
            if(strcmp(res+1,ans+1)>0)strcpy(res+1,ans+1);
        }
        if(res[1]>'z')printf("-1\n");
        else printf("%s\n",res+1);
    }
    return 0;
}

其实离正解只差一步。

我需要找的是可行解，在判断可行解的时候不一定要找出来最优解。也就是说，二分的时候，只需要找出可行位置就可以了。对于一个位置 $x$ ，如果最大字典序的合法串都不行，那就确实不行了。

于是，check 的条件为：对于当前位置，能否找到字典序最大的可行解。

找到位置后，再背包一次就可求出最优解。复杂度 $O(26d(k)\frac{n}{32}\log n)$。

AC代码

点击
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
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<queue>
#include<map>
#include<set>
#include<cmath>
#include<vector>
#include<cassert>
#include<ctime>
#include<bitset>
#include<functional>
typedef long long ll;
using namespace std;
#define pii pair<int,int>
#define pll pair<ll,ll>
#define pil pair<int,ll>
#define pli pair<ll,int>
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define N 100010
char s[N],t[N];
int n,k;
vector<int>fac;
void init(){
    int i;
    fac.clear();
    for(i=1;i*i<=k;i++){
        if(k%i==0){
            fac.pb(i);
            if(i*i!=k)fac.pb(k/i);
        }
    }
    fac.pb(0);
    sort(fac.begin(),fac.end());
}
int num[26];
int check(int x){
    // [0, x] same with s
    int i,j,c;
    memset(num,0,sizeof(num));
    for(i=1;i<=x;i++)num[s[i]-'a']++;
    if(x==n){
        for(i=0;i<26;i++)if(num[i]&&k%num[i])return 0;
        return 1;
    }
    
    bitset<N>bs[27];bs[0].reset();bs[0][0]=1;
    for(i=1;i<=26;i++){
        bs[i].reset();
        for(auto p:fac)if(p>=num[i-1])bs[i]|=bs[i-1]<<(p-num[i-1]);
    }
    if(!bs[26][n-x])return 0;
    
    for(i=25;i>=0;i--){
        while(s[x+1]==i+'a')++num[i],++x;
        if(s[x+1]>i+'a')break;
        for(auto p:fac){
            int len=p-num[i];
            if(len>0&&n-(x+len)>=0&&bs[i][n-(x+len)])return 1;
        }
        if(num[i]&&k%num[i])return 0;
    }
    return 0;
}
void construct(int x){
    int i,j,l,c;
    memset(num,0,sizeof(num));
    for(i=1;i<=x;i++){
        t[i]=s[i];
        num[s[i]-'a']++;
    }
    
    x++;
    for(c=s[x]-'a'+1;c<26;c++){
        num[c]++;
        
        bitset<N>bs[27];
        for(i=0;i<27;i++)bs[i].reset();bs[26][0]=1;
        for(i=25;i>=0;i--)for(auto p:fac)if(p>=num[i])bs[i]|=(bs[i+1]<<(p-num[i]));
        int cur=n-x;
        if(!bs[0][cur]){
            num[c]--;
            continue;
        }
        
        t[x]=c+'a';
        for(i=0;i<26;i++){
            for(j=fac.size()-1;j>=0;j--){
                if(fac[j]>=num[i]&&cur-(fac[j]-num[i])>=0&&bs[i+1][cur-(fac[j]-num[i])]){
                    cur-=fac[j]-num[i];
                    for(l=0;l<fac[j]-num[i];l++)t[++x]=i+'a';
                    break;
                }
            }
        }
        assert(x==n);
        assert(!cur);
        return;
    }
    printf("?");
}
int main(){
    int T,i,j,nCas=0;
    scanf("%d",&T);
    while(T--){
        scanf("%d%d",&n,&k);
        init();
        scanf("%s",s+1);
        if(check(n)){
            printf("%s\n",s+1);
            continue;
        }
        if(!check(0)){
            printf("-1\n");
            continue;
        }
        int L=0,R=n;
        while(L<R){
            int mid=(L+R+1)>>1;
            if(check(mid))L=mid;
            else R=mid-1;
        }
        construct(L);
        t[n+1]='\0';
        printf("%s\n",t+1);
    }
    return 0;
}