边扫边用数组记下每种颜色首次出现的笔编号，第二次遇到同色即输出两个编号，扫完无重复则输出 different。
OJ: roj
题目 ID: 1673
难度:入门
标签:字符串哈希表python
创建: 2026-10-01 01:37
更新: 2026-10-06 01:45
后置题目
roj 1463「一本通 2.1 练习 7」门票A 教的"用一张表记下见过的值、遍历时先查表判重"被 B 原样搬成递推模拟每一步的哈希集合判重，B 只是把这个判重步骤叠在函数迭代建模与 2×10^6 封顶之上，从入门模板升到普及-。noi_openjudge ch0107-11潜伏者B 复用 A 教的「扫描时用字典查表判定已有记录」这一步：A 用它判重复并取首次位置，B 用同一查表判定检验密文→明文与明文→密文两向映射是否与已有记录冲突，再叠加 26 字母全覆盖校验与翻译，属于在 A 基础上叠加额外流程。luogu P2697宝石串B 直接复用 A 教的“记录值首次出现位置、再次出现时用旧位置得出答案”这一关键观察：A 用它配出同色的两个编号，B 把值换成前缀和，用同一张首次位置表算出最长零和区间。
题目描述
一个 16 格的彩笔盒，每格一支笔，颜色用大写字母表示。输入一行 16 个大写字母；题面保证若有同色，只会有一种且恰好 2 支。
若 16 支颜色全不同输出 different，否则按先小后大的顺序输出那两支同色笔的编号。样例输入 ABCDEFAHIJPLMNOT，样例输出 1 7。
思路
从左往右扫一遍，用数组记下每种颜色首次出现的编号；扫到已登记的颜色时，读出的旧编号一定更小，直接输出旧编号与当前编号。
扫完都没命中就输出 different。
参考代码
Python 版：
python
#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-10-01 01:37
# update_at: 2026-10-01 01:37
import sys
def repeated_pair(colors: str) -> tuple[int, int] | None:
"""返回那两支同色笔的编号（较小, 较大）；16 支笔颜色全不同时返回 None。
题面保证同色最多两支：边扫边记每种颜色首次出现的编号，第二次遇到即成答案，
且先登记的编号一定更小，天然满足"先小后大"。
"""
first: dict[str, int] = {} # 颜色 -> 该颜色首次出现的笔编号
for pos, color in enumerate(colors, 1):
seen = first.get(color) # 这个颜色之前登过记吗
if seen is not None:
return seen, pos
first[color] = pos
return None
def solve() -> None:
colors = sys.stdin.buffer.read().decode().strip()
pair = repeated_pair(colors)
print("different" if pair is None else f"{pair[0]} {pair[1]}")
if __name__ == "__main__":
solve()C++ 版（同一算法）：
cpp
/**
* Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
* rbook: -> https://rbook.roj.ac.cn https://rbook2.roj.ac.cn
* rainboy的学习导航网站: https://idx.roj.ac.cn
* create_at: 2026-10-06 01:45
* update_at: 2026-10-06 01:45
*/
#include <iostream>
#include <string>
using namespace std;
typedef long long ll;
ll first_pos[26]; // first_pos[c] 表示颜色 c 首次出现的笔编号，0 表示还没出现
int main() {
string s;
cin >> s;
ll n = s.size();
for (ll pos = 1; pos <= n; pos++) {
ll color = s[pos - 1] - 'A'; // 把 A~Z 映射到 0~25
if (first_pos[color] != 0) {
// 这种颜色之前出现过，first_pos 里存的就是较小的编号
cout << first_pos[color] << " " << pos << "\n";
return 0;
}
first_pos[color] = pos;
}
cout << "different\n";
return 0;
}