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$ 的连续子序列。 两种方法： 固定左…

AtCoder Beginner Contest 127 题解 AC Codes A - Ferris Wheel B - Algae C - Prison D - Integer Cards 有 $N$ 张卡片，每张卡片上有一个数字 $A_i$ ，现在你有 $M$ 次操作，每次操作你都可以选择不超过 $B_j$ 张卡片，将这些卡片上的数字改写为 …

AtCoder Beginner Contest 126 题解 AC Codes A - Changing a Character B - YYMM or MMYY C - Dice and Coin D - Even Relation 给定一棵 $N$ 个点的树，每条边 $(u_i,v_i)$ 都有边权 $w_i$ ，你需要对树上每个点进行黑白染…

AtCoder Beginner Contest 205 AC Codes A - kcal B - Permutation Check C - POW 大力分类讨论。小心两边取 $\log$ 的操作，因为可能会出现 $\log 0$ 这种情况。 D - Kth Excluded 给定一个大小为 $N$ 的正整数数列 $A$ ，询问不属于数列 $A…

AtCoder Beginner Contest 178 题解 AC Codes A - Not B - Product Max C - Ubiquity 询问有多少大小为 $N$ 的数列 $A$ 满足以下条件： 任意一个 $A_i\in[0,9]$ 。 至少存在一个 $8$ 和一个 $9$ 。 $N\leq 2\times 10^5$ 。 简单容…

AtCoder Beginner Contest 179 题解 AC Codes A - Plural Form B - Go to Jail C - A x B + C 直接暴力枚举就能 $O(N\log N)$ 解决了。但是本题还可以优化为 $O(\sqrt{N})$ 。我们可以改写问题为：有几对 $(A,B)$ 满足 $AB\leq N$ 。…