Educational Codeforces Round 136

發表於 更新於 分類於 ， Disqus： 文章字數： 1.5k 所需閱讀時間 ≈ 5 分鐘
F(图,Aho-Corasick automaton,字符串,DP,bitmask)

CF tracker

Edu List

https://codeforces.com/contest/1739

F. Keyboard Design

n个字符串 si, 价值ci

包含的字符都是 ‘a’~’l’ (前12个), 保证每个字符串中相邻字符不同

求 价值最大的 字符串价值集合 满足:

可以制作一个'a'~'l'出现且只出现一次的字符串t, 使得集合中所有字符串si中相邻的字符,在t上也相邻

范围

n 1000

sum |si| 2000

ci [1,1e5]

4s

1024mb

我的思路

2000 这数字有点假, 因为既然是前12个, 真的有用的配对是 11+10+9+..+1 = 12 * 11/2 = 66个

但是 66 个去做bitmask就不现实了,

12个字符,有11个连接,所以这66个中最多同时11个, 更直接就是 12!=479001600, 但是太大了

12如果是bitmask, 但似乎表示不了什么意义, 即使连成链, 不只是两头有意义, 中间的连接方式也会影响

所以其实是 n = 1000

然后每个字符串提供一个 <= 11 的连接方案(66种候选), 如果超过11一定不可能

然后 选一个集合, 使得连接方案的并 依然<= 11, 且没有任何字符连了3个, 也不构成环

样例1

1
2
3
4
3
7 abacaba
10 cba
4 db

就可以变形成

1
2
3
4
3
2 a-b a-c
2 a-b b-c
1 b-d

一个想法是, 从排列来讲是12!, 上面看到是4e8, 但是如果仅仅说连接方式, 一个连接方式 对应两个排列, 所以还是有2e8

难道真的要 暴力搜索+剪枝吗??

这个ci, 1e5 到大不小的,算和的话能有1e8, 没啥想法

想钦定一个 si被选, 但这样的 感觉还没钦定连接好, 但钦定连接就是枚举

题解

每个单词, 考虑12顶点的图, 然后根据相邻建立边, 注意到 一定是连通的!!!, (有道理啊 我还在想可能多个路径呢),

和我一样的分析, 每个最多连两个且不为环, 所以一定是path

从而把path变成string , 那么就只可能正着 或 倒着两种情况, 比如样例1里的 a-b a-c, 其实, 如果选它, 则t里,要么 bac,要么cab !

令这种 从初始si到字符串的转化为 f(si) 和 f’(si) (两个顺序

题意变成 找 ‘a’~’l’的排列串, 使得 它包含子串 f(si) 或 f’(si), 然后代价和最大

长度>1,所以 f和f’, 至多一个属于, 且至多在字符串中出现一次

所以变成 给一堆 [f(si), ci],[f’(si), ci]

找排列, 让包含子串 ci和最大

用AC自动机+dp

dp[mask characters,ac automaton state]

$O(2^K\cdot K\cdot A)$, K = size(12), A = size(state of automaon) ~ 4000

代码

https://codeforces.com/contest/1739/submission/189050459

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
#include <bits/stdc++.h>
using namespace std;
#define rep(i,a,n) for (int i=(a);i<(int)(n);i++)
#define all(o) begin(o),end(o)
int read(){int r;scanf("%d",&r);return r;}
template<class T>
void setMax(T&a,T b){a=max(a,b);}

char tmp[2010];
vector<int> s[1010];
const int INF=0x3f3f3f3f;
const int N = 10000;
const int K = 12;

// AC automaton
int tsz = 0; // ac automaton 节点数
struct acNode{
  array<int,K> next; // [字符] -> 子节点
  array<int,K> nnext; // [字符] -> 成功的state转换, 相当于对跳转做的cache?
  int ch; // 字符
  int fa; // 父节点
  int lnk; // -1, 失配边, 同KMP
  int cost; // 0 当前cost
  int ncost; // -1 累积后缀cost的和
} node[N+10];

int newNode() {
  fill(all(node[tsz].next),-1);
  fill(all(node[tsz].nnext),-1);
  node[tsz].lnk = -1;
  node[tsz].ncost = -1;
  node[tsz].cost = 0;
  return tsz++;
}
const int root=newNode();

int next_state(int,int);
int get_lnk(int x) {
  int& d = node[x].lnk;
  if(d != -1) return d;
  if(x == root || node[x].fa == root) return d = root;
  return d = next_state(get_lnk(node[x].fa), node[x].ch);
}

int next_state(int x/* state */, int y/* char */) { // 失配都到root(空字符串)
  int& d = node[x].nnext[y];
  if(d != -1) return d;
  if(node[x].next[y] != -1) return d = node[x].next[y];
  if(x == root) return d = root;
  return d = next_state(get_lnk(x), y);
}

void add(const string &s, int c) {
  auto nxt=[&](int x/*node id*/, int y/* char */) {
    int &id=node[x].next[y];
    if(id == -1) {
      id = newNode();
      node[id].ch = y;
      node[id].fa = x;
    }
    return id;
  };
  int cur = root;
  for(char x:s) cur = nxt(cur, x - 'a');
  node[cur].cost += c; // 结束节点 增加代价
}

int calc(int x) { // 以x结尾的代价和
  auto &c=node[x].ncost;
  if(c != -1) return c;
  c = node[x].cost; // 以x state结尾 的代价
  int y = get_lnk(x);
  if(y != x) c += calc(y); // 递归算代价, 相当于省略了 ac自动机的last边
  return c;
}

int main() {
  int n = read();
  rep(i,0,n){
    string s;
    int x=read();
    cin>>s;
    map<char, set<char>> adj; // 相邻字符
    rep(j,0,size(s)-1){
      adj[s[j]].insert(s[j+1]);
      adj[s[j+1]].insert(s[j]);
    }
    string res = "";
    rep(c,'a','a'+K) if(adj[c].size()==1) { // 随便找一个度为1作为起点
      bool bad = false;
      res.push_back(c);
      while(adj[c].size() > 0) {
        if(adj[c].size() > 1) bad = true; // 一定连通, 保证成链即可
        char d = *adj[c].begin();
        adj[c].erase(d);
        adj[d].erase(c);
        c = d;
        res.push_back(c);
      }
      if(bad) break;
      add(res, x);
      reverse(all(res));
      add(res, x);
      break;
    }
  }

  // 记录字符是因为有失配的情况, 并不一定能从当前state获得字符
  vector dp(1<<K, vector<array<int,3>>(tsz+1, {-INF,0,0}));// dp[mask][ac state]={代价和,增加的字符,上一个state}
  dp[0][0] = {0,0,0}; // 空字符串
  // 注意顺序, mask 是严格从小到大, 但是state是乱跳的 只是不会循环
  rep(mask,0,1<<K)rep(state,0,tsz+1)if(dp[mask][state][0]!=-INF)rep(c,0,K)if(!(mask & (1<<c))) { // 增加字符c
    int nstate = next_state(state, c);
    setMax(dp[mask|(1<<c)][nstate], {dp[mask][state][0]+calc(nstate),c,state});
  }

  { // 倒着找(因为字符串反顺序 答案也一样,所以ans reverse和不reverse都可以)
    int mask=(1<<K)-1;
    int state = max_element(all(dp[mask])) - dp[mask].begin();
    while(mask) {
      auto [_,c,pstate] = dp[mask][state]; // [_,字符,前一个state]
      printf("%c",'a'+c);
      mask &= ~(1<<c);
      state = pstate;
    }
  }
  return 0;
}

总结

F

明显的一定连通的结论, 想不到!???

ac自动机上做DP 第一次见到, 看懂了觉得好像也不太难, 但第一次见还是有点神奇, 感觉应该可以出个类似简单版本的 KMP+dp

不过看到多个字符串 应该向ac自动机去想

参考

官方

CF 1202 E 也用过AC自动机