Sophonの博客

本文放弃一切经济权利，各网站、公号和其他各类载体可在保持原文完整的基础上自由转载。 这个周末，维基百科终于整体离我们而去。它的404，意味着13亿人再次被隔离于一个“普世产品”之外。 Pingwest创始人托马斯·骆在山寨发布会群里分享了他勤奋更新的微信公众号文章，《自由和美好的事物总是戛然而止：比如约翰 列侬和维基百科》（点击链接可以访问过去，做好他的公众号无所不谈的准备，虽然都挺有趣的）。 知乎讨论这个问题的500多个回答在昨天上午戛然而止，消失无踪。托马斯的这篇文字也不知道能生存到何时。互联网这片沃土在别的地方长出了很多参天大树，在中国却总像城市人行道水泥砖之间的野草，顽强地露头，被碾压而过；又螳臂挡车地冒头，再被碾压。周而复始。 在这些野草之中，我翻出了2010年时采访第一个中文维基百科词条创建者、“维基”这个译名的提出者的随笔。当他以及最早期的维基中文十三人确定这个译名并胼手砥足地一条一条建立起中文维基时，未必能看到这灰暗的未来。但他接受采访时的淡然和话语间隐隐透露出的理想主义，却正是这些年来激励人们前赴后继地传播光明的原动力。 这篇东西同样不知道能存活多久，所以本文开头 ...

说明 看标签 枚举，模拟，暴力。 很容易想到开一个大小N * N 的二维数组，然而数据范围是0 ≤ N ≤10,000 数组大小：10000 * 10000 = 100000000 Byte = 100000 KB = 100MB 刚好跨过了RE与MLE的红线。 另外一种方法是用四个数组来记录长方形的四个参数，再扫一遍检查最上面的地毯。 亲测，完美AC。 代码 1234567891011121314151617181920212223242526#include<stdio.h>const int MAXN = 10000 + 5;//程序里出现幻数可不是好习惯哦~int a[MAXN], b[MAXN], g[MAXN], k[MAXN];int main() { int n, x, y; scanf("%d", &n); for(int i = 0; i < n; i++) { scanf("%d%d%d%d", &a[i], &b[i], ...

2019年4月10日9：00，人类首张对黑洞进行直接拍摄的照片发布。 这张照片可能并不符合许多人想象中常见的“漩涡”形象，但这是最符合目前学术界公认理论的形象。爱因斯坦，史瓦西，克尔，霍金等历代科学家的理论终于在这一天得到了论证，只不过他们都没有活到看到他们预言之物终于被光学设备记录到的那一天。 “黑洞”这个概念在20世纪就早已名扬四海，但这个概念一直只是存在于物理学家的计算中，这多少让人想起海王星，但海王星被计算出后几乎是立刻就被天文望远镜所发现，而黑洞从被计算出（1915年12月德国天文学家卡尔·史瓦西计算出爱因斯坦方程的黑洞解。）到2019年黑洞终于被人类的天文望远镜拍摄到，时隔整整103年。

题目描述 棋盘上\(A\)点有一个过河卒，需要走到目标\(B\)点。卒行走的规则：可以向下、或者向右。同时在棋盘上\(C\)点有一个对方的马，该马所在的点和所有跳跃一步可达的点称为对方马的控制点。因此称之为“马拦过河卒”。 棋盘用坐标表示，\(A\)点\((0, 0)\)、\(B\)点\((n, m)\)(\(n\), \(m\)为不超过\(20\)的整数)，同样马的位置坐标是需要给出的。 现在要求你计算出卒从\(A\)点能够到达\(B\)点的路径的条数，假设马的位置是固定不动的，并不是卒走一步马走一步。 输入输出格式 输入格式： 一行四个数据，分别表示\(B\)点坐标和马的坐标。 输出格式： 一个数据，表示所有的路径条数。 输入输出样例 输入样例#1： 6 6 3 3 ## 输出样例#1： 6 # 说明 结果可能很大！ * * * 看到题目二话不说用了搜索，直到在提交前看了一下算法标签，又看了一下数据范围。。。 状态转移方程的推导并不复杂，每次判断卒是否能走到这个格子，不可以则为0（显而易见），可以则为下方与左方的值之和。 上代码，这道题算是一道DP入门题吧。 12345678910 ...

对于初学计算几何的OIer来说，Graham算法是个不错的凸包算法。Graham算法相比极角排序法来说，更为直观也更容易理解。 数据定义 12345678910111213141516171819202122232425262728293031323334353637383940class Point {public: double x, y; Point(double x = 0, double y = 0):x(x), y(y) {} Point(Point a, Point b) { //构造从a到b的向量 x = b.x - a.x; y = b.y - a.y; } double dist(const Point& p) const { //计算从自身到点P的距离 return sqrt((x - p.x) * (x - p.x) + (y - p.y) * (y - p.y)); } d ...

前言 伸展树（英语：Splay Tree）是一种能够自我平衡的二叉查找树，它能在均摊O(log n)的时间内完成基于伸展（Splay）操作的插入、查找、修改和删除操作。 众所周知，普通BST在进行各种操作时很容易因为左子树与右子树高度差的问题导致时间复杂度退化为O(n)，Splay为了避免这个问题，使用了一种叫做“伸展”的操作来使左右子树平衡，在后面会介绍。 定义 节点 node.v：节点node的值 node.father：节点node的父节点 node.ch[0]与node.ch[1]：节点node的左子节点与右子节点 node.size：以节点node为根节点的子树的节点总数 node.cnt：数值与节点node相同的节点的数量（都储存在节点node中） 代码： 12345678class Node {public: int v, father, ch[2], size, cnt; Node(int v = 0, int father = 0, int size = 0, int cnt = 0):v(v), father(father), size(siz ...

一维数据结构学习笔记 链表 链表:按顺序记录元素的线性数据结构。 其中的“顺序”是逻辑上的顺序，不一定是物理存储上的顺序。 链表分为单向与双向两种： 1.单向链表:每个元素只记录了下一个元素的位置。 2.双向链表:每个元素记录了上一个及下一个元素的位置。 代码实现： 123456789//用类来定义链表中的每个元素。class Node {public: int v = 0; Node * next = NULL, * prev = NULL; /*前一个元素或者后一个元素可以不存在，所以必须要使用指针类型。*/ Node(int v = 0, Node * next = NULL, Node * prev = NULL):v(v), next(next), prev(prev) {}}; ### 链表常用操作:构造链表 通过实例化链表类，创建链表的每个元素并建立元素之间的关系。 代码实现： 123456//构造一个只有头尾两个元素的链表。Node* head = new Node(); Node* tail = ...

题目背景 \(B\)地区在地震过后，所有村庄都造成了一定的损毁，而这场地震却没对公路造成什么影响。但是在村庄重建好之前，所有与未重建完成的村庄的公路均无法通车。换句话说，只有连接着两个重建完成的村庄的公路才能通车，只能到达重建完成的村庄。 题目描述 给出\(B\)地区的村庄数\(N\)，村庄编号从\(0\)到\(N-1\)，和所有\(M\)条公路的长度，公路是双向的。并给出第\(i\)个村庄重建完成的时间\(t_i\)，你可以认为是同时开始重建并在第\(t_i\)天重建完成，并且在当天即可通车。若\(t_i\)为\(0\)则说明地震未对此地区造成损坏，一开始就可以通车。之后有\(Q\)个询问\((x, y, t)\)，对于每个询问你要回答在第\(t\)天，从村庄\(x\)到村庄\(y\)的最短路径长度为多少。如果无法找到从\(x\)村庄到\(y\)村庄的路径，经过若干个已重建完成的村庄，或者村庄\(x\)或村庄\(y\)在第\(t\)天仍未重建完成 ，则需要返回\(-1\)。 输入输出格式 输入格式： 第一行包含两个正整数\(N,M\)，表示了村庄的数目与公路的数量。 第二行包含\(N ...

出师 （1） 起床看见洛谷首页上显示的“距NOIP2018还有-1天”时，差点把嘴里的一口早饭喷了出来。 不过又想一下，要是一大早看见个“距NOIP2019还有365天”，估计瞬间会感觉压力山大。。。 进考场前竟然下起了倾盆大雨，从地铁站出来后，举着伞转了一个小时才找到考场，期间不停的被地图坑。 （我才不会告诉你浪费这么多时间的真正原因是使用迭代加深搜索找考场。） 进了考场发现有惊喜。。。机房竟然有网！有网！结果在考试前网断了。。。然后开始调整编辑器，以至于没注意到别人都开始打代码了。。。 第一题，水题，鉴定完毕。 分析：可能连模拟都算不上，直接从头到尾扫描一遍即可。 但虽说是水题，也有一些坑点： 1. 读入要用 string + cin + getline()! 读入要用 string + cin + getline()! 读入要用 string + cin + getline()! 重要的事情说三遍！ @垃圾一个 就是在这一点上炸了。 判断时要自编函数或alnum，不能用ctype.h中的isprint()函数，要用isalnum()函数。 如果你问"isprint( ...

折腾一番后终于把之前的文章迁移到GitHub Pages + Hexo的博客上了，之所以选择GitHub是因为这个平台忽然关闭的可能性很小，并且可定制性极强，虽然只能做静态网页，但搭个博客还是绰绰有余的。 从另一方面来讲，GitHub的信誉也不错，在服务品质上也比国内的诸多流氓公司强得多。 扯了这么多，博客的本质还是发布文章，就看自己能否坚持写下去了。