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);
			}
    	}

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

省赛 & TCO2C 后有感

今年的省赛算是毫无悬念地夺冠了。
但是感觉猛犸只要配上一个外语好的妹子帮他看题,也是可以夺冠的……
整个流程中只有我的G题稍微显得有点慢,其它的基本都是秒杀。
其实这种分类比较复杂,不容易想清楚的dp我写得比较慢已经是一种常态了。
一直想知道为什么,直到今晚TCO2C 550惨跪以后,好像明白了一点点。
主要原因我觉得有以下两个

  1. 对于相似的转移经常是硬写,并且即使是相似的转移,写到一半也会停下来重复思考这个地方怎么写。也就是不擅于处理类似的东西。所谓的以力破巧么……解决这种相似问题的转移无外乎那么几种方法:

    1. Ctrl-c, Ctrl-v
    2. 写一个函数来处理这些类似的地方(代码重用)
    3. 直接用参数表示那几种相似但不同的情况,然后通过统一的带参数的计算处理

    第一种无疑是最SB的……但是有时候也还是挺有效的。可是万一写错,就是一个个改……实在有点蠢……而且有一些差别容易忘了改掉。
    第二种是比较oop的做法,只要设计好接口。但是这样整体的case划分框架还是得弄出来,但是比第一种好多了,也比较容易让人接受。
    第三种是最神的,首先得清楚地了解哪些状态可以通过参数合并,然后再设计好对应的参数,不想清楚选这种简直是找死……(详情可以参看shi哥ZOJ3466的代码……不知道shi哥是事后看到类似的把代码缩在一起还是写之前就想到这样了-.-)
    而我发现自己很难做到第三种,大概是因为我在写代码前,根本没有做到完全想清楚每一个转移怎么搞。还有一个原因可能是不太擅于对相似的事物找出共同点并归类。
    这种感觉和看functional programming的感觉有点类似,要具备能迅速反应出a其实是b的能力才会比较舒服。

  2. 在写之前这个程序长什么样往往还没有规划好。写一半又犹豫,写一半又犹豫,其实这才是最费时的。

第一个似乎也没什么特别有效的解决方法,碰到类似的问题在AC后注意精炼一下代码也许是个不错的注意。
第二个强迫自己写之前想清楚,而不是只把一个粗略的流程想出来以后马上就开始写。虽然这很多时候有点难度,但是感觉注意一下的话,这种能力总是会提高的吧……