Codeforces vp 寄

发布时间 2023-11-10 21:18:10作者: Tx_Lcy

难度标记:

\(\verb!A!\) :傻逼题。
\(\verb!B!\) :看完题解后马上就会了。
\(\verb!C!\) :看完题解后还需要想一会,甚至仍然不会。

+ 和 - 表示在同档题中的难度。

Codeforces Round 694 (Div. 1)

最终 \(\rm performance\) \(2568\),大概在正式选手前 \(140\)

简要题解:

CF1470A($\verb!A-!$)

考虑贪心,显然 \(k_i\) 越大的需要先匹配。

于是排序,能匹配就匹配即可。

\(2 \min\) 就过了。

CF1470B($\verb!A!$)

发现两个数 \(x,y\) 满足 \(\dfrac{\text{lcm}(x,y)}{\text{gcd}(x,y)}\) 是个完全平方的条件是质因子分解后每个质因子的奇偶性相同。

考虑把 \(a_i=\prod p_i^{q_i}\) 改成 \(a_i=\prod p_i^{q_i \bmod 2}\),然后合并同类项,计每种 \(a_i\) 的出现次数为 \(siz_{a_i}\)

发现如果 \(siz_{a_i}\) 是个偶数则会在第一轮以后和 \(0\) 合并。

然后就做完了,判断 \(w\) 是不是 \(0\),然后对应输出就行了。

用时 \(25 \min\),主要是开 \(\verb!long long!\) 被卡常了。

CF1470D($\verb!A!$)