SRM 620

难得踩楼爷啊……
屏幕快照 2014-05-11 下午1.31.24

 

250

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

500

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

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

800

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

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

SRM 613

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]转移一下就好了。

SRM 577

250pt
略,小心写就好。

500pt

给一个8 * 8的方格,某些格子为#要填东西。每次填一个格子,cost是已填格子里离本格子Manhattan distance最远的点的Manhattan distance。问填出给定的pattern最少需要的代价。

一个奇怪的技巧,Manhattan distance将坐标旋转45°((x,y) -> (x + y, x – y) ———— 记为(p, q))以后,就从
$$abs(x_1 – x_2) + abs(y_1 – y_2)$$ 变为 $$max(abs(p_1 – p_2), abs(q_1 – q_2))$$
因为从+变成了max,所以可以dp了……因为只需要记录已填区域的minx, maxx, miny, maxy就可以转移。

1000pt

给定一个pattern,某些地方要涂上颜色,每次可以用一横或者一竖将一系列没有被涂过颜色的点涂上色。问最少要涂多少笔。

-_-官方题解的建图看着真是太挫了……
关键就在于要给每个要涂色的点分一个状态Down或Right. 而如果我是Down,下面不是一个为Down的点(没有也不算是),那么ans++,如果我是Right,但右边的点不是Right(没有也不算是),ans++。
所以假设每个格子对应一个点,他被割在S一边表示Down的状态,割在T一边表示Right的状态,那么建边就像这样。

    	rep (i, m) rep (j, n) {
    		if (target[i][j] != '#') continue;
			if (i + 1 < m && target[i + 1][j] == '#') {
				addedge(id[i][j], id[i + 1][j], 1);
			} else {
				addedge(id[i][j], T, 1);
			}
			if (j + 1 < n && target[i][j + 1] == '#') {
				addedge(id[i][j + 1], id[i][j], 1);
			} else {
				addedge(S, id[i][j], 1);
			}
    	}

跑一遍最小割就可以得到答案。

SRM 567

Rating += 52

250
这个题写得圡爆了
因为bitset没有重载<弄了好久,最后直接重写了……搞得只剩100分多一点 太圡了。 本质是找<=n的数里面,分解素因子以后,指数奇偶性mask和自己相同的数的个数。 做法是把指数为奇的那些素数乘起来,然后得到一个最小的指数奇偶性mask和自己相同的数值。然后它可以乘的数就是一些完全平方数了。这个先把完全平方数存在一个vector里面然后lower_bound一下算数目就可以了。 500 先统计出每个字母的数目,如果想字典序最小,一定是aaabbbccc这样把相同的字母排在一起的形式。然后和另外的字符串比较的过程中,肯定都是先比a的数目,相等的话再比b的数目,如此下去…… 于是每次选一个X的拥有数目是最大之一的字母。如果此时,X是唯一一个最大的,那么就符合了,否则继续。 比赛的时候cha得不够果断啊,要不然起手就能cha两个500

int num[55][26];
int used[26];

vector  getWinningStrings(vector  S) {
	vector  ans;
	memset(num, 0, sizeof(num));
	int n = S.size();
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < S[i].size(); j++)
			num[i][S[i][j] - 'a']++;
	}
	for (int i = 0; i < n; i++) {
		bool flag = 0;
		memset(used, 0, sizeof(used));
		vector  vec;
		for (int j = 0; j < n; j++) if (j != i) vec.push_back(j);
		while (!flag) {
			bool found = 0;
			for (int j = 0; j < 26; j++) {
				if (!used[j]) {
					int Max = -1;
					foreach (it, vec)
						if (num[*it][j] > Max) Max = num[*it][j];
					if (Max < num[i][j]) {
						flag = 1;
						found = 1;
						break;
					}
					if (Max == num[i][j]) {
						found = 1;
						used[j] = 1;
						vector  tmp_vec;
						foreach (it, vec) {
							if (num[*it][j] == Max) tmp_vec.push_back(*it);
						}
						vec = tmp_vec;
						break;
					}
				}
			}
			if (!found) break;
		}
		if (flag) ans.push_back(i);
	}
	return ans;
}

1000
从后往前搜索,每次对后面的决策有影响的就是那些山的轮廓线……要注意这个轮廓线高度只可能+1 -1或者不变……所以可以用一个初始高度h0加上一个50位的三进制数表示。
然后用map记忆化搜索就好了。
……至于轮廓线数目为什么很少,我也不是很清楚-.-,但是感觉已经把本质相同的状态都合并了,也没有什么再可以利用的信息的,所以不这么做大概也没法做了。
值得一提的是,似乎用map < vector , int >这样的记忆化方法也可以过……真是好像敢写就敢过……
推荐[[iwi]]的代码
还有练习房里WJMZBMR的无节操hash压状态版本……