对于一个图,我们可以用一个度序列来表示这个图。首先理解一个概念，什么是度。 在有向图中： 入度就是：某个顶点作为终点的次数和。 出度就是：某个顶点作为起点的次数和。 在无向图中： 度就是：某个顶点的边数    所以一个图必然可以写出一个度序列（如果顶点没有先后顺序，那么度序列不唯一），给定一个合法的度序列，也可以画出一个或多个图。那么怎样判断一个度序列是否合法并且画出一种可能的图呢？这就需要Havel-Hakimi算法。下面简单介绍下。    首先对于一个度序列，如果某个度比总点数还多，那么这个度序列一定不合法，比如给定三个点，某个点的度最大为2（与其他两个点相连），如果度大于2，那么一...

   一道入门级别的贪心，对于每种作业，最理想的情况是刚好在截止日期完成，然后之前的日子就可以给别的作业。然后尽可能先写分数高的，再写分数低的。我们首先把作业按照分数从高到低排序，如果分数相同，那么截止日期靠前的排在前边。然后从前向后遍历，如果某个作业在截止日期当天没有其他作业安排，那么就在这天完成，否则就要向前寻找空闲的天，如果都找不到，那这么作业就无法完成了，只能扣分，可以用一个一维数组标记某天有没有作业安排。 #include<bits/stdc++.h> using namespace std; struct Node{ int e,s; }node[1005]; ...

   大整数，超过c++ longlong范围的一些数字，可以使用Java自带的大数类进行运算，或者使用字符串进行模拟加减法，这里说一下使用c++字符串进行模拟加减法。  加法    对于加法，首先使用字符串将两个大数读进来，这里注意一下，由于最高位是第一个读进来的数字，所以最高位是首位。如果使用字符数组的话，建议逆置一下。链表的话就没有必要了。然后我们就需要将两个大数进行逐位相加，本人不建议在逐位相加时处理进位，最后处理进位，相加完之后，在从末尾开始处理进位，对于大于10的数字，想前一位进一。(这里简单用数组演示一下):    然后需要从最低未开始向高位处理进位，按照逢十进一的原则处...

   在一个8x8的表格中，起始点任意，且马只可以走日字，要求使用非递归程序给出一种能够走遍棋盘上所有点的一种走法。     由于是数据结构的作业，并且在栈那一章，且要求使用非递归，明显要求是使用深搜，自己起初便写了个深搜(最简单的那种，结果时间复杂度过高，要好几分钟才可以跑出结果)，后来便是用了贪心优化，然后秒出结果。    首先对于最简单的暴力来说，十分的不可行。因为对于棋盘上每个点，都可以拓展出8个点(如果不考虑出界问题的话)，这样就形成了一个八叉树，深度为64。如果考虑最坏的情况，那么大约需要次操作，而且实际操作次数必然会大于这个数。对于计算机每秒千万级别的运算来说，还是小巫见大巫，所...

   全排列，即数学中的排列，一个集合中所有可能的排列方式。比如，{1，2，3}的全排列有{1，2，3}，{1，3，2}，{2，1，3}，{2，3，1}，{3，1，2}，{3，2，1}六种排列方式。STL中提供了专门的全排列函数，但该函数只能按升序或者降序排列，即字典序。主要有两个函数，next_permutation和prev_permutation。     头文件：#include <algorithm>    （1）next_permutation，按照升序进行全排列，参数有两个，需要全排列的数组首地址和数组尾地址。返回类型bool型，成功true，失败false。且该函数...

   简单说下题意，给定一个数字串，问有多少的子串可以被3整除。    首先一个数如果可以被3整除，那么这个数各位和一定可以被3整除。所以这个题应该是线性dp，我们定义dp[i][j]为前i个中整除3余数为j（只有0，1，2三个数）的个数，然后从头到尾线性dp一遍就可以了。    下面看一下代码： #include<bits/stdc++.h> using namespace std; const int mod=1e9+7; int main(){ string t; cin>>t; int len=t.length(); int dp...

   简单说下题意，给定两个有若干的括号的序列s和t，问可否在s中删除若干括号对后(或者不删除)，使得s序列成为t序列。    看了好多题解，思想就是动态规划，我们需要定义dp[i][j][k],dp是bool类型即可，表示序列s在前i个并且删除掉k个左括号 ‘(’ 的情况下，可以与序列t的前j个匹配，如果删除了一个括号对，那么k就要相应的减一，所以最终判断的条件就是dp[len1][len2][0]是否为0，就是表示在恰好删除若干括号对的情况下相匹配。    所以说在状态dp[i][j][k]=true的情况下，对于两个串的下一个字符，只有以下四种情况：    对于第一种情况，可以推出d...

   折腾了差不多两天，终于安装好了Linux(Ubuntu)，并且配置好了环境，自己趟了不少雷，也看了好多博客，这里自己也总结一下，也给大家排排雷。    对于虚拟机呢，现在有很多选择，包括win10自带子系统Ubuntu，不过自带子系统图形界面很难搞，搞了效果也不是很让人满意，所以还是推荐自己装虚拟机。对于虚拟机我强烈安利VM WorkStation；下载地址如下（可能网速有点慢，本人第一次下载了5个小时）： https://my.vmware.com/en/web/vmware/info/slug/desktop_end_user_computing/vmware_workstation...

话不多说，吹爆这个模板，直接上代码： #include<iostream> #include<sstream> #include<algorithm> #include<cstring> #include<iomanip> #include<vector> #include<cmath> #include<ctime> #include<stack> using namespace std; struct Wint:vector<int>//用标准库ve...

   首先看一下题意：有一串数字，要求在这串数字中加入k个乘号，使得乘积最大。比如在1231中加入两个乘号，最大的就是。这个题是一道比较基础的动态规划题目，下面说一下我自己的理解。    我们令dp[i][j]表示前i个数中加入j个乘号的最大值，用num[n][m]表示这串数中从n到m的数值，可以提前预处理下。这里我们让乘号递增，让乘号作为最外层循环。那么我们可以得到状态转移方程:，其中k从j开始，一直加到len-1（字符串长度），因为我们每次多加入一个乘号，就意味着要多一个数字，这个数字必然包括最后一个数字，也就是说这个数字的结尾是确定的，就是i，而开头不确定，所以遍历所有可能的开头位置，找...

   自己之前一直使用邻接矩阵存图，很容易理解，一直听说过邻接表的存图法，但一直没有用过，后来才用了，这里简单说一下。    为什么要使用邻接矩阵，我个人的理解就是对于稀疏图，使用邻接矩阵太浪费空间，遍历也浪费时间，所以就要使用邻接表。这里就说一下我个人的一些理解。    邻接表的存的是边，对边进行编号，1号边，2号边，3号边.....再在每条边上记录边的顶点以及权值等信息。以下图为例     默认各个边权值均为1，添加顺序为 1 2，1 4，1 3，3 4，2 4。依次为1号边，2号边，以此类推。我们记录下了边，还要记录下顶点等信息。    首先我们需要一个head数组，来记录由某一个顶...

   简单说一下题意，给一个矩阵，矩阵上绝大多数数字为0，其余一些数字不为0（为正整数），找出两条条从左上角到右下角的路径，使得数字最大，每条路径只可以向右和向下，且第一条路径走过后，数字变为0。    自己起初隐隐感觉是动态规划，后来也不知道怎么搞，后来看了题解，才恍然大悟，这里说一下自己的理解。    既然是两条路径，我们不妨让两条路径同时出发，假设第一条路径走到了点A(i,j),第二条路径走到了点B(k,l),既然是两条路径同时出发，我们令dp[i][j][k][l]为第一条路径走到A点，第二条路径走到B点的最大值。由于只有两个行走方向，易得:    dp[i][j][k][l]=max...

   题意就是给n个数，你需要按顺序求出每一项和其他项差的平方和。    自己刚开始开始无脑暴力，结果可想而知，TLE，后来推了一下公式，发现好简单。    下面简单写一下(比较简单的数学推理)：    设第i个数字为 ，那么                 这样计算起来就方便多了，提前预处理一下就好了

先简单介绍一下题意：    大意就是给你一个只含有0和1的字符串，找出一种分割方法，使得每个分割出的字符串都是在该字符串自循环节中最小的，什么叫该字符串自循环呢？比如0001自循环就会产生0010，0100，1000，110010自循环就会产生100101，001011，010110，101100，011001，110010.说白了就是后一个数到前一个数的位置，然后前一个数到最后边。你要使得分割次数尽量的少，且每一个分割出的串都要是本身自循环串中最小的。 下面说一下我的思路(其实是菜鸡看了标程)，说一下自己的理解：   首先看一下数据范围，题目中的保证每个01字符串的长度都不会超过200，所...