某島

… : "…アッカリ~ン . .. . " .. .
August 11, 2013

SRM 585

500. LISNumber

Brief description:

… 給定 1 到 n 這些類數,每類數字有 cardsnum[i] 個。。
。。問這些數字所組成的多重集排列中恰好有 K 個 LIS (嚴格)的有多少個。。
( n <= 50, cardsnum[i] <= 50, K <= 1300 )。。

Analysis:

。。。根據數字大小劃分階段,從小到大 DP。。。
狀態只與數字的總數,和 LIS 的段數有關。。而數字的總數容易取得。。。所以狀態只需要記錄 LIS 的段數即可。
. 轉移只有段數加一和不變兩種。。。每個階段。。。需要逐個枚舉當前是第幾次使用這個數字。。(相同的數字可以增加 LIS 段數 + 1 的機會。。。)。。。
。。。然後每個階段結束後需要除以這個排列。。。

        REP(i, n){
            REP(j, cardsnum[i]){
                ++s; swap(p, q); RST(dp[p]);
                REP(k, min(K+1, s)) if (dp[q][k]){
                    int a = max(0, k - j), b = s - a;
                    dp[p][k] += dp[q][k] * a;
                    dp[p][k+1] += dp[q][k] * b;
                }
            }
 
            REP(k, min(K, s)+1) dp[p][k] *= Factt[cardsnum[i]];
        }

1000. EnclosingTriangle

Brief description:

… 給定一個格點正方形。邊長為 m。。。內部有一些點。。。要求在邊上(包括角落)選擇三個點形成一個可以包圍所有內部點的三角形。(可以恰好在邊上)。。
。。問合法三角形的個數。。。
( m<= 58585。。)

Analysis:

。這個題在 Div2 裡邊數變小 (50)。。不能有定點位於同一側。。也不用考慮角落的情況。。所以這要暴力枚舉三個端點。。然後只要不是逐個檢測每個點是否都在三角形內部都可以過。。。。

。。。當我們把每條邊分開來考慮。。就要求。。就是所有黑點都處在這條邊的順時針一側。。。
。。我們把四側邊界上的點按照順序依次排開。。用 mp[i] 記錄每個點最遠可以連的位置。。。這一步可以 two-point。

                int ii = 1; REP(i, n){
		    checkMax(ii, next_side(i) + 1); while (1){
                        int j; REP_N(j, SZ(x)) if (dett(P[i], P[ii%n], Po(x[j], y[j])) > 0) break;
                        if (j == SZ(x)) ++ii; else break;
		    }
		    mp[i] = ii--;
		}

我們設三角型的三個點依次是 a, b, c。。。那麼關鍵的一步就是對於每個 a 。。我們處理出 max_b 和 min_c。。。那麼對於其他所有 b。。答案就是。。mp[b] – min_c + 1。。。
。。注意只有正值的時候我們才計數。。。

於是我們需要一個數據結構。。來支持。。

。。在尾部插入一項 (b, mp[b])。。
。。所有項目 -1。。(min_c 向前移動。)。。
。。刪除隊列前面所有負值項。。。。

。。。我們發現一個帶 offset 的隊列就可以完成所需了。。。

External link:

https://apps.topcoder.com/wiki/display/tc/SRM+585
https://gist.github.com/lychees/6197012