Zth's Blog

记录学习路上的点滴

0%

namonamo Namomo 每日一题div1 03-30

发表于 分类于

题目链接

折半搜索

概述

搜索得到一个集合的幂集， 通常集合大小小于等于$40$， 因为$2^{20} \approx 10^6$， 再来上$10$组$20$组数据差不多就到极限了

搜索方法

将集合分成前后两半， 两半分别进行暴搜， 然后合并两部分的结果得到所需答案

题目

题意

给出一个长度为偶数的仅由小写英文字母组成的字符串$S$， 问$S$能不能被分成两个完全相同的子序列

数据范围

多组数据， $T = 21$

$1 \leq |S| \leq 40$

题解

折半搜索， 搜索前一半的所有子序列和后一半的所有子序列

折半后暴搜其实很简单， 但是怎么将两部分的结果合并是个问题， 直接将枚举出的所有子序列合并的话就是$2^{20} \times 2^{20} = 2^{40}$， 和没折半一样

所以我们要想办法进行线性的合并

思路如下：

对于前半段， 我们分解出的两个子序列$lp_1, lp_2$如果是可能的结果子序列的前缀的话，必有$lp_1$是$lp_2$的前缀或者$lp_2$是$lp_1$的前缀， 这是显然的

对于后半段而言， 必有一个是另一个的后缀

那么我们如果把$lp_1, lp_2$中的公共前缀删去， 会有一个变成空字符串(当然也有两个都是空字符串的情况， 此时$lp_1 = lp_2$)， 那么另一个非空的字符串， 如果我们在后半段序列中能把这段序列补上， 也就是把后半段的两个子序列删除相同的后缀后也出现了这个非空的字符串， 我们就找到了两个完全相同的子序列(如果$lp_1 = lp_2$， 那么后半段也必须找出相同的两个子序列)

那我们将前半段找到的两个序列删除公共前缀后的序列用map存一下， 如果在后半段的查找中删除公共后缀的序列出现了map中存在的序列， 就说明$S$可以被分成两个相同的子序列

代码

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

int t;
int n;
char s[51];
int mid; // [1, mid], [mid + 1, n]
bool sel[51], lept; // sel枚举状态， lept表示左半段能否被分成两段相同的子序列
std:: map<std:: string, bool> mp; // 前半段删除公共前缀后的序列
bool judge;

void Dfsl(int now) // 暴搜左边
{
    if(now > mid)
    {
        std:: string tmp[2];

        for(int i = 1; i <= mid; i ++) tmp[sel[i]] += s[i];

        int l0 = tmp[0].length(), l1 = tmp[1].length();
        int ml = std:: min(l0, l1);
				// 到32行在找公共前缀， pf是第一次不相等的位置
        int pf = ml;
        for(int i = 0; i < ml; i ++)
            if(tmp[0][i] != tmp[1][i])
            {
                pf = i;

                break;
            }

        if(pf == ml) // 其中一个是另一个的前缀， 接下来进行去公共前缀
        {
            if(l0 == l1) // lp1 = lp2
                lept = true;
            else if(l0 < l1)
            {
                std:: string tp;

                for(int i = pf; i < l1; i ++) tp += tmp[1][i];

                mp[tp] = true;
            }
            else
            {
                std:: string tp;

                for(int i = pf; i < l0; i ++) tp += tmp[0][i];

                mp[tp] = true;
            }
        }

        return;
    }

    sel[now] = false;
    Dfsl(now + 1);

    sel[now] = true;
    Dfsl(now + 1);
}

void Dfsr(int now) // 暴搜右边， 和左边差不多
{
    if(now > n)
    {
        std:: string tmp[2];

        for(int i = n; i > mid; i --) tmp[sel[i]] += s[i];

        int l0 = tmp[0].length(), l1 = tmp[1].length();
        int ml = std:: min(l0, l1);

        int pf = ml;
        for(int i = 0; i < ml; i ++)
            if(tmp[0][i] != tmp[1][i])
            {
                pf = i;

                break;
            }

        if(pf == ml)
        {
            if(l0 == l1)
            {
                if(lept) judge = true;
            }
            else if(l0 < l1)
            {
                std:: string tp;

                for(int i = l1 - 1; i >= pf; i --) tp += tmp[1][i];

                if(mp.count(tp)) judge = true;
            }
            else
            {
                std:: string tp;

                for(int i = l0 - 1; i >= pf; i --) tp += tmp[0][i];

                if(mp.count(tp)) judge = true;
            }
        }

        return;
    }

    sel[now] = false;
    Dfsr(now + 1);

    sel[now] = true;
    Dfsr(now + 1);
}

int main()
{
    scanf("%d", &t);
    while(t --)
    {
        lept = false;
        mp.clear();

        scanf("%s", s + 1);

        n = strlen(s + 1);
        mid = n / 2;

        Dfsl(1);

        judge = false;
        Dfsr(mid + 1);

        if(judge)
            printf("possible\n");
        else
            printf("impossible\n");
    }

    return 0;
}