这一题其实并不难，昨天比赛时WA了，下来请教了队友，原来是用的矩形切割
Problem 3634 62MS 224K
本题思路：以出现的矩形端点为交点将所有的矩形分割成一个个小矩形，这里的点要求不重复且升序，正好用到set很方便（相当于离散化）。
然后再把原来的矩形按照value的降序排列，将每个矩形所覆盖的且还没有着色小矩形块统统着色，并求价值和，即得结果。
查找矩形覆盖的小矩形块时可用二分，但本题数据规模较小，就线性扫描查找了。
另外，本题我刚开始定义结果为long long型，用G++提交WA了。后将结果定义为__int64，用C++交，闪亮AC！
#include < iostream > #include < set > using namespace std; struct rect{ int x1,y1,x2,y2,v;}r[ 22 ]; set < int > col[ 2 ]; int map[ 50 ][ 50 ],xcol[ 50 ],ycol[ 50 ],xnum,ynum; int cmp( const void * a, const void * b){ struct rect * aa = ( struct rect * )a; struct rect * bb = ( struct rect * )b; return bb -> v - aa -> v;} int findx( int a){ for ( int i = 0 ;i < xnum;i ++ ) if (a == xcol[i]) return i;} int findy( int a){ for ( int i = 0 ;i < ynum;i ++ ) if (a == ycol[i]) return i;} int main(){ int cas,ca,n,i,j,k; __int64 ans; int sx,sy,ex,ey; scanf( " %d " , & cas); for (ca = 1 ;ca <= cas;ca ++ ) { col[ 0 ].clear(); col[ 1 ].clear(); scanf( " %d " , & n); for (i = 0 ;i < n;i ++ ) { scanf( " %d%d%d%d%d " , & r[i].x1, & r[i].y1, & r[i].x2, & r[i].y2, & r[i].v); col[ 0 ].insert(r[i].x1); col[ 0 ].insert(r[i].x2); col[ 1 ].insert(r[i].y1); col[ 1 ].insert(r[i].y2); } qsort(r,n, sizeof (r[ 0 ]),cmp); memset(map, 0 , sizeof (map)); xnum = ynum = 0 ; set < int > ::iterator it; for (it = col[ 0 ].begin();it != col[ 0 ].end();it ++ ) xcol[xnum ++ ] =* it; for (it = col[ 1 ].begin();it != col[ 1 ].end();it ++ ) ycol[ynum ++ ] =* it; /* for(i=0;i<xnum;i++) printf("%d ",xcol[i]); puts(""); for(i=0;i<ynum;i++) printf("%d ",ycol[i]); puts(""); */ printf( " Case %d: " ,ca); ans = 0 ; for (i = 0 ;i < n;i ++ ) { sx = findx(r[i].x1); ex = findx(r[i].x2); sy = findy(r[i].y1); ey = findy(r[i].y2); // printf("%d %d %d %d \n",sx,xcol[sx],sy,ycol[sy]); // printf("%d %d %d %d \n",ex,xcol[ex],ey,ycol[ey]); // printf("%lld\n",(__int64)(r[i].v)); for (j = sx;j < ex;j ++ ) { for (k = sy;k < ey;k ++ ){ if (map[j][k] == 0 ) { map[j][k] = 1 ; ans += (__int64)(xcol[j + 1 ] - xcol[j]) * (__int64)(ycol[k + 1 ] - ycol[k]) * (__int64)(r[i].v); // printf(" // %d %d %d %d\n",(xcol[j+1]-xcol[j]),(ycol[k+1]-ycol[k]),(r[i].v),ans); } } } } printf( " %I64d\n " ,ans); } return 0 ;}昨天比赛做的是多校（十九），悲剧收场！提一下每题的大致意思吧，以后也好回忆……
3632 决斗问题 DP
3635 并查集 最简单的一题
3636 最优搜索
3637 在区间内找一个分子分母和最小的分数 数论
3638 应该也用搜索解决吧 怪兽的视野会移动 咬笔杆……
3639 老鹰捉小鸡 图论连通问题
转载于:https://www.cnblogs.com/DreamUp/archive/2010/10/03/1841662.html
相关资源：JAVA上百实例源码以及开源项目