打的有点雪崩，不过最后勉强算是苟住了。 第一小时做的还行，虽然wa了几法，但是签掉1002、1004和1006还是比较顺利的，但是因为三个人好像都不是很会做1011埋下了伏笔。3个题之后，因为不是很会1011所以转头开了1005和1010，当时我感觉都是很简单的题，1005用二分随便搞搞就好，就是细节比较烦，准备找ydl写；1010我听完题意感觉太…

幽香这几天学习了魔法，准备建造一个大型的时空传送阵。幽香现在可以在幻想乡的 $n$ 个地点建造一些传送门，如果她建造了从地点 $a$ 与地点 $b$ 之间的传送门，那么从 $a$ 到 $b$ 和从 $b$ 到 $a$ 都只需要单位 $1$ 的时间。同时这些地点之间在地理上是非常遥远的，因此来往他们必须使用传送门。现在幽香想要问你，有多少种建造传送门…

AtCoder Beginner Contest 189 题解 AC Codes A - Slot B - Alcoholic C - Mandarin Orange 寻找直方图的最大矩形。 单调栈经典问题。 D - Logical Expression 给定一个长度为 $n$ 且只含有 AND 和 OR 的逻辑序列 $S$ ，询问满足： \beg…

一个 $5\times 5$ 的矩阵，初始时有一只蚂蚁位于矩阵中心点，矩阵底层（第五行）每一个单元格上各放有一个种子。现在蚂蚁每次将会随机朝某一个相邻单元格（四相邻）移动，每当蚂蚁遇到一个种子时，它会拿起种子（如果已经拿了一个种子就不能再拿了），当蚂蚁将种子搬运到第一行的某个空单元格后就会将种子放下。当第一行放满种子后，蚂蚁将会停止移动。询问蚂蚁的…

马尔可夫链 持续更新中。。。 1. 简介 1.1 定义 我们一般这样描述马尔可夫过程（也叫马尔可夫链）：假设有一系列状态集合 $S=\{s_1,s_2,\ldots,s_r\}$ ，马尔可夫过程（Markov process）是从这些状态中的某一个开始，从一种状态连续移动到另一种状态。每一次移动被称为一步（step）。如果当前位于状态 $s_i$ …

AtCoder Beginner Contest 129 题解 AC Codes A - Airplane B - Balance C - Typical Stairs D - Lamp 给定一个 $H\times W$ 的带障碍物的网格图，询问在某个点放一盏灯最多能够照亮几个单元格。灯只能照亮上下左右四个方向，并且光线遇到障碍物后就会停止。 $H…

AtCoder Beginner Contest 128 题解 AC Codes A - Apple Pie B - Guidebook C - Switches 求解异或方程组的裸题，直接高斯消元后求自由元的个数即可。不过由于数据范围小，暴搜其实就可以做了。 D - equeue 给定一个双端队列，里面有 $N$ 个整数，你可以进行如下 $4$ …

AtCoder Beginner Contest 139 题解 AC Codes A - Tenki B - Power Socket C - Lower D - ModSum 很容易构造出答案为 $\frac{N(N-1)}{2}$ 。 E - League 同一轮中可以参加比赛的人一定是一系列二元环，因此可以用一个优先队列维护比赛的轮次，当某两…

黎曼zeta函数和素数分布的一个小结论 今天发现了一个问题的巧妙解法，记录一下。 问题引入：任取两个自然数 $a,b$ ，求 $a,b$ 互质的概率。 设 $\gcd(a,b)=n$ 的概率为 $p(n)$ 。注意到 $\gcd(a,b)=n$ 的充要条件是 $n|a,n|b$ 并且 $\gcd(\frac{a}{n},\frac{b}{n})=1…

AtCoder Beginner Contest 130 题解 AC Codes A - Rounding B - Bounding C - Rectangle Cutting 只用一刀将一个矩形的面积平分，显然需要经过矩形的几何中心。 D - Enough Array 寻找数列 $A$ 中有几个和不小于 $K$ 的连续子序列。 两种方法： 固定左…