下一页 »Current position : 首页 >> 图论
PKU2019数据结构与算法实习期末考试
http://dapractise.openjudge.cn/2019finalexam2/排队[crayon-6979604f99798758173714/]树状数组过线段树不过[crayon-6979604f997a2208767748/]线段树求最大数[crayon-6979604f997a7170623207/]关键词搜索[crayon-6979604f997ac834436244/]旅行最短路[crayon-6979604f997b4701559972/]强连通分量[crayon-6979604f997ba242200630/]统计不同子串[crayon-6979604f997c1520831027/]匹配网络流模板[crayon-6979604f997cd675380181/]线性...
PKU2019数据结构与算法实习作业 22~30
题目来源：http://dapractise.openjudge.cn/2019hwall/POJ3436ACMComputerFactory[crayon-6979604f9aebc745860985/]POJ2112OptimalMilking[crayon-6979604f9aecc143597547/]POJ1274ThePerfectStall用邻接矩阵写的[crayon-6979604f9aed7493576847/]POJ1269IntersectingLines[crayon-6979604f9aee0474521493/]POJ1569MyacmTriangles[crayon-6979604f9aee3988480022/]POJ1039Pipe[crayon-6979604f9a...
PKU2019数据结构与算法实习作业 11~21
题目来源：http://dapractise.openjudge.cn/2019hwall/多模式串字符串匹配模板题AC自动机模板题[crayon-6979604f9b913663188300/]POJ3987ComputerVirusonPlanetPandora[crayon-6979604f9b91f957353981/]躲不开的病毒找自动机上的环[crayon-6979604f9b929047686574/]POJ3691DNArepairDP，考虑前i个字符且停留在trie树上编号为j的节点时，字符串所修改的最小次数[crayon-6979604f9b930622929828/]POJ3450Corpor...
PKU2019数据结构与算法实习模板
本文包括：并查集最短路强连通分量线段树AC自动机(Trie)网络流后缀数组POJ1182食物链如果并查集中X向Y连边长为1的边，代表X吃Y这题如果用按秩合并并查集比较好想，带路径压缩的话，需要考虑重新连边的时候，边权的设置[crayon-6979604f9c427417252034/]POJ1860CurrencyExchange最短路模板[crayon-6979604f9c432129090657/]POJ2186PopularCows如果X喜欢Y，Y向X连边。缩点以后，计算每个强连通块的入度，唯一...
「CF1276X」Codeforces Round #606 (Div. 1)
A.AsSimpleasOneandTwo当存在twone时，删掉o比较好，其它情况下直接删掉two中的w和one中的n[crayon-6979604f9cb1e203377774/]B.TwoFairs把AB从图中删掉，答案是只和A相连的点个数*只和B相连的点个数[crayon-6979604f9cb2d490647666/]...
2018-2019 NOIP课件 by hzwer
分享一下这两年做的课件链接:https://pan.baidu.com/s/1DUUkwBrAE5tH1lFvNSkocQ提取码:2vfp
「CF1229X」Codeforces Round #588
A.MarcinandTrainingCamp若A觉得自己没有B强，B向A连边度数为0的点，是觉得自己比其它人都强的，把它们依此拓扑排序删除[crayon-6979604f9d03b505886924/]B.KamilandMakingaStream从一个点向上走，区间gcd单调下降，且最多变化log次可以用树上倍增维护区间gcd，枚举每个点往上二分跳，暴力统计答案更简单的做法是用vector维护一个点往上的不同gcd，以及它们贡献答案的次数，这个vector大小是logdfs暴力往儿子转移倍增：...
「CF1209X」Codeforces Round #584
A.PainttheNumbers从小到大排序以后，每次贪心的把能被最小元素整除的划分到一起[crayon-6979604f9d6cc736133263/]B.KoalaandLights因为ab都很小，枚举时间，暴力模拟灯的开关[crayon-6979604f9d6d6092875583/]C.PainttheDigits枚举一下染色成1的最大值x，则比x小的都染色成1，再从右往左，直到第一个比x小的元素出现之前，把所有等于x的元素染色成1剩下的全染色成2，check一下是否合法[crayon-6979604f9d6db530668529/]D...
「百度之星2017」程序设计大赛 初赛(B)
好气啊突然发现复赛的时候要军训1001.Chessf(i,j)表示最后一个棋放在(i,j)的方案[crayon-6979604f9e173313018561/]1002.Factory把集合分为元素个数大于\(m=\sqrt{n}\)，和小等于m的对于元素个数很多的集合，每个集合bfs一次，预处理出到其它集合的距离如果询问的两个集合的元素个数都比较少，建一下虚树dp。。。我不慎误算复杂度把这里写成了记忆化搜索+暴力，结果还过了[crayon-6979604f9e17e713949937/]1005.度度熊的交易计划预...
2017ACM萧山训练第5场(2016 Pacific Northwest – Division 1)
E.Enclosure做出大小两个凸包，即所有点的凸包和前k个点的凸包按动态凸包的思路，新加入的点会把小凸包上连续的一些点弹出，这些点是一个连续的区间相当于切掉凸包的一个角，加入一个三角形若在大凸包上顺时针枚举一个加入的点，这个区间左右端点也是顺时针转的，类似旋转卡壳切掉部分的面积顺便维护由于坐标范围较大，用double精度会炸[crayon-6979604f9ec5e651687289/]G.MaximumIslandsL的上下左右直接贪心为W然后剩下的就...
2017ACM萧山训练第4场(CTUO 2015)
D.FalconDive计算左下角的像素移动的距离，直接模拟[crayon-6979604fb922b092895331/]F.TheFoxandtheOwl贪心如果n是负数，找n最低的非9的位加1考虑在n的某一个高位减1，在之后的低位中加2如果存在多个满足的高位，取最低的一个若不存在，构造一个绝对值最小的负数[crayon-6979604fb9237848351249/]J.JumpingYoshi两个点连边的条件是\(d_y-d_x=a_y+a_x,y>x\)由于点对不超过10^6，扫一遍用map维护，把所有的边用并查集连...
2017ACM萧山训练第3场(World Final 2013)
A.Self-Assembly如果一个正方形有两条边a,b则a->op(b)b->op(a)，判图中是否有环，有环则说明我们能把一些正方形绕成环然后翻折旋转变得无限大[crayon-6979604fa89d5185601877/]C.SurelyYouCongest只有最短路相同的会互相影响按最短路分组后跑c次最大流[crayon-6979604fa89e0226962083/]D.Factors爆搜前16个素数[crayon-6979604fa89ee291133973/]F.LowPower二分答案贪心检验[crayon-6979604fa89f7694611771/]H:М...
近期评论