某島

… : "…アッカリ~ン . .. . " .. .
August 15, 2013

SRM 587

550. TriangleXor

Brief description:

。。。求下圖所示 Pattern 的面積。。

Analysis:

。。。這麼簡單的題都沒過。。。瑪德。。我是 ,b 么?。。。
。。像上圖那樣分三種情況討論。。。。設寬度為 w。。那麼整個矩形的面積也是 w。。。。上面部分顯然是 w/4。。?。。
。。。左邊部分的每個小塊。。就是底邊在左側的相鄰的兩個三角形面積的差。。左側三角形的面積又只和一條對角線和對面的第 ith 條斜線的交點的橫坐標有關。。

。。。而這兩個方程顯然就是。。。就是。。/$:o~o

DB y(int i){return (DB)i/(i+w);}
DB x(int i){return y(i)*w;}

。。。最後底下一堆平行四邊形一行一行的解決就行了。 。。。。。。
。。。(。。。底下圖形的極限。。是 w/8。。。在本題中你取 w/8 作為近似值也是可以過的。。/$:o~o。。。)

DB w;
DB y(int i){return (DB)i/(i+w);}
DB x(int i){return y(i)*w;}

class TriangleXor {
public:
	int theArea(int W) {

        DB res = 0; w = W;

        if (~W&1) res += w/4;

        for (int i=1;i<=W;i+=2){
            res += x(i)-x(i-1);
        }

        //res += w/8;
        for (int i=1;i<=W;i+=2){
            res += (W-2*x(i)) * (y(i+1)-y(i-1))/2;
        }

		return res;
	}
};

900. ThreeColorability

Brief description:

。。。。給定一個邊長為 n*m 的矩形格點。。
。。對每一個小矩形有一個對角線的連接方式。。有些已經確定。。有些沒有。
。。問是否存在一種對角線的連接方案。。。使得格點可以三染色。。如果存在。。輸出字典序最小的解。。。

Analysis:

。。。Div 2 的版本。。只有判定問題。。。
。。。。。只要注意讓所有 2×2 的子格點都合法就行了。。。(必要性顯然。。充分性可以 yy 出來。。/$:o~o

其實就是下面這 8 種 Pattern …

00 00 01 01
00 11 01 10

10 10 11 11
01 10 00 11

於是這個性質等價於每一行和第一行要麼相同要麼相反。。。(。。或者說成列滿足這個性質也行。。反正滿足行的必然也滿足列的。。。
。。。於是變成了一個二染色問題。。/$:o~o。。。字典序最小可以通過逐格枚舉的方式得到。。

External link:

https://apps.topcoder.com/wiki/display/tc/SRM+587
https://gist.github.com/lychees/6233770