Atcoder abc225

發表於 更新於 分類於 ， Disqus： 文章字數： 4.4k 所需閱讀時間 ≈ 15 分鐘
F(字符串,偏序,DP,倒着DP,局部性)G(题意转化,最小割,最大流)H(NTT,FFT,生成函数,分治,归并)

F - String Cards

给N个字符串, 恰好选其中K个, 拼接出的最小字典序的字符串是什么

范围

N 50

|Si| [1,50], 每个长度

只含小写英文字母

2s

1024 mb

我的思路

例如

b和ba

b <= ba

但是

bab <= bba

非前缀的 s1 < s2, 一定s1

s1 是 s2的前缀的 s1 < s2

如果只剩下一个,则s1

否则,形如

1
2
3
4
5
6
7
8
9
[A]
[A][B]
[A][B][C]
[A][B][C][D]

[A][A] ?
[A][B] [A] ?
[A][B][C] [A] ?
[A][B][C][D] [A] ?

如果本身A和B有直接大小, 那么就能知道第一个还是后面3个,A和C再比,A和D再比

但如果A和B依然是前后缀关系, 这会考虑长度,也会考虑要选的个数

少考虑一点, 对于两个

1
2
A
AB

两种排列

1
2
AAB
ABA

长度一致, 考虑是否交换

但感觉两个到三个之间局部性不知道是否成立:

(A,AB)组合A 放在前, (AB,ABC) 组合 AB 放在前, 能否推出 (A,ABC) 中 A要放在前

1
2
3
A
AB
ABC

其实我在想,是不是n^4 可以暴力dp?, 好像会是n^6?

dp[i][j][length], 前i选j,长度=length的最小前缀

题解

有意思, 还给了一些错误解法的反例

反例1, sort取前k个连起来

就是我已经想到的 b, ba

反例2, 还是sort, 保证相邻拼接 < 相邻逆序拼接, 的前k 个

这也是想到了的, 当个数为1时ba,b 还是会选b

反例3, sort, 保证相邻拼接 < 相邻逆序拼接

定义dp[i][j]= 前i个选j个能得到的最小字典序

dp[i][j] = min(dp[i-1][j],dp[i-1][j-1] + Si) 的转移方程, 输出dp[N][K]

对于 baa,ba,b, 选出两个, 期望是baab, 而输出是baaba

应该就是没有最小的性质

前两个选1个最小是ba, 拼接b得到bab

而前两个选2个最小是baaba, 这两个都不是最小答案

最小的构成是 baab = 前两个中大的一个 和最后一个拼接

反例4

同样的排序, 同样的dp定义

但是改变转移方程

dp[i][j] = min(dp[i-1][j],dp[k < i][j-1] + Si) 的转移方程, 输出dp[N][K]

然后

bbaba

bba

b

b

选3个也是反例

其实这列我们可以看到, dp的定义 只能说是希望它是这样,一旦你的转移方程之类出现问题, 它的结果将不满足定义

正确方案

尝试排序 让排序后 任意(i < j) 满足, Si+Sj < Sj + Si

这里有点和我想的有没有偏序关系的问题了一样了, 怎么证明存在啊?

证明

把字符串变成数字 a,b

AB < BA

等价a * 26^len(B) + b < b * 26^len(A) + a

a/(26^len(A)-1) < b/(26^len(B)-1)

好有道理, 事后看起也不难, 我咋自己想不到简单转换一下就证明了

那这样整个问题就简单了

也就是 如果选定了字符串, 那么 它们的顺序就是一定的, 有偏序关系,就可以按照上面的排序来排

那么这样再dp[i][j]= S[i..N] 中选j个能构成的最小字典需

和前面不一样的是, 变成后缀中选j个

转移方程dp[i][j] = min(dp[i+1][j], S[i]+ dp[i+1][j-1])

显然如果S[i] 本来就非前缀的小于S[i+1], 那么min 一定取右侧, 且子问题已经被计算了

而如果要S[i] 则S[i] 一定是开头的

答案是dp[1][K]

这里其实dp的问题在于 为啥正着做不对,而倒着的是对的?

其实问题就在于 选第i个时

正着选第 i个时, 它也在末尾, 但是并不一定意味着 前缀是dp[i-1][j-1], 因为dp[i-1][j-1] 可能是通过长度胜出的最小,而不是字符胜出的最小,

可能有 D0 < D1, 但是D0是D1前缀,

从而 D1+Si < D0+Si的情况, 没有了局部性

而倒过来, Si放在最前

如果同样有 有 D0 < D1, 但是D0是D1前缀

但 Si+D0 < Si + D1始终成立的, 保证了局部性

代码

https://atcoder.jp/contests/abc225/submissions/33909604

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
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
#define rep(i,a,n) for (ll i=a;i<(ll)n;i++)

ll read(){ll r;scanf("%lld",&r);return r;} // read

char s[60][60];
int sz[60];
int idx[60];
char dp[60][60][2500];

int main(){
  int n = read();
  int k = read();
  rep(i,0,n) {
    scanf("%s",s[i]);
    sz[i] = strlen(s[i]);
  }
  iota(idx,idx+n,0);
  sort(idx,idx+n,[=](int i,int j){
      rep(p,0,sz[i]+sz[j]){
        char ch0 = p < sz[i] ? s[i][p] : s[j][p-sz[i]];
        char ch1 = p < sz[j] ? s[j][p] : s[i][p-sz[j]];
        if(ch0 != ch1) return ch0 < ch1;
      }
      return false;
  });
  rep(i0,0,n){
    char *t = s[idx[n-1-i0]];
    rep(j,0,i0+1){ // 选 j+1 个
      // dp[n-1-i][j] = min(dp[n-1-i+1][j], s[n-1-i] + dp[n-1-i+1][j-1]);
      strcpy(dp[i0][j], t);
      if(i0 > 0) {
        if(j > 0) strcpy(dp[i0][j] + strlen(t), dp[i0-1][j-1]);
        if(i0 > j && strcmp(dp[i0][j], dp[i0-1][j]) > 0) strcpy(dp[i0][j], dp[i0-1][j]);
      }
    }
  }
  printf("%s\n",dp[n-1][k-1]);
  return 0;
}

G - X

https://atcoder.jp/contests/abc225/tasks/abc225_g

矩阵H x W, 每个上面Aij

选任意个格子,每个被选的格子画X, 连通左上右下,左下右上角

然后 分数 = 画了X的格子的数字和 - C 乘 画X的最小需要的线段数, 没有选的格子不能画,任何东西

例如这样选的话, 左下角到右上只需要一个长线段,一共是3个线段

1
2
 X
X

求 最大分数 = sum(选的格子) - C 倍最小画线段数

范围

H,W 100

C 1e9

Aij [1,1e9]

2s

1024 mb

我的思路

先试试形状

1
X

1个格子, -2C

1
2
XX
XX

4个格子, -6C

1
2
3
XXX
XXX
XXX

9个格子, -10C

1
2
3
4
XXXX
XXXX
XXXX
XXXX

16个格子,-14C

1
2
3
 X
X X
 X

4个格子,-4C

1
2
3
4
5
  X
 X X
X X X
 X X
  X

9个格子, -6C

收获不大至少说明一点,即使格子本身小于C,但是可以通过相邻的线段可以贯通,而让均摊下来每个减去的不到C

第二个思路就是

如果一排一排的铺

dp[state i] => dp[state i+1], 根据上面左上角和右上角的两个是否被选决定当前选择的贡献是什么

这样 做个类似插头dp的样子, 每次转移O(1) 但是,因为要存边界状态

所以状态 高达 N^2 * 2^N, 分别是切割线的位置, 和 切割线的状态

这里最主要的就是 会受到它顶部两个的选择状态的影响它的贡献

然后考虑说在位置上相邻,在实际填写中互不影响, 其实可以把 横纵坐标和为奇数/ 和偶数分开考虑

1
2
3
4
ABABA
BABAB
ABABA
BABAB

然后可以转个45度, 补成个长方形, 原来空白的地方放0,问题变成选一些数的 和 - C 乘 (纵向连续块数+横向连续块数), 这样最大答案不会变

1
2
3
4
0A00
AAA0
AAAA
0AA0

但这依然有和左侧和上面的关联决定一个块的贡献

整体的考虑

1
2
Y?
 Y

如果出现这样的选择, 那么? 必然选择,因为选择它不会增加带来的收益$\ge 0$

因此在新的里面选的一定是长方形

但可能不止一个长方形

1
2
3
4
00000000
0YY11110
0YY11YY0
01111YY0

例如这样 = S - 8C

1
2
3
4
00000000
0YYYYYY0
0YYYYYY0
0YYYYYY0

而这样是 = S+10-9C

如果是C很大,则上面的更优

每个长方形代价 = sum(长方形) - C 乘 (长+高)

并且显然长方形的 轮廓的 横向和 >= C, 纵向和 >= C,( 内部不一定

1
2
3
YYYY
1111
YYYY

这样是 = S - 10C

1
2
3
YYYY
YYYY
YYYY

这样是 = S+4 - 7C

C很大,后面会更好,但中间行和可能 < C

找不到什么合并不合并规则

如何在100x100量级中 选多个长方形, 每个贡献 = Sum - C(长 + 宽)

让贡献最大

虽然对于单个来说, 可以矩阵前缀,很快算出单个的贡献

不太会了

题解

每个选, +Aij

每个选 左上角不选, -C

每个选 右上角不选, -C

又有加又有减, 不好

变化

如果你不选, Aij代价, 选无代价

每个选 左上角不选, C代价

每个选 右上角不选, C代价

这样就全是 增加了

现在答案 = sum A - 代价

要总代价最小

代价最小 => 最小割问题

S源(与S同块的视作选择),T汇(与T同块的视作不选)

S -> (i,j), 容量Aij, (割这条边相当于不选它 的代价)

对于左上角没有块的(i,j): (i,j) -> T , 容量C (割这条边相当于选它的代价)

对于右上角没有块的(i,j): (i,j) -> T , 容量C (同理,割这条边相当于选它的代价), 相当于可能重边

对于左上角有块的, (i,j) -> (i-1,j-1) 容量C, (割这条边,相当于它和S同块(选择),左上角和T同块(不选择),所产生的代价)

对于右上角有块的, (i,j) -> (i-1,j+1) 容量C, (同理, 割这条边,相当于它和S同块(选择),右上角和T同块(不选择))

这个复杂度, 不理解???

看数据, 似乎没有调小, 还是和题目说的量级

但实际跑起来, 我本地i7-7700HQ, 跑数据最长的0.2~0.3s

但是提交的远端是几十ms

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
TestCase G.in.014 => G.out.014 Time spend: 0.002467s

TestCase G.in.006 => G.out.006 Time spend: 0.002532s

TestCase G.in.033 => G.out.033 Time spend: 0.264098s

TestCase G.in.031 => G.out.031 Time spend: 0.235067s

TestCase G.in.021 => G.out.021 Time spend: 0.012753s

TestCase G.in.012 => G.out.012 Time spend: 0.00644s

TestCase G.in.015 => G.out.015 Time spend: 0.003208s

TestCase G.in.039 => G.out.039 Time spend: 0.04113s

TestCase G.in.002 => G.out.002 Time spend: 0.002386s

TestCase G.in.034 => G.out.034 Time spend: 0.193138s

TestCase G.in.028 => G.out.028 Time spend: 0.227858s

TestCase G.in.005 => G.out.005 Time spend: 0.002228s

TestCase G.in.000 => G.out.000 Time spend: 0.014386s

TestCase G.in.045 => G.out.045 Time spend: 0.163s

TestCase G.in.001 => G.out.001 Time spend: 0.002495s

TestCase G.in.049 => G.out.049 Time spend: 0.166109s

TestCase G.in.040 => G.out.040 Time spend: 0.143258s

TestCase G.in.016 => G.out.016 Time spend: 0.003306s

TestCase G.in.018 => G.out.018 Time spend: 0.003002s

TestCase G.in.023 => G.out.023 Time spend: 0.012607s

TestCase G.in.025 => G.out.025 Time spend: 0.255023s

TestCase G.in.042 => G.out.042 Time spend: 0.150962s

TestCase G.in.003 => G.out.003 Time spend: 0.001938s

TestCase G.in.017 => G.out.017 Time spend: 0.011363s

TestCase G.in.0 => G.out.0 Time spend: 0.001994s

TestCase G.in.004 => G.out.004 Time spend: 0.018588s

TestCase G.in.051 => G.out.051 Time spend: 0.152942s

TestCase G.in.037 => G.out.037 Time spend: 0.017386s

TestCase G.in.047 => G.out.047 Time spend: 0.195896s

TestCase G.in.029 => G.out.029 Time spend: 0.244589s

TestCase G.in.009 => G.out.009 Time spend: 0.017067s

TestCase G.in.041 => G.out.041 Time spend: 0.185784s

TestCase G.in.053 => G.out.053 Time spend: 0.134323s

TestCase G.in.046 => G.out.046 Time spend: 0.199048s

TestCase G.in.019 => G.out.019 Time spend: 0.004681s

TestCase G.in.030 => G.out.030 Time spend: 0.24435s

TestCase G.in.1 => G.out.1 Time spend: 0.002198s

TestCase G.in.035 => G.out.035 Time spend: 0.277394s

TestCase G.in.024 => G.out.024 Time spend: 0.269645s

TestCase G.in.032 => G.out.032 Time spend: 0.276123s

TestCase G.in.026 => G.out.026 Time spend: 0.235927s

TestCase G.in.010 => G.out.010 Time spend: 0.015773s

TestCase G.in.027 => G.out.027 Time spend: 0.239164s

TestCase G.in.013 => G.out.013 Time spend: 0.00688s

TestCase G.in.022 => G.out.022 Time spend: 0.119993s

TestCase G.in.038 => G.out.038 Time spend: 0.038151s

TestCase G.in.007 => G.out.007 Time spend: 0.002414s

TestCase G.in.020 => G.out.020 Time spend: 0.015595s

TestCase G.in.052 => G.out.052 Time spend: 0.134451s

TestCase G.in.044 => G.out.044 Time spend: 0.151272s

TestCase G.in.011 => G.out.011 Time spend: 0.015062s

TestCase G.in.043 => G.out.043 Time spend: 0.163996s

TestCase G.in.036 => G.out.036 Time spend: 0.019596s

TestCase G.in.050 => G.out.050 Time spend: 0.187503s

TestCase G.in.054 => G.out.054 Time spend: 0.123545s

TestCase G.in.048 => G.out.048 Time spend: 0.162755s

TestCase G.in.055 => G.out.055 Time spend: 0.124003s

TestCase G.in.008 => G.out.008 Time spend: 0.016901s

TestCase G.in.2 => G.out.2 Time spend: 0.00257s

这样看来, 如果变成我的那样转化, 其实也可以类似的, 左侧依赖,上侧依赖,不选负贡献 来做最小割

甚至可以变成新的题?

代码

https://atcoder.jp/contests/abc225/submissions/33910465

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
#include <bits/stdc++.h>
#include<atcoder/maxflow>
using namespace std;

typedef long long ll;
#define rep(i,a,n) for (ll i=a;i<(ll)n;i++)

ll read(){ll r;scanf("%lld",&r);return r;} // read

int A[110][110];

int main(){
  int H = read();
  int W = read();
  int C = read();
  auto enc = [=](int i,int j){return i*W+j;};
  atcoder::mf_graph<ll> graph(H*W+2);
  rep(i,0,H) rep(j,0,W) A[i][j] = read();
  int S = H*W; // 源,同块表示选
  int T = S+1; // 汇,同块表示不选
  // S->(i,j), 容量A[i][j], 不选
  rep(i,0,H) rep(j,0,W) graph.add_edge(S,enc(i,j),A[i][j]);
  // (i,j) -> (i-1,j-1), 当前选, 左上不选; (i,j) -> T 当前选,左上不存在
  rep(i,0,H) rep(j,0,W) graph.add_edge(enc(i,j),(i && j    )?enc(i-1,j-1):T,C);
  // (i,j) -> (i-1,j+1), 当前选, 右上不选; (i,j) -> T 当前选,右上不存在
  rep(i,0,H) rep(j,0,W) graph.add_edge(enc(i,j),(i && j+1<W)?enc(i-1,j+1):T,C);
  ll ans = -graph.flow(S,T);
  rep(i,0,H) rep(j,0,W) ans += A[i][j];
  printf("%lld\n",ans);
}

H - Social Distance 2

https://atcoder.jp/contests/abc225/tasks/abc225_h

N个椅子排成一排, 每个最多坐一个人

M个人坐(每个人两两不同)

分数 = 相邻坐标差的乘积,

给定编号1~K的人的坐的位置

问剩下的M-K 的所有坐的方案的分数的和

mod 998244353

范围

2e5

2s

1024 mb

我的思路

类型应该至少是组合数+ 贡献统计吧

要么就是想法容斥

那么考虑是如何归类

一个不满足范围的DP

dp[i][j] = 小于等于给定的第i大的位置内, 坐了j个人的乘积的和,

`dp[i][j] = sum_t ( dp[i-1][t] * (A[i]-A[i-1] 空隙中(最后位置要放一个), 放入 j-t 个 的乘积和) )

状态就是 N^2的

如果后面的乘积和能直接算的话, 也需要N^3的时间复杂度, 即使走fft一类, 也是 N^2 log^2 N

题解

先学一下maspy的三篇博文, 见底部链接

对于未确定的$M-K$, 我们不要关心它们的区别, 直接所有方案乘上 $(M-K)!$ 即可

定义f1[n][k] = , 跨度n的椅子,两端都坐了人, 一共k+2个人,的内部的乘积权和

定义f2[n][k] = , 跨度n的椅子,左端坐了人, 一共k+1个的 内部的乘积权和

定义f3[n][k] = , 跨度n的椅子, 一共k个的 内部的乘积权和

其实区别只在端上

那么有

$\displaystyle f_1(n,k) = \lbrack x^{n-1} \rbrack (x + 2x^2 + 3x^3 + \cdots)^{k+1} $

相当于 从$1$走到$n$,走$k+1$次,每步任意正长度(每步对最终的贡献倍数也是长度的贡献)

$ = \lbrack x^{n-k-2} \rbrack (1 + 2x + 3x^2 + \cdots)^{k+1} $

$ = \lbrack x^{n-k-2} \rbrack \frac{1}{((1-x)^2)^{k+1}}$

$ = \lbrack x^{n-k-2} \rbrack \frac{1}{(1-x)^{2k+2}}$

$ = \lbrack x^{n-k-2} \rbrack \frac{1}{(1-x)^{2k+2}}$

$ = \binom{(n-k-2) + (2k+2-1)}{2k+2-1}$

$ = \binom{n+k-1}{2k+1}$

类似的有

$f_2(n,k) = \binom{n+k-1}{2k}$

$f_3(n,k) = \binom{n+k-1}{2k-1}$

那么对于原问题, 如果$K=0$, 就是所有人都未确定, 使用$f_3$

对于$K\neq 0$

那么其实就是 两端用$f_2$, 中间是$K-1$个$f_1$

然后不要挨个乘,用归并的思想,尽量小乘小,大乘大, 不要太多 大乘小, 就可以了

代码

看起来atcoder的执行是没有-fsanitize参数的, 很快

https://atcoder.jp/contests/abc225/submissions/33929839

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
#include <bits/stdc++.h>
#include <atcoder/modint>
#include <atcoder/convolution>
using mint=atcoder::modint998244353;
using namespace std;

typedef long long ll;
#define rep(i,a,n) for (ll i=a;i<(ll)n;i++)
#define per(i,a,n) for (ll i=n;i-->(ll)a;)
#define pb push_back
ll read(){ll r;scanf("%lld",&r);return r;} // read
const int N = 200000;
ll a[N+10];
mint fac[2*N+10] = {1}; // fac[i] = i!
mint ifac[2*N+10]; // ifac[i] = 1/i!
vector<mint> polys[N+10]; // 总长 <= O(n + k)
mint C(int n,int m){return fac[n]*ifac[m]*ifac[n-m];}
ll n; // 2e5
ll m; // 2e5
ll k; // 2e5

// 本质就是 尽量小乘小, 大乘大, 不要大量 大*小
vector<mint> solve(ll l,ll r) {
  if(l == r) return polys[l];
  auto res = atcoder::convolution(solve(l,(l+r)/2),solve((l+r)/2+1,r));
  if((int)res.size() > m-k+1) res.resize(m-k+1); // 删除不影响结果的
  return res;
}

int main() {
  rep(i,1,2*N+1) fac[i] = fac[i-1]*i;
  ifac[2*N] = fac[2*N].inv();
  per(i,0,2*N) ifac[i] = ifac[i+1]*(i+1);

  n = read(); // 2e5
  m = read(); // 2e5
  k = read(); // 2e5
  rep(i,0,k) a[i] = read();

  if(k==0) { // f_3(n,m) * m!
    printf("%d\n",(C(n+m-1,2*m-1) * fac[m]).val()); // 无序变有序 * m!
    return 0;
  }
  rep(i,0,k-1) { // f_1 中间间隔
    ll len = a[i+1]-a[i]+1; // 区间长度, 两端已经放了
    rep(seg,0,len-1) polys[i].pb(C(len+seg-1,2*seg+1)); // seg = 中间自由的元素个数
  }
  rep(i,0,2) { // f_2 首尾
    auto len = (i==0) ? a[0] : (n-a[k-1]+1); // 区间长度, 一侧已经放了
    rep(seg,0,len) polys[k-1+i].pb(C(len+seg-1,2*seg)); // seg = 中间自由的元素个数
  }
  printf("%d\n",(solve(0,k)[m-k] * fac[m-k]).val()); // 无序变有序 * (m-k)!
  return 0;
}

总结

F

这个字符串的偏序证明 事后看起来还挺简单的,虽然我有这个方向想法, 但没去简单尝试一下

然后就是倒着dp的局部性保证了, 感觉对于这种通过长度悬空,的非真实的小于 似乎都可以类似思考一下

G

题意转化 成 只有增的世界, 题意转化还是不会

最小 转化成 最小割

不过感觉看了第二次这种 最小变成 最小割的建图, 悟出了一点东西

大概,想表达的意思就是,每个点和S同块还是T同块, 而和S同块/T同块 分别表示选和不选的一个对立状态, 而建立的容量边, 便是这些选择状态会长生的代价贡献

H

学了maspy的生成方程,感觉又多会了一点

参考

官方题解

maspy

我基于maspy做的翻译和笔记