CF tracker

Edu List

https://codeforces.com/contest/1620

F. Bipartite Array

给你1~n排列数组a

问能否 给每个数乘上 1或-1,

然后对所有逆序点连边, 让所有点能二分图

范围

n 1e6

2s

256mb

我的思路

考虑一个点是负数, 那么它前面所有点和它相连, 所以前面点和它 都在二分图对面, 所以它们之间不能有边, 所以它们需要单调递增,

如果考虑n是正数, 同理 它右侧的点 需要单调递增

如果n是负数,那么它左侧的点要单调递增

问题是这样分割, 会产生n个分支?

dfs 来控制 ?

CF tracker

Edu List

https://codeforces.com/contest/1622

E. Math Test

n个学生,

m个题目

你知道每个学生 哪些题目对了哪些题目错了, 正确得分错误不得分

r[i] = 第i个学生的真实得分 = 正确题目得分之和

x[i] = 第i个学生的标准得分, 给定

问如何给题目 的分设置为 1~m 的排列

能让 sum |xi-ri| 最大, 求最大值

范围

n 10

m 1e4

2s

256mb

我的思路

这n很小, 就很想bitmask

但是 bitmask怎么用

想的是 分别计算 f(bitmask) = bitmask中的学生真实得分 >= 标准得分, 其它的学生 真实 < 标准

这样去掉了绝对值

然后如何算呢

这样得到 10个 不等式 和一个要求的最大值

正确错误的1/0串[i] * 题目分数设置 = r[i] >= x[i]

…

正确错误的1/0串[j] * 题目分数设置 = r[j] < x[j]

…

要求 max( 正确错误1/0加权和 * 题目分数设置)

有点像线性规划?

但一个是排列, 一个是又有大于等于, 又有小于等于, 并不知道怎么搞

CF tracker

Edu List

https://codeforces.com/contest/1626

F. A Random Code Problem

给长度n的数组a

执行k次i=1..k

每次随机取下标idx,

ans+=a[idx]

a[idx] -= (a[idx] % i)

求 ans的期望, mod998244353

范围

n 1e7

1 <= a[0],x,y < M <= 998244353

1 <= k <= 17

a[i] = (a[i-1] * x + y)%M

3s

512mb

我的思路

这个操作就是 a[idx]变成贡献, 然后a[idx]变成不大于它的最大的i的倍数

这好几个神奇的地方, 首先n很大, 数组都是通过 递推式子给的, 这个递推式如果M小还有周期, 如果M大,不太知道怎么用

然后这个k <= 17 真的很小, 小到 甚至在想 bitmask

f[index][bitmask] = 贡献, 虽然这个状态大小都接受不了

但注意到第一次 的期望就是所有的平均数,

第二次也是, 当第二次选的偶数时, 那么第三次也是, 当第二次选的奇数时, 第三次 = 所有平均数 - 1/n

所以 经过第 i 轮 损失的量的 期望如果能算的话, 也是一个角度

算了下lcm(1…17) = 12252240, 也不小

而且 分支变化 状态也多

要快速计算 a[j] 可以用矩阵乘法, 但是 又要mod 又要加法, 算和也不知道怎么搞, 所以应该直接暴力掉?

12252240 似乎也可以, 每次相当于 n种操作, 那么就是所有 产生n 分, 第i份 处理i

只是在统计上,把它们加在一起, 这样每次 每个产生 1份处理的 和 n-1份没被处理的

r[i][w] += r[i-1][w]*(n-1)

r[i][next(w)] += r[i-1][w]

处理后的一定不大于当前的, 所以可以从大到小滚动掉,

所以可以滚动掉, 大概 O(k lcm(1…k)) ? 能过吗?

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

import math

def f(l,r):
    s = 1
    for i in range(l,r+1):
        s=math.lcm(i,s)
    return s

for i in range(1,17+1):
    print(i, f(i,17))

1 12252240
2 12252240
3 12252240
4 12252240
5 12252240
6 12252240
7 12252240
8 12252240
9 12252240
10 4084080
11 4084080
12 371280
13 371280
14 28560
15 4080
16 272
17 17

题解

还真是这样, 问题在于我想多了, 17并不需要, 因为17虽然改变, 但是贡献是由16决定的

所以 lcm(1..16) = 720720 就相当的小了

就随便做了

总结

试了一下, 看来补atcoder和补cf还是开vp补 比较好, 这场VP了

E 没有在时间内写出来, 翻来覆去才写出, 花了接近1.5h, 还是应该想清楚所有情况才写,不要想一半写一半

F 细节想得有问题, 但总体的思路没问题

然后1e7 果然 for还是随便for的, 不直接给, 估计是因为read慢

参考

官方

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

G

h * w 的格子 要用 1x1 和1x2 填满

上面有写 1,2,? 三种

1需要1x1覆盖

2需要1x2 覆盖(可以旋转成2x1)

? 任意

问 是否有可行方案

范围

h,w 300

3s

1024mb

我的思路

1 不需要关心, 只用关心2, 以及辅助2的?

看起来可以奇偶分边, 来做 二分图最大匹配 O(300^4) 感觉过不了

而且还有问题, 这里并不是要最大匹配, 只是要无冲突和匹配完所有2

另一个想法类似的, 能不能网络流, 还是奇偶分左右点, ?与?不连边, 但是 依然不知道如何表示 优先选2, 难道要费用流? 2的费用更低? 但似乎也没有”保证”

CF tracker

Edu List

https://codeforces.com/contest/1633

E. Spanning Tree Queries

给n点,m边一个连通无向图

k个询问, 每次一个xi

你需要找一个生成树, 让 sum |wj-xi| 最小, wj为生成树的边的权重, 不需要输出具体方案

前 p个询问具体给出 xi

[p+1~k] 的询问 通过 q[j]=(q[j-1]a+b)%c 给出

输出所有询问的结果的xor

范围

n 50

m 300

wi, xi [0,1e8]

p 1e5

k 1e7

c [1,1e8]

4s

256mb

我的思路

对于一个具体的一个询问, 那么就是 经典的最小生成树算法, 让边权 = |wj-xi| 即可

但如果 把边排序了 并记录边的id

如果x变化, 但是排序后id顺序没有变, 那么最小生成树选择的边就不会边(虽然边权重变了)

那么排序后会有多少种情况呢, 感觉上 比 binom(50,25) 还多, 想x分割大于和小于的边,两个穿插

如果这个情况少, 那就变成 统计 情况内的边选择, 和对应>x小于x的个数与和来计算了

p 1e5 n 50 , m 300 是可以接受 暴力的

但是 k 1e7 一定要实现某种批量算法