// CF比赛链接：http://codeforces.com/gym/101650
// POJ链接：http://poj.org/searchproblem?field=source&key=Northeastern+Europe+2006，POJ3379 ~ POJ3389
// Day12 暑训第一阶段最后一场组队赛
// 区域赛难度，表现还可以，前期互相推锅，后半场自闭O.O
B - Bridges
题目大意：
n个地区之间有n-1条道路，两两之间只有一条路径（说明是一个树结构）。初始的道路只有马能走，需要修建k个桥能让车通过，给定马速sh与车速sc，以及地图信息，为了使任意两节点之间所花时间减少最多，求修建k座桥的标号。
分析及代码：
很水的，很容易发现树上每条边走过的次数为两端点子树的总节点个数相乘，要使减少时间最大化，显然应直接选择边长*次数最大的边。
然而测试数据有坑，车速可能比马速还要小，就老老实实算减少时间，排序后选最大的吧。。。
AC代码采取了树上dfs的两种写法：
#include<iostream> #include<cstdio> #include<cstring> #include<queue> #include<vector> #include<algorithm> using namespace std; typedef long long ll; const int maxn = 10100; struct Edge { int to, id, next; double w; }edges[maxn*2]; int head[maxn*2], tot; int n, k, sh, sc; void addEdge(int u, int v, double w, int id) { edges[tot].to = v; edges[tot].w = w/sh - w/sc; // 只记录边长会WA，还是按照题意算减少时间吧 edges[tot].id = id; edges[tot].next = head[u]; head[u] = tot++; } struct node { int id; double w; node (int _id, double _w):id(_id), w(_w) {} bool operator<(const node& a)const { return w<a.w; // 重载小于号，默认大顶堆 } }; priority_queue<node> ans; int cnt; void dfs(int u, int fa) { ++cnt; for(int i=head[u];~i;i=edges[i].next) { int v = edges[i].to; if(v!=fa) { int no = cnt; //cout<<v<<endl; dfs(v, u); //edges[i].w *= (ll)(cnt-no)*(n-(cnt-no)); int son = cnt - no; // cnt已更新到叶子节点，两者差为以v节点为根的子树节点总个数 double times = (son+0.0) * (n - son); ans.push(node(edges[i].id, times*edges[i].w)); //printf("%d->%d:%d ", u, v, w); } } } int main() { cin>>n>>k>>sh>>sc; memset(head, -1, sizeof(head)); for(int i=1;i<n;i++) { int u, v, l; scanf("%d %d %d", &u, &v, &l); addEdge(u, v, l, i); addEdge(v, u, l, i); } cnt = 0; dfs(1, -1); for(int i=1;i<=k;i++) { printf("%d%c", ans.top().id, i==k?' ':' '); ans.pop(); } return 0; }
#include<iostream> #include<cstdio> #include<cstring> #include<queue> #include<vector> #include<algorithm> using namespace std; typedef long long ll; const int maxn = 10100; struct Edge { int to, id, next; double w; }edges[maxn*2]; int head[maxn*2], tot; int n, k, sh, sc; void addEdge(int u, int v, double w, int id) { edges[tot].to = v; edges[tot].w = w; edges[tot].id = id; edges[tot].next = head[u]; head[u] = tot++; } struct node { int id; double w; node (int _id, double _w):id(_id), w(_w) {} bool operator<(const node& a)const { return w>a.w; } }; vector<node> ans; bool vis[maxn]; int cnt; void dfs(int u) { vis[u] = 1; ++cnt; for(int i=head[u];~i;i=edges[i].next) { int v = edges[i].to; if(!vis[v]) { int no = cnt; //cout<<v<<endl; dfs(v); //edges[i].w *= (ll)(cnt-no)*(n-(cnt-no)); int son = cnt - no; double times = (son+0.0) * (n - son); ans.push_back(node(edges[i].id, times*edges[i].w)); //printf("%d->%d:%d ", u, v, w); } } } int main() { cin>>n>>k>>sh>>sc; memset(head, -1, sizeof(head)); for(int i=1;i<n;i++) { int u, v, l; scanf("%d %d %d", &u, &v, &l); addEdge(u, v, l, i); addEdge(v, u, l, i); } cnt = 0; dfs(1); sort(ans.begin(), ans.end()); for(int i=0;i<k;i++) { printf("%d%c", ans[i].id, i==k?' ':' '); } return 0; }
F - Feng Shui
题目大意：
在一块多边形区域铺上两个相同半径的圆形地毯，要使地毯最多与边界相切（不能相交）的情况下，地毯覆盖的面积最大，求两圆心的位置坐标。
分析及代码：
队友分析出，只需要把多边形的每条边往里平移r，得到新的多边形，圆心位置一定在新的多边形端点上，所求圆心为两点之间的距离最长的那两个端点。这样既保证了与边界不相交，求两圆形地毯重叠最少，所以覆盖面积最大。
比赛抄了部分模板，一直WAWA大哭，自闭到比赛结束。
赛后才想到平移之后有的边会消失（移动后的边在多边形外部，如五边形缩小成为了四边形），直接求相邻两边得到新的多边形端点是不对的。
那么该如何修正呢？虽然发现这些边方向会反转，但判断起来太麻烦，因为删去一条边还会影响下一条边。即使算法正确，还需要确定第一条一定相切的边，否则也可能是要删去的边。
其实这题就是半平面交的裸题。
附上计算几何模板+AC代码：（把点乘敲错让我debug了一下午。。。）
#include<cstdio> #include<iostream> #include<vector> #include<cmath> using namespace std; // ***********************模板开始**************************** struct Point { double x, y; Point (double xx=0, double yy=0):x(xx), y(yy) {} }; typedef Point Vector; typedef vector<Point> Polygon; Vector operator+(Point A, Vector B) { return Vector(A.x+B.x, A.y+B.y); } Vector operator-(Point A, Vector B) { return Vector(A.x-B.x, A.y-B.y); } Vector operator*(Vector A, double t) { return Vector(A.x*t, A.y*t); } // 向量叉乘 double cross(Vector A, Vector B) { return A.x*B.y - A.y*B.x; } // 向量点乘 double dot(Vector A, Vector B) { return A.x*B.x + A.y*B.y; } // 与0比较函数 const double eps = 1e-10; int dcmp(double x) { if(fabs(x)<eps) return 0; return x<0? -1:1; } // p是否在线段AB上 bool onSegment(Point p, Point A, Point B) { // 包含端点 return dcmp(cross(A-p, B-p))==0 && dcmp(dot(A-p, B-p))<=0; } // 两直线交点 Point crossPoint(Point P, Vector v, Point Q, Vector w) { Vector u = P-Q; double t = cross(w, u)/cross(v, w); return P+v*t; } // 半平面交模板，直线AB切割多边形poly，返回左侧部分 Polygon cutPolygon(Polygon poly, Point A, Point B, int k) { Polygon newpoly; int n = poly.size(); for(int i=0;i<n;i++) { Point C = poly[i]; Point D = poly[(i+1)%n]; if(dcmp(cross(B-A, C-A))>=0) newpoly.push_back(C); if(dcmp(cross(B-A, C-D))!=0) { // C-D与A-B不平行 Point ip = crossPoint(A, B-A, C, D-C); if(onSegment(ip, C, D)) newpoly.push_back(ip); } } return newpoly; } // ***********************模板结束**************************** Point p[110]; // AB距离 double dis(Point A, Point B) { double x = A.x - B.x; double y = A.y - B.y; double res = x*x + y*y; return sqrt(res); } Polygon init(int n) { Polygon poly; for(int i=0;i<n;i++) { poly.push_back(p[i]); } return poly; } int main() { int n; double x, y, r; cin>>n>>r; for(int i=n-1;i>=0;i--) { scanf("%lf %lf", &x, &y); p[i].x = x; p[i].y = y; } p[n] = p[0]; Polygon poly = init(n); for(int i=0;i<n;i++) { double len = dis(p[i], p[i+1]); double dx = p[i+1].x - p[i].x; double dy = p[i+1].y - p[i].y; Point A = Point(p[i].x - r*dy/len, p[i].y + r*dx/len); Point B = Point(p[i+1].x - r*dy/len, p[i+1].y + r*dx/len); poly = cutPolygon(poly, A, B, i); } double ans = 0; int p1 = -1, p2 = -1; for(int i=0;i<poly.size();i++) { for(int j=i+1;j<poly.size();j++) { if(ans<dis(poly[i], poly[j])) { p1 = i; p2 =j; ans = dis(poly[i], poly[j]); } } } if(p1!=-1) { printf("%.5lf %.5lf %.5lf %.5lf ", poly[p1].x, poly[p1].y, poly[p2].x, poly[p2].y); } else { // 缩成一个点，两圆重合 printf("%.5lf %.5lf %.5lf %.5lf ", poly[0].x, poly[0].y, poly[0].x, poly[0].y); } return 0; }
G - Genealogy
题目大意：
给你一个家谱图组成的树，要使每个家庭成员的儿子节点不超过d个且不改变祖先-子孙关系，求最少需要加入几个节点。
分析及代码：
翻译成数据结构的语言，本题就是n-叉树的转化问题。
直接记录每个节点儿子的数量，然后计算有超过d个儿子的节点经过变换需要添加的节点个数即可。
AC代码就是不断把d个儿子连上新的节点，并作为新的儿子，直到新的儿子总个数小于等于d（注意不是1啊，让我16组T了！）
四行代码就够了：
int res = 0;
while(k>d) {
res += k/d;
k = k/d + k%d;
}
AC代码：
#include<cstdio> #include<iostream> using namespace std; int n, d; int son[100100]; int cal(int k) { int res = 0; while(k>d) { res += k/d; k = k/d + k%d; // cout<<k<<endl; } return res; } int main() { //while(cin>>n>>d) cout<<cal(n)<<endl; cin>>n>>d; for(int i=1;i<=n;i++) { int u; scanf("%d", &u); son[u]++; } int ans=0; for(int i=0;i<=n;i++) { if(son[i]>d) { ans += cal(son[i]); } } cout<<ans<<endl; return 0; }
（未完待续）