Jason_crawford-CSDN博客

原创浮点数编码

本文为浮点数编码的一般情况说明，全文均为白中英教授的《计算机组成原理》一书中的内容，本文仅作简要总结。和采用补码进行编码的整数编码方式不同，浮点数采用科学计数法的形式进行编码，这使得占4字节的浮点型float比占8字节的整形long表示的数据范围还要大。以下为采用科学计数法的这种编码格式的简要说明：我们知道十进制的科学计数法表示数N为：N

2021-02-27 20:17:28 2189

原创关于Java数据类型取值范围的一些思考和理解

事先申明，本文为菜鸡笔者自己学习总结，大佬若觉得笔者说的是废话可自行忽略，如果觉得笔者写的还凑合也请指正其中不对之处，笔者在此感谢。相信搞Java的或正在学java的都应该见过下面这个表格：数据类型关键字内存占用取值范围字节型byte1个字节-128 ~ 127短整型short2个字节-32768 ~ 32767整型int4个字节-231 ~ 231-1

2021-02-27 20:15:19 392

原创 Java中的Timestamp与String之间的转化

初学Java被这个Timestamp快搞吐了，主要是Java的这个类型与数据库中自带的Timestamp类型兼容而且还能精确达到具体时分秒，所以想省掉点转化的麻烦就用的这个，网上的大部分介绍显得较为复杂，然后被一篇百度经验拯救了，大致如下： String类型转化为Timestamp类型——例子如下： //定义一个String类型实体str保存你要的时间，格式如下(...

2018-05-05 22:06:56 25801 1

原创 Java中的&(不短路与)

开始学Java，发现了点新东西。。。 Java中的与逻辑运算符是分类别的，有短路与(&&) 和不短路与(&) 之分, 先说说短路与，我们知道与运算的逻辑规则是与运算的两位操作数必须都是true的情况下才返回true——即： x && y 的值当且仅当a和b都为true时才返回true。那么当x为false时，无论...

2018-04-15 10:39:11 1691

原创 POJ2392——Space Elevator(DP)

题目链接这道题的意思是给定每一块建材的高度和数目，以及其能堆叠的高度上限，求最高能叠多高，这道题和poj上的一道名字是coins的题目比较相似，我用了同样的DP策略，也就是dp[i][j]表示第i种建材块在构成高度为j时能最少能剩下多少块。那么: ①当dp[i-1][j]>=0,也就是当前高度之前的木块就能达到，第种就能全留不用

2017-02-09 17:28:41 455

原创 ZSTUOJ3698——单调序列2

题目链接这题和POJ3666是一样的题目，只是数据范围扩大了，从2000扩大到了5000，做法和POJ3666是一样的，只需扩展数组大小即可，所以就不赘述了，全当我极不负责的水了一篇博客好了。。。，POJ3666的解释可以看这里。#include#include#include#include#includeusing namespace s

2017-01-17 15:47:51 373

原创 POJ3666——Making the Grade(动态规划)

题目链接这题反正我是觉得用DP做有点恶心，看别人的题解做的，转移方程是:dp[i][j]表示前i个元素的最后一个元素为全部元素第j小时的最小代价，则dp[i][j]=min(dp[i-1][k])+abs(s[i]-cop[j]), ( 0≤i<n ,0≤j , 0≤k )从这个式子来看应该是有三重循环的，但有为大牛很巧妙的省掉了k的循环，从而降低了时间复杂度，然

2017-01-17 15:40:00 866 1

原创 HDU1069——Monkey and Banana(动态规划)

题目链接题目要求找最高能叠的箱子的高度，其实就是按照求LIS的方式来求即可，只是此处的最长按照箱子的高度做参数，然后一个箱子能叠在另一个箱子上的前提是处在下面的箱子长和宽都比上面的箱子要大，不能相等，输入时分类一下再处理输入数组，然后按照长或者宽的顺序sort一下，再对另一个参数进行dp即可。#include#include#include#in

2017-01-16 15:40:03 382

原创 POJ1631——Bridging signals(动态规划)

题目链接真的很想说这道题读懂题意比解决题目本身要难。。。然而题目本身的意思又很简单就是求最长递增子序列。但这道题有点特殊的地方就是要优化，常规的两个for的方法会超时，然后在《挑战程序设计竞赛》这本书上给了另一个nlogn的方法——就是定义dp[i]:=长度为i+1的上升子序列中末尾元素的最小值(不存在的话就是INF)，初始化对dp[]数组全部赋值成INF，也就是+∞，然后对

2017-01-15 19:38:58 661

原创 POJ1065——Wooden Sticks(贪心)

题目链接题目大意很好懂，给一连串数对，只要后一个数对的两个值比前一个数对两个值都大，那么该数对不消耗时间，否则消耗1单位时间。求如何安排数对顺序使得耗时最少。这题是贪心，先按L从小到大排序，然后对w进行贪心，其思想上和以前一道导弹拦截的题目几乎一模一样(题解链接)，用vector存当前需要另外加工的w值，然后对每次更新均对vector进行搜索，找出与当前w差值最小且比其小的w

2017-01-15 11:37:10 555

原创 POJ3280——Cheapest Palindrome(动态规划)

题目链接题目意思挺好懂的，就是说给你一个字符串，要求添加或删除若干的字符使得其成为回文串。给出每个字符添加和删除的代价，求出代价最小值。简单的DP，方程为:dp[i][j]=min(dp[i][j-1]+Map[s[j]-'a'],dp[i+1][j]+Map[s[i]-'a']);dp[i][j]表示第i个字符到第j个字符的最小代价，Map[s[i]-'a']表示删除或添加

2017-01-09 10:55:08 342

原创 POJ3616——Milking Time(动态规划)

题目链接这道题感觉有点像任务调度，(由于智商感人)还是看别人的题解做的。题目要求获得更多的牛奶，但区间又不能重叠，所以状态转移函数dp[i]=max(dp[i],dp[j]+s[i].product)，(j表示在i之前的且与第i个区间不重合的区间)，dp[i]表示第i个区间能获得的最大产量。其中第i个并不是题目给出的第i个区间，而是按照结束时间排好序的第i个区间。看一下代码还

2017-01-07 17:09:17 439

原创 POJ2385——Apple Catching(动态规划)

题目链接这道题听说是很水的DP入门题。然而，我连入门题都不会。看别人的题解弄的，关键点就是要抽象出问题的状态转移，其状态转移方程为 dp[i][j] = max（dp[i-1][j] ， dp[i-1][j-1]）。其中dp[i][j] 表示的是第i秒第j跳最多能吃多少苹果，这个看似很简单的方程我都理解了很久，其实主要的是没把别人的代码看完，这个方程是不完整的，还差

2017-01-06 20:28:46 591 1

原创 HDU1257——最少拦截系统(贪心)

题目链接在kuangbin的DP专题里找到的，然而有点坑的是并不是用DP做的。。。此题用贪心才是正解啊~~，对于每一发导弹，若已经存在拦截系统，且可以拦截此导弹，那么重新开一台是没意义的，因为达到的效果和通过降低现有拦截系统高度来拦截所达到的效果是一样的，当然若拦截不了那就另当别论去开一台，问题是有多台可以降低高度那么选哪一台呢？答案当然是选高度最低的且能拦截此导弹的系统

2017-01-06 16:01:32 333

原创 HDU1114——Piggy-Bank(装满的完全背包)

题目链接这道题是一道完全背包练手很好的题，比较容易，但是与纯的完全背包相比却做了部分很巧的改动。其一，这是一个要求装满的完全背包。其二，这个背包求得并不是最大值，而是最小值。那么如何解决这些变动呢？首先是看求最小值，这个好处理，那就是把max( )改成min( )就好了，但求最小值影响的却不只是函数的变化，还影响了对装满背包的处理。我们知道，无论是01背包还

2017-01-05 10:15:52 509

原创 POJ3176——Cow Bowling(水DP)

题目链接开始做DP的我表示要尊重每道水题(其实是只会水题。。。)这道题就是要找一条能从三角形定点到最底边的一条路径，方法是从底边开始往上找，一直取当前节点可达的最大值，最后找到定点即可，方法上模拟了背包问题的数组一维化处理，但是空间消耗还是大大滴(1700K)。。而且时间也跑了76ms。很想知道那些0ms跑出来的大神是如何做到的。#include#inc

2017-01-04 14:25:40 323

原创 POJ3262——Protecting the Flowers(贪心)

题目链接题目大意是说农场主要尽可能的减少牛吃花造成的损失，所以赶牛回牛圈，但是一次只能赶一头牛，现给出赶一头牛花的时间和牛每分钟吃的花的数量，求最少牛会吃掉多少花?处理起来也比较容易，关键找到赶牛的顺序，所以排序是关键。其实利用sort函数就挺好的，写一个cmp，里面比较的就是按照a牛单位时间吃的花与赶b牛的时间乘积与b牛单位时间吃的花与赶a牛的时间乘积，选其较小者。然后统

2017-01-03 11:06:10 561

原创 POJ1017——Packets(贪心)

题目链接一道很简单贪心，结果被自己做蠢了。题目要求有6种不同规格的箱子，分别是1*1,2*2,3*3,4*4,5*5,6*6。要对这6种规格的箱子打包，但是包裹的规格只有6*6的。所以问你如何用尽量少的包裹打包，输出包裹数。我的做法就是老老实实的模拟，先装6*6的，每个包裹只能装一个6*6，再装5*5，一个包裹只能装一个5*5和11个1*1，再是4*4。。。就这样一直模拟下去

2016-12-05 10:48:48 481

原创 POJ2393——Yogurt factory(贪心)

题目链接蛮水的一个贪心，维护当前最优价格就好，可以把储藏时间看做额外加价的次数，每过一周都在最优价上加一次储藏价，然后不断更新最优价即可，注意数据开long long。#include#include#include#include#includeusing namespace std;int main(){ long long n,

2016-12-04 11:52:26 462

原创 POJ3190——Stall Reservations(贪心)

题目链接题目大致是说有一群奶牛要挤牛奶，但是她们只在规定的时间区间内挤牛奶，而且一台挤奶机只能给一头牛挤牛奶，问最少需要几台挤奶机才能给全部的牛挤牛奶，并且输出每头牛是在第几台挤奶机挤的牛奶，第一行输入奶牛数，然后按顺序输入每头奶牛的挤牛奶时间区间。输出则是第一行输出最少的挤奶机数。然后一次输出每头奶牛是在第几台挤奶机挤的奶。首先对挤牛奶区间sort一下，优先按区间左端点从小

2016-12-03 14:21:34 353

原创 POJ1328——Radar Installation(贪心)

题目链接题目大意是在给定的坐标系中在x轴上方有许多岛屿，然后你可以在x轴上设置雷达，雷达有探测范围d，要求尽量少的雷达将所有岛屿探测入内，先开始贪心方式错了，送了两个wrong，起先认为按横坐标从小到大排序然后更新雷达位置就行了，后来发现雷达的位置并不是随岛屿横坐标越大，就一定会更新到越大的位置，有可能会变小，所以这种想法是不对的，后来换成从雷达覆盖区间的交集来考虑才得出正确

2016-11-28 19:07:13 345

原创 POJ2376——Cleaning Shifts(贪心)

题目链接此题就是给你一堆小区间，然后用尽量小的小区间数目填满大区间，输出最小值，如果填不满输出-1,。通常做法就是排序，再贪心最大的区间右边界。但是还有一种做法，是在Discuss里看见一个大神写的一段无排序的精简代码，想法也和贪心方式差不多，精妙之处就是拿了一整段空间来保存每个可用空间，然后用了一个“指针”now来标记当前状态，接着用pre和to去表示区间的起始和终止位置。

2016-11-28 16:12:49 393

原创 hihocoder 1436——GeoHash一·编码解码(Geohash)

题目链接这道题是Geohash得模板题，至于什么是Geohash，网上不管是博客，还是维基百科，解释都够详细了，当然还有这道题的提示里也解释的很详细了(比较推荐看题目里的解释，不但详细，还有伪码模板)，大致就是用经纬度描述地点时，将经纬度通过二分转化为为二进制编码，然后按先经度后维度，再经度再维度........的顺序将两二进制编码合并，接着每5位给出其对应的十进制数，再通过

2016-11-28 14:02:30 2251 1

原创 AOJ0525——Osenbei(DFS)

题目链接题目大致是讲一个烧饼铺烤烧饼，在一个n X m (1<=n<=10,1<=m<=10000)的烤桌上面摆着一堆烧饼，数字1表示烧饼正面，0表示烧饼反面。然后你每次可以将一整行或者一整列的烧饼翻面，即正面翻成反面或者反面翻成正面。但是必须是一整列或者一整行的翻，问最多可以使都少烧饼翻成正面？题意还是很好懂的。由于n比较小，所以可以对行DFS，那列呢？其实列很好处理，对

2016-11-25 19:48:27 892

原创 POJ3187——Backward Digit Sums(暴力)

题目链接这题没什么特别要注意的，直接next_permutation()，暴力走起。#include#include#include#include#includeusing namespace std;int a[15]={0};int b[15]={0};int main(){ //freopen("in.in","r",st

2016-11-25 15:20:07 308

原创 POJ2718——Smallest Difference(暴力瞎搞)

题目链接按从小到大的顺序给你一些数字，不会重复，要求你把这些数字分成两类，每一类可以组成一个整数，要求两类整数绝对值之差最小。输出最小差值。笔者表示并不会优化~~~大致看了一下，最恶心情况下，也就是给了10个数，然后暴力需要约400万次，所以就直接暴力瞎搞了，用了一个牛逼哄哄的函数next_permutation(),并且注意只给了两个数的情况单独写一下，和暴力过程中的前导零

2016-11-25 14:32:34 375

原创 POJ3669——Meteor Shower(BFS)

题目链接此题的意思让我难受，因为描述的很不清晰，而且数据也有问题，首先大致题意就是在一个地方会陨落流星，然后陨落的地方在坐标系的第一象限，当陨石砸中一个点，其不但会破坏被砸中点，还会破坏以被砸中点为中心的上下左右一共5个点，且它们砸落的时间不一，题目的输入就是第一行给定要砸多少陨石，然后接下来就是描述陨石砸落坐标和砸落时间，然后你会从坐标原点出发去寻找一个陨石砸不到的位置，你所

2016-11-24 19:26:11 398

原创 AOJ0121——Seven Puzzle(BFS)

题目链接话说鄙人做这道题都有种把翔都做出来的感觉，主要是死在对string(一个自己不是很懂的东西)的不了解。然后一直在调bug，题意就是给你一个8宫格，然后0表示空缺，可以将相邻位的数字与空缺交换，以表示将该数字块移到空缺，然后会给你多组输入，每一组表示按从左到右，从上到下排列的8个数，问将这样排列的8个数移成01234567，最少移动多少步。输入有多组。先开始老老实实按题意

2016-11-22 21:48:41 515

原创 AOJ0558——Cheese(BFS)

题目链接题目大致是想说有一只生物想吃cheese，然后有n个工厂生产cheese(1，且每个工厂生产起司的消耗量均不一样，刚好有n个工厂，而这只生物只能吃消耗量小于或等于它自己体力的cheese且它在每个工厂吃且只吃一次，其初始体力为1，问从出发点是S开始，如何在最少的步数内吃到所有的cheese，当然，移动方式就是上下左右。题目意思已经很明确了，就是图上的'X'表示障碍物不

2016-11-21 14:19:06 616

原创 AOJ0033——Ball(贪心)

题目链接其实要把该题归为贪心，也不知道是否是对的。。。题目就是有10个球，分别标号为1~10，但是顺序不知，从A管口放下，然后你可以控制当前放下的求进入B管或者C管，如果能使10个球放完，B和C管中的球的标号重下到上依次递增就输出YES，否则NO。看了网上好多说法，有DFS的，还有二进制的，，，搞得我有点慌，因为我自己也看到不是太懂，而本题实际上也很简单，放入当前球时

2016-11-18 16:26:44 692

原创 AOJ0118——Property Distribution(DFS)

题目链接题目意思就是会给你一个矩阵(最多 100 X 100)，然后里面会有三类字符'@', '#', '*', 相邻的(即上下左右)且相同的字符算在一个连通块内，问总共有多少个这样的连通块？裸的DFS，对每种字符用一次DFS再统计总块数即可。#include#include#include#include#includeusing namesp

2016-11-18 14:38:07 393

原创 POJ3009——Curling 2.0(DFS)

题目链接讲道理，看到这道题，第一反应是BFS，毕竟要算最少步数嘛~，但是后来就发现自己蠢了，理由很简单——要回溯，所以只能DFS，但是最小步数怎么破，注意到题目说步数不能超过10次，所以可以总共也就4^10次种可能结果，也就是100万次左右，把所有可能结果放进一个数组存起来，然后sort一下，把最小步数输出即可。如果无法搜索到，输出-1。代码如下。。。#include#

2016-11-17 20:32:19 386

转载 Miller-Rabin素数测试学习笔记

原文出处：http://www.cnblogs.com/vongang/archive/2012/03/15/2398626.html好几天前看了算导上的Miller-Rabin素数测试算法，今天正好总结一下，写写笔记。　　说Miller-Rabin测试以前先说两个比较高效的求a*b% n 和 ab %n 的函数，这里都是用到二进制思想，将b拆分成二进制，然后与a相加（相乘）/

2016-11-04 19:24:46 623

原创 POJ2689——Prime Distance(大区间素数筛)

题目链接题目要求给定区间内求最小和最大间距的素数对，如果没有则输出 There are no adjacent primes.但由于给定区间太大，所以不可能在给定的区间内直接暴力，而要先求出给定区间内的素数，由于区间大小不超过1000000，所以可以对该区间用素数筛法，因为区间在21亿，所以区间内的合数的质因子都在2~√2147483647内，所以先素数筛出1到50000内

2016-08-22 17:06:17 573

转载斐波那契博弈

原文链接：http://blog.csdn.net/acm_cxlove/article/details/7835016引用：http://blog.csdn.net/dgq8211/article/details/7602807有一堆个数为n的石子，游戏双方轮流取石子，满足：1)先手不能在第一次把所有的石子取完；2)之后每次可以取的石子数介于1到对手刚取的

2016-08-06 11:17:15 368

原创 HDU2177——取(2堆)石子游戏(威佐夫博弈)

题目链接这道题是HDU1527的升级版，题意都好懂，是威佐夫博弈的一道模板题，如果不是很了解威佐夫博弈，可以看一看我写的HDU1527的博客，我大致陈述了威佐夫博弈的一些基本知识，有助于解决此题。这道题目就是判断了当前状态为非奇异局势的时候如何拿走石头使其成为奇异局势，由于数据范围在可接受范围之内，所以先吧0#include#include#include#

2016-08-05 19:58:01 1060

原创 HDU1527——取石子游戏(威佐夫博弈)

题目链接这道题是威佐夫博弈的一道入门题，问的十分简单，就是套威佐夫博弈的两个公式即可，因此顺带说说威佐夫博弈，威佐夫博弈和巴什博奕的场景很类似，所以索性就套用我在巴什博奕那篇文章中所描述的的那个场景。有两个二货，比赛拿XX(XX可以是任何东西，只要能定量拿走就好)，只是这一次他们不再将XX混为一堆，而是作为两堆(两堆XX的数量均任意个)，然后拿走的方式也改为： 1，从一堆里

2016-08-05 19:31:59 4202 1

转载 Nim游戏和sg函数

这篇博客是转载自一位不知道来源的大牛的一篇关于博弈论Nim游戏和SG函数的讲解，我也只是看过了PDF档的，看了后觉得写得很好，于是就转载出来与大家分享，写得真的很好，值得大家借鉴。(若此文章原创作者看到此文觉得存在版权问题，请于下方评论，我将尊重原创作者版权撤销此博客。谢谢合作。)接下来是正文: Nim游戏是博弈论中最经典的模型（之一？），它又有着十分简单的规

2016-08-04 20:04:37 361

原创 nefu2——猜想(素数筛法)

题目链接这道题并没有难度，就是一道裸素数筛法，但我还是被恶心到了，因为报MLE了，还是队友的一句提醒，存放判断值的数组vis用bool比int少4倍。。。我才顿悟，，，基础不行遭天谴啊~~~#include#include#include#include#includeusing namespace std;#define MAXN 2000000

2016-07-29 15:55:52 339

原创 HDU1521——排列组合(指数型母函数)

题目链接：最近一直在做组合数学的东西，也转载了部分大牛的博客，这道题若有不是很理解的地方，也可看我最近转载的有关母函数的博客。这道题是一道标准的母函数裸题，直接套用母函数的公式即可

2016-07-25 19:53:55 394

空空如也

空空如也