hzwer.com - Page 57

「BZOJ2618」[CQOI2006] 凸多边形
Description逆时针给出n个凸多边形的顶点坐标，求它们交的面积。例如n=2时，两个凸多边形如下图：则相交部分的面积为5.233。Input第一行有一个整数n，表示凸多边形的个数，以下依次描述各个多边形。第i个多边形的第一行包含一个整数mi，表示多边形的边数，以下mi行每行两个整数，逆时针给出各个顶点的坐标。 Output输出文件仅包含一个实数，表示相交部分的面积，保留三位小数。 SampleInput26-20-1-21-22012-1240-3...
12014年10月16日5,574半平面交

「codecomb2098」stone
Descriptionn个石堆围成一圈，提供两种操作：1、每次将[L,R]堆的石子数量+k，其中，1<=L,R<=n,k>=0。2、询问有最多石子的那一堆有多少石子。现在，要求在线解决该问题。Input第一行两个整数n和m，n表示石子圈的长度，m表示操作数量。以下m行，首先一个是整数t，t=1或2，表示是哪种操作。如果t=1，则后面跟三个整数l,r,k，表示区间[l,r]的所有石子堆石子数量+k，如果t=2表示上述询问操作。 Output 对于...
02014年10月16日2,632线段树
「codecomb2096」lyz
Description滑冰俱乐部初始有1->n号码溜冰鞋各k双，已知x号脚的人可以穿x->x+d号码的鞋子。现在有m次操作，每次两个数r、x，表示r号脚的人来了x个，x为负表示离开。对于每次操作，输出溜冰鞋是否足够。Input第一行四个整数n,m,k,d。以下m行，每行一个操作。Output对于每一个询问，输出是否可行。若可行，输出TAK，反之，输出NIE。Sample Input4 4 2 11 32 33 32 -1Sample OutputTAKTAKNIETA...
02014年10月16日2,896线段树
「codecomb2097」rect
Description在一个n*m的格子棋盘上，有n*m堆石子，现在有两种操作：1、给(x1,y1)->(x2,y2)这个矩形内所有的石子堆加入k个石子。1<=x1<=x2<=n,1<=y1<=y2<=m。2、询问某格(x,y)上面有多少石子。Input第一行两个整数n和m，分别表示棋盘的长宽，n对应上述的x轴，m对应y轴。第二行一个整数p，表示操作数量。以下p行，首先一个是整数t，t=1或2，表示是哪种操作。如果t=1，则后面跟5个整数x1,y1,x2,y2,k，如上所...
02014年10月16日2,801树状数组
「BZOJ1038」[ZJOI2008] 瞭望塔
Description致力于建设全国示范和谐小村庄的H村村长dadzhi，决定在村中建立一个瞭望塔，以此加强村中的治安。我们将H村抽象为一维的轮廓。如下图所示我们可以用一条山的上方轮廓折线(x1,y1),(x2,y2),….(xn,yn)来描述H村的形状，这里x1<x2<…<xn。瞭望塔可以建造在[x1,xn]间的任意位置,但必须满足从瞭望塔的顶端可以看到H村的任意位置。可见在不同的位置建造瞭望塔，所需要建造的高度是不同的。为了节省开支，dadzhi...
82014年10月16日6,625半平面交
「codecomb2094」还是N皇后
Description正如题目所说，这题是著名的N皇后问题。Input Format第一行有一个N。接下来有N行N列描述一个棋盘，“*”表示可放“.”表示不可放。Output Format输出方案总数。Sample Input4**.*************Sample Output1Data Limit对于30%的数据，N≤10;对于100%的数据，N≤14；题解裸的dfs不足以ac我发现n皇后可以用位运算加速参见http://blog.csdn.net/xadillax/article/details/6512318然后就能水过了。。...
02014年10月15日3,132深度搜索
「codecomb2093」牛宫
DescriptionHzgd神牛准备给自己盖一座很华丽的宫殿。于是，他看中了一块N*M的矩形空地。空地中每个格子都有自己的海拔高度。胡张想让他的宫殿的平均海拔在海平面之上（假设海平面的高度是0，平均数都会算吧？）。而且，胡张希望他的宫殿是个矩形且尽量大，能够容纳更多的人来膜拜他。请问胡张的宫殿最后会有多大？Input Format第一行为N和M。之后N行，每行M个数，描述的空地的海拔。Output Format输出一行,表示宫殿最...
02014年10月15日3,812二分法,单调栈
「codecomb2092」课程选择
题目描述大学选课总是烦恼着很多人。现在X同学选出了很多备选课，但是有的课程之间是有时间冲突的。X不会分身，自然无法在同一个时间上不同的课。每个课可能有很多备选时间，但是每个课只需要选一个时间上就可以了。当然X没有必要在不同时间上相同的课。现在把X的备选课及相应的上课时间告诉你，请你求出X一星期最多可以上多少课。输入格式第一行输入一个n，表示X将提供给你n个备选课。接下来n行，每行...
02014年10月13日2,740最大流
「codecomb2091」路径数量
题目描述给定一张n个点的有向图，求从点1到点n最多有多少条不相交的简单路径。所谓不相交即不经过相同的边的路径。输入格式第一行读入一个n，m，表示共n个点，m条边。接下来m行，每行两个整数x，y，表示从x到y有一条有向边。输出格式输出仅包括一行，即最多有多少条不相交的简单路劲。样例数据1输入4712122323233434输出2备注对于20%的数据n<=10，m<=1000；对于100%的数据n<=1000，m<=100000；题...
02014年10月13日3,185最大流
「codecomb2090」最小乘积路
题目描述给定n个点的带权有向图，求从1到n的路径中边权之积最小的简单路径。输入格式第一行读入两个整数n，m，表示共n个点m条边。接下来m行，每行三个正整数x，y，z，表示点x到点y有一条边权为z的边。输出格式输出仅包括一行，记为所求路径的边权之积，由于答案可能很大，因此输出它模9987的余数即可。样例数据1输入331232331310输出9备注对于20%的数据，n<=10。对于100%的数据，n<=1000，m<=1000000。边权不超过10000。题...
02014年10月13日3,625dijkstra
「CF477C」Dreamoon and Strings
Dreamoonhasastringsandapatternstringp.Hefirstremovesexactlyxcharactersfromsobtainingstrings'asaresult.Thenhecalculatesthatisdefinedasthemaximalnumberofnon-overlappingsubstringsequaltopthatcanbefoundins'.Hewantstomakethisnumberasbigaspossible.Moreformally,let'sdefineasmaximumvalueofoveralls'thatcanbeobtainedbyremovingexactlyxcharactersfroms.Dreamoonwantstoknowforallxfrom0to|s|where|s|denotest...
02014年10月13日4,971递推与动规
「CF477B」Dreamoon and Sets
Dreamoonlikestoplaywithsets,integersand.isdefinedasthelargestpositiveintegerthatdividesbothaandb.LetSbeasetofexactlyfourdistinctintegersgreaterthan0.DefineStobeofrankkifandonlyifforallpairsofdistinctelementssi,sjfromS,.Givenkandn,Dreamoonwantstomakeupnsetsofrankkusingintegersfrom1tomsuchthatnointegerisusedintwodifferentsets(ofcourseyoucanleavesomeintegerswithoutuse).Calculatetheminimummth...
02014年10月13日4,131构造