假快读：
比 cin 快，比 scanf 优雅，比 read 好写，
namespace fira {
struct IO { } io; inline void print(char x) {putchar(x);}
template <typename T> inli...
环Description对于一个长度为 $n$ 的 $01$ 串，下标从 $0$ 到 $n-1$ 。定义两种类型的操作：
A类型：选择一个 $x$，将序列循环右移 $x$ 位，也就是新序列的第 $(i+x) \bmod n$ 位对应原序列的第 $i$ 位。
B类型：选择一个 $x$ ，满足序列的第 $x$ 个位置位 $1$ ，且第 $(x+1) \...
Pozhu: 挂分大赛
zerc: 我挂了 80，我说什么了么
所以有了对拍。
注：以下内容均在 Linux(WSL) 下进行。
#include <bits/stdc++.h>
#include <unistd.h>
using namespace std;
const int N = 100;
int main...
小 S 排座位
一对同桌的成绩之差的绝对值必须大于等于给定的常数 $K$，请你求出他最多能排出几对同桌。
答案的配对方式肯定是一段前缀和一段后缀按顺序进行匹配。
然后没有想到，就用了二分答案，
非常精简的做法：
cin >> n >> k, mid = n >> 1;
for (int i = 1; i &l...
众所周知，OI 中的数学不需要证明（最起码大部分是这样的，
所以，这篇博客只保留部分必要的证明。
壹·素数相关判定bool judge(int x) {
if (x < 2) return 0;
for (int i = 2; i * i <= x; i++)
if (x % i == 0) r...
NOIP 模拟赛（三十五）Problem A: 牛堡的十字路口
给定每条街道（南北向，东西向）和经过速度，求到每个交叉口的最短时间。
$10^5$
一种很自然的想法是暴力连边，跑最短路，但你不会发现从原点到目标点是一次函数，然后就是斜率优化 DP。
设 $(i,j)$ 为第 $i$ 行第 $j$ 列的位置。
考虑 dijkstra 求单源最短路...
引言AGC018C Coins 因为不想写反悔贪心所以去学 wqs 二分。
wqs 二分 最初由王钦石在他的 2012 年国家集训队论文中提出，而从 IOI 2016 的 Aliens 题目开始，这种方法开始逐步在竞赛圈中有了一定的地位。在国内一般称为「wqs 二分」，而在国外一般称为「Alien Trick」。
算法引入
有 $n$ 个物品，物品...
AtCoder Regular ContestARC069D Flags | Solution
将 $n$ 个标志放在数轴上。第 $i$ 个标志可以放置在坐标 $a_i$ 或 $b_i$ 上，求出两个标志之间最小距离的最大值。
$n\le10^4$
很显然的二分答案，成功将问题转化为在 $O(n \log n)$ 或 $O(n \sqrt{n}...
动规凸包一相逢，便胜却 oi 无数
CF1146H Satanic Panic
二维平面上有 $n$ 个点，找出来五个点使得形成一个五角星，求方案数。
首先五角星可以转化成 $5$ 个点的凸包，然后就可以用计算几何来求解。
怎么判断是否合法呢？可以用叉积，当然也可以通过极角排序保证合法，我用的是后者。
然后就是统计答案，这里用 DP，$f[i...
数据结构树Problem给定一棵 $n$ 个点的树，每条边有个正整数边权。有 $q$ 次修改操作，每次会修改一条边的边权。
在所有修改之前以及每次修改后，你需要求出有多少个无序点对满足它们之间的最短路径上所有边权的最大公约数 $=1$。
Solution首先考虑莫比乌斯反演，变为统计 $k∣gcd$ 的点对数量。 对于每个边权，首先去掉重...