250. HyperKnight
Brief description:
。。问在一个 (n, m) 的棋盘中。。一个步长为 (a, b) 的 Knight。。合法移动方案为 k 步的格子有多少个。
Analysis:
一图流。。。
#define f8 ((n - 2 * a) * (m - 2 * a))
#define f6 ( ((n - 2 * a) + (m - 2 * a)) * ((a - b) * 2) )
#define f2 ( b * b * 4)
#define f3 ( b * (a - b) * 8 )
#define f4 n*m - f8 - f6 - f2 - f3
class HyperKnight {
public:
long long countCells(LL a, LL b, LL n, LL m, int k) {
if (a < b) swap(a, b);
if (n < m) swap(n, m);
if (k == 8) return f8;
else if (k == 6) return f6;
else if (k == 4) return f4;
else if (k == 3) return f3;
else if (k == 2) return f2;
return 0;
}
};
500. HatRack
Brief description:
。大概就是固定边。。问合法的完全二叉树方案有多少种。。。
Analysis:
。。。比赛时我错误的认为我可以通过组合乱搞搞过去。。结果 fst 成傻逼。。
其实直接枚举根后接记忆化搜索不是很无脑么？！。求放过ww。。。
const int N = 52;
VI adj[N]; LL dp[N][N];
int n;
#define lx (x<<1)
#define rx (lx|1)
LL f(int u, int p = 0, int x = 1){
if (x > n) return 0;
LL &res = dp[u][x]; if (res == -1){
res = 0; VI c; REP(i, SZ(adj[u])) if (adj[u][i] != p) c.PB(adj[u][i]);
if (x>n/2) res = !SZ(c); // suppose to be a leaf ...
else if (!(n&1) && x==n/2) res = SZ(c) == 1; // suppose to have one child .. .
else if (SZ(c) == 2){
res = f(c[0],u,lx)*f(c[1],u,rx) + f(c[1],u,lx)*f(c[0],u,rx);
}
}
return res;
}
class HatRack {
public:
long long countWays(vector <int> knob1, vector <int> knob2) {
n = SZ(knob1) + 1; REP_1(i, n) CLR(adj[i]);
REP(i, SZ(knob1)){
int x = knob1[i], y = knob2[i];
adj[x].PB(y), adj[y].PB(x);
}
LL res = 0; REP_1(i, n){
FLC(dp, -1);
res += f(i);
}
return res;
}
};
f(u, p, x) 表示，当前在 u 结点。父亲是 p。。在完全二叉树的编号是 x 时的方案数。
https://gist.github.com/lychees/6461529
500. CircusTents
Brief description:
。。给定一组圆，找出第一个上的一点。。。。
。。使得这个点到其他圆的距离最大。。。点到圆的集合的距离定义为到集合中最近的圆的距离。。
。。求这个距离。。。
Analysis:
。。。首先来分析一个圆的情况。。
。。一图流。。
。。首先点到圆的距离就是连心线的长度减去半径。。。如果连心线不被遮挡的话那么就是这个。。。否则的话。。要先从圆后后绕一段弧。。
。。。总之也就是这两种情况而已。！！。。。不管我们后面是二分还是三分。。。这个子函数都要先写上。。。。。
。。。为了写的爽。。。。先把第一个圆圆心移动到原点。。。其他圆的圆心通通旋转到 x 轴上。。。并记录旋转角 a。分水岭角为 p。。。
struct Circle{
Po o; DB r, a, p; // 初始旋转角、分水岭角
Circle(cPo o=Po(),DB r=0):o(o),r(r){}
DB d(DB x){
if (x < p) return dist(R*Po(cos(x), sin(x)), o) - r;
return R*(x-p) + sqrt(o.len2() - sqr(R)) - r;
}
} C[N];
。。下面考虑多圆情况。。
。。。。多圆情况似乎非常恶心。。因为很可能被各种遮挡。。。但是实际上一旦要发生遮挡。。那么这个圆肯定不是关键圆。。忽略都行ww。。。。
算法一：二分
。。首先二分答案。。然后对于每个圆可以得到一个弧度区间。。我们知道d() 函数具有单调性。。所以二分得到每个圆对应的区间。。。之后跑扫描线看交集是否为空。。
。。因为 atan2() 的返回区间是 (-PI, PI]。。。所以我通常喜欢把弧度映射到这个区间。。。注意得到的弧度是从 (PI+l -> PI-l)。。别忘了加上开始的旋转。。
。。PI 反正大家都有。干脆去掉。。。最终加入的区间就是 (a+l -> a-l)。。。
https://gist.github.com/lychees/6460116#file-1-cpp
算法二：三分
。。这个题。。。小区间枚举直接三分好像也能过。。。。大概因为d() 函数凸性比较强。。 /$:^ ^
https://gist.github.com/lychees/6460116#file-2-cpp
