XenonWZH's Blog

卷了个寂寞？

0%

发表于 更新于 分类于 ， Disqus：

题意描述

洛谷链接

对于给出的 \(n\) 个询问，每次求有多少个数对 \((x,y)\)，满足 \(a \le x \le b\)，\(c \le y \le d\)，且 \(\gcd(x,y) = k\)，\(\gcd(x,y)\) 函数为 \(x\) 和 \(y\) 的最大公约数。

对于 \(100\%\) 的数据满足：\(1 \le n,k \le 5 \times 10^4\)，\(1 \le a \le b \le 5 \times 10^4\)，\(1 \le c \le d \le 5 \times 10^4\)。

阅读全文 »

发表于 更新于 分类于 ， Disqus：

莫比乌斯函数

了解莫比乌斯反演前，我们先要了解莫比乌斯函数。记 \(\mu(n)\) 为莫比乌斯函数，\(n\) 可被分解质因数为 \(n = \prod_{i = 1}^{m}{ {p_i}^{c_i} }\) 定义如下：

\[ \mu(n) = \begin{cases} 1 & n = 1 \\ 0 & \exists i \in [1, m], c_i > 1 \\ (-1)^m & \forall i \in [1, m], c_i = 1 \\ \end{cases} \]

形式化地解释一下：

  • 当 \(n = 1\) 时，\(\mu(n) = 1\)；
  • 当 \(n\) 存在至少一个出现次数大于等于两次的质因子时，\(\mu(n) = 0\)；
  • 当 \(n\) 的所有质因子仅出现过一次，且 \(n\) 有奇数个质因子时，\(\mu(n) = -1\)；
  • 当 \(n\) 的所有质因子仅出现过一次，且 \(n\) 有偶数个质因子时，\(\mu(n) = 1\)。
阅读全文 »

发表于 更新于 分类于 ， Disqus：

题意描述

洛谷链接

有一次，HKE 和 LJC 在玩一个游戏。

游戏的规则是这样的：LJC 在纸上写下两个长度均为 \(n\) 的数列 \(a\) 和 \(b\)，两个数列一一对应。HKE 每次可以找两个相邻的数 \(a_i\) 和 \(a_{i + 1}\)，如果它们两个不互质，HKE 可以选择得到 \((b_i + b_{i + 1})\) 分，然后擦掉 \(a\) 和 \(b\) 位置上的第 \(i, i + 1\) 个数，并把两个序列重新按顺序编号。当所有相邻的数互质时，游戏结束。

HKE 想知道他最大得分是多少。

阅读全文 »

发表于 更新于 分类于 ， Disqus：

题意描述

洛谷链接

LibreOJ 链接

小豆现在有一个数 \(x\) ，初始值为 \(1\) 。 小豆有 \(Q\) 次操作，操作有两种类型:

  • 1 m： \(x = x \times m\) ，输出 \(x \bmod M\) ；

  • 2 pos： \(x = x /\) 第 \(pos\) 次操作所乘的数（保证第 \(pos\) 次操作一定为类型 1，对于每一个类型 1 的操作至多会被除一次），输出 \(x\bmod M\) 。

阅读全文 »

发表于 更新于 分类于 ， Disqus：

题意描述

HydroOJ 链接

打开了黑魔法师 Vani 的大门，队员们在迷宫般的路上漫无目的地搜寻着关押 applepi 的监狱的所在地。突然，眼前一道亮光闪过。“我，Nizem，是黑魔法圣殿的守卫者。如果你能通过我的挑战，那么你可以带走黑魔法圣殿的地图……”瞬间，队员们被传送到了一个擂台上，最初身边有一个容量为 \(k\) 的包包。

擂台赛一共有 \(n\) 项挑战，各项挑战依次进行。第 \(i\) 项挑战有一个属性 \(a_i\)，如果 \(a_i \ge 0\)，表示这次挑战成功后可以再获得一个容量为 \(a_i\) 的包包；如果 \(a_i=-1\)，则表示这次挑战成功后可以得到一个大小为 \(1\) 的地图残片。地图残片必须装在包包里才能带出擂台，包包没有必要全部装满，但是队员们必须把获得的所有的地图残片都带走（没有得到的不用考虑，只需要完成所有 \(n\) 项挑战后背包容量足够容纳地图残片即可），才能拼出完整的地图。并且他们至少要挑战成功 \(l\) 次才能离开擂台。

队员们一筹莫展之时，善良的守卫者 Nizem 帮忙预估出了每项挑战成功的概率，其中第 \(i\) 项挑战成功的概率为 \(p_i\%\)。现在，请你帮忙预测一下，队员们能够带上他们获得的地图残片离开擂台的概率。

阅读全文 »

发表于 更新于 分类于 ， Disqus：

题意描述

洛谷链接

OI island 是一个非常漂亮的岛屿，自开发以来，到这儿来旅游的人很多。然而，由于该岛屿刚刚开发不久，所以那里的交通情况还是很糟糕。所以，OIER Association 组织成立了，旨在建立 OI island 的交通系统。

OI island 有 \(n\) 个旅游景点，不妨将它们从 \(1\) 到 \(n\) 标号。现在，OIER Association 需要修公路将这些景点连接起来。一条公路连接两个景点。公路有，不妨称它们为一级公路和二级公路。一级公路上的车速快，但是修路的花费要大一些。

OIER Association 打算修 \(n-1\) 条公路将这些景点连接起来（使得任意两个景点之间都会有一条路径）。为了保证公路系统的效率， OIER Association 希望在这 \(n-1\) 条公路之中，至少有 \(k\) 条 \((0 \le k \le n-1)\) 一级公路。OIER Association 也不希望为一条公路花费的钱。所以，他们希望在满足上述条件的情况下，花费最多的一条公路的花费尽可能的少。

而你的任务就是，在给定一些可能修建的公路的情况下，选择 \(n-1\) 条公路，满足上面的条件。

阅读全文 »

发表于 更新于 分类于 ， Disqus：

题意描述

HydroOJ 链接

Tim 正在摆弄着他设计的“计算机”，他认为这台计算机原理很独特，因此利用它可以解决许多难题。 但是，有一个难题他却解决不了，是这台计算机的输入问题。新型计算机的输入也很独特，假设输入序列中有一些数字（都是自然数——自然数包括 \(0\) ），计算机先读取第一个数字 \(s_1\) ，然后顺序向后读入 \(s_1\) 个数字。接着再读一个数字 \(s_2\) ，顺序向后读入 \(s_2\) 个数字……依此类推。不过只有计算机正好将输入序列中的数字读完，它才能正确处理数据，否则计算机就会进行自毁性操作！

Tim 现在有一串输入序列。但可能不是合法的，也就是可能会对计算机造成破坏。于是他想对序列中的每一个数字做一些更改，加上一个数或者减去一个数，当然，仍然保持其为自然数。使得更改后的序列为一个新型计算机可以接受的合法序列。

不过 Tim 还希望更改的总代价最小，所谓总代价，就是对序列中每一个数操作的参数的绝对值之和。

写一个程序：

  1. 从文件中读入原始的输入序列；
  2. 计算将输入序列改变为合法序列需要的最小代价；
  3. 向输出文件打印结果。

\(100\%\) 的数据满足：\(n < 1 \times 10^6 + 1\)

阅读全文 »