hzwer.com - Page 41

「BZOJ2427」[HAOI2010] 软件安装
Description现在我们的手头有N个软件，对于一个软件i，它要占用Wi的磁盘空间，它的价值为Vi。我们希望从中选择一些软件安装到一台磁盘容量为M计算机上，使得这些软件的价值尽可能大（即Vi的和最大）。但是现在有个问题：软件之间存在依赖关系，即软件i只有在安装了软件j（包括软件j的直接或间接依赖）的情况下才能正确工作（软件i依赖软件j)。幸运的是，一个软件最多依赖另外一个软件。如果一个软件不能正常工作，那么它能够...
42014年12月13日6,650树形动规,图的连通

「BZOJ1226」[SDOI2009] 学校食堂Dining
Description小F的学校在城市的一个偏僻角落，所有学生都只好在学校吃饭。学校有一个食堂，虽然简陋，但食堂大厨总能做出让同学们满意的菜肴。当然，不同的人口味也不一定相同，但每个人的口味都可以用一个非负整数表示。由于人手不够，食堂每次只能为一个人做菜。做每道菜所需的时间是和前一道菜有关的，若前一道菜的对应的口味是a，这一道为b，则做这道菜所需的时间为（aorb）-（aandb），而做第一道菜是不需要计算时间的。其中...
12014年12月13日5,835状压动规
「hdu3555」Bomb
ProblemDescriptionThecounter-terroristsfoundatimebombinthedust.Butthistimetheterroristsimproveonthetimebomb.Thenumbersequenceofthetimebombcountsfrom1toN.Ifthecurrentnumbersequenceincludesthesub-sequence"49",thepoweroftheblastwouldaddonepoint.Nowthecounter-terroristknowsthenumberN.Theywanttoknowthefinalpointsofthepower.Canyouhelpthem? InputThefirstlineofinputconsistsofanintegerT(...
02014年12月12日3,639数位动规
「BZOJ1487」[HNOI2009] 无归岛
DescriptionNeverland是个神奇的地方，它由一些岛屿环形排列组成，每个岛上都生活着之中与众不同的物种。但是这些物种都有一个共同的生活习性：对于同一个岛上的任意两个生物，他们有且仅有一个公共朋友，即对同一岛上的任意两个生物a和b有且仅有一个生物c既是a的朋友也是b的朋友，当然某些岛上也可能会只有一个生物孤单地生活着。这一习性有一个明显的好处，当两个生物发生矛盾的时候，他们可以请那个唯一的公共朋友来裁决谁对谁...
32014年12月12日4,525递推与动规,仙人掌
「BZOJ2115」[Wc2011] Xor
DescriptionInput第一行包含两个整数N和M，表示该无向图中点的数目与边的数目。接下来M行描述M条边，每行三个整数Si，Ti，Di，表示Si与Ti之间存在一条权值为Di的无向边。图中可能有重边或自环。Output仅包含一个整数，表示最大的XOR和（十进制结果）。SampleInput57122132241251453534432SampleOutput6HINT题解所有路径实际是一条1-n的路径和一堆环环用dfs求出。。。然后就是高斯消元的经典应用注意TT...
12014年12月12日5,764深度搜索,高斯消元
「hdu4010」Query on The Trees
ProblemDescriptionWehavemetsomanyproblemsonthetree,sotodaywewillhaveaqueryproblemonasetoftrees.ThereareNnodes,eachnodewillhaveauniqueweightWi.Wewillhavefourkindsofoperationsonitandyoushouldsolvethemefficiently.Wishyouhavefun! InputTherearemultipletestcasesinourdataset.Foreachcase,thefirstlinecontainsonlyoneintegerN.(1≤N≤300000)ThenextN‐1lineseachcontainstwointegersx,ywhichme...
172014年12月11日5,441link cut tree
「hdu3949」XOR
ProblemDescriptionXORisakindofbitoperator,wedefinethatasfollow:fortwobinarybasenumberAandB,letC=AXORB,thenforeachbitofC,wecangetitsvaluebycheckthedigitofcorrespondingpositioninAandB.Andforeachdigit,1XOR1=0,1XOR0=1,0XOR1=1,0XOR0=0.Andwesimplywritethisoperatoras^,like3^1=2,4^3=7.XORisanamazingoperatorandthisisaquestionaboutXOR.WecanchooseseveralnumbersanddoXOR...
02014年12月11日7,224高斯消元
「BZOJ3790」神奇项链
Description母亲节就要到了，小H准备送给她一个特殊的项链。这个项链可以看作一个用小写字母组成的字符串，每个小写字母表示一种颜色。为了制作这个项链，小H购买了两个机器。第一个机器可以生成所有形式的回文串，第二个机器可以把两个回文串连接起来，而且第二个机器还有一个特殊的性质：假如一个字符串的后缀和一个字符串的前缀是完全相同的，那么可以将这个重复部分重叠。例如：aba和aca连接起来，可以生成串abaaca或abaca。...
22014年12月11日6,301树状数组,manacher
「BZOJ3306」树
Description给定一棵大小为n的有根点权树,支持以下操作:•换根•修改点权•查询子树最小值Input第一行两个整数n,Q,分别表示树的大小和操作数。接下来n行,每行两个整数f,v,第i+1行的两个数表示点i的父亲和点i的权。保证f<i。如果f=0,那么i为根。输入数据保证只有i=1时,f=0。接下来m行,为以下格式中的一种:•Vxy表示把点x的权改为y•Ex表示把有根树的根改为点x•Qx表示查询点x的子树最小值Output对于每个Q,输出子树最小值...
02014年12月11日7,558dfs序,线段树,树上倍增
NOI2011道路修建
Description在W星球上有n个国家。为了各自国家的经济发展，他们决定在各个国家之间建设双向道路使得国家之间连通。但是每个国家的国王都很吝啬，他们只愿意修建恰好n–1条双向道路。每条道路的修建都要付出一定的费用，这个费用等于道路长度乘以道路两端的国家个数之差的绝对值。例如，在下图中，虚线所示道路两端分别有2个、4个国家，如果该道路长度为1，则费用为1×|2–4|=2。图中圆圈里的数字表示国家的编号。由于国家的数量十...
02014年12月10日3,248树形动规
「CODEVS1743」反转卡片
题目描述Description「dzy493941464|yywyzdzr原创」小A将N张卡片整齐地排成一排，其中每张卡片上写了1~N的一个整数，每张卡片上的数各不相同。比如下图是N=5的一种情况：34215接下来你需要按小A的要求反转卡片，使得左数第一张卡片上的数字是1。操作方法：令左数第一张卡片上的数是K，如果K=1则停止操作，否则将左数第1~K张卡片反转。第一次(K=3)反转后得到：24315第二次(K=2)反转后得到：42315第三次(K=4)反转后得到：...
22014年12月10日5,517splay
「BZOJ2716 / 2648」SJY摆棋子
Description这天，SJY显得无聊。在家自己玩。在一个棋盘上，有N个黑色棋子。他每次要么放到棋盘上一个黑色棋子，要么放上一个白色棋子，如果是白色棋子，他会找出距离这个白色棋子最近的黑色棋子。此处的距离是曼哈顿距离即(|x1-x2|+|y1-y2|)。现在给出N<=500000个初始棋子。和M<=500000个操作。对于每个白色棋子，输出距离这个白色棋子最近的黑色棋子的距离。同一个格子可能有多个棋子。Input第一行两个数NM以后M...
62014年12月10日25,997K-Dtree