A1442 | 微妙的减法
来源官方 / 2023
时间限制1s
内存限制128MB
通过 / 提交0/0
题目描述
$AC$ 狗和小$D$ 正在玩字符串游戏。游戏将进行 $t$ 轮，每一轮中，都会给定一个由小写字母组成的字符串 $s$。
$AC$ 狗先走，两个玩家轮流进行操作。$AC$ 狗被允许删除 $s$ 中任何偶数长度的子串（可能为空串），小$D$ 被允许删除 $s$ 中任何奇数长度的子串。
例如，字符串 $s=$
$s$ 变为空串后，该轮游戏结束，每个玩家计算他本轮的分数。玩家的分数是他移除的所有字符的总和，其中
$AC$ 狗先走，两个玩家轮流进行操作。$AC$ 狗被允许删除 $s$ 中任何偶数长度的子串（可能为空串），小$D$ 被允许删除 $s$ 中任何奇数长度的子串。
例如，字符串 $s=$
s1s2......sk，玩家可以选择奇数长度或者偶数长度的子串 slsl+1......sr-1sr 并删除，$s$ 变为 s1....sl-1sr+1......sk。$s$ 变为空串后，该轮游戏结束，每个玩家计算他本轮的分数。玩家的分数是他移除的所有字符的总和，其中
a 的值为 $1$，b 的值为 $2$，c 的值是 $3$......z 的值是 $26$。得分高的玩家赢得本轮的游戏。对于每一轮，假设两名玩家都是以最佳的状态参加游戏，他们会最大限度的提高自己的得分，你需要确定获胜者是 $AC$ 狗还是小 $D$，还需要确定胜者与败者之间的分数差（分数差大于 $0$）。（可以证明，平局是不可能的）输入格式
输入的第一行包含一个整数 $t$ ($1 \le t \le 5 \times 10^3$) 表示轮数。
接下来的每一行一个字符串 $s$。($1 \le |s| \le 2 \times 10 ^ 3$)
接下来的每一行一个字符串 $s$。($1 \le |s| \le 2 \times 10 ^ 3$)
输出格式
对于每一轮，打印一行包含一个字符串和一个整数。如果 $AC$ 狗赢得了这一轮，字符串为
AC。如果小 $D$ 赢得了这一轮，则字符串为 D。整数为胜者与败者之间的分数差。输入输出样例
输入 #1
5 aba abc cba n acgo
输出 #1
AC 2 AC 4 AC 4 D 14 AC 26
第一轮 ：
第二轮 :
第三轮 :
第四轮 :
第五轮 :
aba-> $AC$ 狗取 ab -> a -> 小$D$ 取 a。$AC$ 狗总分为 3，小$D$ 总分为 $1$。第二轮 :
abc-> $AC$ 狗取 bc -> a -> 小$D$ 取 a。$AC$ 狗总分为 5，小$D$ 总分为 $1$。第三轮 :
cba-> $AC$ 狗取 bc -> a -> 小$D$ 取 a。$AC$ 狗总分为 $5$，小$D$ 总分为 $1$。第四轮 :
n-> $AC$ 狗取空串 -> n -> 小$D$ 取 n。$AC$ 狗总分为 $0$，小$D$ 总分为 $14$。第五轮 :
acgo-> $AC$ 狗取 acgo -> `` -> 小$D$ 取空串。$AC$ 狗总分为 $26$，小$D$ 总分为 $0$。
C++ 编辑器
输入
输出
可保存默认模板；新题优先使用已保存模板。
当前快捷键仅展示，暂不支持修改。
- 撤销
Ctrl / ⌘ + Z - 重做
Ctrl / ⌘ + Y - 查找
Ctrl / ⌘ + F - 全选
Ctrl / ⌘ + A - 复制
Ctrl / ⌘ + C - 剪切
Ctrl / ⌘ + X - 粘贴
Ctrl / ⌘ + V - 自动排版
工具栏排版按钮 - 草稿保存
编辑时自动保存到本机
历史
提交记录
状态说明时间源码
AI
作答助手
你好，我是作答助手。可以问思路、复杂度、样例含义或代码报错原因；不会直接给出完整 AC 代码。
确定要清空代码吗？