Luogu3279 - [SCOI2013]密码

2017/10/24

题目

Fish是一条生活在海里的鱼。有一天他很无聊,就到处去寻宝。他找到了位于海底深处的宫殿, 但是一扇带有密码锁的大门却阻止了他的前进。

通过翻阅古籍,Fish 得知了这个密码的相关信息:

该密码的长度为 N 。

密码仅含小写字母。

以每一个字符为中心的最长回文串长度。

以每两个相邻字符的间隙为中心的最长回文串长度。 很快 Fish 发现可能有无数种满足条件的密码。经过分析,他觉得这些密码中字典序最小的一个 最有可能是答案,你能帮他找到这个密码么?

解法

暴力来讲就是如果有一个以 x 为轴的最长回文串 [Lx, Rx] ,那么回文部分必然满足回文性 质(绕口令),且 Ans[Lx - 1] != Ans[Rx - 1]

对于每一个位置,要么从之前一个回文轴更新他,要么染成不等关系的 mex 。

最后模仿 Manacher 搞一个单增的最左更新位置来降低复杂度。

时间复杂度

代码

实现 mex 的时候智障写成了 Mark ^= (1 << pos) 而不是 Mark &= 0xFFFFFFFF ^ (1 << pos)

妥妥 WA。

 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
//#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <cassert>
using namespace std;
#define lowbit(x) ((x) & (-x))
const int SIZ = int(1e5 + 2007);

int rad1[SIZ], rad2[SIZ], N;
char ans[SIZ];

struct lnk {
    int p; lnk *n;
} POOL[SIZ<<1], *Head[SIZ]; int ppos;

void addLink(int p, int v) {
    POOL[ppos].p = p;
    POOL[ppos].n = Head[v];
    Head[v] = &POOL[ppos++];
}

int main() {    
    scanf("%d", &N);
    
    for(int i=1;i<=N;i++) {
        scanf("%d", &rad1[i]); rad1[i] >>= 1;
        if(i - rad1[i] - 1 >= 1 && i + rad1[i] + 1 <= N)
            addLink(i - rad1[i] - 1, i + rad1[i] + 1);
    }
    
    for(int i=1;i<N;i++) {
        scanf("%d", &rad2[i]); rad2[i] >>= 1;
        if(i - rad2[i] >= 1 && i + rad2[i] + 1 <= N)
            addLink(i - rad2[i], i + rad2[i] + 1);
    }
    
    int maxleft = 1;
    for(int i=1;i<=N;i++) {
//      printf(":i %d\n", i);
        
        if(i >= maxleft) {
            int x = 0x7FFFFFFF;
            typedef lnk* It;
            for(It it=Head[i];it;it=it->n) {
                x &= 0xFFFFFFFF ^ (1 << (ans[it->p] - 'a'));
            }
            char cur = int(log2(lowbit(x))) + 'a';
//          printf("%d %c\n", int(log2(lowbit(x))), cur);
            ans[i] = cur;
        }
        
        maxleft = max(maxleft, i+1);
        
        if(rad1[i]) {
            int left = i + rad1[i] + 1;
            if(left > maxleft) {
                for(int j=maxleft;j<left;j++) {
                    ans[j] = ans[(i << 1) - j];
                }
                maxleft = left;
            }
        }
        
        if(i != N) {
            if(rad2[i]) {
                int left = i + rad2[i] + 1;
                if(left > maxleft) {
                    for(int j=maxleft;j<left;j++) {
                        ans[j] = ans[(i << 1) - j + 1];
                    }
                    maxleft = left;
                }
            }
        }
    }
    
    for(int i=1;i<=N;i++) putchar(ans[i]);
    puts("");
}