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的最小前缀

G - Roll or Increment

https://atcoder.jp/contests/abc224/tasks/abc224_g

1~N 骰子

初始S, 得分f(X) = X

A元, 让得分+1

B元, 重新转

求最小期望代价, 让得分为T

范围

N 1e9

A,B [1,1e9]

2s

1024 mb

我的思路

日常不会概率论

猜一个

S < T

直接通过A, (T-S)A

转一次的期望 E

(N-T)/N * (B+E), 大于T 部分的贡献

1/N ( min(0,B+E) + min(A,B+E) + min(2A,B+E) + … + min((T-1)A,B+E)), $\le T$ 部分的贡献

$E = \frac{N-T}{N} \cdot (B+E) + \frac{1}{N} ( min(0,B+E) + min(A,B+E) + min(2A,B+E) + \cdots + min((T-1)A,B+E))$

若能求出E, 就做出来了

转化一下

$NB + \sum_{i=0}^{T-1} \text{min}(iA-(B+E),0) = 0$

只有E是变化的, 随着E 增大, 表示式变小, 单调, 可二分

好像还真就过了

G - Vertex Deletion

https://atcoder.jp/contests/abc223/tasks/abc223_g

N 点, 标号1到N, 的树

找有几个点满足, 删了它和它直接相连的边以后, 最大匹配个数 = 原图最大匹配个数

限制

N 2e5

2 s

1024 mb

我的思路

显然如果删了u以后最大匹配个数不变, 那么在原图中u所直接连的点,在删除以后的图中都被选了

否则的话, 其中一个和u可以让匹配数+1

并且这些和u直接相连的点在最大匹配中是必选, 也就是不存在方案让它不被选

又因为结构是树

假设断开u-v的连接

以v为根的连通块为根做树

v必选(和子节点匹配)的条件是,任何一个子树的根未被选

v不被选(不和子节点匹配,可能和父节点匹配)的条件是,所有子树的根被选

感觉像是换根dp

也就是求u作为根 f(u) 为不和子节点匹配的 u的个数

f(u) = !(f(v1) & f(v2) & f(v3))

为了减少枚举,可以变成 子点0的个数统计

f(u) = count(f(v) == 0) > 0

u 交换 v

u 的子节点里没有了v, 更新u

v 的子节点里没有了u, 更新v

顺序就dfs顺序就完了

好像就AC了

G - 222

https://atcoder.jp/contests/abc222/tasks/abc222_g

在数列2,22,222,2222,22222,….中

N个X, 首个是 Xi的倍数的下标是?, 或者不存在

范围

N 200

Xi [1,1e8]

我的思路

一眼看上去很数学, 很像Project Euler的题

$2222222 = 2 * 1111111 = 2 * \frac{(10^7 - 1)}{9}$

其实就是问对于x

是否 2 * (10^7 - 1) = 9 k x

首先x的2的幂次为0/1

好像有点绕

$kx = 1111111 = 10^0+10^1+10^2+\cdots$

右边虽然项数为合数时可以拆分, 例如$6 = 3 * 2$, $111111 = 111 \cdot 1001 = 11 \cdot 10101$

但不知道是否能拆出所有

另一个就是对于比较小的11111的部分,可以pollard-rho分解

考虑长除法?

每次 除法取mod 乘10 加1

但1e8 不知道效率怎么样

PE 129 做过类似的, 但是问题是首个 让是它倍数的最小$111\cdots 111$长度超过百万的是哪个因子

而有一些可用的结论

除了上面$2,5$因子外$kx = 111\cdots 111$始终有解, 且$111\cdots 111$ 的长度不超过$n$ (因为模数随着长度变化成环)

因此 如果暴力的话, 期望值是在 $O(NAi)$ 的

想了下打表 超过1e6的记录下来, 未超过的现场算, 但很多 超过1e6的

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

int two(int v){
  int c = 0;
  ll m = 0;
  do{
    m*=10;
    m+=2;
    c++;
    m%=v;
  }while(m!=0);
  return c;
}

void calc(){
  rep(i,1000000, 100000000+1){
    if(i % 1000000 == 0) printf("progress %lld\n",i/1000000);
    if(i % 4 == 0 || i % 5 == 0)continue;
    int res = two(i);
    if(res > 1000000) printf("ans[%lld] = %d\n",i,res);
  }
}

另一个就是根据PE129的证明过程, 反正有$\phi(n)$ 或者$\phi(9n)$ 是一个解

那么可以找$\phi(n) , \phi(9n)$的因子尝试, 但这样是否能保证是最小的呢????? 根据倍数, 显然最小的是这个解的因子

$\phi(n) = n \cdot (1-1/p1) \cdot (1-1/p2) \cdots$

似乎可做?

F - Diameter set

https://atcoder.jp/contests/abc221/tasks/abc221_f

N 点树, 找染色法, 染>=2个点为红色,让红色点两两之间距离为直径

方案数 mod 998244353

范围

N 2e5

2s

1024mb

我的思路

首先直径 是经典算法, 随机点u,找最远点v, 再以v找最远点 便是直径

如果选v

那么可以把v看作根, 相当于做树上dp

因为有深度和直径都知道, 那么对于到叶子距离2倍小于直径的分叉至多选一个,

而2倍大于直径的分叉(不可能都有直径,否则这样能得到更大的长度)

如果直径是偶数, 那么从v到1/2直径点u再到最远点, 这样的点u只有一个,并且这个u可以看成重心

因此可以从重心去找 直径/2 的距离做树上统计 即可

问题来到了奇数长度的直径, 如果直径是奇数, 选了v到最远点的方案 就是最远点的个数

任意两个直径 必有交点, 否则 两个直径上 p1..p2 有一个简单路径 取 p1 — 最远, p2 — 最远, p1-p2, 大于等于 直径/2向上取整 + 1

这样的话

任取一条来看,

v …. x - y…..t

假设,x和y是中间距离的两个点

那么不可能有不经过y的v..x…t1, 否则 t..x..t1 更长

换句话说

一定所有直径有x-y

类似的证明

已经证明了有公共点,

那么假设是y右侧的最近的某个p

同样v ….p…更长的一半, 将会比直径长

x对称同理

所以奇数情况,就是, x 去找距离的方案 乘上 y 去找距离的方案

似乎就推出来了?