首页 > 其他分享 >「Log」2023.10.30 小记

「Log」2023.10.30 小记

时间:2023-10-31 11:45:33浏览次数:38  
标签:对角线 选定 Log 对于 2023.10 列全 概率 30 考虑

序幕

\(\text{6:50}\):昏暗到校,写 CF 杂题。

经过两个小时的思考终于看懂了题解。

\(\color{blueviolet}{CF1530F}\)

此题是神秘题。

考虑反着做,将至少有一行或一列或一条对角线全为 \(1\) 概率转换为所有行列对角线都至少有一个 \(0\)。

先不考虑行与对角线,只考虑满足所有列都至少有一个 \(0\) 该怎么做,为了使得我们的不完全做法有扩展性,我们考虑使用容斥。

过程如下:

  1. 加上至少有 \(0\) 列全为 \(1\) 的概率。(对于至少有 \(x\) 列全为 \(1\) 的概率,可以理解为我们选定 \(x\) 列,使得其全为 \(1\)(概率相乘),其他列的 \(0/1\) 情况我们不考虑(概率为 \(1\))。而选定的 \(x\) 列的所有情况概率要加和,比如我选定 \(1\) 列,那么情况总数有 \(n\) 种,这些情况的概率都要加和。)

  2. 减去至少有 \(2\) 列全为 \(1\) 的概率。

  3. 加上至少有 \(3\) 列全为 \(1\) 的概率。

  4. 以此类推。

这样容斥并不难理解,我们需要求的是所有列至少有一个 \(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}\)

此题是坏题,他卡你空间。

每一个元素有选或不选两种状态,并且有依赖项,元素的贡献有正负,数据范围不大,可以自然联系到最大权闭合子图,采用最小割模型。

建模方式如下:

  1. 对于一个正权点 \(u\),连边 \(S \to u\),容量为 \(b_i\)。
  2. 对于一个负权点 \(u\),连边 \(u \to T\),容量为 \(-b_i\)。
  3. 对于所有 \(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

相关文章

  • 亚信科技AntDB数据库通过GB 18030-2022最高实现级别认证,荣膺首批通过该认证的产品之列
    近日,亚信科技AntDB数据库通过GB18030-2022《信息技术中文编码字符集》最高实现级别(级别3)检测认证,成为首批通过该认证的数据库产品之一。图1:AntDB通过GB18030-2022最高实现级别认证GB18030《信息技术中文编码字符集》是我国自主研制的以汉字为主、包含10种我国少数民族文字的超......
  • 2023.10.30
    运行超市抹零结账行为代码如下:1print("3107")2money=39.87+24.47+78.07#计算总金额3money_str=str(money)4print("商品总金额:"+money_str)5print("实收金额:{:.0f}".format(money))#进行抹零行为结果如下:计算学生成绩的分差和平均分代码如下:......
  • 10.30
    今天Java考试部分代码如下packagebean;publicclassBean{privateintid;privateStringname;privateStringgaishu;privateStringfangshi;privateStringstarttime;privateStringfianltime;privateStringgongyi;publicvoidsetId......
  • 「解题报告」2023-10-30 模拟赛
    1.ABBA企鹅豆豆拿到了一个\(N\timesM\)的矩阵,每个位置要么是\(A\)要么是\(B\)。他希望尽可能少的改变里面的字(即\(A\)变\(B\)或者\(B\)变\(A\))使得这个矩阵有至少\(R\)行是回文串,以及至少\(C\)列是回文串,现在他想知道自己需要的最少操作次数。枚举哪些行和哪......
  • 10.30 献花
    我要学习crimson000的魔怔精神妈的啥玩意啊,去年同一道题写暴力写了70,今年就只有50了??去年能切的题今年挂20,合着往死里退步是吧......
  • 每日总结10.30
    今天上课完成了两个软件设计的实验,下午做了java程序设计的期中测试取得了满分,然后做了一些软考题。  ......
  • 2023/10/30
    今日我发誓每天学习Javaweb的视频,并且做好每一天的笔记,每一次的代码都要自己上手敲,不给自己留下遗憾,我不想大四毕业以后连工作都找不到。我的目标是考研,这就需要严格要求自己,怕什么,别人能完成,为什么就你完不成,别人能学会,为什么就你学不会,就一个字——懒。不去上手,天天刷视频,打游戏......
  • 20231030
    企业ERP生产计划管理系统(20分)1、项目需求:随着企业规模的不断扩大和市场竞争的日益激烈,生产计划管理成为了企业管理中不可或缺的一部分。生产计划管理子系统是企业管理信息系统中的一个重要组成部分,它主要负责生产计划的制定、执行和监控,以确保企业生产活动的高效性和顺畅性。生......
  • 10.30日
    今天早上是机械拆装实训,我们以自行车为例展开了课程教学,以五人小组为单位展开了动手实践。下午极限三小时小考了一下,王老师的简单期中测试罢了(才不是呢)。虽然我周末进行了提前练习,考试勉强通过,但是在三小时里还是出现了未预料到的困难——内部服务器报错500,具体原因是tag的jar包出......
  • 231030校内赛
    T1新的阶乘有三种做法,第一种也就是我写的这种容易被评测机波动坑,复杂度玄学考虑处理出每个数的质因数,然后就暴力除每个数的质因数的种类次非常的简单,也容易被卡第二种是与第一种差距不大,就是在线性筛中处理出质因数之后,再对每个数除以线筛中处理的质因数,将它的答案加到除数和......