Sophonの博客

出于一些众所周知的原因，一些即时通讯软件不能很好地满足我们的需求： QQ/WeChat，国产+闭源+黑历史，不存在的 WhatsApp/iMessages，闭源的商业软件，再加上某Prism，不存在的 Signal/Jabber，在国内比较小众，用户数量太少 Telegram是什么 以下内容摘自维基百科： Telegram是跨平台的即时通信软件，其客户端是自由及开放源代码软件，但服务器是专有软件。用户可以相互交换加密与自毁消息，发送照片、影片等所有类型文件。官方提供手机版（Android、iOS、Windows Phone）、桌面版（Windows、macOS、Linux）和网页版等多种平台客户端；同时官方开放应用程序接口（API），因此拥有许多第三方的客户端可供选择，其中多款内置中文。 在墙越来越高的今天，许多软件都被证实并不可靠，前段时间升至爆出过腾讯一个数据方面的小主管就能调取聊天记录的新闻。于是乎，Sophon开始找在某些方面更优秀的IM（即时通讯）软件，然后就找到了Telegram。 Telegram有以下几个优势： 完全免费，多平台不限制同步消息，比微信QQ之流不 ...

思路 这道题可以从反面去考虑，即：先计算出不可能发生越狱的状态总数，并用它减去总状态数即为这道题要求的答案。 首先，在不失一般性的情况下，不妨设第一个房间里的犯人的宗教信仰为\(p\)，则第二个房间里的烦人的宗教信仰不能为\(p\)，因此第二个房间里的犯人的宗教信仰共有\((m - 1)\)种可能性。同理，第三个房间里的犯人的宗教信仰也共有\((m - 1)\)种可能性……故第二个到第\(n\)个房间里的烦人的宗教信仰共有\((n - 1)^{(m - 1)}\)种可能性。而第一个房间里的犯人的信仰有\(n\)种可能，故不可能发生越狱的状态总数为 \[n×(n - 1)^{(m - 1)}\] 那么，总状态数是多少呢？容易求的总状态数为\(n^m\)，所以题目所求为 \[n^m-n×(n - 1)^{(m - 1)}\] 这道题还有一个要注意的地方：\(m\)最大为\(10^8\)，因此要用快速幂来计算 AC代码： 1234567891011121314151617181920212223242526#include<iostream>using namespace std ...

在模拟赛中遇到了这道题。（后来才知道是SPOJ上的原题） 话不多说，开始动态规划三步走。\(Let's\ go!\) 定义状态 假设第1个人能够赢得整场决斗： 倘若把这位仁兄复制一份，放在\(n + 1\)的；那么，在一阵厮杀后，他和自己的分身应当能够相遇。那么，我们就和 在[NOI1995]石子合并中一样，将数组翻倍后再处理。 显而易见定义状态如下： \(dp_{i,j}\)为第\(i\)人与第\(j\)人是否能够相遇 状态转移方程 现在思考一下：第\(i\)人与第\(j\)人是否能够相遇？ 按照区间DP的思维，我们在\(i\)与\(j\)之间选取一个人\(k\) 若\(i\)与\(k\)能相遇，\(k\)与\(j\)能相遇，且\(i\)与\(j\)当中的任何一个人能干掉\(k\) 故状态转移方程为： \[dp_{i,j} = dp_{i,k} \&\&\ dp_{k,j} \&\&\ (w_{i,k} || w_{j,k})\] 边界条件 显然， 若两人本来就相邻，则\(dp_{i,j} = 1\) 代码 123456789101112131 ...

几年以前，我曾经嘲笑过某科技界大佬。当时他说：也许90后、95后会慢慢不知道谷歌是什么网站。 　　那一年，这对于我来说简直就是世界上最好笑的笑话。谷歌，全世界最卓越的互联网公司，活在互联网的一代中国人，会不知道他们的网站？ 　　今天，我收回这句嘲笑。因为这件不可能的事，它慢慢变成了现实。 　　没有人再关注什么谷歌不谷歌。对他们来说，百度也蛮好用的，反正他们几乎没用过谷歌。没有谷歌又怎样？大家还是开心的刷微博，看微信，听歌，看娱乐节目。对于从来就不知道谷歌的人来说，少了谷歌又有什么影响？ 慢慢的，就没有了，就像从未存在过 　　多年前，我们也是可以登陆Facebook的。其实这个网站和校内一样，也挺蠢的。可在上面你能看到老外们的生活，可以轻易的跟一万公里以外的人互相拜访，可以看到很多根本不会开到校内上的主页。你用汉语回复，下面给你聊起来的可能是香港仔，可能是台湾人。你用英语回复，说不定有比你英语用的更蹩脚的寂寞的北欧人来跟你搭讪。你感觉地球真的变成了地球村，你还没拉门走出去，别人就推门走了进来。 　　然后，它就没有了。起初，它的失踪激起了很大的声音，后来，声音就消失了。 　　多 ...

创刊期 创刊期 大家坚定一个信念吧: 我们是OIER 我们是O——I——E——R！ 我们是OIer， 所以我们 不用在跑道上挥汗如雨； 不用在球场上健步如飞； 更不用在没事的时候， 经受非人的体能训练…… 但是， 我们却要把头脑 高速运转， 还要接受一大堆 大学生也只是 “了解即可”的知识， 把一个个抽象的问题 转化为一篇篇 优美的代码， 才能在F9按下以后 获得欢呼。 不要以为我们 机房里没有风吹， 没有日晒， 就比勤劳的体育生们轻松， 只不过是大脑和四肢 的区别罢了。 可是， OIer的寂寞和委屈又有谁能懂？ 自习课鏖战机房， 却被认为而是逃课上网； 为荣耀耽误考试去比赛， 却被认为是逃避。 体育的同学们虽然辛苦， 但在挥汗如雨的背后， 有人在喝彩鼓掌； 在风吹日晒的同时， 有粉丝在仰慕。 而我们呢？ 与UnAC较劲的时候， 只有那一遍遍的运行窗口， 知道我们的不屈； 刷题的漫漫长夜， 只有陪伴我们的笔记本电脑， 知道我们的不懈； 在自习课别人学习的时候， 只有板砖般的算法导论， 知道我们的进取； 在机房泡得抢不上饭的时候， 只有五毛一包的干脆面， 知道我们的执着…… 没有人会理 ...

　　天冷极了，下着雪，又快黑了。这是NOIP的前夜。在这又冷又黑的晚上，一个衣衫破烂的小女孩在机房敲着代码。她从班里逃出来的时候还拿着一本算导，但是有什么用呢？那是一本很破旧的书——那么大，一向是她妈妈垫桌角的。她默写SPFA的时候，年级主任突然冲进机房，吓得她把算导都丢掉了。书叫一个学数竞捡起来拿着跑了。他说，他可以用那本书当草纸，证明切比雪夫定理。 　　小女孩只好自己写二叉堆，一双小脚冻得红一块青一块的。她面前的草纸堆得满满的，上面全是DP转移方程。这一整天，没有一个OJ让她AC一道题，她已经交了32遍采药了。 　　可怜的小女孩！她又冷又饿，浑身战栗地写着二叉堆。CRT显示器发出的光落在她的枯黄的长头发上，那干枯的头发打成卷儿披在肩上，看上去就像二叉树，不过她没注意这些。每个显示器里都透出光来，机房里飘着一股CPU发糊的怪味，因为这是NOIP前夜——她可忘不了这个。 　　她在主函数前面停了下来，蜷着趴在键盘上。她觉得更冷了。她不敢回家，因为她还没调完二叉堆，没写对一个DP方程，教练一定会骂她的。再说，换成别的数据结构，一样写不出来。这些题都太水，虽然神犇都写过题解了，但是题解上一般 ...

已死之人，向赴死者致敬。 我想要宪法赋予我的那个世界。 大概你的确是死了，但我们还在前行，消逝的能够被盖棺定论，而还存在着的仿徨呐喊抗争着，却在眨眼就会丧命，空中会窜出无敌吃人大蜥蜴，永远有儿童和女孩在惨叫的世界的黄昏里，拾起那一朵清晨看见过的花。 当你们的时代过去，请继续送出信息，好让下一个声音响起来对抗黑暗。 他们很快乐，至少在最后之前。不是所有的船都得在黑夜中航行。 你已经做完了你必须去做的事，现在，请休息吧，晚安。 我会使得我们的宇宙成为一个值得拯救的宇宙的。 她死在一个遥远的地方，脸上带着笑容，手里握着武器，身边围着敌人。她向我们展示了一个真正的战士应该是什么样子。 我看到一片广阔的海岸，在我们面前展现的事物超越头脑所能理解的范畴，沙滩上的每一粒沙子，每一滴水和空气分子都是在讲述一个故事。每个都是要被唱响的歌。他们每个人都充满生机，笑声，苦难和仇恨。他们都是一样的，即使他们都是不同的。 我爱你，红。我爱你，安娜。五年，十一个月，二十天。 那些受影响的人，是因为他们失去了他们内心世界的孩子。他们不能只看到最表面的东西，他们把自己的观点注入一切然后从中获取乐趣。 神破碎自己，我 ...

题目描述 洛谷P1226 说明 看到题解里貌似并没有Python的题解，我来发一个，共两行。 众所周知，为什么有时候洛谷er们要用Python呢？因为Python里已经包装了很多算法，用在OI中基本上等于打游戏时开外挂。虽然 对于这道题，Python 3中有一个数学函数pow()，它在help()函数中的说明是这样的： 12345pow(x, y, z=None, /) Equivalent to x**y (with two arguments) or x**y % z (with three arguments) Some types, such as ints, are able to use a more efficient algorithm when invoked using the three argument form. x**y % z，这正好就是这道题所用到的算法，所以直接调用pow(b, p, k)就OK了。一般来说，编程语言本身的库函数都会往死里优化，基本上不用担心时间复杂度的问题。（除了某些特别坑的） 最后要注意的一点就是，很多人提交Pyt ...

　　工业世界的政府，你们这些肉体和钢铁的巨人，令人厌倦，我来自赛博空间，思维的新家园。以未来的名义，我要求属于过去的你们，不要干涉我们的自由。我们不欢迎你们，我们聚集的地方，你们不享有主权。 　　我们没有民选政府，将来也不会有，所以我现在跟你们讲话，运用的不过是自由言说的权威。我宣布，我们建立的全球社会空间，自然地不受你们强加给我们的专制的约束。你们没有任何道德权利统治我们，你们也没有任何强制方法，让我们真的有理由恐惧。 　　政府的正当权利来自被统治者的同意。你们从来没有要求过我们的同意，你们也没有得到我们的同意。我们没有邀请你来，你们不了解我们，不了解我们的世界。赛博空间不在你们的疆界之内。不要认为你们可以建造这样一个疆界，好像建造一座公共建筑。你们没有这个能力。这个疆界是一件自然行为，它将从我们的集体行动中生发出来。 　　你们从来没有参加过我们的大会，你们也没有创造我们的市场财富。对我们的文化，我们的道德，我们的不成文法典，你们一无所知，这些法典已经在维护我们社会的秩序，比你们的任何强制所能达到的要好得多。 　　你们说我们有问题，你们要解决这些问题。你们用这个借口侵犯我们的领地。你 ...

本文同步发布于 Heliumの博客，到我的博客阅读体验更佳QwQ DNS是什么 DNS（Domain Name System）是一项网络服务，用途是对全球各个网站的域名进行解析。如果听不懂上面这句话也没关系，接下来会讲解。如果你是网络方面的大牛可以直接跳过或关闭此网页。 简明易懂的DNS 举个例子，从前有个叫小明的人（目测此人已累死），开了一家商店。一开始顾客要去购物时,就直接去商店里买。 但由于网络环境的复杂性，让顾客直接记住地址是不太可能的。（你试试看？）于是就有人动了脑筋，推出了一样类似DNS的服务：你只需要说出地点（小明杂货店），服务商就会开车送你去目的地。 很多大公司实际上都推出了这份服务，例如阿里，百度，谷歌，Cloudflare等。 实际网络中的DNS，则是向服务器询问域名，而服务器返回IP地址。 顺便推荐几个质量好的良心DNS如下： Cloudflare DNS: 1.1.1.1, 1.0.0.1 Google Public DNS: 8.8.8.8, 8.8.4.4 OpenDNS 208.67.222.222, 208.67.220.220 DNS查询 看到这里你可 ...