金华の第三场模拟赛

无论从rank还是自我感觉，这都是最差的一次。

---

预期：100+100+100+70+80+45=495
实际：100+100+ 80 +40+ 8 + 0 =328
能力范围内的分每次都拿不满（叹气

T1
求\(5^n\), \(n\in[1, 1023]\)
高精乘，签到题
T2
给定一个排列，m次操作（操作1：交换\(a[i]\),\(a[j]\) ； 操作2：交换前k块和后n-k块）求每次操作后的逆序对个数的奇偶性
容易发现操作1会改变奇偶性，操作2仅当n为偶数且k为奇数时会改变奇偶性。
T3
求有恰好X张太阳牌与Y张月亮牌的概率（初始状态1张太阳1张月亮）
场上手玩样例发现式子\(\frac1{(x+y-1)!}\times(x-1)!\times(y-1)!\times\tbinom{x+y-2}{x-1}\)，但是没有想到化简(?什么智障),果然TLE。化简得\(\frac1{(x+y-1)}\)。
T4
一回合一方到达m分结束，已知两方在比赛中共得X、Y分，求比赛可能有多少回合。
是一道“小清新”推式子题，场上虽说也想到了推式子，但推的式子方向错了。设a、b为两方赢得场数，k=a+b，有

\[\begin{cases} \quad am+(m-1)b \geq X \\ \quad bm+(m-1)a \geq Y \end{cases}\]

最后我只得到了

\[\begin{cases} \quad k \leq \lfloor \frac{X}{m} \rfloor+\lfloor \frac{Y}{m} \rfloor \\ \quad k \geq \frac{X+Y}{2m-1} \end{cases}\]

发现不过样例，于是直接枚举了a。没有计入等于的情况，于是40pts。(加上等于后70ptsTLE)
事实上式子应该为

\[\begin{cases} \quad am+(m-1)b \geq X \geq am\\ \quad bm+(m-1)a \geq Y \geq bm \end{cases}\]

也就是说我少了一半的约束条件，不错才怪，可以得到

\[\begin{cases} \quad k \geq \frac{Y-\lfloor \frac{Y}{m} \rfloor}{m-1} \\ \quad k \geq \frac{X-\lfloor \frac{X}{m} \rfloor}{m-1} \end{cases}\]

答案为上下边界相减
T5
给定一个长度为 n 的串 ，包含 01x?: 把 x 替换成 0 或 1 ，求最后所有可能串求出来的值之和
场上写了没有x的部分分，用栈维护，类似普通的加减运算。但是没有注意到三目运算符右结合的性质，循环应该从右往左而不是从左往右。因为这个48->8，挂完了。其实80pts也好拿，直接暴力递归即可。
正解和部分分解法很像，也是用栈模拟，只是多需要维护两个值：val(多少个1)，cnt(可取数量)。
T6
给定整数k，两个序列A和B，x、y、z张不同的牌，求\(A_x\times B_y\times 2^z\)的最大值(x+y+z=k)
这题要高精度，写挂了QnQ。痛失$O(n^2) $暴力的45pts。
正解：注意到，所有 \(z<t−60\) 的方案一定不是最优解，枚举 \(A_x \times B_y\) 的最大值乘上 \(2^z\) 即可