Views

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}$$...

原问题: 从数轴原点开始, 每次抛一枚正反概率相等的硬币, 如果是正面就沿正方向走1单位长度, 否则沿反方向走1单位. 设走n步之后的位移为x, 求(x^2)的期望(E(x^2)). 答案是n. 即随机游走时, 位移的平方的期望为步数. 并且这个结论可以推广到k维. (因为我的三角函数太捉鸡所以只推了2维, 但是目测了一下更多维都是对的) 看了zhihu上的一篇答案是关于一维情况的证明, 我受到了启发. 链接在这. 答主用的我不认识的东西有点多. 所以他证明过的部分我还是用自己的语言重新写一遍. 设第i次移动的位移为(x_i). 引理: 对于两次不同的位移(x_i)和(x_j), ( E(x_i*x_j)=0). 这个很好想, (x_i)的有0.5的概率为1和-1, 列个分布列(雾), 答案显然为0. 证明: $$E(x^2)=E((\sum_{i=1}^n x_i)^2)$$ $$E(x^2)=E(\sum_{i=1}^n x_i^2) + 2E(\sum_{i=1}^n\sum_{j=i+1}^n(x_ix_j))$$ 后面那坨的E可以扔进里面去, 根据引理该部分值为0. 前面那部分显然有 $$x_i^2=1$$ 于是得证 $$E(x^2)=n$$ 然后是向高维推广. 这里是二维的证明. 只需要改引理. 对于两次不同的位移(\vec{a_i} )和(\vec{a_j} ), (\vec{a_i} \cdot \vec{a_j} = 0 ) 证明: 设两个向量的角度分别为( \theta_i )和( \theta_j ). $$ \theta_i , \theta_j \in [0, 2\pi) $$ 因为它们都是单位向量, 所以 $$\vec{a_i} \cdot \vec{a_j} = cos(\theta_i - \theta_j) $$...

在网页上写数学公式怎么少得了MathJax. 然而这玩意因为功能复杂所以比showdown之类的库要难配置一些. 首先从Github上把它clone下来. 然后发现这玩意真的好大. 后来发现是有一堆迷之png. 别人家的cdn的速度从我这来看都不怎么样, 所以还是只能扔到自已的server上. 最简单的用法就是在html head里加一行 <script src='xxx/MathJax.js?config=default'></script> 然后它就会用默认配置在网页加载的时候把那些玩意给转换了. 这里有一个config的文件可以选择. 在unpacked里的default.js里有很详细的说明. (虽然是英文的) 看上去能用了? 然后问题来了. 我的前端是先加载网页框架, 再用js去加载内容, 然而内容加载出来的时候MathJax已经把活干完歇菜了. 显然应该有什么控制单元能随时更新某个element. google了一下发现MathJax有个子类控制单元叫Hub. Hub有个方法叫Typeset, 能重新检查页面. 于是这么写? $.post("xxx", {xx}, function(res) { $("#xxx").html(res.content); MathJax.Hub.Typeset(); }); 然而这样的话是不是我每加载一个listitem或者comment都要重新扫一遍整个页面啊? 卡死啦. 于是加了个triggerCount. 麻烦死了. 然后想想觉得没对, 肯定能直接改某个元素啊. 仔细看看document. Typeset([element[, callback]]) 对啊ovo可以直接指定element. 而且还各种类型都资瓷. 在类型这种问题上js比c高到不知道哪里去了. 于是代码写成 $.post("xxx", {xx}, functoin(res) { $("#xxx").html(res.content); MathJax.Hub.Typeset(getMyId()); }); 搞定啦. 然后config里还可以指定是用$$还是$之类的玩意. 然后似乎MathJax还自带Async一类的玩意? 感觉很赞.

公式: 一枚硬币扔一次有p的概率朝上, 扔n次, 朝上次数的方差为`n * p * (1-p)\\\'. 证明: 归纳法(增量证明) 设D(n)表示扔n次时的方差. E(n)表示扔n次时的期望. P(n, i)表示扔n次, 朝上i次的概率. 对于n=1的情况显然成立. 对于n>1的情况 $$D(i)=\sum_{i=0}^{n}P(n,i)*(i-E(n))^2$$ 对于D(n+1) $$D(i+1)=\sum_{i=0}^{n}P(n, i) * (p * (i + 1 - E(p) - p)^2 + (1-p) * (i - E(p) - p)^2)$$ 再两式相减, 式子有点麻烦, 但是可以巧妙地拆开然后用平方差化简. $$D(n+1) - D(n) = \sum_{i=0}^{n}P(n, i) * p * (1-p)$$ 右边那坨是常数. 左边这坨和刚好为1. 于是 $$D(n+1) - D(n) = p * (1-p)$$ 搞定. 数学考试遇到直接背公式就好. 可以记一个简单的结论是方差与n成正比. 不知道有没有奇怪的证明方法可以直接证这个来证上面那个公式. 思考了好久才思考出这种证法ovo. mathJax还没搞定所以公式全是乱码qwq. 随便喂给一个TeX编译器应该都能看. 推荐bestcoder的这个http://bestcoder.hdu.edu.cn/latex.php

造出了一个功能叫点赞qwq. 想起上周和czr讨论点赞到底应不应该重新从后端获取数据.ovo 然而这一部分的前端写得好丑啊. 然而后端水平进步了的感觉好开心. (虽然还是丑) 主要是前端动态渲染的方式会让js各种回调于是很讨厌. 而且$.post的异步在这种时候确实会造成麻烦. jquery里面一个element被clone之后要先加到document里才能再修饰它的属性, 不然会有奇怪的事情OvO. 噢对laekov为了好玩允许一个人点0xf个赞. 为什么点赞只能点一个呢? 反正后端都写成这样了就多允许几个好了…(其实可以调成0xff或者0x3f3f3f3f什么的23333) 另外也受到了知乎的一些启发. 评论什么的东西其实都可以加这么一个玩意, 反正都写出了通用的接口, 只是多几个接入而已. 感觉这种通用性的思路很有价值.

听说造了登陆之后就没人愿意来评论了. 于是窝决定去造个第三方登陆. 于是花了一晚上造出了oauth组件. (其实有sdk的啊摔) 于是有了github登陆. 其实还有企鹅啥的. 然而企鹅就是强行降低网站的逼格这怎么行呢. (其实是企鹅强行要求sdk懒得搞了) oauth的登陆简单过程是酱的(有点三次握手的感觉) 网站要去第三方申请一个application. 然后会得到client_id和client_secret. 然后把登陆的链接接到指定的页面去, 用get把client_id和泥要哪些数据传过去. 网站会和用户交流人生(登陆). 然后会用get方式调用callback, 这个是在注册application的时候指定的. callback的get参数里有一种东西叫code. 这东西要用. 用code来换access_token. 把code和client_id和client_secret一起当post参数传给第三方指定的第二个url. 如果没错会返回access_token, 这玩意是真正用来换数据的. 用access_token再去第三方提供的第三个url来get用户的数据, 比如avatar_url什么的. 那这和登陆有啥关系呢? 在第3步的时候如果泥得到了正确的access_token, 泥就可以认为用户正确登陆辣~ 然后就发生了一件鬼蓄的事情: 窝在去和github换数据的时候, 莫名其妙地就被403了. 大概就是酱(get为粟) function getData($url){ $opts = array(\'http\' => array( \'method\' => \'GET\' ) ); $context = stream_context_create($opts); $result = file_get_contents($url, false, $context); return $result; } 赶紧google了一下发现github会按照心情拒绝php发送的请求. 于是窝假装窝不是php而是善良可爱的少年就好了啊2333.于是强行骗人. function getData($url){ $opts = array(\'http\' => array( \'method\' => \'GET\', \"header\" => \"User-Agent: Mozilla\" ) ); $context = stream_context_create($opts); $result = file_get_contents($url, false, $context); return $result; } 假装窝叫Mozilla....

之前版本找list都是去硬盘里枚举一遍文件. 本地我有ssd速度还行. 传到服务器上就慢暴了. 因为有导入之前的博文加起来也有几百篇. 枚举一遍就要开将近1k个文件. 这里O(1000)和oi里的概念完全不一样啊ovo几乎就是要几秒的意思了. 然后没有发现php怎么把东西常驻内存里. 于是灵机一动拿单个文件来存常用的数据. 然后就叫它伪缓存好了. 按照时间和需要对缓存进行更新, 每次查询所有东西的list只需要开一个文件. 果然就快多了好感动23333.

这是 laekov 的博客, 曾经 proudly (并不) using laekov 高中的时候自己造的 shiruku 博客框架. laekov 的身份包括但不限于: 前 OIer @CDQZ. 前计算机系本科生 @Tsinghua 现高性能所博士生 @Tsinghua 一个对轮子和有轮子的东西感兴趣的人