hzwer.com - Page 74

「BZOJ2733」[HNOI2012] 永无乡
Description永无乡包含n座岛，编号从1到n，每座岛都有自己的独一无二的重要度，按照重要度可以将这n座岛排名，名次用1到n来表示。某些岛之间由巨大的桥连接，通过桥可以从一个岛到达另一个岛。如果从岛a出发经过若干座（含0座）桥可以到达岛b，则称岛a和岛b是连通的。现在有两种操作：Bxy表示在岛x与岛y之间修建一座新桥。Qxk表示询问当前与岛x连通的所有岛中第k重要的是哪座岛，即所有与岛x连通的岛中重要度排名第k小的岛是哪座...
12014年7月31日8,835线段树

NOI2003Editor
DescriptionInput输入文件editor.in的第一行是指令条数t，以下是需要执行的t个操作。其中：为了使输入文件便于阅读，Insert操作的字符串中可能会插入一些回车符，请忽略掉它们（如果难以理解这句话，可以参考样例）。除了回车符之外，输入文件的所有字符的ASCII码都在闭区间[32,126]内。且行尾没有空格。这里我们有如下假定：MOVE操作不超过50000个，INSERT和DELETE操作的总个数不超过4000，PREV和N...
152014年7月31日5,072STL
「BZOJ2002」[HNOI2010] Bounce 弹飞绵羊
Description某天，Lostmonkey发明了一种超级弹力装置，为了在他的绵羊朋友面前显摆，他邀请小绵羊一起玩个游戏。游戏一开始，Lostmonkey在地上沿着一条直线摆上n个装置，每个装置设定初始弹力系数ki，当绵羊达到第i个装置时，它会往后弹ki步，达到第i+ki个装置，若不存在第i+ki个装置，则绵羊被弹飞。绵羊想知道当它从第i个装置起步时，被弹几次后会被弹飞。为了使得游戏更有趣，Lostmonkey可以修改某个弹力装置的弹力系数，任...
102014年7月30日16,755分块,link cut tree
「BZOJ2049」[SDOI2008] Cave 洞穴勘测
Description辉辉热衷于洞穴勘测。某天，他按照地图来到了一片被标记为JSZX的洞穴群地区。经过初步勘测，辉辉发现这片区域由n个洞穴（分别编号为1到n）以及若干通道组成，并且每条通道连接了恰好两个洞穴。假如两个洞穴可以通过一条或者多条通道按一定顺序连接起来，那么这两个洞穴就是连通的，按顺序连接在一起的这些通道则被称之为这两个洞穴之间的一条路径。洞穴都十分坚固无法破坏，然而通道不太稳定，时常因为外界影响而发...
322014年7月30日9,398link cut tree
NOI2005维修数列
DescriptionInput输入文件的第1行包含两个数N和M，N表示初始时数列中数的个数，M表示要进行的操作数目。第2行包含N个数字，描述初始时的数列。以下M行，每行一条命令，格式参见问题描述中的表格。Output对于输入数据中的GET-SUM和MAX-SUM操作，向输出文件依次打印结果，每个答案（数字）占一行。SampleInput982-6351-5-363GET-SUM54MAX-SUMINSERT83-572DELETE121MAKE-SAME...
252014年7月30日24,523splay
「BZOJ1584」[Usaco2009 Mar] Cleaning Up 打扫卫生
Description有N头奶牛，每头那牛都有一个标号Pi，1<=Pi<=M<=N<=40000。现在FarmerJohn要把这些奶牛分成若干段，定义每段的不河蟹度为：若这段里有k个不同的数，那不河蟹度为k*k。那总的不河蟹度就是所有段的不河蟹度的总和。Input第一行：两个整数N，M第2..N+1行：N个整数代表每个奶牛的编号Output一个整数，代表最小不河蟹度SampleInput1341213223434314SampleOutput11题解不会做TT看了半天题解这...
12014年7月30日4,566递推与动规
「BZOJ1710」[Usaco2007 Open] Cheappal 廉价回文
Description为了跟踪所有的牛,农夫JOHN在农场上装了一套自动系统.他给了每一个头牛一个电子牌号当牛走过这个系统时,牛的名字将被自动读入.每一头牛的电子名字是一个长度为M(1<=M<=2,000)由N(1<=N<=26)个不同字母构成的字符串.很快,淘气的牛找到了系统的漏洞:它们可以倒着走过读码器.一头名字为"abcba"不会导致任何问题,但是名为"abcb"的牛会变成两头牛("abcb"和"bcba").农夫JOHN想改变牛的名字,使得牛的名...
02014年7月29日3,516递推与动规
NOI2014随机数生成器
DescriptionInput第1行包含5个整数，依次为x_0,a,b,c,d，描述小H采用的随机数生成算法所需的随机种子。第2行包含三个整数N,M,Q，表示小H希望生成一个1到N×M的排列来填入她N行M列的棋盘，并且小H在初始的N×M次交换操作后，又进行了Q次额外的交换操作。接下来Q行，第i行包含两个整数u_i,v_i，表示第i次额外交换操作将交换T_(u_i)和T_(v_i)的值。Output输出一行，包含N+M-1个由空格隔开的正整数，表示可以得到...
22014年7月29日7,536贪心
「BZOJ1697」[Usaco2007 Feb] Cow Sorting牛排序
Description农夫JOHN准备把他的N（1<=N<=10,000）头牛排队以便于行动。因为脾气大的牛有可能会捣乱，JOHN想把牛按脾气的大小排序。每一头牛的脾气都是一个在1到100，000之间的整数并且没有两头牛的脾气值相同。在排序过程中，JOHN可以交换任意两头牛的位置。因为脾气大的牛不好移动，JOHN需要X+Y秒来交换脾气值为X和Y的两头牛。请帮JOHN计算把所有牛排好序的最短时间。Input第1行：一个数，N。...
32014年7月29日5,736置换
「BZOJ2100」[Usaco2010 Dec] Apple Delivery
DescriptionBessiehastwocrispredapplestodelivertotwoofherfriendsintheherd.Ofcourse,shetravelstheC(1<=C<=200,000)cowpathswhicharearrangedastheusualgraphwhichconnectsP(1<=P<=100,000)pasturesconvenientlynumberedfrom1..P:nocowpathleadsfromapasturetoitself,cowpathsarebidirectional,eachcowpathhasanassociateddistance,and,bestofall,itisalwayspossibletogetfromanypasturetoanyotherpasture....
02014年7月29日4,492spfa
「BZOJ1673」[Usaco2005 Dec] Scales 天平
DescriptionFarmerJohnhasabalanceforweighingthecows.HealsohasasetofN(1<=N<=1000)weightswithknownmasses(allofwhichfitin31bits)foruseononesideofthebalance.Heplacesacowononesideofthebalanceandthenaddsweightstotheothersideuntiltheybalance.(FJcannotputweightsonthesamesideofthebalanceasthecow,becausecowstendtokickweightsinhisfacewhenevertheycan.)Thebalancehasamaximummassratingandwillbreak...
02014年7月29日3,801深度搜索
「BZOJ2015」[Usaco2010 Feb] Chocolate Giving
DescriptionFarmerJohn有B头奶牛(1<=B<=25000)，有N(2*B<=N<=50000)个农场，编号1-N，有M(N-1<=M<=100000)条双向边，第i条边连接农场R_i和S_i(1<=R_i<=N;1<=S_i<=N)，该边的长度是L_i(1<=L_i<=2000)。居住在农场P_i的奶牛A(1<=P_i<=N)，它想送一份新年礼物给居住在农场Q_i(1<=Q_i<=N)的奶牛B，但是奶牛A必须先到FJ(居住在编号1的农场)那里取礼物，...
02014年7月29日4,669spfa