HDU5922 - Minimum’s Revenge(2016CCPC东北地区大学生程序设计竞赛A题)
Minimum’s Revenge 因为边权是两个数之间的lcm，而对于所有的数，1和任意数的lcm都是最小的，故只需要求2 + 3 + 4 + 5 + ...... + n即可
Read moreCodeforces Round #544 (Div. 3)
A - Middle of the Contest 这没什么好说的了吧......
Read more
HDU2647 - Reward
Reward 其实就是用拓补排序判一下环，但需要注意两点：一是反向建图。这主要是为了计算奖金时的方便，因为反向建图就可以从奖金最少的那个人出发，遍历整个图，逐步累加得到答案；如果是正向建图，则需要先找到奖金最少的那个人，将他作为起点......二是这道题其实是根据每个点(人)在图中的深度来确定每个点(人)的奖金的。已下图为例： 3和4的深度是一样的，所以两者的奖金也一样。因此，不能简单地认为，如果可以拓补排序了，答案就是888 + (n * (n - 1)) / 2 代码如下: #include <cstdio> #include <iostream> #include <cstring> #include <cmath> #include <a..
Read moreHDU1811 - Rank of Tetris
Rank of Tetris 根据题单的提示，这是一道拓补排序+并查集的题目，然而我并不会拓补排序......所以这里先写一下拓补排序相关的东西吧...... 首先，拓补排序是对一系列有先后顺序的“活动”的排序。何为“有先后顺序的‘活动’”？举个例子，假如现在某人要穿衣服，那他必须要先穿内衣再穿中间的毛衣，最后再穿外套。拓补排序就是使用有向无环图(DAG)来对这些有先后顺序的活动进行排序，得到一个可行的顺序。对于同一系列的活动，可能有多于一种顺序可以使他们满足拓补排序。这跟穿衣服时可以先穿裤子再穿毛衣然后再穿外套，也可以先穿毛衣再穿裤子然后穿外套是一样的。 拓补排序的实现：先找出入度为0的点，然后将这个点以及与这个点相连的边删除，并将与这个点直接相连的点的入度都减一。再找出当前入度为0的点，重..
Read more
【C++学习笔记】虚函数(虚方法)
介绍 对于一个派生类以及他的基类，若两者都有一个相同名字的方法，但这两个方法的实际行为并不相同，那应将这个方法声明为虚方法(virtual)。原因在于，如果方法是通过引用或指针调用的，在不声明位虚方法的情况下，程序将根据引用类型或指针类型确定使用的是具体哪个方法。而声明为虚方法，程序将根据引用或指针具体所指向的对象的类型来调用方法 e.g. 使用引用来调用方法 首先是不使用虚函数的情况 #include <iostream> #include <cstdio> #include <cstring> #include <string> #include <cctype> using namespace std; class Human{ ..
Read more
【C++学习笔记】关于继承，基类与派生类
一、概念 继承：继承是C++中的一种机制，通过这种机制，我们可以基于已有的旧的数据类型创建出新的数据类型。在C++中，继承分三种:公有继承(public)，私有继承(private)，保护继承(protected)。不同的继承类型在在访问权限上会有区别。 基类：即被继承的类。 派生类：即由一个已有的类派生过来的新的类。 二、继承 1)公有继承(public) 公有继承指的是基类的公有成员和保护成员保持不变，但派生类无法直接访问私有成员，需要通过基类的公有成员函数或友元函数访问。 2)私有继承(private) 私有继承指的是，在派生类中，基类的公有成员和保护成员都成为了派生类的私有成员，且这个派生类的派生类(子类)无法访问。 3)保护继承(protected) 保护继承是指基类的公有..
Read moreHDU4133 - StrangeStandard
StrangeStandard 一道反素数的题目，求的是区间内的最大反素数。一开始做我是打表的(而且这表还不是自己打出来的),代码如下:
Read moreUVA294 - Divisors
Divisors 题意是说算一个区间内的因子数最大的数。网上题解大都是用的dfs，但我又不想写dfs······然后看了一下，区间长度最长才1e4，用质因数分解求出区间内每一个数的因子数然后用最朴素的方法找出答案应该也能过吧······事实证明真的可以，而且只用了40ms 2333333。 这里做个笔记，所谓质因数分解求因子数，指的是，对于一个数x,必定存在以下式子: x = (a1^p1)*(a2^p2)*(a3^p3)*(a4^p4)*···*(an^pn)(其中,a1,a2,···，an均为质数) 那么,x的因子个数则为: sum(x) = (1+p1)*(1+p2)*(1+p3)*(1+p4)*···*(1+pn)..
Read morePOJ2891 - Strange Way to Express Integers
Strange Way to Express Integers 拓展中国剩余定理的模板题，但我并看不懂模板OTZ(过段时间会补上个人理解，先把代码放这)
Read more欧拉路、欧拉回路与Fleury算法
一、概念解释 欧拉路：给定无孤立结点图G，若存在一条路，经过图中每边一次且仅一次，该条路称为欧拉路。 欧拉路的存在条件：没有孤立结点，同时奇数度数的点只有2个或0个。 欧拉回路：若一个连通图中没有奇数度数的点，则该图中一定存在一条起点与终点重合的欧拉路，称为欧拉回路。 通俗地讲，欧拉路就是一笔画游戏，每条边只能走一次，问怎么画才能把所有边都画出来。欧拉回路就是在此基础上，不仅要把所有边都画出来，还要求起点和终点要是同一个地方。 二、判断欧拉路是否存在 要判断欧拉路是否存在，只需要判断奇数度数的个数即可。一般使用并查集来实现。代码如下： //判断欧拉路是否存在 #include <iostream> #include <cstdio> #include <cstrin..
Read more