序幕
\(\text{6:50}\):昏暗到校,写 CF 杂题。
经过两个小时的思考终于看懂了题解。
\(\color{blueviolet}{CF1530F}\)
此题是神秘题。
考虑反着做,将至少有一行或一列或一条对角线全为 \(1\) 概率转换为所有行列对角线都至少有一个 \(0\)。
先不考虑行与对角线,只考虑满足所有列都至少有一个 \(0\) 该怎么做,为了使得我们的不完全做法有扩展性,我们考虑使用容斥。
过程如下:
-
加上至少有 \(0\) 列全为 \(1\) 的概率。(对于至少有 \(x\) 列全为 \(1\) 的概率,可以理解为我们选定 \(x\) 列,使得其全为 \(1\)(概率相乘),其他列的 \(0/1\) 情况我们不考虑(概率为 \(1\))。而选定的 \(x\) 列的所有情况概率要加和,比如我选定 \(1\) 列,那么情况总数有 \(n\) 种,这些情况的概率都要加和。)
-
减去至少有 \(2\) 列全为 \(1\) 的概率。
-
加上至少有 \(3\) 列全为 \(1\) 的概率。
-
以此类推。
这样容斥并不难理解,我们需要求的是所有列至少有一个 \(0\) 的情况,对于第一步加的概率显然是全情况的概率,我们减去其中有一列为 \(1\) 的概率,但此时对于两行为 \(1\) 的情况我们减了两遍。举个例子,对于 \(1,2\) 号列全为 \(1\) 的某种情况,我们选定 \(1\) 号列时和选定 \(2\) 好列时分别减去了一遍,所以要在接下来的运算中将其加回来,以此类推。
接下来考虑在这样计算列的贡献时计算行的贡献,首先每一行的贡献互不影响,考虑固定选定的列进行某一行的运算,我只要保证舍去行的全为 \(1\) 的概率即可。我们设 \(f_{i,j}\) 表示对于第 \(i\) 行,选定 \(j\) 状态列(\(j\) 是一个状压状态,这里选定其中的列就相当于在第 \(i\) 行中该位置一定为 \(1\)。),不考虑其他位置 \(0/1\) 状态的概率。这个东西显然是可以预处理的。
于是就有第 \(i\) 行在状态 \(j\) 下的贡献概率 \(g_{i, j} - g_{i, 2 ^ {n - 1}}\),其中我们减掉的是此行全为 \(1\) 的状态,也就是上文说到舍去的部分
最后对角线与列的处理相同,枚举一下状态即可,使得一行与对角线交点的位置为 \(1\) 即可。
\(\color{blueviolet}{CF1530F}\)
此题是坏题,他卡你空间。
每一个元素有选或不选两种状态,并且有依赖项,元素的贡献有正负,数据范围不大,可以自然联系到最大权闭合子图,采用最小割模型。
建模方式如下:
- 对于一个正权点 \(u\),连边 \(S \to u\),容量为 \(b_i\)。
- 对于一个负权点 \(u\),连边 \(u \to T\),容量为 \(-b_i\)。
- 对于所有 \(i\),对于其所有依赖的 \(j\) 连边,容量为正无穷。
但这样建边空间就爆炸了,考虑到值域很小,一个数不同约数个数不会很多。对于一个数 \(a_i\),枚举其约数 \(x\),对于每一个 \(x\) 只需要向最近的 \(x\) 建边即可,这样由于依赖关系的传递性不会出问题。
现在考虑最小割的意义,对于源点到正权点的一条边流满表示这个点我们舍弃掉了,对于负权点到汇点的边流满表示这个点我们被迫选择了,所以有答案 \(\left( \sum \limits _ {b_i > 0} b_i \right) - f\),其中 \(f\) 为最小割。
间幕 \(1\)
上午做题比较慢,应该是因为题难,感觉 CF 比 POI 普遍难做(也可能是因为评分稍高)。
中午和府捞面欲望上升,吃和府捞面,没吃早饭差点要饿死。
中午毫无犹豫直接选择昏迷,十四点多起床,状态良好,写写博客,点两杯茉莉奶绿,三点二十开始做题。
看不懂题解。
不会。
然后就晚休了。
晚上和 iazm 出去溜达,互相话疗了一下,感觉良好。
晚上写了一道题但发现假了,直接开摆。
间幕 CF 1891
A 结论很显著,切掉了。
B 显然操作完一个数之后大于等于它的就都没啥意义了,操作次数减少到最多 \(30\) 次,模拟时间复杂度降到线性对数。
C 凭感觉写了个贪心,正确行大概没问题就切掉了。
D 感觉会了,但时间不咋够。
尾声
快到两点就睡觉了。
标签:对角线,选定,Log,对于,2023.10,列全,概率,30,考虑 From: https://www.cnblogs.com/Eon-Sky/p/17793460.html