Atcoder arc058

發表於 更新於 分類於 ， Disqus： 文章字數： 2.8k 所需閱讀時間 ≈ 9 分鐘
E(状态压缩,DP)F(z function,DP)

https://atcoder.jp/contests/arc058/tasks

E -  Iroha and Haiku

有多少个 长度n,值域 [1,10]整数的数组a 满足 子区间

sum a[x..y) = X

sum a[y..z) = Y

sum a[z..w) = Z

答案mod 1e9+7

n [1,40]

x [1,5]

y [1,7]

z [1,5]

4s

512mb

我的思路

范围这么小,可以打表!

想的还是 容斥暴力

总状态 =[5的实际状态][7的实际状态][5的实际状态]

考虑首个匹配在哪个位置,

sum (a[i…] 满足, a[<i…] 不满足)

问题是转移的话,似乎并不好转移

题解

还是状态压缩

但是 直接考虑反过来,就不需要容斥了

ans = 1- 不合法

然后这里有个妙一点的表示法, i => 2^{i-1} 然后二进制拼接

(3,2,4,5) => (2^2,2^1,2^3,2^4) => 10010100010000

$2^{17} * 10 * 40 = 52428800$

代码

https://atcoder.jp/contests/arc058/submissions/43441191

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
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll MOD = 1000'000'007;
#define rep(i,a,n) for (ll i=a;i<(ll)n;i++)
ll read(){ll r;scanf("%lld",&r);return r;}
int main() {
  int n=read();
  int x=read();
  int y=read();
  int z=read();
  auto _=[](int v){return 1<<(v-1);}; // 数字 转为2进制表示
  const int end=_(x+y+z)|_(y+z)|_(z); // end 结束状态
  const int msk=(1<<(x+y+z))-1;
  vector dp(n+1,vector<ll>(msk+1,0));
  dp[0][0]=1;
  rep(i,1,n+1) rep(j,0,msk+1) if(dp[i-1][j]!=0) rep(k,1,10+1){
    int now = ((j<<k) | _(k)) & msk;
    if((now&end)!=end) (dp[i][now] += dp[i-1][j]) %= MOD; // 非法状态
  }
  ll ans = 1;
  rep(i,0,n) (ans*=10)%=MOD;
  rep(j,0,msk+1) (ans -= dp[n][j])%=MOD;//用总字串数减去不满足俳句字串数
  printf("%lld\n",(ans+MOD)%MOD);
  return 0;
}

F - Iroha Loves Strings

n个小写字母字符串

选取一些 按照原来的顺序 拼接

问能得到的 长度为K的字典序最小的字符串

$n \in [1,2000]$

$k \in [1,10^4]$

$\sum_i |s_i| \le 10^6$

5s

750mb

我的思路

如果 先上 SA

那么问题是 它这里的 顺序限制 和 长度限制 还没有解决

从空字符串开始的话,当前方案可以表示成SA中一个区间, 和一个起始坐标

1
2
3
4
5
ab
abc
abcd
acbd
ca

然而因为字符串之间长度不固定,所以可能 abc的方案有的会跳到c开头,这样会拆分成很多段

1
2
for i in [1..K]:
	state = array { [index [l,r], start >= pos }

如果同一个状态, 遇到相同的字符并要跳出, 那么考虑 坐标小的作为pos跳出后的

1
2
ab
ab

按照上面这样做, 每次的state 总个数 <= n, 总转移代价也是

看起来可以做了

而实际上, 因为length 恰好为K, 和这个做法并不满足

因为这样每次贪心的是目前最小的字典序列 拼接,但是这种拼接可能无法达到恰好长度为K

第一个想法就是 先dp[end pos] = {正向可达 s的idx}

for i in N: for pos(从大到小): dp[pos+len[i]].push(i)

就最简单的全部是a, 那么方案数都是 binom(n,k), 所以不可能枚举所有方案, 也需要状态表示

而上面这种方式, 其实按照这个顺序的话,当前的 dp[end po]虽然记录了一系列idx, 但从贡献角度来看,只用记录 字典序列最小的

然而直接记录整个字符串 或者拼接index 都会挺大

考虑 dp[i] = vector<状态(当前最后的s[idx]的idx,上一个dp[j][idx]的j和idx)>, 这样vector顶部 就是最后的最小的,

如果能快速比较 两个链式状态,这个题就解决了

然而只想到O(K)的暴力,这样还停留在 O(N K K)的复杂度

1
2
3
[.....][.....][.....]
<=?=>
[.........][........]

一个就是, 长度倍增? 但连接部分不知道怎么处理

题解

一样的先考虑 dp[i][j] = 前i个字符串能够拼接的长度恰好为j的最小字典序的字符串

显然状态 O(nk^2)

转移也是一样的 dp[i][j]贡献dp[i+1][j+|si|]

然后这里的优化是 删除 无用的答案

dp[i][j]=t后面 s[i+1..n]不能 拼接成长度为k-j 的那么 不要这种dp[i][j]

如果有 dp[i][j']=t', 且 $t’[min(|t’|,|t|)] < t[min(|t’|,|t|)]$(也就是 他们的最小长度,严格更小),那么也不需要这个dp[i][j], 这里j'和j的大小关系不限制,因为上一个 删除无效答案已经保证了总是能拼接出

至此当进行到指定的i时, dp[i][j] 如果有值,那么它们两两之间构成前缀关系

1
2
3
4
dp[i] = '...................' 上述里面最长的 字符串 
      =     1    1    1   11  0/1 表示对应长度能否被 前面i个拼出来

				 1[.s[i+1].]

那么考虑 增加s[i+1]

从前到后找 1指向的后面拼接, 如果有位置 严格小于, 则变为.....1....1[...1..[<].....1] 注意 新增的里面也可能有1, 只要在严格小于的前面的位置的1就可以保留

而从前到后 也不是 先匹配的就最小

1
2
3
4
5
 1231235
1  1  11
[1234]
   [1234] 先匹配了
      [1234] 更小

所以这里要比较所有

[...1][si]

这里需要下面的z-function, 可以O(n)计算 z[i] = lcp(s,s[i..]) lcp最长公共前缀

怎么用呢

先拼接t[i] = s[i] + dp[i]

那么原来比较 dp[i][0..j0] + s[i] 与 dp[i][0..j1] + s[i]

1
2
3
4
5
dp0+si: [0......j0][si.......]
dp1+si: [0............j1][si.......]
                   [....]
                         [...]

实际上 是先计算dp[i][j0+1..] 和 s[i]的 lcp 与 len(j0+1..j1) 的大小关系

在t中就是 lcp(t, t[|si|+j0+1]) = z[|si|+j0+1]

如果 大于等于 len(j0+1..j1)

那么再 比较的是 $si[j1-j0…], si$ 的lcp与 j0+|si| 的大小关系

那么在t中就是, $lcp(t[j1-j0..],t) = z[j1-j0]$

同样, 如果两个串之间是前缀关系,则保留长的

至此O(n) 可以完成转移, 同时因为有了lcp,所以上面 0/1 的可转移部分也可以完成

z-function

z[i] = lcp(s,s[i..]) lcp最长公共前缀

1
2
3
4
5
6
7
8
9
10
0-index:

   0    z[i]-1
   [    ]   
            j
s: [......i........]
		 [......i........]
	 len([.....]) = z[i]
	           |
	           i+z[i]-1

当$i < j \le i+z[i]-1$ 时 s[j..i+z[i]-1] = s[(j..i+z[i]-1)-i] = s[j-i..z[i]-1]

若 z[j-i] < len(s[j-i..z[i]-1]), 则$z[j] = z[j-i]$

若 z[j-i] >= len(s[j-i..z[i]-1]), 则s[j..i+z[i]-1] = s[(j-i..z[i]-1)-(j-i)] = s[0..z[i]-1-j+i]比较 s[i+z[i]-1+t] 和 s[z[i]-j+i-1+t], 其中t=1...

当$j$不在 任何 $[i,i+z[i]-1]$时, 也是逐个比较

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
vector<int> calcZ(vector<char> s) {// 0-indexed
  int n=size(s);
  vector<int> z(n, 0);
  int l = 0; // 保持 r 最大
  for(int i=1;i<n;i++)
    int r=l+z[l]-1;
    if(z[i-l] < r-i+1) z[i]=z[i-l];
    else {
      z[i]=max(0,r-i+1);
      while(i+z[i]<n && s[z[i]]==s[i+z[i]]) z[i]++;
      l=i;
    }
  }
  z[0]=n;
  return z;
}

注意到每次 if 成立都是O(1)的,而else里的while增加 会让r增加1,而r是单调递增有界的, 所以总的复杂度是O(n)

代码

https://atcoder.jp/contests/arc058/submissions/43460450

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
#include <bits/stdc++.h>
using namespace std;
#define rep(i,a,n) for (int i=a;i<(int)n;i++)
#define per(i,a,n) for (int i=n;i-->(int)a;)
int read(){int r;scanf("%d",&r);return r;}

const int K = 10000;
const int N = 2000;
bitset<K+10> can[N+10]; // can[i...n][长度] = bool(后面i..n的字符能否品出 长度)
bitset<K+10> dp[N+10]; // dp[1..i][长度] = bool(可能对答案贡献(后缀长度可能+前缀最小),且前缀1..i 可拼成
string ans[2]; // ans[i] = 处理完前i个 最长的 可能的 字符串, 滚动i&1
string&cs(int i){return ans[i&1];}
vector<string> arr;
char tmp[K+10];

vector<int> make_z(const string&s) {
  int l = 0; // 保持r最大
  int n = size(s);
  vector<int> z(n,0);
  rep(i,1,n) {
    int r = l + z[l] - 1;
    z[i] = max(0,min(r-i+1,z[i-l]));
    while(i + z[i] < n and s[i + z[i]] == s[z[i]]) z[i]++;
    if(i + z[i] - 1 > r) l = i;
  }
  z[0] = n;
  return z;
}

// prefix[p] vs prefix[q] + arr[j]
int cmp(const vector<int>&z,int i, int p, int q) {
  // [............]
  // [........p]..]
  // [.....q][si....]
  const int szs = size(arr[i]);
  if (p <= q) return 0;
  int lcp = z[szs + q];
  if (lcp >= szs || q + lcp >= p) return 0;
  return (cs(i-1)[q + lcp] < arr[i][lcp]) ? -1 : 1;
}

// sign( (ans[i-1][0..p] + s[i])
//   -   (ans[i-1][0..q] + s[i]))
// < -1, = 0, > 1
int cmp2(const vector<int>&z,int i,int p, int q) { // p,q 0-index
  // z = s[i] + '$' + ans[i-1]
  // [.....p][si......]
  // [..........q][si......]
  //         [   ]      lcp(si,ans[i-1][p+1..q])
  //              [   ] lcp(si,si[q-p..])
  //z:       0      szs-1
  // szs+1
  int szs = size(arr[i]);
  if (p > q) return -cmp2(z,i, q, p);
  int lcp = z[szs + p]; // lcp(si,ans[i-1][p+1..q])
  if (lcp < q - p) {
    if (lcp >= szs) return 0;
    return (cs(i-1)[p + lcp] < arr[i][lcp]) ? -1 : 1;
  }
  lcp = z[q - p]; // lcp(si,si[q-p..])
  if (q + lcp >= p + szs) return 0;
  return (arr[i][lcp] < arr[i][q - p + lcp]) ? -1: 1;
}

int main() {
  int n=read();
  int k=read();
  arr.resize(n+1); // 1-index
  rep(i,1,n+1) {
    scanf("%s",tmp);
    int sz=strlen(tmp);
    rep(j,0,sz) arr[i].push_back(tmp[j]);
  }
  can[n + 1][0] = 1;

  // Zeroes are shifted in, and bits that would go to an index out of range are dropped (ignored).
  per(i,1,n+1) can[i] = can[i + 1] | (can[i + 1] << (int)size(arr[i]));

  dp[0][0] = 1;
  rep(i,1,n+1){
    // 不使用j的情况
    cs(i) = cs(i - 1);
    per(j,0,k+1) if(dp[i-1][j] and can[i+1][k-j]) { // 对于上一个成立,对于当前不使用, 可能不成立
      cs(i) = cs(i).substr(0,j); // 先只用关心最长的即可
      break;
    }
    const int sz = size(arr[i]);
    auto z = make_z(arr[i] + cs(i - 1)); // [0..sz-1][sz..sz+len(cs(i-1))-1]
    z.push_back(0); // cmp2 中 z[q-p] 可能超长
    // decide cs[i]
    int nxt = -1; // 只记录合成的(prefix[ans[i-1]] + s[i])最优的
    rep(j,0,k-sz+1) if (dp[i-1][j] and can[i+1][k-(j+sz)]) { // j => j+sz
      if (nxt == -1) { // 暂无方案
        int res = cmp(z,i,size(cs(i)), j); // 和 转移过来的 方案比
        if (res == 1 || (res == 0 and j + sz > (int)size(cs(i)))) nxt = j; // 更小,或前缀相等但是更长
      } else if (cmp2(z,i, nxt, j) <= 0){
        nxt = j;
      }
    }
    if (nxt == -1) {// s[i] is not a suffix of cs[i]
      // 对于上一个成立, 对于当前不使用, 可能不成立,
      // 这种状态不清理其实也不影响,因为后面拼接时也有校验,不会产生贡献
      rep(j,0,k+1) if(dp[i-1][j] and can[i+1][k-j]) dp[i][j] = 1;
    } else {
      // ans [.............]
      //     [.....nxt][si.....]
      //                 | 匹配以后的0/1会变
      cs(i) = cs(i - 1).substr(0, nxt) + arr[i];
      // 和原来相等的部分
      rep(j,0,size(cs(i - 1))+1) dp[i][j] = (dp[i - 1][j] and can[i+1][k-j] and cmp(z,i, j, nxt) == 0);
      dp[i][size(cs(i))] = 1;
      // 又 前面 的 + arr[i] 拼成
      rep(j,0, size(cs(i)) - sz) if(dp[i - 1][j] and can[i+1][k-sz-j] and cmp2(z,i,j,nxt) == 0)dp[i][j+sz]=1;
    }
  }
  printf("%s\n",cs(n).c_str());
  return 0;
}

总结

E

一个是反过来考虑,一个是状态表示!!

F

这个”只留有用的”优化,想之前觉得不会有啥,仔细一想真的优化了不少

后面这个z-function 第一次见,有点像kmp但不完全一样, 毕竟kmp的核心是求以这个位置结束 的后缀的最长lcp, 而z-function是以这个位置开始的最长lcp

然后z-function 的 z[0] 感觉似乎没有地方会用到,实际要用到不用z-function这个值也是显然的

Ref

https://www.luogu.com.cn/problem/solution/AT_arc058_c