Views

有个科学发现说观测到一个疑似戴森球的东西. 于是寝室里引发了如下讨论. lr: 泥觉得外星文明存在么. 众: 存在. lr: 有没有一种低级文明间交流的方式? 比如运气好的虫洞? 可能有. lr: 高级文明间一定有_三体_里描述的_黑暗森林法则_吗? 黑暗森林法则的原理在于文明之间无法充分交流来取得互相信任. 两方如果都具备 (或者可能具备) 直接摧毁对方的能力. 那么选择 “摧毁” 和 “不摧毁” 将是一个类似于纳什均衡的博弈问题. 每个回合, 两者都可以选择摧毁或不摧毁. 如果两方都选择不摧毁, 都欢喜. 如果两方中的任何一方选择摧毁, 那么游戏结束. 根据四年前 lyd 在 wc 上讲的课, 如果游戏在有限轮内结束, 那么两方都会选择在第一轮就摧毁. 如果游戏可以无限继续, 那么两方就会一直选择不摧毁. 而宇宙的寿命相对来说可以认为是无限的. 所以法则错误了么? 原作中有进一步假设: 摧毁所消耗的成本几乎可以忽略不记, 而不摧毁几乎不能带来任何好处. 与对方交流并获取收益的期望可以认为是极低的. 所以直接摧毁依然是最佳决定. 然而这步假设与人类的现状显然不符合. 所以说假设没错, 但是也不一定适用.

#include #include #include using namespace std; typedef long long qw; typedef pair <qw, int> dpair; #ifdef WIN32 #define lld “%I64d” #else #define lld “%lld” #endif const int maxn = 13; const int maxw = 400009; int n, w[maxn]; qw b0, b1, d[maxw]; dpair hp[maxn * maxw]; void dijkstra() { int th = 1; memset(d, -1, sizeof(d)); hp[0] = dpair(0, 0); while (th) { dpair g = hp[0]; pop_heap(hp, hp + (th –)); if (d[g....

组合数 求n和m都各在一个范围里的组合数里能被k整除的数的个数. 用熟悉的组合数的公式. \( C_n^m = C_{n-1}^{m-1} + C_{n-1}^m \) 把组合数先处理出来. 对于多组询问, 求出上面那个数组的二维前缀和即可. 蚯蚓 你有n只蚯蚓. 每秒把最长的蚯蚓砍成同比例的两段, 且其它蚯蚓变长. 求m秒中每一秒被砍的蚯蚓和最后所有的蚯蚓. \( n \leq 10^5, m \leq 7*10^6 \) 目测那个t只是为了输入输出不超时. 正常的暴力是用堆来维护蚯蚓长度. 发现一个性质, 下一次被砍的蚯蚓被砍之后两段肯定会分别短于本次被砍的蚯蚓的两段. 仔细想想没有低于\( O(m) \) 的做法. 所以我们把堆换成若干个队列, 每次只取队首的蚯蚓来比较, 砍, 然后塞回队尾. 保证队列中的元素单调. 这样时间复杂度就变成线性了. 小鸟 平面上有若干只猪. 你可以从原点发射一个抛物线并消灭抛物线上的所有猪. 求最小发射多少次. \( n \leq 18 \) 我们知道两点确定一条过原点的抛物线. 所以枚举两只猪就能得到所有能消灭至少两只猪的消灭方式. 剩余的猪只能直接消灭. 可以使用状态压缩型动态规划来解决这个问题. 只需要记录下当前已经消灭了哪些猪, 就可以进行转移了. ps 题目难度还是比去年高. 祝各位好运. laekov版权所有, 未经允许不得转载. 侵权必究.

简单看了看NOIP2016的题. 口糊一下自己的想法吧. 玩具 描述好乱. 反正就是一群人围成圈, 若干次左走右走问最后到哪. 加加减减取模就好了. 水水水水过. 跑步 一棵n个点的树, m条路径, 问对于每个点, 经过本点且起点距离本点为本点点权的路径条数. \( n, m \leq 3*10^5 \) 我感觉这个题有点难呀. 很有可能是我想复杂了. 把每条路径从lca处拆成两段. 考虑对于每个点的询问. 对于起点到lca这段, 询问就是询问子树里lca深度小于等于当前深度的深度刚好为某个值的路径起点个数. 对于lca到终点这段, 询问就是询问子树里lca深度小于等于当前深度的 (长度-深度) 刚好为某个值的路径终点个数. 然后就成了一个比较简明的数据结构问题. 一种思路是平衡树启发式合并, 但是时间可能会炸. 另一种思路是用dfs序式树链剖分, 每条路径会被拆分为不超过lg个dfs序上的子段. 在路径的每个子段的起点和终点处分别打上标记. 然后对dfs序进行一次扫描即可得出答案. 复杂度比较优. 换教室 n节课, v间教室. 每节课有两种教室位置选择, 其中一种是已定的. 你有m次机会申请换掉其中一节课的教室位置, 每个请求有独立的p的概率成功. 教室在一张图上, 求最小总奔波路期望. \( n, m \leq 10^3, v \leq 3*10^2 \) 个人认为这题比上一题水. 先用floyd处理出任意两间教室间的最短路. 然后用dp. \( f_{i,j,k} \) 表示前i间教室, 用了j次交换机会, k表示上一次有没有换. 存答案. 转移就是一个概率的算式, 较为简单. 略. ps 八年来第一次没有在赛场上考noip. 今年题目描述好长好长好长....

据说本学期程设的大作业是写个魔方. 看到别人都开动了, laekov就有点方. 所以laekov也开动了. 为了表现laekov很弱就随手记录一下好了. 10.21 晚上9点左右开始写魔方类. 支持三轴整体转动和四种八向扭动. 其实是用两轴转动和一种扭动组合出来的. 然后发现写得不太对. debug到12点搞定. 10.22 早上有运动会. 九点左右开始写层洗ai. 中午随便吃了点然后接着写. 全程没make. 大概一点左右写完开始debug. 两点惊闻有项目. 直到晚上六点半去听心理讲座接着debug. 晚上回寝室接着debug. 很多公式和判定都有小小的问题. 不过幸好函数都分开写了, 调试还算方便. 晚上九点左右能跑过随机了. core部分基本完结撒花. 顺手完善了一下document. 准备开始看qt. 10.23 懒死了不想看qt. 晚上决定图形还是就用h5写吧.

" local syntax file - set colors on a per-machine basis: " vim: tw=0 ts=4 sw=4 " Vim color file " Maintainer: laekov laekov@163.com " Last Change: 2015 Feb " hi clear set background=dark syntax reset let g:colors_name=‘pineapple’ if has(‘gui’) hi Normal guibg=#000000 guifg=white hi SpecialKey term=bold ctermfg=4 guifg=Blue hi Directory term=bold ctermfg=4 guifg=Blue hi ErrorMsg term=standout cterm=bold ctermfg=7 ctermbg=1 gui=bold guifg=White guibg=Red hi IncSearch term=reverse cterm=reverse gui=reverse hi Search term=reverse guibg=Blue guifg=White hi MoreMsg term=bold ctermfg=2 gui=bold guifg=White hi ModeMsg term=bold cterm=bold gui=bold hi LineNr term=underline ctermfg=3 guifg=Pink guibg=#222222 hi Question term=standout ctermfg=2 gui=bold guifg=White hi StatusLine term=bold,reverse cterm=bold,reverse gui=bold guifg=White guibg=Grey35 hi StatusLineNC term=reverse cterm=reverse gui=bold guifg=Grey10 guibg=Gray85 hi VertSplit guibg=Pink guifg=Black hi Title term=bold ctermfg=5 gui=bold guifg=DeepPink3 hi Visual term=reverse cterm=reverse gui=reverse guifg=Grey80 guibg=fg hi VisualNOS term=bold,underline cterm=bold,underline gui=bold,underline hi WarningMsg term=standout ctermfg=1 gui=bold guifg=Red hi WildMenu term=standout ctermfg=0 ctermbg=3 guifg=Black guibg=Yellow hi Folded term=standout ctermfg=4 ctermbg=7 guifg=Black guibg=#e3c1a5 hi FoldColumn term=standout ctermfg=4 ctermbg=7 guifg=DarkBlue guibg=Gray80 hi DiffAdd term=bold ctermbg=4 guibg=White hi DiffChange term=bold ctermbg=5 guibg=#edb5cd hi DiffDelete term=bold cterm=bold ctermfg=4 ctermbg=6 gui=bold guifg=LightBlue guibg=#f6e8d0 hi DiffText term=reverse cterm=bold ctermbg=1 gui=bold guibg=#ff8060 hi Cursor guifg=black guibg=white hi lCursor guifg=bg guibg=fg hi CursorLine guibg=#222222 hi CursorLineNr guibg=#222222 guifg=red hi NonText guifg=green guibg=#1a1a1a " Colors for syntax highlighting hi Comment term=bold ctermfg=4 guifg=Cyan hi Constant term=underline ctermfg=1 guifg=Yellow hi Special term=bold ctermfg=5 guifg=#ff9c3a hi Identifier term=underline ctermfg=6 guifg=#9999ff hi Statement term=bold ctermfg=3 gui=bold guifg=#09f93f hi PreProc term=underline ctermfg=5 guifg=#888888 hi Type term=underline ctermfg=2 gui=bold guifg=#598ff9 hi Ignore cterm=bold ctermfg=7 guifg=bg hi Error term=reverse cterm=bold ctermfg=7 ctermbg=1 gui=bold guifg=White guibg=Red hi Todo term=standout ctermfg=0 ctermbg=3 guifg=Blue guibg=Yellow else hi Normal ctermfg=white ctermbg=0 hi ErrorMsg cterm=standout cterm=bold ctermfg=7 ctermbg=1 hi IncSearch cterm=reverse ctermbg=1 ctermfg=7 hi Search cterm=reverse ctermbg=7 ctermfg=blue hi Visual cterm=reverse if $TERM == ‘xterm-256color’ " hi NonText cterm=bold ctermbg=232 ctermfg=2 " hi Type cterm=bold ctermfg=4 " hi Special cterm=bold ctermfg=172 hi NonText cterm=bold ctermbg=234 ctermfg=2 hi Type cterm=bold ctermfg=4 hi Special cterm=bold ctermfg=1 else hi NonText cterm=bold ctermbg=8 ctermfg=2 hi Type cterm=bold ctermfg=32 hi Special cterm=bold ctermfg=1 endif hi LineNr cterm=bold ctermfg=5 hi ModeMsg cterm=bold hi StatusLine cterm=bold ctermfg=7 ctermbg=8 hi StatusLineNC ctermfg=7 ctermbg=8 hi VertSplit ctermfg=0 ctermbg=5 hi Folded cterm=standout ctermfg=3 ctermbg=4 hi FoldedColumn cterm=standout ctermfg=3 ctermbg=4 “For syntax hilighter hi Comment cterm=bold ctermfg=6 hi Constant ctermfg=yellow hi Indentifier cterm=bold ctermfg=2 hi Statement cterm=bold ctermfg=2 hi PreProc cterm=bold ctermfg=darkgrey hi Ignore ctermfg=7 hi Error term=reverse cterm=bold ctermfg=7 ctermbg=1 hi Todo term=standout ctermbg=6 ctermfg=0 endif

一些可以用的轮子. passportjs 用户登陆/管理模块 zmq 消息队列. 处理后台各种不能异步的请求. openjudge-sandbox oj评测沙箱(还没搞懂) react 前端框架 angularjs 更重量更强大的前端框架 bootstrap css板子 nodegit 顾名思义 grunt 开发自动化 threejs h5的3d绘图 phoria 另一个h5的3d绘图 // 似乎star比上一个多, 然而没有文档, 玩ball喽 // 开始考虑要不要重写srk了然而没有时间>_<

这是一篇乱七八糟的瓦尔登湖读后感. 可能要花很多天才能写完>_< 一湖一林一屋一人, 就是一个世界. 人们常常抱怨这个世界过于喧嚣, 却没有发现世界的喧嚣源于自己的索求. 如梭罗自己所实验的, 如果你不需要整日辛勤劳作开荒种田, 你就不需要厚实的衣服鞋子. 如果你不需要为了咖啡和茶而赚钱, 那你就不需要用它们来支撑你的体力. 正所谓世上本无事, 庸人自扰之. 虽然东西不同, 但是梭罗的思想和中国古代的道家不谋而和. 人类的麻烦都是自找的. 我们明明可以选择一种悠闲而优雅的生活方式, 浪迹山林, 仰观蓝天, 坐看清湖. 然而啊, 存在即合理. 为什么人类是这样而不是那样啊? 明明全人类都可以退隐山林, 回归原始人. 即环保, 又悠闲. 然而, 发展是人类的必然趋势.所以我们必然也必需社会化, 工业化, 以及未来的信息化, 宇宙化. 如果不求上进, 和那些动物一样只会吃吃吃睡睡睡, 那么人凭什么能有今天如此悠闲的生活? 上进是人类的必需品. 环保, 回归, 可以是人类的幻想, 也有如作者一般的人会追求它, 赞扬它, 但是他们永远只能是少数. 另一方面讲, 人们从梭罗研究环保的先驱. 然而这样的环保是真正的环保吗? 未必. 真正的环保应该是尽量减少资源的浪费. 即最大化资源利用效率. 可是我们的梭罗先生呢? 伐木为柴, 折枝为箭. 他才是真正挥霍资源的人. 他所谓的情怀, 不过是文人式的矫情的无病呻吟罢了. 以上. 20160829

题意: 给你n个数和一个k. 求这n个数的一个最小子集, 使得元素乘积为k的倍数, 且元素之和最小. 要输出方案. \( n \leq 10^3, k \leq 10^{12} \) 结局: 死在输出方案上了. 思路: 首先发现k的质因数不会很多, 最多有14个. 然后k的因数也不会很多. 所以就dp一下. \(f_i\)表示当前积与k的gcd为i的时候的元素个数. 然后就像个背包一样嘛. 输出方案? 记录从哪里转移来的不就好了. 然后. 考虑这个例子. 3 9 3 24 21 你会先拿24从3更新到9. 然后21就会把3和9的转移都更新. 然后就炸了. 因为3应该是从原来的状态更新的. 但是现在被覆盖了. 然后发现状态是棵树. 可以把状态可持久化记下来. 更新一个状态的时候, 不是直接覆盖, 而是新建一个状态来保证从原来的状态转移出去的情况不会出错. 这样空间复杂度应该和转移次数有关? 然后怎么就糊过去了. 另一个细节是k=1是答案不能是0. woc. 依然感觉很鬼蓄. 代码

#include #include #include using namespace std; typedef long long dint; #define _l (long long int) #ifdef WIN32 define lld “%I64d” #else define lld “%lld” #endif const int maxs = (1 « 22) + 1; const int maxf = 23; const int inf = 0x3f3f3f3f; const int maxn = 1003; typedef pair <dint, int> item; item a[maxn]; dint k, kf[maxf], fs[maxs]; int f[maxs], ff[maxs], cs[maxs], fv[maxs], n, m, t, cf[maxf], v[maxf], vn[maxf], c;...