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连的点和相同,且度相同

第一类stirling数

$s(n,k) = \begin{bmatrix} n \\ m \\ \end{bmatrix}$ 表示n个不同元素, 划分成m个非空段(每个非空段 满足循环平移等价) 的方案数

(n个两两不同元素,划分为k个互不区分的非空轮换的方案数, 也就是 如果划分出 [1,2,3] 那么 和[2,3,1]等价和[3,1,2]等价, 但是和[3,2,1]等价

$\begin{bmatrix}n\\ k\end{bmatrix}=\begin{bmatrix}n-1\\ k-1\end{bmatrix}+(n-1)\begin{bmatrix}n-1\\ k\end{bmatrix}$ 一样的也是考虑 最后一个单独放还是插入到前面某个序列里

边界$\begin{bmatrix}n\\ 0\end{bmatrix}=[n=0]$

生成函数

构造生成函数 $F_n(x)=\sum\limits_{i=0}^n\begin{bmatrix}n\\ i\end{bmatrix}x^i$

根据递推公式$F_n(x)=(n-1)F_{n-1}(x)+xF_{n-1}(x)$

有 $F_n(x)=\prod\limits_{i=0}^{n-1}(x+i)=\dfrac{(x+n-1)!}{(x-1)!}$