SRM 614

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的。
代码在此

发表评论

电子邮件地址不会被公开。