首页 > 其他分享 >近期总结 2024.2.19

近期总结 2024.2.19

时间:2024-02-26 11:14:47浏览次数:26  
标签:总结 2024.2 le frac 19 sum 合并 第四种 三种

ARC098D Donation

题意:一张无向连通图,\(n\) 个点 \(m\) 条边。你一开始选择任意一个点开始走,到达点 \(u\) 时,要求你必须有 \(a_u\) 元,且可以在点 \(u\) 捐赠 \(b_u\) 元。可以以任意一点结束,求在所有点捐赠一次的前提下,你的最小初始钱数。 \(1\le n\le n,m\le 10^5\)


考虑倒着来,到达一个点 \(u\) 的条件是手里至少有 \(\max(0,a_u-b_u)\) 元,第一次到达 \(u\) 后可以赚钱 \(b_u\) 元。不妨设 \(c_u=\max(0,a_u-b_u)\)

从 \(u\) 走到 \(v\),我们走的一定是 \(c\) 最大值最小的那条路径。

因此考虑构建 Kruskal 重构树(边权是两个端点的 \(c\) 较大值),发现我们一定是从一个叶子开始走,一个子树会先走完里面的点再走外面的点。

考虑 dp,设 \(f[u]\) 表示走完 \(u\) 子树的最小初始钱数。枚举初始从哪个儿子子树开始走,且走到 \(u\),设为 \(v\)。那么

\[f[u]=\min_v\{\max(f[v],c[v]-s[u])\} \]

其中 \(s[v]\) 表示 \(v\) 子树内 \(b\) 的总和,时间复杂度 \(O(m\log m)\)。


CF715E Complete the Permutations

题意:两个排列 \(p,q\),长度都是 \(n\)。定义 \(w(p,q)\):每次交换 \(p\) 中的两个数,将 \(p\) 变成 \(q\) 的最少交换次数。现在两个排列中有一些数字未知(标记为 \(0\)),求对于所有 \(i(0\le i<n)\),有多少种可能的 \(p,q\) 满足 \(w(p,q)=i\),答案摸 \(998244353\)。


最少操作次数,把 \(p_i\to q_i\) 连边,间接相当于形成环数量。

去掉已经形成的环,我们会剩下四类边:

  • \(x\to y\)

  • \(0\to x\)

  • \(x\to 0\)

  • \(0\to 0\)

对于第一类,我们把 \(x,y\) 合并成一个点,那么相当于我们有一些点,有四种属性:

  • 两端没有 \(0\)

  • 左端有 \(0\)

  • 右端有 \(0\)

  • 两端都有 \(0\)

分别计算这四种点的个数。然后发现,如果将第四种点和第二或三种点合并,还是第四种点;如果将第四种点和第一种点合并,会变成第二或三种点;第二或三种点可以和同种点合并;一个第二或三种点,可以自己形成一个环。

注意到每个第四种点都一定会一个第一种点合并。考虑一个最终的环,分为包含第四种点和不包含两大类。

如果不包含,那么环内都是第二或三种点,且不同时包含两种点。

如果包含,定义 \(A\) 为一个第四种点和二、三种点进行若干次合并后的点,\(B\) 为第一种点,不难发现最终的环一定是形如 \(ABAB...\) 这样的。显然,第二、三种点和这个步骤是独立的,可以分开计算,然后这个就直接用第一类斯特林数乘个阶乘。

现在考虑第二、三种点如何分配,枚举不包含第四种点的环的个数以及内部的点的个数总和,然后将剩余的分配下去。显然两种点是独立的,可以分开计算。

时间复杂度 \(O(n^2)\)。


AGC034F RNG and XOR

题意:一个变量 \(x\),初始值为 \(0\),每次随机选择一个 \([0,2^n)\) 内的数 \(y\),概率为 \(\frac{a_y}{\sum_i a_i}\),然后 \(x\gets x\operatorname{xor} y\)。对于每个 \(i(i\in [0,2^n))\),求出 \(x\) 第一次变为 \(i\) 的期望次数,答案模 \(998244353\)。 \(1\le n\le 18\)


选到 \(i\) 的概率为 \(p_i=\frac{a_y}{\sum_i a_i}\)。显然有个 dp,设 \(f[i]\) 表示变为 \(i\) 的期望次数。

\[f[i]= \begin{cases} 0 & i=0\\ \sum\limits_j 1+p_j\cdot f[i\operatorname{xor} j] & i\not =0 \end{cases} \]

高斯消元是 \(O(n^{3n})\) 的,无法通过。

令 \(f\) 和 \(p\) 的集合幂级数分别为 \(F(x),P(x)\)。

则 \(F(x)=\sum\limits_S x^S + F(x)*P(x)\)

但是 \(f[0]\) 是已知等于 \(0\) 的,上式其实是不成立的。

考虑修正 \(f[0]\):\(F(x)+c=\sum\limits_S x^S+F(x)*P(x)\)

显然 \(c\) 是常数。把两边的系数相加,即可得到 \(c=2^n\):\(F(x)+2^n=\sum_S x^S +F(x)*P(x)\)

整理得

\[F(x)=\frac{\sum_S x^S-2^n}{1-P(x)} \]

集合幂级数是无法求逆的。但这里比较特殊,如果我们给 \(f[0...2^n-1]\) 全部加上 \(t\),由于 \(P(x)\) 的系数总和为 \(1\),\(F(x)+2^n=\sum_S x^S + F(x)*P(x)\) 仍然成立,那么 \(F(x)=\frac{\sum_S x^S-2^n}{1-P(x)}\) 也成立。因此我们先通过 fwt 相除的方式求出一个 \(F(x)\),然后通过整体偏移的方式修正 \(f[0]\)。时间复杂度 \(O(n2^n)\)。

标签:总结,2024.2,le,frac,19,sum,合并,第四种,三种
From: https://www.cnblogs.com/Sktn0089/p/18020740

相关文章

  • 模拟赛 2024.2.16 解题报告
    A.楼房搭建题意:有\(n\)个数\(a_{1...n}\),以及初始全是\(0\)的\(b_{1...n}\)。现在每次选择一个\(i\in[1,n-1]\),然后选择下面一个操作:\(a_i\getsa_i+1,\spacea_{i+1}\getsa_{i+1}+2\)\(a_i\getsa_i+2,\spacea_{i+1}\getsa_{i+1}+1\)求使得\(\foralli,b......
  • 近期总结 2024.2.20
    AGC050CBlockGame题意:一个由B,S组成的字符串\(s\),你和对手在一个无限长的一维网格图进行游戏,对手一开始在其中一个格子。游戏第\(i\)轮:若\(s_i\)为B,你在网格图上的一个没有障碍以及非对手所在格子的格子上放一个障碍。若此时对手左右相邻两个格子上都有障碍,你胜利并......
  • 近期总结 2024.2.23
    dp专场。CF1784EInfiniteGame题意:一个由a和b构成的字符串\(s\),长度为\(n\)。两个人Alice和Bob在玩游戏,第\(i\)场中如果\(s_{(i-1)\bmodn+1}\)为a则Alice赢,否则Bob赢。两人遵循三局两胜原则:每当一个人胜场满两场时,称那个人赢了一轮,然后清空胜场记录开始......
  • 上周热点回顾(2.19-2.25)
    热点随笔:· 开年!5款令人惊艳的开源项目「GitHub热点速览」 (削微寒)· SQL中为什么不要使用1=1? (萤火架构)· 编写高效的代码,你应该了解Array、Memory、ReadOnlySequence... (Artech)· 都说了能不动就别动,非要去调整,出生产事故了吧 (青石路)· 4.1kStar!全面的C#/......
  • P1975 [国家集训队] 排队 题解
    题目链接:排队水紫,\(n\)不大,树套树或者分块都能做。分块的话,最优序列分块套套值域分块最优。观察到是可差性问题维护,即权值数量维护,那我们就树状数组套权值线段树即可。由于\(n\)不大,我们可以不用回收标记,直接数组空间开大点就行。我们预处理出初始逆序对,每一次操作都是基于......
  • NanoFramework操作ESP32(一)_基础元器件篇(十七)_ KY-019继电器(1路5V继电器)
    一、元器件介绍 1、针脚介绍针脚(左到右)介绍S控制针脚+电源+-电源-二、示例代码元器件的针脚ESP32模块的针脚SIO16+3.3V-GND1、代码 publicstaticvoidMain(){#region激光头KY008HelperkY008=newKY008H......
  • 寒假总结3spark简介
    ApacheSpark是专为大规模数据处理而设计的快速通用的计算引擎。Spark是UCBerkeleyAMPlab(加州大学伯克利分校的AMP实验室)所开源的类HadoopMapReduce的通用并行框架,Spark,拥有HadoopMapReduce所具有的优点;但不同于MapReduce的是——Job中间输出结果可以保存在内存中,从而不......
  • 第五周训练总结
    这周最令我印象深刻的是一道本来不难但迟迟做不对的一题。这道题能让其中一个数字加一,另一个减一,因此总数不变,于是我们准备从总数入手。很容易发现只要让总数能够分配出相同的数字,如24=6+6+6+6,并且分配出来的份数大于题目给的数组长度,便满足题意。但由于忘记考虑特殊情况:数组......
  • 《系统科学方法概论》绪论总结
    一,系统科学是以系统为研究对象的科学,分为:1,系统论2,信息论3,控制论特征:1,系统科学是以系统为研究对象的学科群2,系统科学是一门横断科学3,系统科学是一门应用科学4,系统科学带有极强的方法论性质二,系统科学的历史发展时期1,20世纪40-20世纪50年代的形......
  • 《程序是怎样跑起来的》第五章总结
    一,1,存储程序方式:程序要先存储在存储器中,然后才被依次读取执行。2,计算机中的存储器包括内存和磁盘,存储在磁盘中的程序要加载到内存才能运行。二,磁盘缓存:用于临时存放从磁盘读取出来的数据,可以提高磁盘数据的访问速度。三,虚拟内存:将磁盘的一部分模拟成内存来使用。磁盘缓存:将......