Description

题目链接:Codeforces 1153D

Serval 在一棵有根树上玩数字游戏。这棵有根树有 $n$ 个节点,节点 $1$ 是根节点,节点 $i$ 的父亲节点用 $f_i$ 表示。所有非叶子节点上有一个操作 $\max$ 或 $\min$,这意味着这个节点上的值为其所有儿子节点的最大值或最小值。

假设这棵树上有 $k$ 个叶子节点,Serval 会把 $1, 2, \dots, k$ 写在这 $k$ 个节点上(每个数字恰好使用 $1$ 次),并且他想要最大化根节点的值。作为他的好朋友,请你帮他求出根节点的最大值。

数据范围:$2 \le n \le 3 \times 10 ^ 5​$,$1 \le f_i \le i - 1​$。

- 阅读剩余部分 -

Description

题目链接:Codeforces 1138E

在国家 $N$ 中,有 $n$ 个城市通过 $m$ 条单向道路连接。尽管这个国家看起来并不是那么引人注目,但是这里有两件很有意思的事情。首先,这里的一周有 $d$ 天;另外,每个城市恰好有一个博物馆。

旅行社的员工知道每个博物馆的开放日期,他们正在为游客们制定一项新的旅游计划。旅游从标号为 $1$ 的首都城市出发,并且旅游的第一天必须在某一周的第一天。每天白天,如果当前城市的博物馆开放,那么游客可以进入博物馆参观;否则什么都做不了。晚上,游客要么结束旅游,要么通过道路前往下一个城市。注意,旅游过程中允许重复经过同一个城市。

你需要为旅游制定一条路线,使得在旅游期间参观的不同博物馆数量最多。

数据范围:$1 \le n \le 10 ^ 5$,$0 \le m \le 10 ^ 5$,$1 \le d \le 50$。

- 阅读剩余部分 -

Description

题目链接:LOJ 10059

有一个字符串 $S$。Farmer John 希望在 $S$ 中删掉 $n$ 个屏蔽词(一个屏蔽词可能出现多次),这些词记为 $t_1 \sim t_n$。

FJ 在 $S$ 中从头开始寻找屏蔽词,一旦找到一个屏蔽词,FJ 就删除它,然后又从头开始寻找(而不是接着往下找)。FJ 会重复这一过程,直到 $S$ 中没有屏蔽词为止。注意删除一个单词后可能会导致 $S$ 中出现另一个屏蔽词。这 $n$ 个屏蔽词不会出现一个单词是另一个单词子串的情况,这意味着每个屏蔽词在 $S$ 中出现的开始位置是互不相同的,请帮助 FJ 完成这些操作并输出最后的 $S$。

数据范围:$1 \le \lvert S \rvert, \sum\lvert t_i \rvert \le 10 ^ 5$。

- 阅读剩余部分 -

Description

题目链接:Codeforces 1151E

Kremland 的王国是有 $n$ 个节点的树,第 $i$ 个节点有权值 $a_i$,对于所有的 $1 \le i < n$ 都有一条连接节点 $i$ 和 $i + 1$ 的边。

对于整数 $l, r(l \le r)$,我们设函数 $f(l, r)$ 表示:

  • 我们将权值在区间 $[l, r]$ 内的点保留。
  • 函数的值为新图中连通块的数量。

你需要求出如下式子的值:

$$ \sum_{l = 1} ^ n \sum_{r = l} ^ n f(l, r) $$

数据范围:$1 \le n \le 10 ^ 5$,$1 \le a_i \le n$。

- 阅读剩余部分 -

Description

题目链接:LOJ 2095

我们知道,从区间 $[L, H]$($L$ 和 $H$ 为整数)中选取 $N$ 个整数,总共有 $(H - L + 1) ^ N$ 种方案。小 Z 很好奇这样选出的数的最大公约数的规律,他决定对每种方案选出的 $N$ 个整数都求一次最大公约数,以便进一步研究。然而他很快发现工作量太大了,于是向你寻求帮助。你的任务很简单,小 Z 会告诉你一个整数 $K$,你需要回答他最大公约数刚好为 $K$ 的选取方案有多少个。由于方案数较大,你只需要输出其除以 $10 ^ 9 + 7$ 的余数即可。

数据范围:$1 \le N, K \le 10 ^ 9​$,$1 \le L \le H \le 10 ^ 9​$,$H - L \le 10 ^ 5​$。

- 阅读剩余部分 -

Description

题目链接:LOJ 6229

这是一道非常简单的数学题。

最近 LzyRapx​ 正在看 mathematics for computer science 这本书,在看到数论那一章的时候,LzyRapx 突然想到这样一个问题。

$$ F(n) = \sum_{i = 1} ^ n \sum_{j = 1} ^ i \frac{\operatorname{lcm}(i, j)}{\gcd(i, j)} $$

其中,$\operatorname{lcm}(a, b)$ 表示 $a$ 和 $b$ 的最小公倍数,$\gcd(a, b)$ 表示 $a$ 和 $b​$ 的最大公约数。

给定 $n$ ,让你求: $F(n) \bmod (10 ^ 9 + 7)​$。

数据范围:$1 \le n \le 10 ^ 9$。

- 阅读剩余部分 -

Description

题目链接:LOJ 3083

Freda 学习了位运算和矩阵以后,决定对这种简洁而优美的运算,以及蕴含深邃空间的结构进行更加深入的研究。

对于一个由非负整数构成的矩阵,她定义矩阵的 $\text{AND}​$ 值为矩阵中所有数二进制 $\texttt{AND(&)}​$ 的运算结果;定义矩阵的 $\texttt{OR}​$ 值为矩阵中所有数二进制 $\texttt{OR(|)}​$ 的运算结果。

给定一个 $n \times n$ 的矩阵,她希望求出:

  1. 该矩阵的所有子矩阵的 $\texttt{AND}​$ 值之和(所有子矩阵 $\texttt{AND}​$ 值相加的结果)。
  2. 该矩阵的所有子矩阵的 $\texttt{OR}​$ 值之和(所有子矩阵 $\texttt{OR}​$ 值相加的结果)。

接下来的剧情你应该已经猜到——Freda 并不想花费时间解决如此简单的问题,所以这个问题就交给你了。

由于答案可能非常的大,你只需要输出答案对 $10 ^ 9 + 7​$ 取模后的结果。

数据范围:$1 \le n \le 10 ^ 3$,$\text{矩阵中的自然数} \le 2 ^ {31} - 1$。

- 阅读剩余部分 -

Description

题目链接:LOJ 3048

小粽是一个喜欢吃粽子的好孩子。今天她在家里自己做起了粽子。

小粽面前有 $n$ 种互不相同的粽子馅儿,小粽将它们摆放为了一排,并从左至右编号为 $1$ 到 $n$。第 $i$ 种馅儿具有一个非负整数的属性值 $a_i$。每种馅儿的数量都足够多,即小粽不会因为缺少原料而做不出想要的粽子。小粽准备用这些馅儿来做出 $k$ 个粽子。

小粽的做法是:选两个整数数 $l,r$,满足 $1\le l\le r\le n$,将编号在 $[l,r]$ 范围内的所有馅儿混合做成一个粽子,所得的粽子的美味度为这些粽子的属性值的异或和。

小粽想品尝不同口味的粽子,因此它不希望用同样的馅儿的集合做出一个以上的粽子。

小粽希望她做出的所有粽子的美味度之和最大。请你帮她求出这个值吧!

数据范围:$1 \le n \le 5 \times 10 ^ 5$,$1 \le k \le \min\left\{\frac{n(n - 1)}{2}, 2 \times 10 ^ 5\right\}$,$0 \le a_i \le 2 ^ {32} - 1$。

- 阅读剩余部分 -

Description

题目链接:LOJ 3052

距离苏拉威西只有一百公里了,车内的空气比窗外更加冰冷。四双眼睛紧盯着艾莉芬面前的屏幕,那是控制行星发动机的关键程序:春节十二响。他需要将其部署到电力控制系统的一个芯片中。

「春节十二响」由 $n$ 个子程序构成,第 $i$ 个子程序所需的内存空间是 $M_i$。这 $n$ 个子程序之间的调用关系构成了一棵以第 $1$ 个子程序为根的树,其中第 $i$ 个子程序在调用树上的父亲是第 $f_i$ 个子程序。

由于内存紧张,电力控制芯片上提供了一种内存分段机制。你可以将内存分为若干个段 $S_1, S_2, \dots, S_k$,并将每个程序预先分配到一个固定的段。如果两个子程序没有直接或间接的调用关系,则他们可以被分配到同一个段中,反之则不能。换言之,当且仅当 $a$ 和 $b$ 在调用树上不是祖先-后代关系,$a$ 和 $b$ 可以被分配到同一个段中。

一个段的大小应当是所有分配到这个段的子程序所需内存大小的最大值,所有段大小的和不能超过系统的内存大小。

现在艾莉芬想要知道,电力控制芯片至少要有多少内存,才能保证春节十二响的正确运行。即:最少需要多大的内存,才能通过先将内存分成若干个段,再把每个子程序分配到一个段中,使得每个段中分配的所有子程序之间不存在祖先-后代关系

数据范围:$1 \le n \le 2 \times 10 ^ 5$,$1 \le M_i \le 10 ^ 9$。

- 阅读剩余部分 -