Brief description:
Problem 250. RabbitNumber (兔子数 …
问 [l, r] 区间内 “兔子数” 的数字有多少。
兔子数为满足 S(x^2) = S(x)^2 的数字, 这里 S(x) 为 x 的数位和。
( .. . 1 <= l, r <= 10^9 .. )
Problem 550. PuyoPuyo
一个堆栈, 可以往里面放 4 种颜色的球，当栈顶连续 L 个球颜色相同时，消去这 L 个球。
问往里面放 n 个球的话有多少种放法使得栈空。
( . ..n <= 1000, L <=10 .. .)
Problem 950. NumberMagic (猜数游戏。。
Taro 在心中想了一个 1～n 之间的数字 x，Hanako 每次可以询问一个 m 大小的集合。
Taro 返回 x 在 / 不在 其中。。。问至少多少次询问一定可以猜出这个数。
Analysis:
Problem 250. RabbitNumber
。貌似暴力 DFS() 可过。。
( 可以推出兔子数就是满足 x^2 不产生进位的数。。(。。反证立得。。一旦产生进位则必然有所损耗。。。
( 则每一位只能是 [0, 3] 。。并且前缀一定也是兔子数。。。
Problem 550. PuyoPuyo
略。( dp[i][j] 为当前使用了 i 个球, 还需要 j 个球才能彻底消完的方案数。。。
Problem 950. NumberMagic (猜数游戏。。
要一定能猜出这个数，则在所有询问中，某两个数不能总是作为一个整体出现（否则无法区分开。。
。。也就是对任意的 i, j，都有 {Si} 不同于 {Sj} 。。。（ {Si} 表示包含 i 的询问集合。。
设 f(n, m) 表示所求函数。。
… 然后这个题很容易让人往不对的地方想 。。。
确实也可以得到一些性质。。例如
f(n, m) = f(n, n – m)。（因而该函数类似组合数。是对称的、单峰的、不过是凹的。。
f(2^k, 2^(k-1)) = k 。
甚至还有在 m 等于某些固定的值时，能分析出解。。。
但是这些方法都不能应用到一般情况。。。
int f(LL x){
int s = 0;
while (x) s += x%10, x/=10;
return s;
}
class RabbitNumber{
public:
int L, R, res;
void dfs(LL x, LL s){
if (s > 14 || x > 1e9) return;
if (L<=x && x<=R)
if (s*s==f(x*x)) res++;
for (int i=0;i<4;i++)
dfs(x*10+i, s+i);
}
int theCount(int l, int r){
L = l, R = r, res = 0; if (R==1e9) res++, R--;
for (int i=1;i<4;i++) dfs(i, i);
return res;
}
};
const int N = 1009, M = 10009;
int dp[N][N];
class PuyoPuyo {
public:
int theCount(int l, int n) {
RST(dp), dp[0][0] = 1; REP(i, n) {
INC(dp[i+1][l-1], pdt(4, dp[i][0]));
REP_1(j, min(n-i, (l-1) * i)){
INC(dp[i+1][j-1], dp[i][j]);
INC(dp[i+1][j+(l-1)], pdt(3, dp[i][j]));
}
}
return dp[n][0];
}
};
.. .
int n, m;
LL C(int n, int m){
LL res = 1; REP_1(i, m) res *= (n - i + 1), res /= i;
return res;
}
bool check(int k){
LL r = (LL) m * k; int n = ::n, t;
for (int i=0;i<=k&&n&&r>=0;++i){
t = min(C(k, i), (LL) n);
n -= t, r -= (LL) i * t;
}
return r >= 0 && n == 0;
}
class NumberMagic {
public:
int theMin(int n, int m) {
m = min(m, n - m), ::n = n, ::m = m;
int l = 0, r = n - 1;
while (l < r){
int k = (l + r) >> 1;
if (check(k)) r = k;
else l = k + 1;
}
return l;
}
};
嘛。。总之还是看题解和程序重新理思路了吧。。
最关键的地方在于先 Ban 掉 m 这个 restriction。。。
要点是注意到以下引理：
If it is possible to place a total of M*K numbers on K cards in a way that satisfies the original condition, it is possible to place exactly M numbers on each of K cards in a way that satisfies the original condition.
如果可以总共在 k 次询问中，共包含 m*k 个数，则可以在这 k 次询问中，每次询问恰好 m 个数。。（。。。
之后就是考虑验证答案的函数 bool check(k); 了。。
。下面给出构造方案。。（ k 太小的话构造不出满足条件的解。。
依次枚举有多少个数字，在询问中出现了恰好 i 次
。。考虑到 “用料最省” 的原则。。（同时又要满足最开始所述的条件。。。
。。0 次 的只能有 1 个数字。。（如果有 2 个则无法区分开。。
。。1 次 的只能有 k 个数字。。（每张牌占一个。。
。。2 次 的只能有 C(k, 2) 个数字。。。。（。。同理。。
。。。。。
。。K 次 的只能有 C(k, k) 个数字。。。
当然注意到对后面一组的组合项的求和中间会超过 N 的问题。。。
同时存在一种对称的构造。。。既。。
。。K 次 的只能有 1 个数字。。（如果有 2 个则无法区分开。。
。。K-1 次 的只能有 k 个数字。。（每张牌占一个。。
。。K-2 次 的只能有 C(k, 2) 个数字。。。。（。。同理。。
。。。。。
。。0 次 的只能有 C(k, k) 个数字。。。
注意到如果中间没有发生超过 N 的事件。。也就是 N = 2^k 次方的话。。
这两种构造出来的 1 的个数是一样多的。。。
这两种构造是对称的。。知道其中一个的结果。。另一个可以用 nk 相减得到。。
（。化简后。。逻辑上理解即取反。。。
于是对任意的 k 将会得到一个 minT 和 maxT。。。
以下又产生了一些问题。。
是否所以 minT ~ maxT 之间的数都可以构造出。。
。这个区间是否可以包含 mk。。。
（。。证明不能。。
前面所说的 f(2^k, 2^(k-1)) = k 。。这种。。
就是 minT = maxT 的情况 。。（。。而且这个值恰好是 mk 。。。
External link:
http://www.hhanger.com/?p=675
http://apps.topcoder.com/wiki/display/tc/SRM+484
