sjj118's Blog

记录历史，让历史记住。

Mathematical Analysis of Algorithms 笔记

《Mathematical Analysis of Algorithms》是著名计算机科学家 Donald Knuth 在 1971 年发表的一篇论文，这篇论文的核心是对两个问题的算法分析，其中的运用的技巧是最值得我们关注的内容。 引言 算法分析可以分成两大类： 一、分析一个算法：对一个确定的算法，分析其时间复杂度、空间复杂度，在最坏情况下或平均情况下。 二、分析一类算法：对一个确定的问题，考虑......

Posted by sjj118 on 2020-03-13

蒙特卡洛树搜索

摘要 在完全信息博弈中，极大极小搜索加上 Alpha-Beta 剪枝是最常用的算法，然而，极大极小搜索必须遍历所有的状态，能搜索的深度非常有限，即便加上 Alpha-Beta 剪枝也没有太大的帮助。因此在这篇文章讲介绍另一种更有效的方法——蒙特卡洛树搜索(MCTS)，它将更加有选择性的进行搜索，因此能取得更好的效果。我们将先介绍蒙特卡洛树搜索的大体框架，然后详细分析 MCTS 中最重要的多臂老虎机......

Posted by sjj118 on 2019-01-04

民科转动动力学

最近开始写物理引擎，才发现高中物理对转动的问题一点都没有提到。高中物理中的运动都是平动，而现实中更多的情况下都会发生转动。于是我结合自己的思考并查阅了一些资料后进行了一些总结。 由于我不太会积分，所以会用一些不太严谨的方法来定义。并且由于我写的是二维物理引擎，以下讨论只考虑二维情况。本文默认读者已掌握所有高中物理知识。 基本定义 刚体 首先，我们假设一个物体是由 \(n\) 个质量极小的质点组成的......

Posted by sjj118 on 2017-12-21

Hexo 博客

沉迷建博客不可自拔 由于对 Ruby（Jekyll 基于 Ruby）的不熟悉，以及对 Node.js（Hexo 基于 Node.js）的莫名亲近感，几个月前我就开始准备把博客换成 Hexo 的。 然后发现 Hexo 居然有一个跟我原来博客很像的主题，不过没有原来博客那么强大丰富的功能，我就打算基于这个主题自己把各种功能添加起来（挖了个巨坑）。后来填了几天的坑，完善了不少功能，然后就填不动了，就一直......

Posted by sjj118 on 2017-10-22

新评论插件

多说倒了之后就换了 Disqus，昨天 kcz 告诉我看不到我博客上的评论框才发现 Disqus 貌似被墙了，便打算再找一个评论插件。 先是在知乎上看到了 Gitment。由于这是个静态博客，只能把评论存到第三方平台上。而这个评论插件用 Github 帐号登录，然后把评论就会变成在 Github Issue 回复，插件再读取 Issue 中的内容显示到博客上。反正我博客也是放到 Github 上的......

Posted by sjj118 on 2017-08-11

多项式讲课课件

本来打算弄个 ppt 的，准备写的时候发现这个课件里要写很多公式，于是就顺便学了一下用 Latex 写 slide。 课件pdf 课件源代码 做课件好累啊，做了两个晚上的课件一个小时就讲完了。。 ......

Posted by sjj118 on 2017-08-09

退役感言

OI回忆录

0x0 2017 年 4 月 28 日下午，我坐在回温州的车上，还在思考着上午比赛的题目。突然，我想到了我第三题程序的一个 bug 。进省队的最后一丝希望，破灭了。 曾看过很多人写的退役感言，那时觉得退役还很远，没想到转眼间便到了退役的时候。发现我 OI 生涯的很多细节都记不清了，再过几年可能都忘了吧，于是就写了篇流水账记录一下。 0x1 2012 年的暑假，我正在洞头旅游。我妈接了一个电话后，告......

Posted by sjj118 on 2017-05-19

Kosaraju 算法

算法介绍： Kosaraju 算法是一个求强连通分量的算法。因为某道题要压位求强连通分量所以学习了一下这个算法，不过听说 tarjan 也能压位，然而我没有看懂。。 算法流程： 对原图进行 dfs ，记录 dfn 为每个节点的离开时间 按照 dfn 从大到小的顺序对反图进行 dfs ，能够遍历到的节点作为一个强连通分量。 算法证明： 充分性： 若两个点 a 和 b 在同一个强连通分量内，则步骤......

Posted by sjj118 on 2017-02-01

TCO2016 练习记录

已弃坑 1A EllysTree Description 给出一棵有根树，每次跳跃可以跳向当前节点的祖先或者是它子树中的节点。要求从根节点开始，经过每个节点一次且仅一次，求字典序最小的路径，或者说路径不存在。 Solution 假如没有字典序最小的限制，我们可以按照这样的策略：每次跳向能跳的节点中深度最大的节点。这个策略保证如果有解，那么这个策略一定能找到解。于是这个策略可以判断是否有解。 事实上......

Posted by sjj118 on 2017-01-17

Welcome

a new start

欢迎来到我的新博客 本博客基于 Jekyll + Github Pages，主题 fork 自 hux 。 一年前第一次建博客时，因为 wordpress 比较有名，所以打算用它建站，考虑过用 Github Pages 作主机，但 github 不支持数据库，只好租了个 36 元／年的虚拟主机。后来开始使用 markdown ，但一直没有找到比较优雅的在 wordpress 上通过 markdow......

Posted by sjj118 on 2017-01-04

比赛经验谈

如何保证正确 数组尽量开大（不要爆空间） 多组数据的题对拍也要造多组数据的数据 对拍很重要 对拍也不能保证完全正确 肉眼检查也很重要 long long保平安 一些检查的技巧 拷贝一份代码，将数组全都开大，跟原代码对拍，以检查数组越界 分块题将两个块大小不同的程序对拍 如何想出难题 想题目的广度很重要，如果在推导的过程中发现不对劲，要立即停下来重新看一看题目，或是检查一下推导中有没有考虑......

Posted by sjj118 on 2016-12-31

计数问题

一些零散的总结 计数问题是OI中很难的一类问题，往往能够考察选手的多方面能力。 计数问题的常见解法有以下几种： 递推与动规 容斥 组合数 生成函数 一道题目往往需要结合多种方法才能解决。 很多题目通过比较复杂的式子推导后往往能得出比较简洁的答案，所以找规律也是一种解题方法。 常用公式 组合数的重要公式：\(\sum_{k=0}^s\binom{k}{n}\binom{s-k}{m}=\bino......

Posted by sjj118 on 2016-12-09

图的匹配专题

对于二分图匹配的题目，我之前一直都是用网络流解决的，但是，二分图匹配的其它算法也有着自己的特点，在解决图的匹配问题时有时能够更简洁，更灵活，这些算法有时也能给我们解题带来启发。 二分图最大匹配 二分图最大匹配的常用算法是匈牙利算法，代码非常简洁： int find(int k){ for(int p=head[k];p;p=next[p])if(!used[to[p]]){ ......

Posted by sjj118 on 2016-11-27

POI2011练习记录

Conspiracy 可以发现这是一个2-sat模型，单2-sat只能求合法方案，不能求方案数。发现一个方案每个部分的人都最多有一个到另一个部分去，所以就可以枚举哪些人换位置判断是否合法了。 Lollipop 一个比较暴力的想法就是每个询问都利用单调性直接找区间，这样是\(O(nm)\)的。另a为原数组，s为其前缀和，我们发现在q<=s[n]时，如果固定左端点l为1，那么一定能找到一个右端点......

Posted by sjj118 on 2016-11-21

Hello World

此博客首次建立于2016年1月，湖南师大附中元旦培训期间。 早期的文章由于太傻已经被我基本删除。 ......

Posted by sjj118 on 2015-12-31