算法 - Page 37 - hzwer.com

「BZOJ1924」[SDOI2010] 所驼门王的宝藏
「问题描述」==============================================================在宽广的非洲荒漠中,生活着一群勤劳勇敢的羊驼家族。被族人恭称为“先知”的AlpacaL.Sotomon是这个家族的领袖,外人也称其为“所驼门王”。所驼门王毕生致力于维护家族的安定与和谐,他曾亲自率军粉碎河蟹帝国主义的野蛮侵略,为族人立下赫赫战功。所驼门王一生财宝无数,但因其生性节俭低调,他将财宝埋藏在自己设计的地下宫殿里,这也是今天HenryCurt...
02014年12月20日6,482递推与动规,STL,图的连通

「BZOJ2438」[中山市选2011] 杀人游戏
Description一位冷血的杀手潜入Na-wiat，并假装成平民。警察希望能在N个人里面，查出谁是杀手。警察能够对每一个人进行查证，假如查证的对象是平民，他会告诉警察，他认识的人，谁是杀手，谁是平民。假如查证的对象是杀手，杀手将会把警察干掉。现在警察掌握了每一个人认识谁。每一个人都有可能是杀手，可看作他们是杀手的概率是相同的。问：根据最优的情况，保证警察自身安全并知道谁是杀手的概率最大是多少？Input第一行有两...
32014年12月20日6,224图的连通
「图论练习」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,768图的连通
「图论练习」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日4,910图的连通
「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,205线段树
「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,823链表
「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,3972-SAT
「codechefFNCS」Chef and Churu
题解分块水过将函数分块，每一块大小√n，预处理一块内的函数统计每一个数字的次数，以及这一块的答案这一部分n√n并用树状数组维护a的前缀和，线段树呵呵。。。对于询问将整块的答案加起来，其余部分的每个函数在树状数组中查询对于修改修改树状数组依照每一个数字在每一块的次数，更新每一块的答案这一部分n√nlogn若理论分析似乎分块设小会更优，但若考虑下常数会发现好像并不会。。。注意本题要用unsignedlonglong还有一个很牛...
12014年12月18日4,476分块,树状数组
「BZOJ3166」[HEOI2013] Alo
DescriptionWelcometoALO(ArithmeticandLogisticOnline)。这是一个VRMMORPG ，如名字所见，到处充满了数学的谜题。现在你拥有n颗宝石，每颗宝石有一个能量密度，记为ai，这些宝石的能量密度两两不同。现在你可以选取连续的一些宝石（必须多于一个）进行融合，设为 ai,ai+1,…,a j，则融合而成的宝石的能量密度为这些宝石中能量密度的次大值与其他任意一颗宝石的能量密度按位异或的值，即，设该段宝石能量密度次...
22014年12月18日7,843贪心,可持久化字典树
「CF497C」Distributing Parts
Youareanassistantdirectorinanewmusicalplay.Theplayconsistsofnmusicalparts,eachpartmustbeperformedbyexactlyoneactor.Afterthecastingthedirectorchosemactorswhocantakepartintheplay.Yourtaskistoassignthepartstoactors.However,thereareseverallimitations.First,eachactorhasacertainvoicerangeandtherearesomepartsthathecannotsing.Formally,therearetwointegersforeachactor,cianddi(ci ≤ di) —thepitcho...
02014年12月18日3,979贪心
「CF497B」Tennis Game
PetyaandGenaloveplayingtabletennis.Asinglematchisplayedaccordingtothefollowingrules:amatchconsistsofmultiplesets,eachsetconsistsofmultipleserves.Eachserveiswonbyoneoftheplayers,thisplayerscoresonepoint.Assoonasoneoftheplayersscorestpoints,hewinstheset;thenthenextsetstartsandscoresofbothplayersarebeingsetto0.Assoonasoneoftheplayerswinsthetotalofssets,hewinsthematchandthematchisover.Heresandt...
02014年12月18日3,864二分法
「CF497A」Removing Columns
Youaregivenann × mrectangulartableconsistingoflowercaseEnglishletters.Inoneoperationyoucancompletelyremoveonecolumnfromthetable.Theremainingpartsarecombinedforminganewtable.Forexample,afterremovingthesecondcolumnfromthetable[crayon-68737b33ab3c7944643002/]weobtainthetable:[crayon-68737b33ab3cf505223751/]Atableiscalledgoodifitsrowsareorderedfromtoptobottomlexicographically,i.e.eachrowislex...
02014年12月18日2,865贪心