最小生成树Kruskal算法Kruskal算法的思想比Prin好理解一些。先把边按照权值进行排序,用贪心的思想优先选取权值较小的边,并依次连接,若出现环则跳过此边(用并查集来判断是否存在环)继续搜,直到已经使用的边的数量比总点数少一即可。证明:刚刚有提到:如果某个连通图属于最小生成树,那么所有从外部连接到该连通图的边中的一条最短的边必然属于最小生成树。所以不...

并查集 并查集,在一些有N个元素的集合应用问题中,我们通常是在开始时让每个元素构成一个单元素的集合,然后按一定顺序将属于同一组的元素所在的集合合并,其间要反复查找一个元素在哪个集合中。这一类问题近几年来反复出现在信息学的国际国内赛题中,其特点是看似并不复杂,但数据量极大,若用正常的数据结构来描述的话,往往在空间上过大,计算机无法承受;即使在空间上勉强通过,...

正文 好了,下面说正经的。 在许多浙江人看来,初赛那是世上最大的坑啊。 很多人觉得初赛跟复赛没啥关系啊,初赛不就是考考硬件嘛。 其实初赛大部分的分数都是考察你的代码能力相关联的东西的。 你有没有发现,初赛里的选择题一题才1.5分(而且最近几年初赛选择题里CCF赞歌的题越来越多了),而看程序写结果一题就8分。而问题求解一共10分,考的是数学,而且跟信息...

前言 SPFASPFA算法由于它上限 O(NM) = O(VE)O(NM)=O(VE)的时间复杂度,被卡掉的几率很大.在算法竞赛中,我们需要一个更稳定的算法:dijkstradijkstra. 什么是dijkstradijkstra? dijkstradijkstra是一种单源最短路径算法,时间复杂度上限为O(n^2)O(n 2 )(朴素),在实际应用中...

前言 P/NP/NPC问题在2012年左右曾经火了一阵,如果你做过2012年和2013年的提高组真题的话,你会发现,那两年每年都有一道这种问题的多选题。(不过之后就凉凉了),所以这类问题还是有必要了解一下的。 反正重要的知识点就这么几句话,我都划重点了,其他都是瞎扯可以无视的啦QAQ(这句不是重点啊) 零、预备内容:时间复杂度 时间复杂度分为两种:多项式级...

前置知识 1. a%b=d,c%b=e, 则(a+c)%b=(d+e)%b(正确性在此不加证明) 2. a%b=1,则(d\times×a)%b=d%b(正确性在此不加证明) 下面先看一道题(改编自曹冲养猪): 烤绿鸟的故事 题目描述: mian包是一个贪吃的孩子,这天,他买了一堆绿鸟吃。当然他的妈妈并不想让他吃太多食物(因为那样会发胖),为了避免老妈...

求乘法逆元是一个很简单的问题,特别是你掌握了扩欧求法,线性筛法之后。但是,这个问题引申出了各种的优秀想法,它也是一个模意义下的运算非常好的例子,作为一个比较简单的内容,可以说是对初学者的一扇通往模世界的大门了。 问题一:什么是乘法逆元呢? 简单来说就是这样:在\pmod p(modp)意义下,如果a*a' \equiv 1a∗a ′ ≡1,那么我们就说...

本文将给各位介绍一些无论是平时训练或者参加比赛时都比较有用的编程技巧,它们可以让我们的程序可读性更强,方便我们的调试,有些技巧甚至可以帮助我们获得更多的分数。 PS:本文已经同步发表于我的博客,欢迎各位dalao前来围观。 重载运算符 重载运算符是通过对运算符的重新定义,使得其支持特定数据类型的运算操作。 有的时候,我们构造了一种新的数据类型(高精度...

我们都知道,计算机是使用二进制进行存储和计算的。十进制的出现是因为人类有十个手指,比较方便表示十进制;而对于计算机而言,因为计算机要依靠电源,而电源只有通电和断电两种情况,所以二进制就成为了计算机的基础进制。 一道送分题 对于二进制,似乎更多的考题是在初赛,但复赛也会涉及到一些内容,而且也可以运用在生活中。 接下来介绍一下二进制数 对于二进制数,首...

快速排序由于排序效率在同为O(N*logN)的几种排序方法中效率较高,因此经常被采用,再加上快速排序思想----分治法也确实实用,因此很多软件公司的笔试面试,包括像腾讯,微软等知名IT公司都喜欢考这个,还有大大小的程序方面的考试如软考,考研中也常常出现快速排序的身影。 总的说来,要直接默写出快速排序还是有一定难度的,因为本人就自己的理解对快速排序作了下白话...

推荐阅读

 2018-11-17 14:31:12   ex_jason

最小生成树

 2018-11-10 20:40:14   ex_jason

LOL S8 决赛视频

 2018-11-10 07:41:45   ex_jason

并查集

 2018-11-10 07:28:04   ex_jason

写代码的小女孩

 2018-11-09 20:18:38   ex_jason

谈谈关于初赛的那些事

 2018-11-09 20:03:06   ex_jason

dijkstra 详解

  文章归档

ex_jason的博客"    我要留言
Catfish(鲶鱼) CMS V 4.8.39