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

Posted by xiaodao
Category: TopCoder