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

组合数 求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写吧. Historical Comments lyzy at 2016-10-26T20:22:21 膜Qt大神 至今不会release lyzy at 2016-10-26T20:27:43 我还是没有名字 I still have no name Todavia no tengo un nombre. lyzy at 2016-10-26T20:28:57 怎么办 What to do ¿Cómo？ lyzy at 2016-10-26T20:29:21 太年轻 too young muy joven

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

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

题意: 给你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. 依然感觉很鬼蓄. 代码

Ps: 在思考ingress自动规划连边的时候顺便想到的一个题. 题: Ingress里要连多重来刷ap. 这是一种简化的情况. 假设平面上有点(A), (B), (C_1, \dots , C_n). 其中(C_1 , \dots , C_n)在直线(AB)同侧. 要连一个多重就要选一些点( { C_{a_i} } ), 使得( \Delta ABC_{a_1}, \Delta ABC_{a_2}, \dots \Delta ABC_{a_m} ) 依次包含. 即( C_{a_i} )在( \Delta ABC_{a_{i-1}} ) 内. 然后每个(C_i)都有个权值( W_i ), 求所有方案中最大的权值和. 另: 把权值和最大改成权值积最大, 对( 998244353 )取模. 让一群人写高精去然后再随便把高精卡T掉哈哈哈哈哈哈哈. 解法: (口糊的请打脸) 大概是个dp题. 把(C_i)按照离直线(AB)的距离排序即可保证拓补序. (其实这题我觉得有意思的地方就是这个了. 然而太简单) 然后就是找平面上某个三角形里的最大(f)值. KD树搞之. (AFO太久的我已经不知道KD树是什么了. 似乎有人告诉过我KD树这么用保证不到时间复杂度.) 印象中KD树常年被用来打脸和被打脸. 也许有更方便的搞法? 然而我的数据结构实在太渣ovo. 就酱.

yzy给的题. 感觉挺有意思. 听说是thu的自招题. 题: yzy有个计算器, 只有一个按键. 计算器上有一个自然数n, 每按一次按键这个数就会等概率变成区间[0,n)中的一个自然数. 现在的数字是2333, yzy不停地按直到变成0. 问同时出现过999, 99, 9的概率. 解法: 首先随便想个dp类似的递推. 然后推一下前几项就发现规律了. 然后就完了. 答案是(\frac{1}{10^6}). 可以拿来出题用.

(madan打到一半不小心把浏览器关了) (微分方程挺有意思的. 要是暑假有人找我出oi题我就出数学题吼吼吼) 题: 一维空间里有个质点. 速度为\(v\)的时候加速度为\(-k\sqrt{a^2-v^2}\) (即与速度方向相反). 求速度从\(v_1\)变成\(v_2\)的过程中的位移\(x_m\). 其中\(0\leq v_2 \leq v_1 < a\). 歪: 仔细看看这不就是简谐振动么? mdzz题. 算都不用算随便看看就出来了. 下面的东西不用看了. 解: 根据题意列个方程. $$\frac{dv}{dt}=-k\sqrt{a^2-v^2}$$ 整理. $$\frac{dv}{\sqrt{a^2-v^2}} = -kdt$$ 两边积分. $$arcsin\frac{v}{a} = -kt + C_1$$ 顺手整理. $$v = -a*sin(kt-C_1)$$ $$t = \frac{C_1 - arcsin\frac{v}{a}}{k}$$ 再对\(v\)积分求位移. $$x=\int vdt = -\frac{a}{k} \int sin(kt-C_1)dkt$$ $$x=\frac{a}{k}cos(kt-C_1)=\frac{a}{k}cos(arcsin\frac{v}{a})$$ 再定积分. $$x_m = \int_{v_1}^{v_2}vdt$$ $$x_m = \frac{a}{k} [cos(arcsin\frac{v_2}{a})-cos(arcsin\frac{v_1}{a}) ] $$ 顺手化简. $$x_m = \frac{a}{k} ( \sqrt{1-(\frac{v_2}{a})^2} - \sqrt{1-(\frac{v_1}{a})^2}$$ $$x_m = \frac{\sqrt{a^2-v_2^2}-\sqrt{a^2-v_1^2}}{k}$$...