社区讨论

快来做DeepSeek出的“省选”题！！！

llibu2333
灌水区参与者 6已保存回复 13

讨论操作

快速查看讨论及其快照的属性，并进行相关操作。

当前回复
12 条
当前快照
1 份
快照标识符
@m6upkniz
此快照首次捕获于
2025/02/07 19:54
去年
此快照最后确认于
2025/02/07 22:19
去年
查看原帖
rt,题目如下：

1. 有效括号子序列计数

题目描述

给定一个仅由 '(' 和 ')' 组成的字符串 S，求其不同的有效括号子序列的个数。子序列不要求连续，但不同的位置选择视为不同的子序列，即使它们形成的括号序列相同。
有效括号子序列必须满足：
  1. 左右括号数量相等；
  2. 任意前缀中左括号数不少于右括号数。
由于答案可能很大，请输出结果对 109+710^9+7 取模后的值。

输入格式

输入第一行包含一个整数 TT，表示测试数据组数。
接下来 TT 行，每行一个字符串 SS。

输出格式

输出 TT 行，每行一个整数，表示对应答案。

样例 #1

样例输入 #1

CPP
3
()
()()
(())

样例输出 #1

CPP
1
3
2

提示

样例解释

第三组数据中，字符串 (()) 的有效子序列为：
  • 选取第 1 和第 2 个字符得到 ()
  • 选取第 1 和第 4 个字符得到 ()
  • 选取第 2 和第 3 个字符得到 ()
  • 选取第 3 和第 4 个字符得到 ()
  • 选取所有字符得到 (())
    总共有 55 个，但样例输出为 22。注意题目中子序列需满足有效条件，例如选取第 1 和第 4 个字符时，前缀顺序为 ()，满足条件。

数据范围

对于所有测试点，保证 1≤T≤101 \leq T \leq 10，1≤∣S∣≤10001 \leq |S| \leq 1000。

2. 最长重复子串

题目描述

给定一个字符串 SS 和一个整数 kk，找出 SS 中最长的子串，该子串至少出现 kk 次（出现位置可以重叠）。若存在多个最长子串，输出任意一个；若不存在，输出 -1。

输入格式

第一行输入整数 TT，表示数据组数。
每组数据包含两行：第一行为字符串 SS，第二行为整数 kk。

输出格式

输出 TT 行，每行一个字符串或 -1。

样例 #1

样例输入 #1

CPP
2
ababa
2
aaaaa
3

样例输出 #1

CPP
aba
aaa

提示

数据范围

对于所有测试点，保证 1≤T≤101 \leq T \leq 10，2≤k≤∣S∣2 \leq k \leq |S|，1≤∣S∣≤1041 \leq |S| \leq 10^4。

3. 分割回文串 II

题目描述

给定一个字符串 SS，将其分割成若干子串，使得每个子串都是回文。求最少需要分割几次。若无法分割，输出 -1。

输入格式

第一行输入整数 TT，表示数据组数。
接下来 TT 行，每行一个字符串 SS。

输出格式

输出 TT 行，每行一个整数。

样例 #1

样例输入 #1

CPP
3
aab
a
ab

样例输出 #1

CPP
1
0
-1

提示

数据范围

对于所有测试点，保证 1≤T≤101 \leq T \leq 10，1≤∣S∣≤10001 \leq |S| \leq 1000。

4. 编辑距离

题目描述

给定两个字符串 AA 和 BB，求将 AA 转换为 BB 所需的最小操作次数。允许的操作包括：插入一个字符、删除一个字符、替换一个字符。

输入格式

第一行输入整数 TT，表示数据组数。
每组数据包含两行：第一行为字符串 AA，第二行为字符串 BB。

输出格式

输出 TT 行，每行一个整数。

样例 #1

样例输入 #1

CPP
2
kitten
sitting
abc
abd

样例输出 #1

CPP
3
1

提示

数据范围

对于所有测试点，保证 1≤T≤101 \leq T \leq 10，1≤∣A∣,∣B∣≤10001 \leq |A|, |B| \leq 1000。

回复

共 13 条回复，欢迎继续交流。

正在加载回复...