- 博客(75)
- 收藏
- 关注
RSS订阅
原创 DP的见解
这个可以根据你的动归的状态划分阶段，所谓的阶段就是每个状态它由哪些状态转移过来时，这两者的差别，通过状态推导转移再划分阶段，这大概就是基本的动归思想吧，滚动数组其实就是为了优化动归的空间的，有些状态的解虽然由前面转移过来但是我们没有必要将其保存起来，因为我们只需要最终的答案，这样就可以优化，降低DP的空间复杂度，因为动归就是个用空间换时间的典型嘛，但是空间也是有限的。实际一点就是我们每次
2016-11-30 21:57:10
211
原创 滚动数组
01背包 有N元求取K件是的w[i]*v[i]和最大#include<bits/stdc++.h>using namespace std;typedef long long LL;const int maxn = 30000 + 10;int n,m;int v[maxn];int p[maxn];int dp[maxn];///用dp[i]表示花费i元的最优解。void solve()
2016-11-30 21:31:11
246
转载 题意就是让我们找一个数只能有三个约数，很明显素数有两个，那么容易找到规律，这个数只能有着三个约数。1和自己还有sqrt(n)。sqrt(n)自然要是素数
题意就是让我们找一个数只能有三个约数，很明显素数有两个，那么容易找到规律，这个数只能有着三个约数。1和自己还有sqrt(n)。sqrt(n)自然要是素数。 #include<bits/stdc++.h>using namespace std;const int maxn=400;const int max1=100000+10;bool vis[maxn];int a[max1];in
2016-11-29 13:35:04
344
原创 2016大连网络赛1006
有N 支球队. 每只球队之间两两踢球, 赢得加2分, 平手各加1分, 输的不得分. 现在告诉你每只球队最后的分数, 问这个分数序列是否正确.#include<iostream>#include<cstdio>#include<algorithm>#include<cstdio>#include<queue>#include<map>#include<set>#include<stack
2016-09-10 21:45:27
472
原创 UVALive 3523 圆桌骑士
题目大意：有n个骑士经常举行圆桌会议，每次圆桌会议至少要有3个骑士参加(且每次参加的骑士数量是奇数个)，且所有互相憎恨的骑士不能坐在圆桌旁的相邻位置，问有多少个骑士不可能参加任何一个会议思路,首先根据给出的憎恨图得出补图，然后就是找出不能形成奇圈的点利用下面二个定理：1.如果一个双连通分量的某些顶点在一个奇圈中(即双连通分量含有奇圈)，那么这个双连通分量的其他顶点也在这个奇圈中2.如果一个双连
2016-09-02 15:26:59
416
原创 usaco 01串 Stringsobits
题目背景 考虑排好序的N(N<=31)位二进制数。 题目描述他们是排列好的，而且包含所有长度为N且这个二进制数中1的位数的个数小于等于L(L<=N)的数。你的任务是输出第i（1<=i<=长度为N的二进制数的个数）小的（注：题目这里表述不清，实际是，从最小的往大的数，数到第i个符合条件的，这个意思），长度为N，且1的位数的个数小于等于L的那个二进制数。（例：100101中，N=6，含有位数为1的个
2016-08-29 09:13:30
499
原创 USACO/stamps
/* TASK:stamps LANG:C++ */includeincludeincludeincludeincludeincludeusing namespace std;typedef long long LL; const int maxn = 100; const int INF = 0x3f3f3f3f; const int N = 2e6 + 10;int a[maxn]
2016-08-28 12:44:51
400
原创 POJ3320
尺取法做，在某个区间[s,t]已经覆盖了所有的知识点的情况。 有了如下的等价关系，所有的知识点被覆盖等价于每个知识点出现的次数不少于1.附上代码。#include<iostream>#include<cstdio>#include<queue>#include<set>#include<algorithm>#include<map>using namespace std;const
2016-05-13 12:15:06
316
原创 POJ3061
http://poj.org/problem?id=3061先说一种nlogn的算法，预先以O(N)的时间计算好sum,二分搜索，序列和不小于的结尾T的最小值。#include<iostream>#include<algorithm>#include<cstdio>#include<queue>#include<cstring>using namespace std;const int
2016-05-13 09:00:55
479
原创 POJ1064
http://poj.org/problem?id=1064题意：知道N段电缆的长度，从他们中切割出K条长度相同的电缆，求最大可以切多长，答案保留2位小数。二分搜索。#include<iostream>#include<cstdio>#include<algorithm>#include<queue>#include<cmath>using namespace std;const in
2016-05-11 20:53:51
532
原创 noi2010超级钢琴
优先队列+st#include<iostream>#include<cstdio>#include<queue>#include<algorithm>#include<cmath>using namespace std;typedef long long ll;const int INF=1E9;const int maxn=5e5+10;int n,k,minlen,maxlen
2016-05-11 13:27:17
394
原创 NOI能量采集
http://www.lydsy.com/JudgeOnline/problem.php?id=2005这道题第一个想到了一种解法，和挑战上求线段的格点数一样，只要求出gcd(x-0,y-0)-1就是当前点的于（0，0）点的格点数，于是这里只要枚举x,y即可求解。。80的算法。。对于数据大的会超时。。下面先附上算法。#include<iostream>#include<cstdio>#incl
2016-05-10 11:30:08
961
原创 POJ2395最小生成树水
题意是从1号点出发最短路遍历所有点求其中最长的边。 思路，很明显是最小生成树问题，用kruskal去做每次更新最大边即可。 附上代码。#include<iostream>#include<cstdio>#include<algorithm>#include<queue>using namespace std;const int maxn=1e4+10;const int maxa=2
2016-05-07 09:06:54
446
原创 spring data jpa 快速使用
依赖maven依赖<dependency> <groupId>org.springframework.boot</groupId> <artifactId>spring-boot-starter-data-jpa</artifactId></dependency>...
2018-04-28 17:26:32
356
原创 leetcode 超过经理收入的员工
Select e1.Name as Employee from Employee e1 , Employee e2 where e1.ManagerId = e2.Id and e1.Salary > e2.Salary或者使用join# Write your MySQL query statement belowSelect e1.Name as Employee from...
2018-03-27 10:34:39
3676
原创 leetcode 第二高薪水
直接查询如果不存在第二高的Salary不会返回值，所以应该用子查询select (select distinct Salary from Employee order by Salary desc limit 1,1) as SecondHighestSalary也可以用IFNULL ifnull(exr1,exr2) 如果exr1是null那么返回exr2否则返回exr1sel...
2018-03-27 10:19:16
506
原创 leetcode-db 组合两个表
直接使用Left join 。如果使用where的话如果右表不存在匹配的行，那么不会返回数据，所以用Left join。select p.FirstName, p.LastName, a.City,a.State from Person p left join Address a on p.PersonId = a.PersonId...
2018-03-27 09:41:10
1086
原创 spring data jpa 学习整理
Spring Data Jpa依赖maven依赖<dependency> <groupId>org.springframework.boot</groupId> <artifactId>spring-boot-starter-data-jpa</artifactId>...
2017-12-29 13:47:47
3090
原创 mysql基础语法
mysql登陆 mysql -u root -p创建数据库 create database 数据库名； create database 数据库名 character set gbk;中文显示数据库 show databases;选择数据库 use 数据库名；建表 create table 表名（）；显示表show tables;向表中插入数据 插入全部数据 insert into 表名
2017-08-28 09:13:49
261
原创 ros服务学习
服务之前讨论的是消息如何在节点之间传递服务和消息调用的 区别是 服务调用 是双向的，一个节点给另一个节点发送信息并等待响应，因此信息流是双向的。而消息发布后就没有响应的概念，甚至不能保证有订阅。服务调用实现的是一对一的通信。每一个服务由一个节点发起，对这个服务的响应返回同一个就节点，另一方面，每一个消息都和一个话题相关，这个话题可能有很多的发布者和订阅者。服务的过程其实就是一个客户端节点发
2017-06-29 15:56:22
392
原创 ros学习笔记，有错，后期陆续修正，菜鸡学习笔记 makedown代码
启动小乌龟的命令source /opt/ros/indigo/setup.bash然后分别在三个终端下命令三段命令启动节点管理器 roscorerosrun turtlesim turtlesim_node 打开仿真器rosrun turtlesim turtle_teleop_key 控制方向 功能包/软件包turtlesim_node和turtle_teleop_key都属于tur
2017-06-29 15:06:12
588
原创 ros基础部分 之后分章节做笔记（弱鸡，有些错误的地方后续修正）
启动小乌龟的命令source /opt/ros/indigo/setup.bash然后分别在三个终端下命令三段命令启动节点管理器 roscorerosrun turtlesim turtlesim_node 打开仿真器rosrun turtlesim turtle_teleop_key 控制方向 功能包/软件包turtlesim_node和turtle_teleop_key都属于tur
2017-06-29 15:02:35
758
原创 欢迎使用CSDN-markdown编辑器
启动小乌龟的命令source /opt/ros/indigo/setup.bash然后分别在三个终端下命令三段命令启动节点管理器 roscorerosrun turtlesim turtlesim_node 打开仿真器rosrun turtlesim turtle_teleop_key 控制方向 功能包/软件包turtlesim_node和turtle_teleop_key都属于tur
2017-06-12 12:20:42
225
原创 java的各种集合使用
import java.util.ArrayList;import java.util.Arrays;import java.util.Collections;import java.util.Comparator;import java.util.HashMap;import java.util.HashSet;import java.util.TreeMap;import java
2017-05-21 17:31:05
225
原创 浅谈堆以及java优先队列的详细使用
最近在学习集合框架整理下感觉有用的东西。我们知道优先队列其实内部实现就是一个堆的数据结构，java默认的是一个小跟堆，每次取出最小的元素，因为堆的性质他可以做到O(logn)级别的插入和删除操作。我们知道堆的性质是有： 1.堆中某个结点的值总是不大于（或不小于）其父结点的值； 2.堆总是一棵完全二叉树。将根结点最大的堆叫做大根堆，根结点最小的堆叫做小根堆。常见的堆有二叉堆、斐波那契堆等插入：向堆
2017-05-19 08:40:30
11336
原创 区间dp括号匹配
题目#include<bits/stdc++.h>using namespace std;typedef long long LL;int t;int n;int dp[110][110];string s;bool judge(int i,int j){ if(s[i-1]=='('&&s[j-1]==')' || s[i-1]=='['&&s[j-1]==']') return
2017-05-04 17:46:42
270
原创 石头合并学习区间dp
区间动态规划问题一般都是考虑，对于每段区间，他们的最优值都是由几段更小区间的最优值得到，是分治思想的一种应用，将一个区间问题不断划分为更小的区间直至一个元素组成的区间，枚举他们的组合 ，求合并后的最优值。 设F[i,j]（1<=i<=j<=n）表示区间[i,j]内的数字相加的最小代价 最小区间F[i,i]=0（一个数字无法合并，∴代价为0）每次用变量k（i<=k<=j-1）将区间分为[i,k]和
2017-05-04 15:49:19
313
原创 st表求最值
题目大意：给定一个n,q，代表n个数字和q个询问，每次询问，求出给定区间内的最大值和最小值的差值。我们可以根据st表来做， st表是有点类似动态规划f(i,j)表示从i开始的长度为2^j区间内的最值， 我们可以得到f[i][j] = max(f[i][j-1],f[i+2^(j-1)][j-1]) 1<=j<=mn[n] mn代表每次取对数保存的值 1<=i<=n-2^(j-1) +1 ac
2017-04-26 17:33:50
470
原创 折线分割平面hdu2050
折线分割平面 对于一条折线我们可以清楚的发现有两个面，如果我们现在在加一条直线，那么可以很清晰的看到了我们多增加3个平面，那么如果我们再增加折线的另一部分发现又增加了两个面，所以我们可以得到了5个面，当且仅当i=2的时候，瞎推理了下，发现每增加一条边上是当前是第i个折线的2倍-1，继续增加下一条发现是2倍-2所以我们得到递推式， a[i] = a[i-1] + 2 * i -1 +2*i-2。附
2017-04-19 21:38:55
234
原创 折线分割平面hdu2050
折线分割平面 对于一条折线我们可以清楚的发现有两个面，如果我们现在在加一条直线，那么可以很清晰的看到了我们多增加3个平面，那么如果我们再增加折线的另一部分发现又增加了两个面，所以我们可以得到了5个面，当且仅当i=2的时候，瞎推理了下，发现每增加一条边上是当前是第i个折线的2倍-1，继续增加下一条发现是2倍-2所以我们得到递推式， a[i] = a[i-1] + 2 * i -1 +2*i-2。附
2017-04-19 21:38:30
260
原创 超级楼梯hdu2041
超级楼梯#include<bits/stdc++.h>using namespace std;typedef long long LL;const int maxn = 1000 + 10;int t;int n;LL a[maxn];void solve(){ scanf("%d",&t); a[0] = 1; a[1] = 1; a[2] = 2;
2017-04-19 18:05:51
257
原创 一只小蜜蜂hdu2044
一只小蜜蜂这道题目一开始没看懂，后面发现就是只能往右和相邻的走，然后模拟了下发现其实就是个斐波那契数，大数据要爆int，然后起点和终点没有关系，因为图是固定的，所以我们只需要知道距离差就可以了，附上代码。#include<bits/stdc++.h>using namespace std;typedef long long LL;const int maxn = 1000 + 10;int t;
2017-04-19 17:14:56
255
原创 母牛的故事hdu2018
母牛的故事 该题一开始就想模拟做，然后模拟了下过程发现了这个数列是1，2，3，4，6，9，13，可以发现递推式a[i] = a[i-3] + a[i-1]，这样我们应该就能算出结果.#include<bits/stdc++.h>using namespace std;typedef long long LL;const int maxn =1000 + 10;int a[maxn];int n;
2017-04-19 15:37:39
234
原创 hdu2084数塔问题
数塔问题是一个很明显的递推问题，我们可以推出递推式dp[i][j] = max(dp[i+1][j],dp[i+1][j+1)) +a[i][j],我们从下往上递推，所以dp[n][i] = a[n][i]（循环位置i n->1 j 1->i），答案很显然是dp[1][1],下面贴上代码。#include<bits/stdc++.h>using namespace std;typedef l
2017-04-19 10:54:06
244
原创 蓝桥杯省赛
第一次参加蓝桥杯，听人说很水于是就参加了，一路折腾总算来到宾馆，10几个人，发现多了个人，只能开个家庭房，随机分配了下，和学霸一间房间，期间背了下快速IO，血长，补了几部番，传来学霸说美赛出成绩，拿了h奖，睡觉。第二天来到学校，喝了瓶红牛，开始写题，第一题水题，看了几遍题目怕题意出错，暴力算了下，第二题是个全排列+判重，第三题是个杨辉三角类似的题目，没写出来，第4题是个魔方，有点难（赛后听说没什么人
2017-04-16 21:35:48
1745
原创 选数-计蒜客
本题的思路应该就是先筛选出一个素数表。。不过数据范围太大20*5000000，直接上筛法肯定爆空间，所以我们需要优化一下，我们这时候可以直接判断是不是素数时间复杂度sqrt(n)，然后我们应该搜索所有的k个数字的组合，dfs搜索下，可以分为当前选或者不选，选了之后记得回溯现场，边界条件判断一下，是否递归到了选到了第k个数字了。import java.io.BufferedInputStream;
2017-03-30 15:18:00
335
原创 java stl 和一些打包好的数学板子
class usemap{ HashSet<String> set = new HashSet<String>(); HashMap<Integer,String> map = new HashMap<Integer,String>(); public void us() { set.add("df");//添加 set.add("d
2017-03-27 18:49:59
664
原创 md5加密 java打包
支持32位/16位class CreateMD5 { //静态方法，便于作为工具类 public static String getMd5(String plainText) { try { MessageDigest md = MessageDigest.getInstance("MD5");
2017-03-26 22:27:01
391
原创 01背包
01背包 有N元求取K件是的w[i]*v[i]和最大#include<bits/stdc++.h>using namespace std;typedef long long LL;const int maxn = 1000 + 10;const int maxn1 = 30000 + 10;int n,m;int v[maxn];int p[maxn];int dp[30][maxn
2016-11-29 13:46:15
162
原创 三角形上的格点数
三角形上的格点数#include<iostream>#include<cstdio>#include<cmath>using namespace std;typedef long long LL;const int maxn = 10000 + 10;int a,b,c,d,e,f;///匹克定理 多边形的面积 = (多边形上的格点数) + 二分之一边界上的格点树 - 1///海伦公式
2016-11-29 13:45:49
1160
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人