dijkstra - hzwer.com

2016 ACM / ICPC Asia Regional Qingdao Online
大部分都是队友写的代码QAQ我主要是填坑个题解1001ICountTwoThree定义『ICountTwoThreeNumber』为\(2^a3^b5^c7^d\)问超过n的最小的这种数字显然这样的数字数量是很少的，其质因数个数不会超过30个dfs出所有数字，二分查询1002Cure求\(\sum\limits_{k=1}^n\frac{1}{k^2}\)\(\lim_{n\rightarrow\infty}\)\(\sum\limits_{k=1}^n\frac{1}{k^2}=\frac{\pi^2}{6}\)n超过十几万之后就达到精度上限1003FamilyView把一个文本...
12016年10月8日4,138哈夫曼树,最小割,STL,dijkstra,深度搜索,二分法,AC自动机,欧拉图,记忆化搜索

「CF715X」Codeforces Round #372 (Div. 1)
A.PlusandSquareRoot推公式可得，可构造每次按完的数为i*(i+1)[crayon-5df3b5492f483679065263/]B.CompleteTheGraph给一张无向图，要求赋值一些边的边权，使得最终S到T的最短路为L用f(i,j)表示从S到点i，经过j条无边权的边的最短路选择一个最小的j，使得f(T,j)+j<=L更改这条路径上的边权，使得最短路为L，将其它无边权的边赋值为L可以证明不会产生其它的最短路似乎还可以采取一些暴力调整的做法，写起来会短一些...
02016年9月19日2,216dijkstra,构造
「小奇模拟赛2」小奇的危机
「题目背景」小奇驾驶飞船来到了一个奇怪的星球，这个星球的所以城市都在地下，而且由于环境不断恶化，星球上发生了可怕的生化危机。「问题描述」星球上有n个城市，标号为1-n，用n-1条双向通道连接，保证任意两个城市能互相到达。生化危机爆发了！但由于政府安全能力有限，安全区只包括在标号l到r的城市，小奇现在在城市x，它想知道最近的安全城市的距离。「输入格式」第一行有1个整数n。接下来n-1行，每行3个整数u，v，l，表示u，...
02016年5月22日2,507STL,dijkstra,分块
「BZOJ2118」墨墨的等式
Description墨墨突然对等式很感兴趣，他正在研究a1x1+a2y2+…+anxn=B存在非负整数解的条件，他要求你编写一个程序，给定N、{an}、以及B的取值范围，求出有多少B可以使等式存在非负整数解。Input输入的第一行包含3个正整数，分别表示N、BMin、BMax分别表示数列的长度、B的下界、B的上界。输入的第二行包含N个整数，即数列{an}的值。Output输出一个整数，表示有多少b可以使等式存在非负整数解。SampleInput251035S...
02015年7月5日4,336STL,堆,dijkstra
「CF545X」Codeforces Round #303 (Div. 2)
A.ToyCars模拟[crayon-5df3b54930196492172460/]B.EquidistantString[crayon-5df3b549301a0584836988/]C.Woodcutters给n棵树在一维数轴上的坐标，以及它们的高度。现在要你砍倒这些树，树可以向左倒也可以向右倒，砍倒的树不能重合、当然也不能覆盖其他的树原来的位置，现在求最大可以砍倒的树的数目。题解第一棵树的左边和最后一棵树的右边没树，所以他们向两边倒，然后对于中间的树来说，首先先向左边倒，然后左边...
12015年5月20日1,940模拟,贪心,STL,dijkstra
「BZOJ3931」[CQOI2015] 网络吞吐量
题意即题解最短路+网络流1A了赞233[crayon-5df3b549308c0188529755/]
82015年4月7日3,071STL,dijkstra,最大流
「BZOJ1922」[SDOI2010] 大陆争霸
Description在一个遥远的世界里有两个国家：位于大陆西端的杰森国和位于大陆东端的克里斯国。两个国家的人民分别信仰两个对立的神：杰森国信仰象征黑暗和毁灭的神曾·布拉泽，而克里斯国信仰象征光明和永恒的神斯普林·布拉泽。幻想历8012年1月，杰森国正式宣布曾·布拉泽是他们唯一信仰的神，同时开始迫害在杰森国的信仰斯普林·布拉泽的克里斯国教徒。幻想历8012年3月2日，位于杰森国东部小镇神谕镇的克里斯国教徒发动起义。幻想...
22014年12月22日3,805STL,dijkstra
NOI2010海拔
DescriptionYT市是一个规划良好的城市，城市被东西向和南北向的主干道划分为n×n个区域。简单起见，可以将YT市看作一个正方形，每一个区域也可看作一个正方形。从而，YT城市中包括(n+1)×(n+1)个交叉路口和2n×(n+1)条双向道路（简称道路），每条双向道路连接主干道上两个相邻的交叉路口。下图为一张YT市的地图(n=2)，城市被划分为2×2个区域，包括3×3个交叉路口和12条双向道路。小Z作为该市的市长，他根据统计信息得到...
02014年12月17日2,006STL,最小割,dijkstra
「BZOJ4016」[FJOI2014] 最短路径树问题
cxjyxx_me:先求一个最短路图然后再这个图上dfs对于一个点的所有出点按编号从小到大dfs这样可以保证dfs树就是题目要求的树然后在这棵树上跑树分治f[i][j][2]表示前i棵子树从根出发链长为j[0：最长长度][1:这个长度条件下的方案数]对于第i+1棵子树单独跑一个f’[i][j][2]意义一样枚举这颗子树上链长和f一起更新答案然后用f‘更新f[crayon-5df3b54931ede903330042/] ...
52014年12月15日5,109STL,dijkstra,点分治
「BZOJ2407」探险
Description探险家小T好高兴！X国要举办一次溶洞探险比赛，获奖者将得到丰厚奖品哦！小T虽然对奖品不感兴趣，但是这个大振名声的机会当然不能错过！比赛即将开始，工作人员说明了这次比赛的规则：每个溶洞和其他某些溶洞有暗道相连。两个溶洞之间可能有多条道路，也有可能没有，但没有一条暗道直接从自己连到自己。参赛者需要统一从一个大溶洞出发，并再次回到这个大溶洞。如果就这么点限制，那么问题就太简单了，可是举办方又...
12014年11月27日2,422STL,dijkstra
「BZOJ2259」[Oibh] 新型计算机
DescriptionTim正在摆弄着他设计的“计算机”，他认为这台计算机原理很独特，因此利用它可以解决许多难题。但是，有一个难题他却解决不了，是这台计算机的输入问题。新型计算机的输入也很独特，假设输入序列中有一些数字（都是自然数——自然数包括0），计算机先读取第一个数字S1，然后顺序向后读入S1个数字。接着再读一个数字S2，顺序向后读入S2个数字……依此类推。不过只有计算机正好将输入序列中的数字读完，它才能正确处...
02014年11月25日2,225STL,dijkstra
「BZOJ1665」[Usaco2006 Open] The Climbing Wall 攀岩
DescriptionOneofthemostpopularattractionsatthecountyfairistheclimbingwall.Bessiewantstoplanhertripupthewallinadvanceandneedsyourhelp.Thewallis30,000millimeterswideandH(1001<=H<=30,000)millimetershighandhasF(1<=F<=10,000)hoof-holdsatuniqueX,Ycoordinatesexpressedinmillimeters.0,0isatthegroundlevelontheleftsideofthewall.Hoof-holdsareseparatedbyatleast300millimeterssincenocowcan...
02014年10月29日2,013STL,dijkstra