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被选, 但这样的 感觉还没钦定连接好, 但钦定连接就是枚举

https://codeforces.com/contest/1743

D. Problem with random tests

给你长 n的0/1

问它的两个子串(连续)的 bit or 的最大为多少

范围

n 1e6

4s

512mb

随机生成数据 不支持 hack

我的思路

首先一个肯定是原串,为了最高位1

那么剩下的一定是从最前连续1里面开始的

1
2
3
4

11100001....
3个1 len1=3
   4个0 len0=4
       ....

那么为了尽量高位填1, 如果len1 <= len0, 那就是都从第一个1开始,长度差为len1

1
2
3

11110001.....
len1=4
    len0=3

但如果len1 > len0

那么可以选的 有从头开始,和从偏移一个开始, 这两个都会or掉第一节的0, 但是后面的情况是未知的

看着禁止hack 似乎需要上string hash的意思?

如果暴力找就是 候选的开头在

1
2

11111110001....
xxxxx 这些位置都是候选

然后对于原串, 找每个0的位置, 反过来在候选中找是否为1, 不为1则剔除候选,

这样感觉要n^2

有点想后缀数组排序, 但问题是, 这里只有原串为0的对应位置需要是1(参与比较), 而原串已经是1的则可以忽略

不会啊,干

https://codeforces.com/contest/1749

F. Distance to the Path

给一定n点树, 初始每个点的值为0

m 个询问, 两种操作

1. 输出点v的值
2. 对所有到路径u..v 距离小于d的点 +k

范围

n 2e5

m 2e5

d [0,20]

k [1,1000]

4s

512mb

我的思路

如果 d = 0, 就是每次对路径上的点 增加k

似乎可以树上差分+lca维护?

但实际上 中间穿插着求一个点的值, 这样每次求值还是 O(dep[u]), 并不可行

怎么有点 树链剖分的味道?

树链剖分+线段树维护每个链???

那么 d != 0 ??

似乎会变成菊花状

https://codeforces.com/contest/1783

F. Double Sort II

给你两个 1~n的排列a,b

每次操作可以任选一个i, 交换 a[i] 和 a[?]=i, 交换 b[i] 和 b[?]=i

求最小操作次数 的一个具体方案 让 a,b 有序

范围

n 3000

2s

512mb

我的思路

又是排列问题, 排列的交换就是和 i -> a[i] 建立的环相关, 每次交换不同的值,环变化都是1(+1/-1),

如果单独看 a,

每次只要不是操作 swap(ai,ai), 都是 环+1

所以问题变成:

找尽量少的 下标集合, 使得a,b 中的 环中被选中的个数 >= 所在环点的个数-1

3000 似乎希望n^2 的样子

考虑 如果把一个变有序

(x-x-x-x) (x-x-x) ...

另一个怎么转移

1
2

a: 1-2 3-4 5-6-7-8
b: 1-2-3-4 5-6 7-8

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

Ex - Count Unlabeled Graphs

按照下面步骤生成图

选 简单,无向,n个无标签点 的图

给每个点 写 <= k的数, (1~k每个都至少出现一次

找方案数 mod p(质数 1e8~1e9)

范围

k <= n <= 30

我的思路

无标签的图 和 有标签的图之间 如何进行 重复统计的转化 ???

考虑按照连通块来划分

连通块大小 和 同联通块大小的选择个数

f[s] = 每个连通块大小为s 的 染色方案数 的生成方程 = a[s] x^s + a[2s] x^2s + a[3s] x^3s …

为了统计 g[s] = 加上外部贡献的选择倍数 = a[s]/s! x^s + a[2s]/(2s)! x^2s + a[3s]/(3s)! x^3s …

这样 ans = [x^n] n! g[1] * g[2] * g[3] * ... * g[n]

那么问题来了, 如何计算f[i]

h[i] = 1个大小为i的联通块的染色方案数

a[i] = h[i], 直接染色

a[2i] = binom(2i,i-1) h[i] * h[i], 确定1在地一个块

a[3i] = binom(3i,i-1) * binom(2i,i-1) h[i]^3, 确定1在地一个块, 不在第一个块中最小的在第二个块

那么如何计算h[i]

count[形状] = 一个形状的染色方案数

h[i] = sum count[形状i]

形状不同, 染色后一定不同, 但是相同形状 染色后可能相同,

如何判断两个形状不同, 如何枚举形状, 每个形状如何计算染色方案??????????????????????????

并不会

能想到一些必要条件, 但没啥充分条件, 比如 点i连的点和相同,且度相同