-------------------------------------------------------------------------------
ZOJ 3805 Machine
有 n 个不同的机器，他们之间的生产关系构成一棵二叉树，要求使用管道把它们连接起来完成这个生产线，并使得整体的宽度最小 ，管道只有两种（具体形状参考题目），不能旋转管道。机器的输入和输出口 只有固定的3个位置。
?
简单二叉树遍历
?
#include
#include
#include
#include
#include
#include
#include
-------------------------------------------------------------------------------
ZOJ 3806 Incircle and Circumcircle
给你三角形外接圆和内切圆的半径（R,r），求出一个可行的三角形。
无解的情况(r>R/2)
然后我们能发现等腰三角形就能构造出所有的情况，于是只要算出等腰三角形的情况就好了。
然后二分三角形底边d，比较算出来的内切圆半径r’与r。
?
?
#include
#include
#include
double r, R; double h, x; double cal(double a) { double d = a / 2; h = sqrt(R * R - d * d) + R; x = sqrt(h * h + d * d); return a * x * x / (2 * R * (a + x + x)); } void solve() { double lx = 0, rx = sqrt(3.0) * R; double mid; for (int i = 0; i < 100; i++) { mid = (lx + rx) / 2; double tmp = cal(mid); if (tmp > r) rx = mid; else lx = mid; } cal((lx + rx) / 2); printf(%.10lf %.10lf %.10lf , mid, x, x); } int main() { while (~scanf(%lf%lf, &r, &R)) { if (r * 2 > R) printf(NO Solution! ); else solve(); } return 0; }
用下面的定理也能解出来。。。
欧拉定理(几何):设三角形的外接圆半径为R，内切圆半径为r，外心与内心的距离为d，则d^2=R^2-2Rr．
?
-------------------------------------------------------------------------------
?
ZOJ 3807 Just a Palindrome
给你一个长度最大为 105 的字符串，你可以选择两个位置，然后交换他们，求最长回文子串。
?
hash & SA 不会。。。。
-------------------------------------------------------------------------------
ZOJ 3808 The Sum of Unitary Totient
已知 Φ?(n)=(p1a1?1)(p2a2?1)?(prar?1),n=p1a1p2a2?pkak 。求 ∑Ni=1Φ?(i). n≤ 109
题意简单，可是想不出2s时限内的算法。 呵呵。。。