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

Ex - Popcount Sum

$0 \le R,M+R,2M+R,3M+R,\cdots < N$

$R \in [0,M]$

问上述[0,N]中的这些数, 的二进制下的1的个数的总数

范围

t 组数据 1e5

n 1e9

4s

1024mb

我的思路

分类一下, 感觉就需要一点数学, 然后t 1e5, 基本也就是说, 要么O 1,要么O sqrt 左右

如果m==1, 那么就是1…n 的所有数的二进制1的个数和, [1…2^t,2^t+1…n] 这样划分就是 sqrt

如果m==2^k, 那么这些数的 低k位都一样, k位以上, 和上面是一样的

如果m 不是上面的情况,进位的时刻, 似乎并不好拿捏

2, 3+2,6+2,9+2

1
2
3
4
5

  10
 101
1000
1011
1110

能说的是 低两位4次的循环节, 比3还大, 高位也没啥规律

对称相加

R, M+R, 2M+R, … , kM+R

kM+R, (k-1)M+R,…, R

对称的和始终是 (k+1)M+R, 有办法 只算 一半 与 (k+1)M+R 的bit的联系, 这样一半

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

G - Similar Permutation

两个长n排列A,B

相似度为 相邻同增次数 + 相邻同减次数, (A[i+1]-A[i])(B[i+1]-B[i]) > 0

问 相似度为k的有序对 (A,B) 有多少个, mod p

范围

n 100

p [1e8~1e9]

4s

1024mb

我的思路

看这 n, 感觉有可能就要到4次方, 想一维度的排列,每次 从N-1到n, 就是考虑n的插入位置

但是两个序列的话

a0 a1 a2…..

b0 a1 b2…..

插入一个值, 会让后面的值平移, 增减关系会错位

变一变, f(k) = 至少k个位置增减关系一致, 那么ans = f(k) - f(k+1)

但这样也不知道怎么统计

因为

1 2 3, 假设定了第一个位置是增

那么

1-2 3

2-3 1

1-3 2

第二个位置并不是增 减 数量相等的

如果a和b在从n-1变到n时, 插入位置相同, 那么这个位置的左右增减都是相等的, 但是插入前可能相等可能不等,增量是1, 但不同怎么处理

再就是不要插入n, 而是末尾插入一个

f(len a, last a, len b, last b), 似乎可以搞?, 注意到两个len是相等的

插入 x, 等于 原来 [1…x-1] 不变, [x..n-1] 平移1变成[x+1,n]

f(len, last a, last b,同增减k)

f[n][a1][b1][k1] += f[n-1][a0][b0][k0] , k1 = k0+ bool( (a1 <= a0)^(b1 <= b0) )

这样状态是 O(n^4) 转移是 O(n^2) 一共O(n^6) 过不了

可能需要二维前缀和搞一搞?, 实际就是一条纵线 a1 = a0 和 b1 = b0 划分的

https://codeforces.com/contest/1767

E. Algebra Flash

长n的 染色格子

每次只能走 i+1 或 i+2

颜色要激活才能走(一次激活所有同色), 求最小代价, 让1到n是通的

范围

n 3e5

颜色种类 m [1,40]

激活代价 [1,1e7]

2s

256mb

我的思路

只感受到 i如果不激活, 那么i-1 和i+1必定要激活, 这样有一定的 约束性, 不知道能不能2-sat, 但感觉2-sat 出来的强联通块的意义 也不明

m 40 的话, 就没法直接bitmask

https://codeforces.com/contest/1762

D. GCD Queries

交互题

有 [0…n-1] 的排列 固定但是隐藏

你最多 2n 次询问, 找到2个下标, 其中一个要是0的下标

每次可以询问 gcd(a[i],a[j]), i!=j

范围

n 2e4

3s

256mb

我的思路

筛出 2的倍数

筛出 4的倍数

这样下去就可以了

但 次数无法保证

要找2的倍数 首先得找到一个是2的倍数的, 这最坏需要 n/2 + 3 次, 再找 就需要 n - 4 次

https://codeforces.com/contest/1766

F. MCF

n 点 m边 网络求一个最大流,最小费用 方案

且满足每条边上 实际流 与 其容量 奇偶性一致

输出方案, 或不存在

范围

n 100

m 200

容量 [1,100]

单位代价 wi [-100,100]

我的思路

想着把奇数处理掉, 剩下就是容量处以2, 费用乘以2的问题了

但不会处理奇数, 想到可以每个点出度入度, 但具体也不会