某島

… : "…アッカリ~ン . .. . " .. .
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