标签存档：Topcoder

难得踩楼爷啊……

 

250

直接辗转相减法，把所有中途的pair放进set，查一查就出来了。

500

给n个元素，每个元素都包含m个关键字的value，再给一个排序后的结果，问是否存在一种对关键字重要程度的排序，使得按多关键字排序这n个元素以后，得到某个给定的顺序。

按重要到不重要的顺序贪心取这个关键字。正确性的关键在于，如果有两个关键字当前都可以取，那么取了其中一个以后，另一个在之后任意时刻都是可以取的。

800

01域下的高斯消元求方案数。直接算秩，2^(元素个数-秩)就是答案。当然还要小心无解的情况。

250

三次方枚举卡住左方，下方，以及右方/上方，再一个for计算矩形内的点，n^4暴力。

其实枚举前两个之后，每个点要求的len是固定的，按这个sort能达到n^3 lg n的复杂度。

525

这题比赛的时候没有过是很不应该的……就是一个很典型的dp。回忆一下这场SRM的过程，总结了一下为什么写这种计数自己经常会写但写得很慢。得出以下几点：

1. 我想的过程中，经常会陷入局部情况或者说特例的求解，这样弄得最后整个代码就非常混乱，往往写出很多种情况，而这会极大的降低编码的效率。
2. 组合计数问题，对独立的步骤进行划分是尤为重要的。而不同情况下每个步骤的操作都是类似的。把类似的过程统一处理往往能得到事半功倍的效果。
3. 总得来看，其实这是architecture上的失败和大局观上的失败。

既然意识到了这个问题，那就在以后练习/比赛的时候注意提高吧。

算法大致是分小环和大环dp。

小环通过一个函数统一处理：count(int x, int y, int n, bool o)。这个函数返回的是，在小环上，一个接口在x号点，另一个接口在y号点，整个环的人数是n，x接口和y接口的颜色是否相等时的方案数。这个conut可以通过递推进行预处理(只和两条独立的链有关)。

然后在大环上，用g[i][j]表示处理完前i个小环，给下面的接口的颜色和“第0个环给第n-1个环的颜色”是否相等。再次递推。

最后输出g[n-1][0]即可。

代码

1000

这题就是给定N, M, goalX, goalY求下面这个函数……

1. 当i = goalX, j = goalY, f(i, j) = 0
2. 其他情况 f(i, j) = (f((i + 1) % N, j) + f(i, (j + 1) % M)) / 2 + 1

输出f(0, 0)即可。

规模有100，迭代是可行的一个做法。

但是这样的迭代是过不了的……

        clr(f, 0);
        rep (it, 10000) {
            rep (i, N) rep (j, M) {
                if (i != goalX || j != goalY) {
                    int ni = (i + 1) % N, nj = (j + 1) % M;
                    f[i][j] = 1 + (f[ni][j] + f[i][nj]) / 2;
                }
            }
        }

这是因为顺序不科学导致的……因为(goalX, goalY)才是不动点，这样盲目地走看上去就很悲剧。
假设现在我在goalX, goalY，那么我影响到的路线应当是沿着-1方向过来的。
所以改成下面这样迭代顺序就过了。

        clr(f, 0);
        rep (it, 10000) {
            rep (_i, N) rep (_j, M) {
                int i = goalX - _i, j = goalY - _j;
                if (i < 0) i += N;
                if (j < 0) j += M;
                if (i != goalX || j != goalY) {
                    int ni = (i + 1) % N, nj = (j + 1) % M;
                    f[i][j] = 1 + (f[ni][j] + f[i][nj]) / 2;
                }
            }
        }

除了迭代以外，对于这种互相依赖的关系，迭代矩阵的又是满秩的，高斯消元解方程也是一个选择。那么假设M+N-1个未知量，其中M个在同一行，N个在同一列(为了方便，最好把不动点放在交错的位置)。这样其它的所有函数值都可以表示为这N+M-1个未知量的线性组合。绕了一圈一个，就可以得到M+N级别个方程，而M+N只有200，高斯消元是没有压力的。

但是zYc大师说好像有问题，等下写个代码看看能不能过。

更新
这个高斯消元算法是可以AC的。
代码在此

250

枚举分隔的位置，左边的一起向左，右边的一起向右。统计答案即可。

500

看了WJMZBMR的代码才明白过来T_T，容斥太弱了。算出区间内每个数包含的素因子。然后因为要gcd变为1，所以可以看成不能包含素因子Pi这若干个条件的与。接着就可以用容斥原理了。

900

看了芒果的代码才明白过来。首先是不能一行一行来填，这样dp的状态太难表示。

然后考虑一列一列来填。

1. 假如只有left的话，就可以f[i][j]来表示填好前i列，其中有j列还没分配的时候的方案数。然后这个j其实蕴含了前面有j列是要填东西的，但是还没决定填在哪些行这么个意思。然后遇到left的结束端点，就可以拿这些数目去分配。大致就是乘个A几几的组合数。
2. 现在如果有right的话，可以按left反过来那样处理，但是现在要统一起来，只能考虑从左往右填。由于一个行进入可填范围就不会变没了，所以f[i][j]表示填好前i列，还有j行没搞定。于是每次可以选择(或者不选)一个行，用当前列来填上。
3. 最后把前两种dp合起来，f[i][j][k]转移一下就好了。