某岛

… : "…アッカリ~ン . .. . " .. .
July 4, 2012

SRM 484

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