算法复健计划——构造题专栏

第一篇博客就献给算法题解了，根据知乎上大佬的说法，可以先做构造题，提升自己的思维水平，我这里也就先从构造题入手，慢慢恢复自己的做题能力。那么就开始吧！

cf round 735D (1554D) 2023/10/14

题目

给定一个正整数n，要求构造字符串，满足如下条件：

  1. 长度为n；
  2. 仅包含小写字母；
  3. 相同子串出现次数为奇数。

数量级：t次询问（$1 \leq t \leq 500$），每次的n（$3 \leq n \leq 10^5$），n之和不超过$3 \cdot 10^5$。

解法

由于需要设计一个通用的构造算法，那么首先可以猜测，大概率不会将26个小写字母全部用到，所以目前目标为：用较少的字母种数，设计一个通用的生成算法。

其次，可以发现，对一个字符串中某个字母而言，如果它仅出现了一次，那么包含它的所有子串均仅出现了一次。比如aabbcaab中的c，如果一个子串包含c，不论它的左边界和右边界在哪里，这样的子串有且仅有一个。

因此，可以选定一个字母作为分隔符，放在字符串中间，该字母左边的字符串用于满足长度要求，右边的字符串用于满足相同子串出现次数为奇数。

可以先从短的序列入手，用数学归纳法分析：

  • 左边长度 $\leq$ 2：随便构造；
  • 左边长度 $ = $ 3：如aba，子串a有偶数个，需要用1个a来平衡，所以右边字符串为a可平衡；
  • 左边长度 $ = $ 4：如abab，子串a、b、ab有偶数个，右边字符串为ab可平衡；
  • 左边长度 $ = $ 5：如ababa，子串b、ab、ba有偶数个，右边字符串为aba可平衡；
  • 左边长度 $ = $ 6：如ababab，子串aba、bab、abab有偶数个，右边字符为abab可平衡；

通过观察，可以找到以下规律：设字符串ababab……为S（a或b结尾均可），则字符串ab+S+c+S一定为满足题目要求的字符串。证明如下：

  1. 不包含c的子串：对于前一个S中任何一个子串，都有在后一个S中与其位置完全对应的子串。所以如果不考虑最初的ab，对每类子串来说，该类子串均有偶数个。当加入最初的ab时，以这里的a或b作为子串左端点，每类子串又各多了一个，此时每类子串均有奇数个。
  2. 包含c的子串：c是分隔符，因此每类子串有且只有一个。

字符串ab+S+c+S的长度为 $2|S|+3$ 。

最终解法如下：

  • n较小（$n\leq26$）的时候：直接放n个不同字母；
  • n较大的时候：n是奇数，直接用ab+S+c+S的方式构造；n是偶数，字符串最后放一个d，问题退化为n-1的形式，使用奇数方法解决即可。

代码（核心部分）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
char s[100005];
void solve(){
    int n;
    scanf("%d",&n);
    s[n]=0;
    if(n<26){
        for(int i=0;i<n;i++){
            s[i]='a'+i;
        }
        return;
    }
    if((n&1)==0){
        s[n-1]='d';
        n--;
    }
    int x=(n-3)/2;
    s[0]='a';
    s[1]='b';
    s[x+2]='c';
    for(int i=2;i<x+2;i++){
        s[i]=s[i+x+1]=s[i-2];
    }
}

思考

好久没有写算法题和博客了，下次一定注意~

这道题是div2的D，也是想了得有一二十分钟才会做，之前还走了点岔路。老样子，总结复盘一下：

前期思考

第一眼看到这道题，下意识以为是分治+递归，将字符串从中间劈开，左右两边分别考虑。后面发现不太行，有两点原因：

  1. 小写字母个数有限，最终两边的字符串不得不用相同的字母时，无法将二者独立考虑；
  2. 无法独立考虑，可以记录状态。但这里的状态过多，包括每类子串个数的奇偶性，难以完全记录。

总的来说，分治的前提是能将原问题的分拆成多个类似的子问题，同时这些子问题能在一定程度上解耦，这道题很难做到真正的解耦，所以很难通过分治来解决。

换个思考方式，那就是归纳/递推。我在这里是发现分隔符的特性之后，便尝试让左边字符串的重点关注字符串长度，右边字符串的重点满足奇偶性。将长度要求和子串奇偶性要求解耦，发现规律后可以很方便地证明合理性。

代码实现非常简单，没有太多可以说的。标准答案子串S仅用了字母a，构造成a+S+b+S的形式，更加方便。

cf round 629D (1328D) 2023/09/30

题目

题意还是比较简单的，n个动物排成一圈，需要给每个动物染色。要求：相邻的不同动物染成不同的颜色，同种动物没有要求。

问：给出最少所需颜色数量和对应的染色方式。

数量级：动物个数为n（$3 \leq n \leq 2 \cdot 10^5$），种数为k（$1 \leq k \leq 2 \cdot 10^5$）。

解法

可以从所需颜色数量（记为m）入手考虑，可以发现最多需要三种颜色（每个动物只有两个相邻的动物，如果两个动物颜色不同，中间这只染成第三种颜色就行）。

此时就可以分别讨论满足m=1，m=2，m=3的情况：

  1. m=1：显然，只有一种动物的话，才能这样；

  2. m=2：

    2.1：n是偶数：那么1212…12这样染色就行（泛化性更强结论的可以参见图的着色）；

    2.2：n是奇数，但是有连续的动物是同一种类：如果还是1212这样染，最后一个动物和第一个动物的颜色都会是1，不可以。但连续同种动物给了一些操作空间，可以把任意一对相邻同种动物染成同样颜色，那么最后一个动物就可以是颜色2，不与第一个动重复了；

  3. m=3：也就是n是奇数，且相邻动物种类均不同，那只能多加一个颜色，像1212…123这样构造了。

代码（核心部分）

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
int a[200005];
queue<int> ans;
void print_ans(int num){
    printf("%d\n",num);
    while(!ans.empty()){
        printf("%d%c",ans.front(),ans.size()==1?'\n':' ');
        ans.pop();
    }
}
void solve(){
    int n;
    scanf("%d",&n);
    for(int i=0;i<n;i++){
        scanf("%d",&a[i]);
    }
    // 1
    int flag=1;
    for(int i=1;i<n;i++){
        if(a[i]!=a[i-1]){
            flag=0;
            break;
        }
    }
    if(flag){
        for(int i=0;i<n;i++){
            ans.push(1);
        }
        print_ans(1);
        return;
    }

    // 2
    flag=-1;
    for(int i=0;i<n;i++){
        if(a[i]==a[(i+1)%n]){
            flag=i;
            break;
        }
    }
    if(n%2==0){
        for(int i=0;i<n;i++){
            ans.push((i%2)+1);
        }
        print_ans(2);
        return;
    }
    else if(flag!=-1){
        int tmp[n]={0};
        tmp[(flag+n)%n]=1;
        tmp[(flag+1+n)%n]=1;
        int now=0;
        for(int i=2;i<n;i++){
            now^=1;
            tmp[(flag+i)%n]=now+1;
        }
        for(int i=0;i<n;i++){
            ans.push(tmp[i]);
        }
        print_ans(2);
        return;
    }

    // 3
    for(int i=0;i<n-1;i++){
        ans.push(i%2+1);
    }
    ans.push(3);
    print_ans(3);
    return;
}

思考

这道题是div3的D，其实挺简单的，但一开始想的时候还是走错了路，最后看了题解，wa了几次才做对的。这里简单复盘一下：

前期思考

自己一开始想的时候，发现了了可以想象成一个graph然后进行着色。但关键是，没有意识到最多只需要三种颜色，所以打算用dp的思路。

后期发现了这一点，但还是走在dp的道路上一去不复返了。在写状态转移的过程中，发现倒推染色构造方式有些麻烦，觉得dp应该不是正解，所以去看题解了。

代码实现

实现的时候wa了几发，原因如下：

  1. 在m=3时，没有多想，觉得12312312…这样的构造方式可以解决所有问题。但是问题就出在第n个动物和第1个动物的关系上，事实上，多一种颜色就是为了解决这个问题，正确的构造方式为1212…123；

  2. 代码没有考虑到第1个动物和第n个动物颜色相同，导致满足m=2的情况；

总结

很久没有写题了，思维方面，想出一个div3 D也磕磕绊绊的；相应的，写作方面，第一次写题解，行文逻辑和简约程度都有待优化。但不管怎么说，也算一个开始了，还是要继续努力呀！

#技术沉淀
算法复健计划——构造题专栏
http://example.com/2023/09/30/algo-contrustive/
作者
changez
发布于
2023年9月30日
许可协议