M_GSir-CSDN博客

原创区间DP经典三道题目

题目：NYOJ 746：http://acm.nyist.NET/JudgeOnline/problem.PHP?pid=746题意：给定一个数，要求拆成m个数相乘，求最大的结果是多少代码：#include#include#include#include#define MAX 30using namespace std;long long dp[MAX][MAX

2017-06-17 15:33:25 497

原创 java回忆篇

内部类(1) 在方法间定义的非静态内部类：● 外围类和内部类可互相访问自己的私有成员。● 内部类中不能定义静态成员变量。(2)在方法间定义的静态内部类：● 只能访问外部类的静态成员。(3)在方法中定义的局部内部类：● 该内部类没有任何的访问控制权限● 外围类看不见方法中的局部内部类的，但是局部内部类可以访问外围类的任何成员。● 方法体中可以访问局部内部类，但是

2017-06-17 14:59:48 506

原创 tensorflow demo

一、项目简介：1.项目环境：ANDROID 编译环境：androidstudio 2.2.2测试设备：armabi-v7a,测试机型为vivo x3LTensroflow环境：GPU版、Linux系统（ubuntu 16.04）2.MNIST数据集简介： MNIST是一个非常有名的手写体数字识别数据集，在很多资料中，这个数据集都会被用作深度学习的入门样例。MN

2017-06-17 14:43:58 1505

原创计算机网络总结篇

计算机网络三次握手和四次挥手 1）请求端发送一个syn段指明客户打算连接的服务器的端口，以及初始序号。2）服务器发回包含服务器的初始序号的syn报文段，同时将确认序号设置为客户的序号加1. 3）客户必须将确认序号设置为服务器的序号加1以对服务器的syn报文段进行确认 TCP提供了连接的一端在结束它的发送后还能接收来自另一端数据的能力。这就是所谓的半关闭。只有很少

2017-05-30 09:39:10 460

原创二维树状数组（poj 1195）

题目：http://poj.org/problem?id=1195题意：给出一个全0的矩阵，然后一些操作0 S：初始化矩阵，维数是S*S，值全为0，这个操作只有最开始出现一次1 X Y A：对于矩阵的X,Y坐标增加A2 L B R T：询问(L,B)到(R,T)区间内值的总和3：结束对这个矩阵的操作题解：利用二维树状数组，利用logn复杂度对

2017-02-07 22:21:07 508

原创 hdu 6012(离散+思路)

题目：http://acm.hdu.edu.cn/showproblem.php?pid=6012中文题意：这几天Lotus对培养盆栽很感兴趣，于是她想搭建一个温室来满足她的研究欲望。Lotus将所有的nnn株盆栽都放在新建的温室里，所以所有盆栽都处于完全相同的环境中。每一株盆栽都有一个最佳生长温度区间[l,r][l,r][l,r]，在这个范围的温度下生长会生长得最好，但是不一定会

2017-02-03 22:37:13 503

原创排序算法汇总三------选择类排序法

堆排序：void sift(int *d,int r,int length){ int now=d[r]; int i=r,j=2*i; bool finish=false; while(j<=length && !finish) { if(j<length && d[j]<d[j+1]) {j=j+1;} if(now

2017-02-01 23:02:33 501

原创排序算法汇总二------交换类算法

冒泡排序：void BubbleSort(int *d,int length){ bool finish=false; for(int i=1;i<=length-1&&!finish;i++) { finish=true; for(int j=0;j<length-i;j++) { if(d[j

2017-02-01 22:59:15 320

原创排序算法汇总一------插入类算法

直接插入算法：void InsSort(int *d,int length){ for(int i=1;i<length;i++) { int next=i-1; int nowdata=d[i]; while(nowdata>d[next]&&next>=0) { d[next+1]=d

2017-01-28 21:42:01 321

原创 hdu 6011

题目：http://acm.hdu.edu.cn/showproblem.php?pid=6011题意：给定n个字符，并给出每个字符的价值和数量，要求按顺序挑选出字符，组成字符串，要求得到价值最大的字符串的价值，价值的计算方法是第一个字符*1+第二个字符*2+......第i个字符*i。题解：先根据字符的价值堆字符进行排序，选择其中价值>0的字符先求和，这些一定会让价值提升，再在价值0，则

2017-01-26 22:21:35 519

原创 linux ubuntu 16.04下deb文件的安装和一些问题的解决

pkg 是Debian Package的简写，是为Debian 专门开发的套件管理系统，方便软件的安装、更新及移除。所有源自Debian的Linux发行版都使用dpkg，例如Ubuntu、Knoppix 等。以下是一些 Dpkg 的普通用法：1、sudo dpkg -i 安装一个 Debian 软件包，如你手动下载的文件。2、sudo dpkg -c 列出的内容。3、sudo dp

2017-01-16 14:46:55 9676

原创 Java 访问 access 数据库

首先先进行配置数据源（32位）：控制面板--->系统与安全--->管理工具--->ODBC数据源（32位）--->添加数据源新建一个java工程，导入一个access操作包Access_JDBC30,然后就可以进行操作了；建立连接：public static void main(String arg[]) { try { Class.forName("com.h

2016-11-22 22:47:53 574

原创字典树基础篇一（hdu 1251）

题目：hdu 1251题意：给定一堆单词，再给定一些前缀用于查询，每次输入一个前缀，就输出单词中以这为前缀的单词数题解：字典树基础代码：#include#include#include#include#includeusing namespace std;char s[15];struct Trie//字典树{ int cont; Trie *

2016-11-12 22:08:35 464

原创操作系统-------进程调度算法(C++实现)

(1) 优先数法进程就绪队列按优先数大小从高到低排列，链首进程首先投入运行。进程每执行一次，进程需要的时间片数减1、该进程的优先数减3。这样，该进程如果在一个时间片中没有完成，其优先数降低一级。接着仍是用该进程降低一级后的优先数与就绪队列中链首进程的优先数进行比较，如果仍是该进程的优先数高或相同，便让该进程继续执行；否则，调度就绪队列的链首进程投入运行。原运行过的进程按其现行优先数大小插

2016-11-10 22:45:10 6512

原创求最长连续递增公共子序列

题目：http://acm.hdu.edu.cn/showproblem.php?pid=5904题意：求最长连续递增公共子序列题解：代码：#include#include#include#include#include#include#define N 100050using namespace std;int v_a[N]; //记录第一个数字数组int v

2016-11-09 22:04:00 400

原创 hdu 4283 （区间dp）

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=4283题目大意：以下思路转自（http://www.tuicool.com/articles/jyaQ7n）当中思路已经很明确有n个男屌丝事先按1,2,3,,,,,,n的顺序排好，每个人都有一个不开心值unhappy[i]，如果第i个人第k个上台找对象，那么该屌丝男的不开心值就会为（k-1)

2016-11-03 12:13:37 589

原创 Nim游戏

题目：hdu 5795题意：给定几个堆，并告诉你每个堆的石头数量，每次可以取一堆中的任意数量不能不取，并且可以分成3堆，求最后的赢家题解：由打表可知，sg[i]={i,i-1(i%8==0),i+1(i%8==7)},只要满足每堆sg 异或和为0 就为必胜战略打表：代码：#include#include#include#include#include

2016-11-01 21:28:28 291

原创最短路变形(hdu 5521)

题目：http://acm.hdu.edu.cn/showproblem.php?pid=5521题意：两个人分别从1和n的城市出发，要求在途中的一个城市相遇并且在该城市开会，求所需要的最短时间，不一定要同时到达，可以一个人在一所城市等着另一个人，要求输出所有满足最小时间的最终开会城市。输入说明：输入t表示有多少组样例输入n，m表示有多少城市n，接下来m行输入，

2016-10-24 20:02:01 536

原创 KM算法（完备匹配下的最大权匹配）

KM算法求的是完备匹配下的最大权匹配：在一个二分图内，左顶点为X，右顶点为Y，现对于每组左右连接XiYj有权wij，求一种匹配使得所有wij的和最大。题目：http://acm.hdu.edu.cn/showproblem.php?pid=2255题意：分房子，对于n个人对n所房子有自己的最大承受价格，要求每个人分到一所房子，并且要求收入最大输入说明：输入n，代表n个人和n所房子

2016-10-24 09:22:16 2321

原创 2-sat(任意可能性输出o（n）)

该类问题算法的主要思路：1.建图（方法前面已说）2.tarjan算法、判断可行性、缩点、逆序建边（这个暂时没懂）3.拓扑排序染色4.输出具体模板见下：题目：http://poj.org/problem?id=3648题意：有一对新人结婚，邀请n对夫妇去参加婚礼。有一张很长的桌子，人只能坐在桌子的两边，还要满足下面的要求：1.每对夫妇不能坐在同一侧 2.

2016-10-23 23:02:01 728

原创 2-sat(Tarjan算法+二分)

此博客是指一类2-sat的题目，需要通过二分，将答案不断精确化判断是否存在解来得出最临近临界值的解，具体见题。题目：http://acm.hdu.edu.cn/showproblem.php?pid=3622题意：一个人在玩游戏，这个游戏的规则是每次给两个点x1，y1，x2，y2，每次只能选择其中的一个点，然后以所有选择的点为圆心做同样大小的圆，这些圆可以相切，但不可以相交，求圆半径的

2016-10-23 22:21:39 803

原创 2-sat(强连通分量求法一判断是否存在解法)

好博客链接:http://www.cnblogs.com/ambition/archive/2011/07/30/2-sat.html(内有ppt讲解、题集、论文)建图如上篇一样，主要不同是上篇利用暴力来求，但上篇可以保证按字典序最小进行输出，此处利用了比较好的算法，产生了o（m）的复杂度，应用于所有题，主要思路是利用了图的对称的原理，根据建图后可知，若存在强连通图，则其中选择了一个，其他点也

2016-10-23 21:57:55 1590

原创 2-sat(求最小字典序 hdu 1814)

2-sat:http://blog.csdn.net/swm8023/article/details/6952741,http://www.doc88.com/p-0012079707313.html2-sat 问题一般可以简化成每对（两个）元素中必须选一个，并且每对元素间有关系，比如两对元素中x1，x2和y1，y2中必须存在x1与y1矛盾，即满足选了x1必选y2，选了y1必选x2（因为每对必

2016-10-21 23:26:30 1151

原创强连通分量（强连通缩点（tarjan））+最小路径覆盖（匈牙利算法）

题目：http://acm.hdu.edu.cn/showproblem.php?pid=3861题意：王国划分区域，每个城市间的路是有方向的，要求每个区域满足：1.存在环路的必定在一个区域内。2.一个区域中的城市必定满足两两之间有一个可以到达另一个，求可以划分的区域数题解：对于第一个条件即是要求出图中的环路缩点，即用tarjan算法进行强连通分量的计算，对于第二个条件即是求最小路径覆盖

2016-10-17 22:40:20 548

原创二分匹配续（hdu 1845,hdu 2063）

题目：http://acm.split.hdu.edu.cn/showproblem.php?pid=1845题意：给一些无向的无环连线，求最大匹配题解:最大匹配，两种算法（hk算法和匈牙利算法）代码：匈牙利算法：#include#include#include#include#include#includeusing namespace std;const in

2016-10-10 23:52:29 319

原创图论之二分匹配（好博客汇总）

二分匹配好博客：http://blog.csdn.net/xu3737284/article/details/8973720,https://www.byvoid.com/blog/hungaryhttp://blog.csdn.net/thundermrbird/article/details/52231639匈牙利算法可以解决的图的问题：（二分图）1.图的最小点覆盖数 = 图的

2016-10-08 22:27:48 401

原创数位dp续（给定区间求除以某个值余数一定的dp）dfs版

题目：http://acm.split.hdu.edu.cn/showproblem.php?pid=3652题意：给定一个上限n，求在1--n中满足含有13并且可以被13整除的数的个数题解：数位dp，具体见下，不懂可参见上一篇模板代码：#include#include#include#include#includeusing namespace std;long l

2016-10-05 21:48:58 425

原创变形kmp（hdu 5918）

题目：http://acm.hdu.edu.cn/showproblem.php?pid=5918题意：给定两个字符串A，B和一个数字p，求出A中有多少个间隔为p的连续字符串与B相同输入说明：先输入测试的次数，每次测试输入三行，第一行为三个数，分别为n（字符串A的长度），m（字符串B的长度），p（间隔长度）第二行输入数组A，第三行是数组B题解：

2016-10-05 21:25:19 436

原创数位dp（dfs版）

题目：http://acm.split.hdu.edu.cn/showproblem.php?pid=3555题意：给定一个上限n，求1--n中存在多少个数，数中含有49题解：dfs数位dp，此题一共三种状态：st：0：前一个数为4的状态，此位加9就可满足题意；1：前面数字中已经含有49；2：前面中没有49并且前一位不是4状态转移：状态49其他数字

2016-09-22 09:34:28 494

原创超大01背包（hdu 5887）

题目：http://acm.hdu.edu.cn/showproblem.php?pid=5887题意：01背包，就是收集草药，每个收集和整理的过程需要时间，整理收集完一个草药会获得一定的分数，要求在限定时间内整理和收集的草药得到的分数最高，就是数据范围有点大，到10的9次方题解：范围太大，不能用一般的数组存下，10的9次方，内存会爆，可以采用减少内存的办法，即是每次记录可以达到的重量

2016-09-17 19:22:23 1370

原创并查集（hdu 5441）

题目：http://acm.split.hdu.edu.cn/showproblem.php?pid=5441题意：给定一些城市，城市间带距离的路连接，一个懒人要去旅游，带不想走太远，给定一个最大忍耐距离，要求他去的城市间不能超过这个距离，a-->b算一条，反过来也算，如果3个城市联通的，那他可以去的城市为3*2=6，不联通的不算一起，分开算相加题解：先根据输入的查询和边距进行排序，从小到

2016-09-17 10:54:36 423

原创拓扑排序（栈模拟）+dfs（hdu 5438）

题目：http://acm.split.hdu.edu.cn/showproblem.php?pid=5438题意：有一些带权的池塘,池塘间用管道连接，要求去掉剩下池塘中度数题解：先利用拓扑方法，利用栈，将所有度数代码：#include#include#include#include#include#includeusing namespace std;int va

2016-09-17 10:30:49 926

原创 rmq-st算法<区间最大最小>(hdu 5875)

题目：http://acm.hdu.edu.cn/showproblem.php?pid=5875题意：给定一个数组，并给出[l，r]，要求求出A（l）%A（l+1）%......%A（r）的值，当l==r时直接等于A（l）题解：这道题的意思就是每次找到区间内最靠近l的且比当前ans小的进行取模，每次都这么取，知道到r，可以利用rmq算法先用o（nlogn）进行预处理，然后查找时的复

2016-09-16 11:47:18 337

原创树状数组+dfs（hdu 5877）

题目：http://acm.hdu.edu.cn/showproblem.php?pid=5877题意:给定一棵树（带根），定义weak pair 为1.u为v的祖先，2.a(u)*a(v)题解：先用map对a进行离散化处理，因为总共10W的点，但数据表示范围很大，树状数组完全存不下，所以要离散化，然后找出根结点，从根结点遍历子节点，每次遍历的时候先统计之前加入的满足a（u）

2016-09-16 11:30:38 378

原创模拟优先队列（hdu 5437）

题目：http://acm.hdu.edu.cn/showproblem.php?pid=5437题意：一个派对，每次开一次门，开m次门，每次开门选择一定数量的人进来，先进来的满足带的礼物价值最大，当价值相同时要求来的早的人先进，最后一次全都可以进，给定查询，问第几个进去的人的名字。题解：用优先队列模拟门口的情况，每次取出最符合条件的人进行标记代码：#include#incl

2016-09-12 23:29:34 403

原创离线记录+树状数组（hdu 5869 统计任意区间的不同gcd值）

题目：http://acm.hdu.edu.cn/showproblem.php?pid=5869题意：给定一个数组，给出范围[l,r],求在这范围内的不同gcd值得个数（连续下标）题解：用o(nlogA)计算出gcd值并进行记录，每次固定右值，枚举前一个得出的gcd值，记录左边的坐标和不同gcd值，然后用树状数组维护，具体见注释代码：#include#include#in

2016-09-12 23:26:17 543

原创背包问题（01背包 + 完全背包 + 多重背包）

背包九讲：https://yunpan.cn/cMTIQHeafPeBH 访问密码 1e4f01背包问题：题目：http://poj.org/problem?id=3624题意：相当于给定n个价值为v[i],重量为w[i]的东西，求在不超过最大重量的情况下的最大价值，输入说明：先输入物品数n和最大重量m 然后输入n行，表示第i物品的重量和价值题解：01背包代码：

2016-09-07 21:05:55 539

原创深度优先搜索dfs（poj 1655）

题目：poj 1655题意：给定一个树状图，要求去掉一个节点，得到几个子树，并且规定这些子树中拥有的最大节点的子树的节点数为去掉该节点的平衡值，求该平衡值最小为多少，并且求出此时去掉的是哪个点，当平衡值相当时要求去掉的点的序号最小题解：建树，再进行一次深度优先搜索，找出该点的各个子树中有多少节点，取最大值，当然题目中是无向连接，所以要考虑双向，要用一个数组表示该点事前有没考虑代码：

2016-09-02 20:45:29 454

原创树状数组+离散化（hdu 5862）

题目：hdu 5862题意：给定几个线段，求有多少个线段的交点，输入解释：第一行表示测试数据，第二行表示有多少条线段，第三行开始是每个线段的两点坐标题解：树状数组+离散化（Y坐标太大，要压缩存储空间，采用离散化），先用map对y坐标进行离散化，再将与x轴平行的线段拆成两个点，一个是记录起点x坐标，一个记录末点x坐标+1（这样就可保证末点相交被记录进去，方便），与y轴平行的只要记录x坐标和两

2016-09-02 10:23:53 428

原创 AC自动机（hdu 2896 hdu 3065）

题目：hdu 2896题意：中文题目，可自己理解，简单说就是给定一些子字符串，再给出一些母字符串，找出母字符串中包含哪些子字符串题解：AC自动机模板题代码：动态申请：#include#include#include#include#include#include#define MAX 59999using namespace std;struct Node{

2016-09-02 10:05:47 305

MusicPlayer

空空如也