Description

题目链接:ARC 102C

Takahashi 有 $n$ 个骰子,每个骰子有 $k$ 个面分别标号为 $1$ 到 $k$。对于每个 $i = 2, 3, \dots, 2k$,求满足以下条件的方案数对 $998244353$ 的值。

  • 投掷这 $n$ 个骰子,没有任何两个不同骰子的数字之和为 $i$。

注意骰子之间是相同的。也就是说,当存在整数 $k$ 使得两个方案数数字 $k$ 的骰子数量不同,那么这两个方案被认为是不同的。

数据范围:$2 \le n \le 2000$,$1 \le k \le 2000$。

- 阅读剩余部分 -

Description

题目链接:ARC 102B

给定一个整数 $L$,构造一张满足如下条件的有向图。图中可以包含重边,可以证明这样的图一定是存在的。

  • 这张图的点数 $n$ 至多为 $20$,点从 $1$ 到 $n$ 标号。
  • 这张图的边数 $m$ 至多为 $60$,边的长度为 $[0, 10 ^ 6]$。
  • 每条边从标号小的点连向标号大的点,也就是说 $1, 2, \cdots, n$ 是这张图的一种可能的拓扑序。
  • 从点 $1$ 到 $n$ 有 $L$ 条不同的路径,这些路径的长度两两不同,长度分别为 $0$ 到 $L - 1$。

此处路径的长度为这条路径上所有边的长度之和。当两条路径包含的边的集合不同时,这两条路径是不同的。

数据范围:$2 \le L \le 10 ^ 6$。

- 阅读剩余部分 -

Description

题目链接:ARC 103D

你有一个长度为 $n$ 的序列 $D_1, D_2, \cdots, D_n$,所有的 $D_i$ 是两两不同的。是否存在一棵树满足如下条件?

  • 节点从 $1$ 到 $n$ 标号,边从 $1$ 到 $n$ 标号。
  • 对于每个节点 $i$,它到其他节点的距离之和为 $D_i$,注意每条边的长度都是 $1$。

如果存在这样一棵树,求出这棵树。

数据范围:$2 \le n \le 10 ^ 5$,$1 \le D_i \le 10 ^ {12}$。

- 阅读剩余部分 -

Description

题目链接:ARC 103C

你有一个长度为 $n$ 的字符串 $s$。是否存在一棵有 $n$ 个节点的树满足如下条件?

  • 节点从 $1$ 到 $n$ 标号。边从 $1$ 到 $n - 1$ 标号。
  • 如果字符串 $s$ 的第 $i$ 个字符为 $1$,那么我们可以通过删掉其中一条边得到一个大小为 $i$ 的连通块。
  • 如果字符串 $s$ 的第 $i$ 个字符为 $0$,那么我们不能通过删掉任何一条边得到一个大小为 $i$ 的连通块。

如果存在这样一棵树,求出这棵树。

数据范围:$2 \le n \le 10 ^ 5$。

- 阅读剩余部分 -

Description

题目链接:ARC 103B

Snuke 正在向他的工厂介绍一款机械臂:

  • 机械臂由 $m$ 个部分和 $m + 1$ 个关节组成,关节标号为 $0$ 到 $m$。第 $i$ 个部分连着第 $i - 1$ 和 $i$ 个关节。第 $i$ 个部分的长度为 $d_i$。
  • 对于每个部分,可以单独指定其动作。现在有 $4$ 种模式:$\text{L}$、$\text{R}$、$\text{D}$ 和 $\text{U}$。如果我么把工厂视为坐标平面,那么关节 $i$ 的位置将通过如下方法确定(我么将它的坐标表示为 $(x_i, y_i)$):

    • $(x_0, y_0) = (0, 0)$。
    • 如果第 $i$ 个模式为 $\text{L}$,那么 $(x_i, y_i) = (x_{i - 1} - d_i, y_{i - 1})$。
    • 如果第 $i$ 个模式为 $\text{R}$,那么 $(x_i, y_i) = (x_{i - 1} + d_i, y_{i - 1})$。
    • 如果第 $i$ 个模式为 $\text{D}$,那么 $(x_i, y_i) = (x_{i - 1}, y_{i - 1} - d_i)$。
    • 如果第 $i$ 个模式为 $\text{U}$,那么 $(x_i, y_i) = (x_{i - 1}, y_{i - 1} + d_i)$。

Snuke 想要引入一种机械臂,以便通过正确的指定模式,使得关节 $m$ 可以到达所有的 $n$ 个点 $(X_1, Y_1), (X_2, Y_2),\cdots, (X_n, Y_n)$。请判断这是否可行。如果可行,那么请你构造一个满足条件的机械臂,并分别给出到达 $n​$ 个点的模式方案。

在你构造出的方案中,必须满足 $1 \le m \le 40$,$1 \le d_i \le 10 ^ {12}​$。

数据范围:$1 \le n \le 1000$,$-10 ^ 9 \le X_i, Y_i \le 10 ^ 9$。

- 阅读剩余部分 -

Description

题目链接:Codeforces 1073G

定义 $\text{LCP}(s, t)$ 字符串 $s$ 和 $t$ 的最长公共前缀,再定义 $s[x\dots y]$ 为字符串 $s$ 从位置 $x$ 到 $y$ 的子串。

给定一个长度为 $n$ 的字符串 $s$ 和 $q$ 个询问。每次询问给出两个长度分别为 $k_i, l_i$ 的序列 $a, b$。你需要计算 $\sum_{i = 1} ^ k \sum_{j = 1} ^ l \text{LCP}(s[a_i \dots n], s[b_j \dots n])$ 的值。

数据范围:$1 \le n, q, \sum k_i, \sum l_i \le 2 \times 10 ^ 5$,$1 \le k_i, l_i \le n$。

- 阅读剩余部分 -

Description

题目链接:Codeforces 452E

你有三个字符串 $(s_1, s_2, s_3)​$。对于每个整数 $l(1 \le l \le \min(\vert s_1 \vert, \vert s_2 \vert, \vert s_3 \vert)​$,你需要求出有多少三元组 $(i_1, i_2, i_3)​$ 满足 $s_k[i_k \dots i_k + l - 1](k = 1, 2, 3)​$ 两两相等。答案对 $10 ^ 9 + 7​$ 取模。

数据范围:$3 \le \sum_{i = 1} ^ 3 \vert s_i \vert \le 3 \times 10 ^ 5$。

- 阅读剩余部分 -

Description

题目链接:Codeforces 204E

小象非常喜欢字符串。他拥有 $n$ 个包含小写字母的字符串,第 $i$ 个字符串记为 $a_i$。对于每个字符串 $a_i(1 \le i \le n)$,小象想要求出二元组 $(l, r)$ 的对数,其中 $(l, r)$ 需要满足:$1 \le l \le r \le \lvert a_i \rvert$ 且子串 $a_i[l\dots r]$ 是至少 $k$ 个字符串的子串。

数据范围:$1 \le n, k \le 10 ^ 5$,$\sum_{i = 1} ^ n \lvert a_i \rvert \le 10 ^ 5$。

- 阅读剩余部分 -

Description

题目链接:Codeforces 271D

你有一个包含小写字母的字符串 $S​$,有一些字母是好的,其余的是坏的。如果在 $S_l, S_{l + 1}, \cdots, S_r​$ 中有至多 $k​$ 个坏的字母,那么子串 $S_{l,r}​$ 是好的。

你需要找出 $S​$ 中本质不同的好的子串数量。两个子串 $S_{x, y}​$ 和 $S_{p, q}​$ 是不同的当且仅当 $S_{x, y} \ne S_{p, q}​$。

数据范围:$1 \le \lvert S \rvert \le 1500$,$0 \le k \le \lvert S \rvert$。

- 阅读剩余部分 -

Description

题目链接:SPOJ 220

你是 Byteland 的国王,你的特工刚刚截获了 $n$ 条敌方的加密信息 $s_i$。你请来的密码学家声称他只能解密文本中最重要的部分,这个文字片段在所有信息中至少出现 $2​$ 次且不相交。你需要求出这个文字片段的最长长度。

本题有 $T$ 组数据。

数据范围:$1 \le T \le 10$,$1 \le n \le 10$,$2 \le \lvert s_i \rvert \le 10 ^ 4$。

- 阅读剩余部分 -