国庆集训 Day 4
2024 年 10 月 4 日
Status: CLOSED
中间咕了。。
\(\def\EZ{\textcolor{#51af44}{\text{EZ}}}\EZ\) 表示简单，10分钟内就能想到。
\(\def\HD{\textcolor{#3173b3}{\text{HD}}}\HD\) 表示中等，能独立想出
\(\def\IN{\textcolor{#be2d23}{\text{IN}}}\IN\) 表示困难，独立思考能想到 \(50\%\) 以上
\(\def\AT{\textcolor{#383838}{\text{AT}}}\AT\) 表示非常困难，独立思考只能想出 \(50\%\) 以下
Overall
\(\HD\)
| matrix | monster | gcd | sequence | total | |
|---|---|---|---|---|---|
| Score | 100 | 100 | 60 | 20 | 280 |
| Expected | 100 | 100 | 60 | 70 | 330 |
| Ideal | 100 | 100 | 60 | 100 | 360 |
T1. 友矩阵 matrix
\(\EZ\)
容易知道对于每个边长 \((a,b)\) 的矩形，可能成为友矩阵的矩阵右下角只有两个，二维前缀和判定即可。
T2 打怪兽 monster
\(\EZ^{+}\)
考虑一种贪心，令 \(t_i=\frac{a_i}{k-c_i}\)，则把怪兽按照 \(\frac{b_i}{t_i}\) 从大到小排序，该顺序即为杀死怪兽的最优顺序。
思考过程供参考
肯定会集火一一打死，不可能打游击战
总是可以计算出怪兽要打多久才会死
总时间是固定的
这可以转化成 Haffman 树的构造问题
不过，普通的 Haffman 树构造是基于边权都是 1
这个前提，现在就不一定了
但是直观上，应该将又脆攻击力又高的放上面
又厚攻击力又低的放下面
综合考虑，应该把 b_i/t_i 大的放上面
过大样例了！！真是一场酣畅淋漓的赤石啊~
T3 最大公约数 gcd
\(\HD^{+}\)
没做出来，被评价为唐。
由于最大公约数不能重复，且时限有 3s，考虑枚举最大公约数并判定。如何判定？如果求出一个数是多少数的因数，这是好做的（求因数求倍数都可以调和级数/根号做），那么也就求出了一个数是多少对数的公约数，但是怎么才是最大的呢？考虑把什么时候他不是最大的，就是当他的倍数也有这一对的时候，则去掉其倍数的，但是会不会去多了呢？
实际上一个数有这一对，其因数必然也有这一对，即这个值代表最大公约数至少为 x 的数对个数，在此基础上，使用容斥，对于所有 x 的倍数 y，求出最大公约数恰好为 y 的数对数目，减去即可。
T4 序列 sequence
\(\HD^{++}\)
不是，能不能大样例强一点啊。
注意到最多能连续平方/开方 \(\log\log 2^{64}=8\) 次 ，考虑在每个节点上维护一个数组表示这个节点上平方若干次的值，然后维护一个指针指向当前值，平方右移，开方左移，即可避免由于重复执行平方/开方消耗额外复杂度，当指针指向最左边，若还要开方，则进行暴力更新，记录当前点是否已经全部变成 1。
死因：下传标记的时候没有判断左右节点是否全部为 1，过度移动指针，导致询问时错误访问。
标签：text,集训,最大公约数,国庆,EZ,100,textcolor,Day,HD From： https://www.cnblogs.com/haozexu/p/18447159