首页 > 其他分享 >10.28 ~ 11.3 总结

10.28 ~ 11.3 总结

时间:2024-11-03 22:30:39浏览次数:4  
标签:总结 log 10.28 容斥 11.3 枚举 即可 答案 dp

联考

联考打得不怎么样,一个原因是有两场 T3T4 全放 DS,可能适合叫练习赛,但是顶个模拟赛的名字就有点有点了。但是省选联考本来认为擅长的 T1 这样的题目也没有做出来。

题解还是在这里 https://www.cnblogs.com/british-union/p/liankao.html

做题

ARC155D 对于博弈论的题目目前还是不得要领。一个局面 \(g\nmid A_i\) 的 \(A_i\) 是一定还活着的,而剩下的数我们是只关心有多少个的。进一步的,我们只关心剩下的个数的奇偶性。然后直接 dp 转移即可,这里转移需要容斥处理,暴力枚举因数是 \(O(\sum _{i\le n}d(i)^2)\) 的,但是据信这是 \(O(n\log^3 n)\) 的,总之值并不大。

ABC236H 容斥需要计算容斥系数,写出来一看不是 \(\mu(\Pi_n)\) 吗!斯特林反演即发现为 \((-1)^{n-1}(n-1)!\)。然后做集合幂级数 exp 即可。

AGC037E 考虑最大化前缀最小字符。这个画一画发现是 \(\ge 2^{k-1}t\) 的,其中 \(t\) 是 \(ss_R\) 中 a 的最长连续段,并且答案后面跟和 \(ss_R\) 后面跟的的是一段,直接比较或者 SA。

P9542 首先发现非链树是可以做到黑白染色后的棋子和最大边全凑拢的。所以非链二分图也可以。非链非二分图考虑某个奇环,这个是可以达到上界的,即黑棋白棋凑拢。最后还剩链,记录相邻两点之间距离之后相当于每次操作将一个减小 \(2\),因此直接 dp 即可,记录 \([l,r]\) 集合在 \(i\) 的最大贡献,复杂度 \(O(n^4)\)。

ARC153C 类似介值原理: \(\pm 1\) 的前缀和如果有正/负数,必然存在 \(1/-1\)。直接加即可。

AGC068D 冷静分析,当且仅当不可交换的时候,即 \(x_{i+1}\) 是 \(x_{i}\) 的祖先不存在的时候才是极小。对这一点容斥,即在树上选 \(k\) 条祖孙链计 \((-1)^{n-k}\)。统计哈希值,枚举位置的贡献,dp 即 \(f_{i,l,r}\) 是 \(i\) 左侧有 \(l\),右侧 \(r\) 的贡献之和,这个可以合并子树答案后枚举当前点行为 dp,是 \(O(n^5)\) 的。但是 \(f_{i,l,r}\) 大多相等,于是记 \(f_{i,l,r,0/1}\) 表示被枚举的点是否在子树内部之后再转移,情况比较多。时间复杂度变成了 \(O(n^4)\)。

鉴于只跑 \(O(1)\) 秒,\(O(n^5)\) 可能也可以通过,,

P10509 比较奇异搞笑的组合题,证明不想写。

P9062 平面最近点对的平面分块做法加以改进,不再维护答案的块长,而是维护块长为 \(2^k(k=1,2,\dots )\),这样的好处是当块内或临块距离 \(< 2^{k-1}\) 时就可以直接删除,因为贡献被统计过了,这样一块内仍然是 \(O(1)\) 个点。扫描线统计答案,于是最后的复杂度是 \(O(n\log V+q\sqrt n)\),这里使用分块 \(O(1)-O(\sqrt n)\) 单点改区间查 min,因为 \(n\log V\) 一部常数较大。

CF914H Ember 获胜当且仅当所有链的点序列均单峰或单谷。这样的树有性质:令小数连向大数,则存在一个点作为根,其子树均为内向或外向树。这样,我分别 dp 再合并即可,钦定根是靠近内向树那边那个,即入度 \(>1\)。

CF1158B 诡异构造,,,设 \(a=(n-k)/2\),则 \(111111011111101111110111\dots\) 其中 \(1\) 连续个数是 \(a\) 是满足条件的。不知道是怎么想到的。

CF1981F 关于最小化 mex 的神秘技巧。扩大可行域:钦定 \(i\) 不出现,就把 \(i\) 当成 mex 处理,如果不是就不优。还有神秘结论:选取的 mex \(\le \frac n{\log n}\)。证明好像不是很自然,,。但是也可以使用线段树合并或者启发式合并处理。

CF1375F 神秘构造,,后手输,当形成等差数列,给的值是公差,且最大值操作过。现在构造等差数列。首先给个 INF 造最大值,然后给个 3*INF-SUM 就完成了。

CF1450H1 比较套路的计数,H2 不知道。

CF1305F 显然答案 \(\le n\),所以至少有一半的数之多被操作一次。因此随机很多次,每次随机一个数拉出来逐个计算 \(a_i\pm 1\) 和 \(a_i\) 的因子的答案即可。

CF1295F duel 的题。比较暴力的做法是,直接 dp 的 dp 值关于值域分段是多项式,直接拉插转移。

CF1453F 注意到走到 \(n\) 的数必须留且仅留一个,这个变成新的 \(n\)。因此设 \(f_{i,j}\) 为 \(i\) 为终点,走到 \(\ge j\) 且 \(<i\) 的位置已经删除的最小代价(不算已经删除的),这个正着转移是很好做的。

CF1951G 板子的停时定理。

CF794D 有题解。发现仅需考虑第一个不相等的位置的限制!层层拆开相当于辗转相除,最后得到 gcd 为单位字符串,限制只有是两个单位相等!之后直接统计即可。

CF566C 分析一通发现两点间的“距离”和总是凸的,这也就是说一个点到答案的“距离”和是递增的,从而一个点伸出去只有一个邻点比他小(或者没有)。点分治这个过程,只需 \(O(n)\) 计算是哪个邻点。对“距离”和求导,到一个子树的导数就容易计算了。

CF1951H 这样的交换两数在二分答案后非常简单:\(01\) 交换。进一步的,我只需要考虑 0 变 1,因为如果 1 变 0 那一边出问题就不进行交换。因此在线段树结构上设 \(f_i\) 为保证 \(i\) 胜所需最小的预交换次数。对于非叶子节点,至少需要凑够 \(2^{t-dep+1}\) 个 \(1\),然后再考虑左右两边:加起来 \(-1\) 即所至少需要。

标签:总结,log,10.28,容斥,11.3,枚举,即可,答案,dp
From: https://www.cnblogs.com/british-union/p/18524134

相关文章

  • 2024-2025-1 20241327 《计算机基础与程序设计》 第六周学习总结
    作业信息|2024-2025-1-计算机基础与程序设计)||--|-|2024-2025-1计算机基础与程序设计第六周作业)||快速浏览一遍教材计算机科学概论(第七版),课本每章提出至少一个自己不懂的或最想解决的问题并在期末回答这些问题|作业正文|https://www.cnblogs.com/shr060414/p/18440575|教......
  • 2024-2025-1 20241409司马平珏《计算机基础与程序设计》第六周工作总结
    作业归属课程:https://edu.cnblogs.com/campus/besti/2024-2025-1-CFAP作业要求:https://www.cnblogs.com/rocedu/p/9577842.html#WEEK06作业目标:Polya如何解决问题、简单类型与组合类型、复合数据结构、查找与排序算法、算法复杂度、递归、代码安全作业正文:https://www.cnblogs.......
  • 学期(如2024-2025-1) 20241406刘书含)《计算机基础与程序设计》第六周学习总结
    教材学习内容总结《计算机科学概论》第七章计算机硬件基础:计算机硬件是计算机系统的物质基础,包括中央处理器(CPU)、内存、存储设备、输入输出设备等。中央处理器(CPU):CPU是计算机的大脑内存:内存(RAM)是计算机的短期记忆,用于存储当前正在处理的数据和程序。包括随机访问存储器(RAM......
  • git常见命令总结
    文章目录什么是git? 远程仓库相关操作初始化git仓库查看状态信息工作区<=>暂存区相关操作暂存区<=>本地存储仓库。配置作者的信息分支相关操作标签操作常见错误什么是git?Git是一个分布式版本控制系统,由LinusTorvalds于2005年创建,最初是为了更好地管理......
  • 2024-2025-1 20241318《计算机基础与程序设计》第六周学习总结
    这个作业属于哪个课程https://edu.cnblogs.com/campus/besti/2024-2025-1-CFAP这个作业要求在哪里https://www.cnblogs.com/rocedu/p/9577842.html#WEEK06这个作业的目标<Polya如何解决问题简单类型与组合类型复合数据结构查找与排序算法算法复杂度......