Description

题目链接：ARC 102C

Takahashi 有 $n$ 个骰子，每个骰子有 $k$ 个面分别标号为 $1$ 到 $k$。对于每个 $i = 2, 3, \cdots, 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 \le 2 \times 10 ^ 5$，$1 \le k_i, l_i \le n$，$\sum_{i = 1} ^ q k_i \le 2 \times 10 ^ 5$，$\sum_{i = 1} ^ q l_i \le 2 \times 10 ^ 5$。

- 阅读剩余部分 -

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 \vert a_i \vert$ 且子串 $a_i[l\dots r]$ 是至少 $k$ 个字符串的子串。

数据范围：$1 \le n, k \le 10 ^ 5$，$\sum_{i = 1} ^ n \vert a_i \vert \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 \vert S \vert \le 1500$，$0 \le k \le \vert S \vert$。

- 阅读剩余部分 -

Description

题目链接：SPOJ 220

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

本题有 $T$ 组数据。

数据范围：$1 \le T \le 10$，$1 \le n \le 10$，$2 \le \vert s_i \vert \le 10 ^ 4$。

- 阅读剩余部分 -

  1. 1
  2. 2
  3. 3
  4. 4
  5. ...
  6. 12