遵义模拟赛Day2

· · 个人记录

T1 Chino and Paper

结论题，直接输出 n \times m -1 即可，注意数据范围 n,m \leq 10^9 ，要开long long

T2 Coin game

一道非常有意思的题目，只需要判断开局能不能在正中央放下一枚硬币，如果不能放下则是LMJ胜利，否则对手怎么下Aegir只需要对称下，必胜

T3 LanrTabe Loves Binary

对于 40\% 的数据，考虑直接算出每一个 a_i 然后用 lowbit 统计累加就行， 时间复杂度 O(64n)

对于 100\% 的数据，考虑预处理 2^{16} 以内的 f_i ,每次将 a_i 在二进制下分为四个部分，每个部分 16 位，然后用预处理的 f_i 在 O(1) 内统计累加即可，时间复杂度可以降至 O(4n)

T4 -Past 过去之时-

题目求在 [1,n] 内找出有几个三元组 \{a,b,c\}(a \leq b \leq c) 满足 \sqrt a + \sqrt b = \sqrt c

可以将等式 \sqrt a + \sqrt b = \sqrt c 化为

a+b+2 \sqrt {ab} = c

由于 a,b,c 均为正整数，所以当 ab 为完全平方数时等式才有可能成立

对于 50\% 的数据，考虑预处理 f_i 为 i^2 ,由于 a+b+2\sqrt {ab} 小于 n ，根据基本不等式 a+b \geq 2 \sqrt{ab} ，有 4 \sqrt{ab}\leq n ，所以 f_i 只需要处理到 \frac {n}{4} ，然后再对于 f_i ,i \in [1,\frac{n}{4}] ，枚举因子 a,b ，判断 a+b+2\sqrt{ab} 是否小于 n ，统计答案即可，时间复杂度为 O(\frac{n^2}{4})

对于 100\% 的数据，不会，但是下发的 solution 说是把枚举 ab 的因子转化为找 \sqrt {ab} 的因子，回头再研究研究

总结

本次模拟赛除了第一题签到题外，后面三道题均有一定的思维难度，但是每道题都有一定的朴素算法分数可拿，本次比赛最大失误是忽略了 T1 的数据范围，没有开long long导致的失分，丢掉的 70pts 当作教训，今后每次模拟赛一定注意数据范围

赛时估分: 100pts+30pts+40pts+50pts=240pts

实际分数: 30pts+10pts+40pts+50pts=130pts

赛后vp分数: 100pts+100pts+100pts+50pts=350pts