![2023年9月30日模拟赛](/img/20231001204946.jpg)
2023年9月30日模拟赛
![](https://picx.zhimg.com/v2-9e83e1fd23eccdb98450679841a3a4bc_xll.jpg)
[[数论]] [[计数]] [[并查集 ]] [[Hall 定理]]
前情提要
喜报:CSP-S 89分顺利通过初赛!
今天的题目又是思维题。
题解代码都很短。
显得我很蒻薙。
题解
T1
这个题我是真的喜欢。
简单而巧妙。经过一些观察可以发现要倒着来,如果正着的话后面就是
这个函数满足一个像对数函数一样的性质,可以把乘法转换为加法,就能引出下面的思考了。
还能发现前缀 gcd 的一个性质,前面的是后面的倍数。可以发现倒着贪心有正贡献就行,可以画一个前缀乘数的阶梯图来理解(每一个乘数代表其函数值,最后是加起来)。
然后简单用线性筛求一下,质因数求一下就over。
T2
我现在发现有个问题,经常读题不仔细,太浮躁了捏。比如说就没有看到逐步移动,导致我只写了 sp = 1
的情况,后来发现我所想的就是正解的思路。
后来改正解,发现还是有很多细节的。比如说在树上 dfs 时候求时间要注意,最后求答案也要注意取舍,有时候时间相等的情况也是可行的。
T3
这道题做出来啦。我发现我现在相对擅长计数题。这道题也给了我们一个启发,有时候求一个范围内的情况的时候会很复杂,但是如果去求补集就可能会很简单。
T4
这道题有一点难度,现在也只是相对理解。
对于一种度数分配我们可以求出最大匹配的上限,也可以根据 hall 定理求出下限,并且这其中的值都能取到。
因此只要找到一个 S 和对应的 N(S) 使得
只需要最小值和最大值满足和 l,r 的对应关系即可。
然后就可以用背包(dp),这是怎么想到背包的我也不太理解。
大概是因为一个确定的 S 的大小和对应的 N(S) 的大小和
但是 dp 的时候不能只有这两个值,不然无法确定情况,还需要有:已经讨论过的点数,有度的点数,已用去的边,S 的大小,sum(S) 的大小。这样就可以有转移方程了,最后再转化成只有 S 和 sum(S),的背包就行。
很巧妙啊!
暴力的话,直接暴力连边情况然后求最大匹配即可。
后记
前路漫漫,未来可期!
- 标题: 2023年9月30日模拟赛
- 作者: 混氏新子
- 创建于 : 2023-10-01 19:56:38
- 更新于 : 2023-10-02 20:05:46
- 链接: https://blog.huasushis.cn/2023/2023年9月30日模拟赛/
- 版权声明: 本文章采用 CC BY-NC-SA 4.0 进行许可。