hzwer.com - Page 38

「图论练习」medium
hzwer蒟蒻刚刚学了点图论，现在他面对一张无向连通图他想问你最少添加多少条边，使得任意两点之间有两条无公共边的路（可以有公共点）输入格式第一行n，m，n个点m条边接下来m行，每行u，v表示u到v之间有一条无向边（可能重复描述一条边）输出格式一行，答案样例输入551223344545样例输出1 数据范围20%的数据N<=20,M<=5040%的数据N<=2000,M<=200070%的数据N<=20000,M<=20000100%的数据N&...
42014年12月20日3,925图的连通

「图论练习」easy
hzwer蒟蒻刚刚学了点图论，现在他面对一张有向图他想问你：1：最少选择多少个点，使得从这些点出发能遍历完整个图2：最少添加多少条有向边，能使得整个图成为强连通图输入格式第一行n，m，n个点m条边接下来m行，每行u，v表示一条u到v的有向边输出格式两行，分别为两问答案样例输入53122334样例输出22 数据范围20%的数据N<=20,M<=5040%的数据N<=2000,M<=2000070%的数据N<=5000,M<=5000010...
12014年12月20日5,081图的连通
「BZOJ3747」[POI2015] Kinoman
Description共有m部电影，编号为1~m，第i部电影的好看值为w[i]。在n天之中（从1~n编号）每天会放映一部电影，第i天放映的是第f[i]部。你可以选择l,r(1<=l<=r<=n)，并观看第l,l+1,…,r天内所有的电影。如果同一部电影你观看多于一次，你会感到无聊，于是无法获得这部电影的好看值。所以你希望最大化观看且仅观看过一次的电影的好看值的总和。Input第一行两个整数n,m(1<=m<=n<=1000000)。第二行包含n个整数f[1],...
22014年12月19日5,320线段树
「BZOJ3750」[POI2015] Pieczęć
Description一张n*m的方格纸，有些格子需要印成黑色，剩下的格子需要保留白色。你有一个a*b的印章，有些格子是凸起（会沾上墨水）的。你需要判断能否用这个印章印出纸上的图案。印的过程中需要满足以下要求：（1）印章不可以旋转。（2）不能把墨水印到纸外面。（3）纸上的同一个格子不可以印多次。Input第一行一个整数q(1<=q<=10)，表示测试点数量。接下来q个测试点，每个测试点中：第一行包含4个整数n,m,a,b(1<=n,m,a,...
02014年12月19日3,944链表
「BZOJ2199」[Usaco2011 Jan] 奶牛议会
Description由于对FarmerJohn的领导感到极其不悦，奶牛们退出了农场，组建了奶牛议会。议会以“每头牛都可以获得自己想要的”为原则，建立了下面的投票系统：M只到场的奶牛(1<=M<=4000)会给N个议案投票(1<=N<=1,000)。每只奶牛会对恰好两个议案B_iandC_i(1<=B_i<=N;1<=C_i<=N)投出“是”或“否”（输入文件中的'Y'和'N'）。他们的投票结果分别为VB_i(VB_iin{'Y','N'})andVC_i(VC...
12014年12月19日5,5302-SAT
「codechefFNCS」Chef and Churu
题解分块水过将函数分块，每一块大小√n，预处理一块内的函数统计每一个数字的次数，以及这一块的答案这一部分n√n并用树状数组维护a的前缀和，线段树呵呵。。。对于询问将整块的答案加起来，其余部分的每个函数在树状数组中查询对于修改修改树状数组依照每一个数字在每一块的次数，更新每一块的答案这一部分n√nlogn若理论分析似乎分块设小会更优，但若考虑下常数会发现好像并不会。。。注意本题要用unsignedlonglong还有一个很牛...
12014年12月18日4,621分块,树状数组
「BZOJ3166」[HEOI2013] Alo
DescriptionWelcometoALO(ArithmeticandLogisticOnline)。这是一个VRMMORPG ，如名字所见，到处充满了数学的谜题。现在你拥有n颗宝石，每颗宝石有一个能量密度，记为ai，这些宝石的能量密度两两不同。现在你可以选取连续的一些宝石（必须多于一个）进行融合，设为 ai,ai+1,…,a j，则融合而成的宝石的能量密度为这些宝石中能量密度的次大值与其他任意一颗宝石的能量密度按位异或的值，即，设该段宝石能量密度次...
22014年12月18日8,232贪心,可持久化字典树
「CF497C」Distributing Parts
Youareanassistantdirectorinanewmusicalplay.Theplayconsistsofnmusicalparts,eachpartmustbeperformedbyexactlyoneactor.Afterthecastingthedirectorchosemactorswhocantakepartintheplay.Yourtaskistoassignthepartstoactors.However,thereareseverallimitations.First,eachactorhasacertainvoicerangeandtherearesomepartsthathecannotsing.Formally,therearetwointegersforeachactor,cianddi(ci ≤ di) —thepitcho...
02014年12月18日4,226贪心
「CF497B」Tennis Game
PetyaandGenaloveplayingtabletennis.Asinglematchisplayedaccordingtothefollowingrules:amatchconsistsofmultiplesets,eachsetconsistsofmultipleserves.Eachserveiswonbyoneoftheplayers,thisplayerscoresonepoint.Assoonasoneoftheplayersscorestpoints,hewinstheset;thenthenextsetstartsandscoresofbothplayersarebeingsetto0.Assoonasoneoftheplayerswinsthetotalofssets,hewinsthematchandthematchisover.Heresandt...
02014年12月18日4,045二分法
「CF497A」Removing Columns
Youaregivenann × mrectangulartableconsistingoflowercaseEnglishletters.Inoneoperationyoucancompletelyremoveonecolumnfromthetable.Theremainingpartsarecombinedforminganewtable.Forexample,afterremovingthesecondcolumnfromthetable[crayon-693ebad0a2403938937486/]weobtainthetable:[crayon-693ebad0a240a561631621/]Atableiscalledgoodifitsrowsareorderedfromtoptobottomlexicographically,i.e.eachrowislex...
02014年12月18日2,989贪心
「BZOJ2809」[Apio2012] dispatching
Description在一个忍者的帮派里，一些忍者们被选中派遣给顾客，然后依据自己的工作获取报偿。在这个帮派里，有一名忍者被称之为 Master。除了 Master以外，每名忍者都有且仅有一个上级。为保密，同时增强忍者们的领导力，所有与他们工作相关的指令总是由上级发送给他的直接下属，而不允许通过其他的方式发送。现在你要招募一批忍者，并把它们派遣给顾客。你需要为每个被派遣的忍者支付一定的薪水，同时使得支付的薪水总额不超...
22014年12月17日5,895可并堆
「BZOJ1367」[Baltic2004] sequence
DescriptionInputOutput一个整数RSampleInput794820141518SampleOutput13HINT所求的Z序列为6,7,8,13,14,15,18.R=13题解 hyh论文例题http://wenku.baidu.com/link?url=t55yGX-UkUdEXBhpvBwuzjKP16F7lFl0RKSVVBBW5zXWRB7rRXvLLj1jM-pzhbH834hQl0KKT4va247VmSepsGDSrYF1E3le_WpnKc2xfCi[crayon-693ebad0a2f71410014763/] ...
42014年12月17日5,403可并堆