话说这次比赛做的叫一个纠结啊，各种粗心的错误，输入数据搞倒了，数组开的大小搞倒了，纠结死了。哎...粗心啊！！！wa致死才检查出这种粗心的错误。。
hdu4301
题意：
官方是状态压缩dp，我按比率排了个序贪心的选择，险过。
View Code #include#include #include #define maxn 22using namespace std;struct node{ int d,h; double f;}p[maxn];int cmp(node x,node y){ return x.f > y.f;}int main(){ int i,n; while (~scanf("%d",&n)) { for (i = 0; i < n; ++i) { scanf("%d%d",&p[i].d,&p[i].h); p[i].f = (1.0*p[i].d)/p[i].h; } sort(p,p + n,cmp); int t = 0; int ans = 0; for (i = 0; i < n; ++i) { t += p[i].h; ans += (t*p[i].d); } printf("%d\n",ans); } return 0;}
hdu 4311
题意：
给定平面上n个点，求以一个点为中心，所有点到该点的最小曼哈顿距离x1 - x2| + |y1 - y2|.
思路：
给定的n比较大O(n^2)肯定超时，本来我以为二分，但是就是想不来怎么二分。
二官方做法是：
平面上两点间的 Manhattan 距离为 |x1-x2| + |y1-y2|
X 方向的距离与 Y 方向上的距离可以分开来处理。假设我们以 (xi,yi) 作为开会的地点，那么其余的点到该开会地点所需的时间为 X 方向上到 xi 所需要的时间加上 Y 方向上到 yi 所需要的时间。
对数据预处理后可以快速地求出x坐标小于xi的点的个数rankx, 并且这些 x 坐标值之和 sumx，那么这些点 X 方向上对结果的贡献为 rankx * xi - sumx；同理可以处理出 x 坐标大于 xi 的点在 X 方向上对结果的贡献值。同理可求得其余点在 Y 方向上到达 yi 所需要的总时间。
我这里给出自己推的公式
L[i] = i*p[i].x - X[i - 1] + (X[n - 1] - X[i]) - (n - i - 1)*p[i].x;
R[i] = i*p[i].y - Y[i - 1] + (Y[n - 1] - Y[i]) - (n - i - 1)*p[i].y;
L[i]表示以p[i].x为中心点的X上的时间消耗，X[i]表示0 - i的x坐标的和
R[i]表示以p[i].y为中心点的Y上的时间消耗，Y[i]表示0 - i的y坐标的和
View Code #include#include #include #include #include #define maxn 100007#define ll __int64using namespace std;struct node{ ll x,y; int num;//记录原来该点的序号 int numx,numy;//记录该点的x值是按X排序之后的序号,记录该点的y值是按Y排序之后的序号,}p[maxn],tp[maxn];ll X[maxn],Y[maxn];ll L[maxn],R[maxn];int cmp1(node a,node b){ return a.x < b.x;}int cmp2(node a,node b){ return a.y < b.y;}int main(){ //freopen("1.txt","r",stdin); int t,i,n; scanf("%d",&t); while (t--) { scanf("%d",&n); for (i = 0; i < n; ++i) X[i] = Y[i] = L[i] = R[i] = 0; for (i = 0; i < n; ++i) { scanf("%I64d%I64d",&p[i].x,&p[i].y); p[i].num = i; tp[i].x = p[i].x; tp[i].y = p[i].y; } sort(p, p + n,cmp1); //记录该点的x值是按X排序之后的序号 for (i = 0; i < n; ++i) tp[p[i].num].numx = i; X[0] = p[0].x; for (i = 1; i < n; ++i) X[i] = X[i - 1] + p[i].x; L[0] = (X[n - 1] - X[0]) - (n - 1)*p[0].x; for (i = 1; i < n; ++i) L[i] = i*p[i].x - X[i - 1] + (X[n - 1] - X[i]) - (n - i - 1)*p[i].x; sort(p, p + n,cmp2); //记录该点的y值是按Y排序之后的序号 for (i = 0; i < n; ++i) tp[p[i].num].numy = i; Y[0] = p[0].y; for (i = 1; i < n; ++i) Y[i] = Y[i - 1] + p[i].y; R[0] = (Y[n - 1] - Y[0]) - (n - 1)*p[0].y; for (i = 1; i < n; ++i) R[i] = i*p[i].y - Y[i - 1] + (Y[n - 1] - Y[i]) - (n - i - 1)*p[i].y; //求出的L[0 - n - 1] R[0 - n - 1]不是对应的点，所以通过numx，numy来统一成一个点 int l = tp[0].numx; int r = tp[0].numy; ll mi = L[l] + R[r]; for (i = 1; i < n; ++i) { l = tp[i].numx; r = tp[i].numy; mi = min(mi,L[l] + R[r]); } printf("%I64d\n",mi); } return 0;}
灵活的骗数据做法表示很ym能够AC。。。分别按x,y排序找出x,y的中位数，然后以它为基准按Manhattan 距离排序，然后枚举该点左右各100个即可：（经测试枚举左右1个点都能过）
View Code #include#include #include #include #define ll __int64#define maxn 100007using namespace std;struct node{ ll x,y;}p[maxn];ll midx,midy;const ll inf = 0x7fffffff;ll Abs(ll x){ if (x > 0) return x; else return -x;}int cmp1(node a,node b){ return a.x < b.x;}int cmp2(node a,node b){ return a.y < b.y;}int cmp3(node a,node b){ return Abs(a.x - midx) + Abs(a.y - midy) < Abs(b.x - midx) + Abs(b.y - midy);}int main(){ //freopen("1.txt","r",stdin); int i,j,t,n; scanf("%d",&t); while (t--) { scanf("%d",&n); for (i = 0; i < n; ++i) scanf("%I64d%I64d",&p[i].x,&p[i].y); sort(p,p + n,cmp1); if (n%2 == 1) midx = p[n/2].x; else midx = (p[n/2].x + p[n/2 - 1].x)/2; sort(p,p + n,cmp2); if (n%2 == 1) midy = p[n/2].y; else midy = (p[n/2].y + p[n/2 - 1].y)/2; sort(p,p + n,cmp3); ll mi = -1; for (i = 0; i <= 200; ++i) { ll sum = 0; for (j = 0; j < n; ++j) { sum += Abs(p[i].x - p[j].x) + Abs(p[i].y - p[j].y); } if (mi == -1 || sum < mi) mi = sum; } printf("%I64d\n",mi); } return 0;}
hdu 4312
做法同上题，只不过这里题目给的不是Manhattan 距离了，而是Chebyshev 距离，将坐标（x,y）转换成（x - y,x + y）Manhattan 除以2即得结果；
View Code #include#include #include #include #include #include
灵活骗数据的做法同上题，经测试只要枚举左右1个点即可水过：继续YM
View Code #include#include #include #include #define ll __int64#define maxn 100007using namespace std;struct node{ ll x,y;}p[maxn];ll midx,midy;const ll inf = 0x7fffffff;ll Abs(ll x){ if (x > 0) return x; else return -x;}int cmp1(node a,node b){ return a.x < b.x;}int cmp2(node a,node b){ return a.y < b.y;}int cmp3(node a,node b){ return Abs(a.x - midx) + Abs(a.y - midy) < Abs(b.x - midx) + Abs(b.y - midy);}int main(){ //freopen("1.txt","r",stdin); int i,j,t,n; scanf("%d",&t); while (t--) { scanf("%d",&n); for (i = 0; i < n; ++i) scanf("%I64d%I64d",&p[i].x,&p[i].y); sort(p,p + n,cmp1); if (n%2 == 1) midx = p[n/2].x; else midx = (p[n/2].x + p[n/2 - 1].x)/2; sort(p,p + n,cmp2); if (n%2 == 1) midy = p[n/2].y; else midy = (p[n/2].y + p[n/2 - 1].y)/2; sort(p,p + n,cmp3); ll mi = -1; for (i = 0; i <= 2; ++i) { ll sum = 0; for (j = 0; j < n; ++j) { sum += max(Abs(p[i].x - p[j].x),Abs(p[i].y - p[j].y)); } if (mi == -1 || sum < mi) mi = sum; } printf("%I64d\n",mi); } return 0;}
hdu 4318
题意：
西电东送，给出N个传输点，每个传输点与Ki个点连接，以及他们之间的消耗百分数。给出起点s,终点t，其实值v。求s到t的最小消耗。
思路：
才开始，我想的是用bfs将图的边转化成消耗量，然后Dijkstra求最短路，写完了一提交wa，思考了一下，不对，因为一个点可能被多个点更新，所以当前点的剩余值不能确定所以边的权值也就无法确定。最后想了想只要bfs一遍每个点存放最大的剩余值，最后val[t]终点剩余值最大即可，v - val[t]即得结果。这里存在环也不怕，因为当前点如果往他的子节点传输的话，必定减小，如果在环中返回到了其父节点，最后得到的剩余值必定小于父节点存储的剩余值，故不会进入队列。
View Code #include#include #include #include #include #define maxn 50007using namespace std;const double inf = 0x7fffffff;double val[maxn];struct node{ int u,v; double w; int next;}g[maxn*50];int cnt,head[maxn];int s,t,v;void add(int u,int v,double w){ g[cnt].u = u; g[cnt].v = v; g[cnt].w = w; g[cnt].next = head[u]; head[u] = cnt++;}void bfs(){ queue q; while (!q.empty()) q.pop(); q.push(s); while (!q.empty()) { int u = q.front(); q.pop(); for (int i = head[u]; i != -1; i = g[i].next) { int v = g[i].v; double w = g[i].w; double tmp = (val[u]*(100 - w))/100.0; //这里选择最大的剩余值 if (tmp > val[v]) { val[v] = tmp; q.push(v); } } }}int main(){ int i,j,x,y,n,ki; while (~scanf("%d",&n)) { cnt = 0; memset(head,-1,sizeof(head)); for (i = 1; i <= n; ++i) { scanf("%d",&ki); for (j = 1; j <= ki; ++j) { scanf("%d%d",&x,&y); add(i,x,y); } } scanf("%d%d%d",&s,&t,&v); val[s] = v; for (i = 1; i <= n; ++i) { if (i != s) val[i] = -inf; } bfs(); if (val[t] == -inf) printf("IMPOSSIBLE!\n"); else printf("%.2lf\n",1.0*v - val[t]); } return 0;}
hdu 4313
题意：
王国里有n个城市n-1条道路将他们连接，机器人要攻击这个王国，已知有K个机器人住在k个城市，国王要求你摧毁一些道路，使这K个机器人无法互通。
思路：
因为保证任意两点互通，而且给定n个点，n-1条边，所以该图一定是生成树的形式。我们只需要用类似Kruskal算法的形式，将边从大到小排序，在合并的时候判断两个集合是否都含有要被删除的点，即可。注意在合并的时候保证每个集合的根是要被删除的点（即K个机器人中的点）。
以后要对大数据敏感一些，这里结果要用long long(__int64)。wa好几次才发现的。
View Code #include#include #include #include #define maxn 100003#define ll __int64using namespace std;bool hash[maxn];int f[maxn],n;struct node{ int u,v; int w;}e[maxn];int cmp(node a,node b){ return a.w > b.w;}int find(int x){ if (f[x] != x) f[x] = find(f[x]); return f[x];}void Union(int x,int y){ if (hash[x] && !hash[y]) f[y] = x; else f[x] = y;}void kruskal(){ int i; ll ans = 0; for (i = 0; i < n - 1; ++i) { int u = e[i].u; int v = e[i].v; int w = e[i].w; int tp1 = find(u); int tp2 = find(v); if (tp1 != tp2)//不是同一个集合 { if (hash[tp1] && hash[tp2]) ans += w;//两个集合的根都是要删除的点 Union(tp1,tp2); } } printf("%I64d\n",ans);}int main(){ int t,i,x,m; scanf("%d",&t); while (t--) { memset(hash,false,sizeof(hash)); scanf("%d%d",&n,&m); for (i = 0; i <= n; ++i) f[i] = i; for (i = 0; i < n - 1; ++i) scanf("%d%d%d",&e[i].u,&e[i].v,&e[i].w); for (i = 0; i < m; ++i) { scanf("%d",&x); hash[x] = true; } sort(e,e + n -1,cmp); kruskal(); /*for (i = 0; i < n; ++i) printf("%d %d\n",i,find(i));*/ } return 0;}
参考虎哥的dfs做的，这样的dfs累死属性dp搜索到叶子节点后然后往上走。走的过程记录所有子树到该点要删除的最小边的权值，还要记录一个最小中的最大的，因为在当前点不是与机器人的点的时候，要利用它往上更新。
View Code #include#include #include #include #include #include
官方结题报告：