srm-775.md

Topcoder SRM 775

• IterateOverACube
• CardDrawGame
• FairSplit

IterateOverACube

题意：考虑如下的伪代码，给出$N$和$index$，求出第$index$次访问的点的坐标：

for sum = 0 .. 3*N-3:
    for x = 0 .. N-1:
        for y = 0 .. N-1:
            for z = 0 .. N-1:
                if x+y+z == sum:
                    visit (x,y,z)

$1 \le N \le 10^6, 0 \le index \le N^3-1$

题解：先二分下$sum$，求出$x+y+z$的和，之后枚举$x$，求出$y$和$z$即可。

CardDrawGame

题意：有$n$种牌，第$i$种有$count_i$个($0 \le i < n$)。考虑如下过程：

• 把所有牌随机洗牌

• 拿出最上面三张

• 选择丢掉任意张，也可以选择不丢

• 然后从牌堆中补牌，直到手中有三张牌

• 如果手中三张牌之和是$target$，你有就赢了，否则你就输了。

如果你从空牌堆里补牌，也算输。求最优策略下，你赢的概率。

$0 \le target \le 50, 1 \le n \le 20, 0 \le count_i \le 100$

题解：直接枚举前三张牌，然后算出丢掉一些牌后获胜的概率即可。

FairSplit

题意：一对$(A, B)$ ($A \le B$)是好的，当且仅当可以把${A, A+1, \dots, B}$分成两个和一样的非空不相交集合。给出$loA, hiA, loB, hiB$，求出有多少$(A, B)$满足$loA \le A \le hiA, loB \le B \le hiB$，是好的。

$1 \le loA \le hiA \le 2 \times 10^9, 1 \le loB \le hiB \le 2 \times 10^9$

题解：首先可以发现一个必要条件是$(A+B)(B-A+1) \equiv 0 \pmod 4$。但是有反例，比如$A=7,B=9$，虽然满足条件，但是不合法。

令$n=B-A+1$，我们发现当$n$是偶数的时候，总是可行的。当$n$是奇数的时候，如果$(\frac{n-1}{2})^2 < A$，是不可行的。

道理是这样的，如果我们分成前$\frac{n+1}{2}$小的数$X$和后$\frac{n-1}{2}$大的数$Y$，如果$X$的和都已经大于$Y$的和了，我们没法做出调整。

计算就很简单，枚举$a$和$b$，使得$A \equiv a \pmod 4$和$B \equiv b \pmod 4$。可以快速算出总得$(A,B)$的个数。之后枚举$n$，去掉非法的即可。