动态规划-01背包问题之我见

背包问题是信息学奥赛中最经常考的动态规划形式,而01背包又是背包问题的基础。除此之外,背包问题还分为完全背包、多重背包等。 01背包定义如下: 对于1个容积为v的背包和n个物品,这些物品分别有自己的体积Vi,和价值Pi,我们需要有一种算法在背包可以容纳的情况下使装入的物品价值最大。此时n个物品不一定全部放入,背包也不一定装满。 与完全背包不同的是,01背包中是n个物品,而完全背包是n种物品,每种物品可多次放入。 这样的问题为什么不用搜索解决呢? 显然,如果搜索可以完美解决这样的问题,我们自然也就不需要用更好的算法来解决问题了。 通过分析问题,我们可知,对于每个物体都有放入背包和不放入背包两种情况,如果我们使用传统的搜索算法解决这个问题,那么时间复杂度为O(2^n),数据大了难免超时。 何为动态规划: 动态规划是通过拆分问题,定义问题状态和状态之间的关系,使得问题能够以递推(或者说分治)的方式去解决。继续分析,我们可以通过递推的方式解决该问题,从问题分析出递推式的方法,便是动态规划。 如何用动态规划高效地解决01背包问题? 这是一个01背包常见的递推式 f[i][j]=max(f[i-1][j],f[i-1][j-Vi]+Pi) 其中,i从1到n,j从1到v,条件为j>=Vi 许多人与我一样,在第一次看到这个递推式的时候都十分困惑,全然不知它的含义。 实际上,f[i][j]就是我们在写动态规划程序时所需要开的一个数组,f[i][j]表示放入前i个物品(包含i,但这前i个物品不一定完全放入),背包容积为j时,背包内物品价值和的最大值。 这样,f[i-1][j]显然就是不考虑放入编号为i的物品的情况下背包内物品的最大价值和,而f[i-1][j-Vi]+Pi,便是在只考虑放入前i-1号物品且背包容积为j-Vi时,背包内物品的最大价值和,再放入编号为i的物品,因此加上Pi,也就得到了f[i][j],即放入前i个物品,背包容积为j时背包内物品的价值的最大值。 对于这个算法,在C语言中通常采用两层for循环解决,以下为C++写法。大家可以根据题目自己修改以符合题目要求。 该方法的时间复杂度为O(n*v)…

解决U盘启动Linux后重启Mac黑屏

今天早上把Mac启动到了我的U盘里的一个Ubuntu系统,做完各项事情后我打算重启返回macOS,我便在重启时等待电脑黑屏后拔下U盘,我之前也是这么做一直没有出过问题,直到今天。 这时听到了Mac开机的“灯”一声,之后屏幕就黑屏了,于是我按住电源键强行关机,之后再开机,可以看到触摸板可以按下并且USB通电了,但是电脑始终没有开机音,屏幕也没有亮,紧张之中,我拨打了苹果中国的400客服电话。 向客服表明情况后,客服让我尝试清除NVRAM,失败,之后让我按住Shift和电源键开机重置SMC,可是忘了让我按Control和Option,显然,还是失败,开机后依旧是USB通电、触摸板可以按下,但没有开机音,屏幕也没有亮。 之后客服就帮我预约了Genius Bar了,好在厦门有Apple Store,但是最近的预约需要8月1日中午。虽然我的数据都有在自己家的服务器上用afp开Time Machine备份,但是并没有什么取出文件的方法,于是我便开始尝试自己解决问题。 几经辗转,我在网上看到了一篇解决Mac开机黑屏问题的文章http://osxdaily.com/2014/11/22/fix-macbook-pro-booting-black-screen/ 按住Shift+Control+Option+Power,只听“灯”一声,成功进入了macOS的登录界面。 祝愿每个看到这篇文章的朋友们都能顺利解决自己遇到的问题。   最后给大家看个笑话

如何理解Linux的文件系统挂载点

对于大多数Linux初学者而言,最痛苦的事情莫过于理解Linux文件系统的挂载点。 我们都知道,在一个硬盘上,我们通过分区把硬盘空间分成几块来使用,在这些分区上可以创建文件系统,而文件系统最终能被访问就需要挂载(mount)。 在传统Windows中,所有分区都被挂载为盘符,比如C:、D:、E:、F:,相当于每一个文件系统都是一个根节点。 而在Linux中,是以一个系统盘为根节点,而其他的文件系统都挂载在根节点下的目录中 仅仅这样说可能对于大多数没接触过Linux的人而言难以理解,现在我们就在Windows中模拟一下Linux的文件系统挂载方式。 不知大家何曾想过,若Windows的26个盘符用完了怎么办?不仅仅是这些带着好奇心的用户想到了,当然,微软也想到了。 在Windows NT中,一种新的分区挂载方式出现,就是把分区作为文件夹挂载在NTFS文件系统中。 这样,原本在Windows应为根节点的分区就成了文件系统根节点中的一个子节点。 我们来到Windows的磁盘管理,查看当前的磁盘分区信息。 可以看到我这里有个256G的物理硬盘,还有一个1TB的虚拟硬盘。 这1TB的虚拟硬盘中,有个99M的ESP分区(当时用DiskGenius随便分的就忘了取消勾选了)。还有三个NTFS文件系统的数据分区。分别被挂载为D、E、F。 现在我们来使用Windows NT提供的另一种挂载方式,将这三个分区的文件系统挂载到C盘的文件夹中。 现在,我们所看到的只有一个C盘(网络驱动器请忽略),并且空间并没有扩大。 但在C盘中出现了3个文件夹,分别对应之前的D、E、F盘的文件系统。当然这里也可以用其它的名称来命名这三个文件夹。 看到这里,相信大家对Linux的目录挂载点有个基本的认识了吧。

StrongSwan IKEv2 IPv6配置

我有了个想法,能不能通过我的Linode,给我的其他服务器和终端设备也接入Linode的IPv6,取而代之当下速度极慢的电信IPv6,毕竟当前电信IPv6用户少之又少,相信广大电信v6用户也都体验过Linux里面把包管理器的源设置成中国各大学的源,然后更新源、下载软件包的速度。 于是,我就给Linode发了个ticket,告诉他我需要更多IPv6地址,不久便收到了回复。 可以看出Linode客服还是非常有礼貌的。这里小小地震撼一下。 现在问题来了,既然/116地址够用,为什么我最后还是选择了/64呢? 我们来看看Linode官方IPv6文档 看到这里,我想到/116地址可能并非路由到自己的Linode上,而是可以通过以太网与该数据中心的所有Linode共享。 既然我们需要搭建一个IPv6隧道,如果通过以太网桥接接入将会有各种各样的问题,既然Linode也说给我们/64的地址段很容易了,我就选择了/64地址段。 之后,我就得到了一个IPv6地址段   好了,现在/64的地址段拿到了,IPv4地址总数量的平方倍的地址段都拿到了,想想也有点小激动,Linode真大方啊。 之后,就开始配置这台IPv6路由器了。 首先在/etc/sysctl.conf里把IPv6转发打开,实现路由器功能 net.ipv6.conf.all.forwarding=1 之后运行sysctl -p使配置生效 这时,我发现服务器的IPv6地址都没有了,只有一个fe80::的Link Local地址。 原来,Linux在开启IPv6路由功能后会关闭IPv6…

在NTFS分区创建swap

迫于学校机房电脑有硬盘保护的无奈(尽管很容易移除,但我们学校毕竟没有专用的信息学奥赛机房,信息技术教室的电脑如果没有硬盘还原将带来一系列问题),我在U盘中分了一个ext4分区安装Ubuntu,然而,在学校机房电脑上登录后系统便卡死不能动弹。我想可能是学校机房电脑内存不足所致,便有了在NTFS分区开swap的想法。 首先,在登录界面上,按下Ctrl+A l t+F1,进入控制台 登录 进入root用户 fdisk -l 看看当前磁盘分区信息 学校电脑真寒酸,1G内存+250G机械硬盘,据说今年暑假要换? 由于机械硬盘最外圈线速度最大,读写速度也最快,考虑到第一分区可能存在大量磁盘碎片影响读写速度,所以我选择了第五分区作为要挂载的文件系统。 用dd命令创建一个大小为2G(128M*16次)的全0文件 mkswap 文件名 swapon 文件名 这样就完成了swap的挂载 再按Ctrl+Alt+F7回到图形界面,输入密码,登录 日常,立于卡顿之世,奏响硬盘之音。 最后,也希望我在信息学奥赛退役之前能见到学校机房换新电脑吧。

来说说我的红包

看大家都抢不到我的红包v2与红包v3,我自己来说说我的红包好了。 其实大家应该都知道,我的红包第一版把3位数字藏在http header的date中,特意留下了一个错误的星期,让大家注意到这个Date中的问题。另外5位数字我藏在页面动画的延时中。看起来这纯粹是脑洞大开,即使这样,群众的智慧是无穷的,最后红包在半小时内就陆续被聪明的林兔兔、吕世博等人相继破解了。不服气的我选择做了v2和v3版本。 v2版本中,我把前4位数字的md5藏在了一个注释中,并用一个磁力链接的形式加以伪装,我原本以为,这样大家就会关心如何下载那个本不存在的磁力链接,而忽视如何去破解其中的md5。  然而,做过黑客的应该都知道像cmd5这样的密文数据库,红包前4位get✅。  剩下4位呢,也是本次红包最坑的地方,我换了一种藏红包的方式,在文件末尾填充”/0″,藏在html的文件大小中,以及把页面动画的js独立出来转移注意。 是不是想打我?哈哈哈哈哈哈 于是,这个红包就这样变成了无解之谜。 再来说v3 我直接上代码吧。  没错,就是这样,提示了支付婊,你们应该首先想到WP,这个只需要使用一个WP 10的UA访问看注释即可。 最后,祝大家新年快乐!

我的红包被抢了

曾以为自己设计的红包没人看出来,看来我还真是Too young, too simple. https://cyyself.name/redbag.php 不多说了,你们看laosb写的博文吧 新春红包解析:别人家的 那么我怎么办呢?当然,我还是设计了红包v2和红包v3,参见: 红包v2 红包v3 欢迎破解

7:2:1

3天前,我与一位朋友相约共赴厦门SM新开的Apple Store,参与Mac基础知识讲座,尽管当时只是抱着去Apple Store玩玩的心态,却收获颇多。 为我们进行演讲的是Sam,见我们两位参与者都是OS X老用户,便与我们展开了关于OS X和苹果的相关谈论。使我留下最深印象的,便是Sam提到的“7:2:1”的学习方式。 Sam大概是这样解释7:2:1的,在学习中,有10%的知识是老师传授的,正如Apple Store开办的讲座,演讲者传授便是这其中10%。而更为重要的20%,是与同学交流讨论中学会的知识。最后也是最重要的70%,则是依靠自己探索,自主学习所学到的知识。这7:2:1构成了我们最终所学到的知识。 在他介绍完这“7:2:1”后,我便感到这样的学习方式所带来的好处。作为学生的我们,在学校里所学的知识,大多数都依靠着老师灌输,而在“7:2:1”中,老师的灌输只占到了10%。在与同学交流讨论所占的20%中,我们也往往没有让这个环节发挥它最大的作用。而到最后的70%,却有太多太多的人无动无衷,这情有可原,也许是我们在应试教育下失去了自己对兴趣事物的探索。 回顾起自己学习编程的经历,从小学玩VB6和易语言以及机器人编程,到初中玩基于C的Arduino开发、C#、VB.net,再至高中参加NOIP而去学习各种各样的算法。在这期中,除了小学玩的机器人编程和高中学的程序算法有老师传授知识外,其他依靠看书、上网自学,与朋友交流相关问题,也取得了一定的收获,我想这便是自主探索学习的重要性,这也是学习中最重要的一部分。 我开始明白,自学在一个人对知识的学习中有多么重要,也许7:2:1便是最理想的学习方式。在学习中,少不了老师的传授,少不了同学间的交流,但我认为最重要的,是带着求知欲去探索一切,依靠自己的力量充实自己,才能在茫茫人海中出类拔萃。

《全民K歌》地址解析工具下载歌曲教程

2年前,一个朋友问我如何下载全民K歌的歌曲,我和Soha顺手研究了一下,做了一个解析工具。并写了一个傻瓜式教程,时隔2年,全民K歌的API已不知经过了多少次更新迭代,许多App也在飞逝的时光中不断变迁,例如之前教程中所提及的迅雷已经从App Store下架了,因此我决定重写一个傻瓜式教程。 几经辗转,终于找到了一个iOS下的支持http下载的浏览器,海豚浏览器。之前使用的VLC播放器虽然支持http下载,但当前版本不知为何无法使用,因此大家可以在继续往下看之前先在App Store中下载它。 之后,我们复制出一个共享链接 用海豚浏览器打开地址解析工具,将它粘贴到地址解析工具的文本框中 之后在链接上长按,点击目标另存为 自己给文件取个名吧 之后打开下载菜单,点击这个文件后再点击其它程序打开 之后点击快速查看就可以了