Posts by hostmaster

题意 看守打算和 A 、 B 两名囚犯做一个游戏。首先，看守从一副牌中取出大小王，将剩余的 52 张牌洗好，并在桌子上从左至右地把它们摆成一排，每张牌都是正面朝上。然后，看守让囚犯 A 来到桌前，允许囚犯 A 观察牌面，并交换其中两张牌的位置。接着，看守将囚犯 A 关回牢房，把所有牌全都翻到背面朝上（但位置不变），让囚犯 B 来到桌前。看…

由于停课训练了，所以可能会提高更新频率。 一道趣题。 题意 无穷多个相同大小的正方形格子排成一排，向左右两边无限地延伸。每个格子里都有 $0$ 个、$1$ 个或多个原子。每一次，你可以对它们做下面两种操作之一： 选择某个格子，保证该格子内至少含有 $1$ 个原子。将该格子内的其中 $1$ 个原子分裂为 $2$ 个，从而使得该格子内的原子数…

题意 你有一个数 $a$，初始时是 $0$。 你要生成 $n$ 个对 $a$ 操作。每个操作可以是加 $1$，减 $1$，或者不变。 要求：任意时刻 $a \geq 0$，且最终 $l \leq a \leq r$，其中 $l$ 和 $r$ 是给定的。 答案对给定质数 $p$ 取模。 目前我的做法可以做到 $\mathcal O\left(n \log n\right)$…

题意 给定长度为 $n$ 的数组，求： $$\displaystyle\sum\limits_{i=1}^n\sum\limits_{j=i}^n \gcd\left\{a_i, a_{i + 1}, \ldots, a_j\right\}$$ 对 $998244353$ 取模。 题解 对于这个问题，$\gcd$ 是单调递减的，因此可以使…

闲聊 好久不见啊，终于放暑假了。这题好妙啊，写个题解吧。 题意 随机生成 $n$ 个点 $\left(x_i, y_i\right)$，你要用尽可能少的询问来找出这些点。坐标的绝对值不超过 $100$ 且任意两点之间的横纵坐标之差都大于等于 $1$。 每次询问给出 $a, b, c$，评测机按任意顺序返回这 $n$ 个点在直线 $ax + by + c = 0$…

方法 0 直接长链剖分，常数大 时间复杂度 $\Theta\left(n \log n + q\right)$ 方法 1 直接倍增 时间复杂度 $\Theta\left(n \log n + q \log n\right)$ 方法 2 使用重链剖分，跳到刚好超过 $k$ 级的链的顶端，然后通过 dfs 序推 $k$ 级祖先。 时间复杂度…

没想到真的能参加省选。 这次省选主要就是熟悉一下环境。 Day 1 首先开 T1，挺简单的，但是写了个小 Bug，好在没挂多少分。 后面的题完全不会啊，打暴力。 yq 同学没带身份证惨遭爆 0。 Day 2 好难好难，啥也不会，依旧是打暴力。 省选就这样结束了。。。

前置知识 普通莫队 算法 需要回滚莫队的问题一般不好增加或不好删除一个位置。 假设，现在我们维护的东西可以 $\mathcal O\left(1\right)$ 缩小区域，但是增加区域需要 $\mathcal O\left(n\right)$。 为了防止增加，我们可以将每个操作的右边界从大到小排序。 假设现在莫队维护的区域是 $\left[L, R\right]$…

此博客就是基于 Typecho 搭建的。使用感觉还不错。 我也试过 WordPress，感觉比较复杂，没有 Typecho 那么简洁。 第一步：安装博客 方案 1：免费版 免费版比付费版慢，而且还不支持地址重写功能。 地址重写功能就是，php 网站都会在域名后面跟一个 index.php，地址重写功能就是去掉这个东西。 我们可以使用 by…

这篇博客已过时 最新版 题意 有一个 $N$ 层的大楼，你有 $M$ 个鸡蛋。每个鸡蛋的硬度都是相同的。碎鸡蛋不能用来测试。你要求出 至少扔多少次才能保证测出鸡蛋的硬度。 假设你在第 $x$ 层扔下鸡蛋，如果鸡蛋碎了，说明鸡蛋硬度不能承受在 $x$ 层扔下。如果没碎则说明鸡蛋硬度能承受在 $x$ 层扔下。 题解 动态规划解法 首先，我们可…