下一页 »Current position : 首页 >> 最短路
PKU2019数据结构与算法实习期末考试
http://dapractise.openjudge.cn/2019finalexam2/排队[crayon-6a090b6adc41d164499054/]树状数组过线段树不过[crayon-6a090b6adc42b175288209/]线段树求最大数[crayon-6a090b6adc435772091560/]关键词搜索[crayon-6a090b6adc43f145482528/]旅行最短路[crayon-6a090b6adc44c722070355/]强连通分量[crayon-6a090b6adc45a119488032/]统计不同子串[crayon-6a090b6adc466066685480/]匹配网络流模板[crayon-6a090b6adc4b2953144027/]线性...
PKU2019数据结构与算法实习作业 11~21
题目来源：http://dapractise.openjudge.cn/2019hwall/多模式串字符串匹配模板题AC自动机模板题[crayon-6a090b6ade653703958240/]POJ3987ComputerVirusonPlanetPandora[crayon-6a090b6ade668704812187/]躲不开的病毒找自动机上的环[crayon-6a090b6ade679508702202/]POJ3691DNArepairDP，考虑前i个字符且停留在trie树上编号为j的节点时，字符串所修改的最小次数[crayon-6a090b6ade687522560569/]POJ3450Corpor...
PKU2019数据结构与算法实习模板
本文包括：并查集最短路强连通分量线段树AC自动机(Trie)网络流后缀数组POJ1182食物链如果并查集中X向Y连边长为1的边，代表X吃Y这题如果用按秩合并并查集比较好想，带路径压缩的话，需要考虑重新连边的时候，边权的设置[crayon-6a090b6adf6c9501999159/]POJ1860CurrencyExchange最短路模板[crayon-6a090b6adf6da172134541/]POJ2186PopularCows如果X喜欢Y，Y向X连边。缩点以后，计算每个强连通块的入度，唯一...
「百度之星2017」程序设计大赛 初赛(B)
好气啊突然发现复赛的时候要军训1001.Chessf(i,j)表示最后一个棋放在(i,j)的方案[crayon-6a090b6ae0252895213285/]1002.Factory把集合分为元素个数大于\(m=\sqrt{n}\)，和小等于m的对于元素个数很多的集合，每个集合bfs一次，预处理出到其它集合的距离如果询问的两个集合的元素个数都比较少，建一下虚树dp。。。我不慎误算复杂度把这里写成了记忆化搜索+暴力，结果还过了[crayon-6a090b6ae0262634534543/]1005.度度熊的交易计划预...
2017ACM萧山训练第3场(World Final 2013)
A.Self-Assembly如果一个正方形有两条边a,b则a->op(b)b->op(a)，判图中是否有环，有环则说明我们能把一些正方形绕成环然后翻折旋转变得无限大[crayon-6a090b6ae122a141959304/]C.SurelyYouCongest只有最短路相同的会互相影响按最短路分组后跑c次最大流[crayon-6a090b6ae123b897634078/]D.Factors爆搜前16个素数[crayon-6a090b6ae1252237367625/]F.LowPower二分答案贪心检验[crayon-6a090b6ae125e716401577/]H:М...
2016程序设计实习实验班免修考试(算法)
02:热血格斗场[crayon-6a090b6ae20ef752122496/]05:MPIMaelstrom[crayon-6a090b6ae20fd412866144/]06:Ultra-QuickSort[crayon-6a090b6ae2106653401104/]08:DrainageDitches[crayon-6a090b6ae210e665812268/] ...
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把一个文本...
「CF715X」Codeforces Round #372 (Div. 1)
A.PlusandSquareRoot推公式可得，可构造每次按完的数为i*(i+1)[crayon-6a090b6ae31cd533231216/]B.CompleteTheGraph给一张无向图，要求赋值一些边的边权，使得最终S到T的最短路为L用f(i,j)表示从S到点i，经过j条无边权的边的最短路选择一个最小的j，使得f(T,j)+j<=L更改这条路径上的边权，使得最短路为L，将其它无边权的边赋值为L可以证明不会产生其它的最短路似乎还可以采取一些暴力调整的做法，写起来会短一些...
2016 ACM / ICPC Asia Regional Dalian Online
1002DifferentGCDSubarrayQuery问长为n的序列，m个询问，问区间[L,R]所有子段的不同gcd值个数考虑固定左端点，随着右端点的移动，gcd至多衰减log次（每次至少折半）从n开始添加询问的左端点，用树状数组维护每个gcd右端点的最小值[crayon-6a090b6ae3992316007308/]1007FriendsandEnemiesn个人，每个人可以用m种颜色中的一部分染色自己的项链两个人是朋友当且仅当他们拥有相同的颜色敌人不拥有任何相同的颜色问对于任意一...
「小奇模拟赛2」小奇的危机
「题目背景」小奇驾驶飞船来到了一个奇怪的星球，这个星球的所以城市都在地下，而且由于环境不断恶化，星球上发生了可怕的生化危机。「问题描述」星球上有n个城市，标号为1-n，用n-1条双向通道连接，保证任意两个城市能互相到达。生化危机爆发了！但由于政府安全能力有限，安全区只包括在标号l到r的城市，小奇现在在城市x，它想知道最近的安全城市的距离。「输入格式」第一行有1个整数n。接下来n-1行，每行3个整数u，v，l，表示u，...
「省选模拟赛」[BZOJ1556] 小奇走迷宫
![「省选模拟赛」[BZOJ1556] 小奇走迷宫](http://hzwer.com/wp-content/themes/ly/image/image_post/2014-12-10_12-32-38.jpg)
原题：「bzoj1556」墓地秘密「题目背景」小奇驾驶G-1500机器人探险时落入了一个有魔法的迷宫，一旁的木牌上写着：“你可以回头，但你永远无法离去。”「问题描述」木牌下方有一行小字：“撞击所有机关墙”。G-1500机器人每次可以朝着前方光速移动，质量、动能无穷大，可以选择自己在行进中停下来或者撞墙后停下来，移动时只有转向需要花费时间。真是个诡异的迷宫，不过，小奇的眼前已经出现了迷宫的地图，它想尽早离开这里，请你...
「BZOJ2118」墨墨的等式
Description墨墨突然对等式很感兴趣，他正在研究a1x1+a2y2+…+anxn=B存在非负整数解的条件，他要求你编写一个程序，给定N、{an}、以及B的取值范围，求出有多少B可以使等式存在非负整数解。Input输入的第一行包含3个正整数，分别表示N、BMin、BMax分别表示数列的长度、B的下界、B的上界。输入的第二行包含N个整数，即数列{an}的值。Output输出一个整数，表示有多少b可以使等式存在非负整数解。SampleInput251035S...
近期评论