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 作为近似值也是可以过的。。
。。。）
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 出来。。
其实就是下面这 8 种 Pattern …
00 00 01 01 00 11 01 10 10 10 11 11 01 10 00 11
于是这个性质等价于每一行和第一行要么相同要么相反。。。（。。或者说成列满足这个性质也行。。反正满足行的必然也满足列的。。。
。。。于是变成了一个二染色问题。。。。。字典序最小可以通过逐格枚举的方式得到。。
External link:
https://apps.topcoder.com/wiki/display/tc/SRM+587
https://gist.github.com/lychees/6233770
