| 题目名称 | 3318. [USACO19 DEC Bronze]Where Am I? |
|---|---|
| 输入输出 | whereami.in/out |
| 难度等级 | ★ |
| 时间限制 | 1000 ms (1 s) |
| 内存限制 | 256 MiB |
| 测试数据 | 10 |
| 题目来源 |
 leon
于2019-12-20加入 |
| 开放分组 | 全部用户 |
| 提交状态 | |
| 分类标签 | |
| 分享题解 |
| 通过：3， 提交：8， 通过率：37.5% | ||||
 1020 |
100 | 0.000 s | 0.00 MiB | C++ |
 ┭┮﹏┭┮ |
100 | 0.000 s | 0.00 MiB | C++ |
 leon |
100 | 0.017 s | 13.66 MiB | C++ |
 萨利哈米季奇 |
40 | 0.000 s | 0.00 MiB | C++ |
|
┭┮﹏┭┮ |
40 | 0.000 s | 0.00 MiB | C++ |
|
┭┮﹏┭┮ |
10 | 0.000 s | 0.00 MiB | C++ |
|
萨利哈米季奇 |
0 | 0.000 s | 0.00 MiB | C++ |
|
萨利哈米季奇 |
0 | 0.004 s | 13.66 MiB | C++ |
| 关于 Where Am I? 的近10条评论(全部评论) | ||||
|---|---|---|---|---|
|
STL大法好(substr)
| ||||
3318. [USACO19 DEC Bronze]Where Am I?
★ 输入文件：whereami.in
输出文件：whereami.out
简单对比时间限制：1 s 内存限制：256 MiB
【题目描述】
Farmer John 出门沿着马路散步，但是他现在发现可能迷路了！
沿路有一排共N 个农场（1≤N≤100）。不幸的是农场并没有编号，这使得 Farmer John 难以分辨他在这条路上所处的位置。然而，每个农场都沿路设有一个彩色的邮箱，所以 Farmer John 希望能够通过查看最近的几个邮箱的颜色来唯一确定他所在的位置。
每个邮箱的颜色用 A..Z 之间的一个字母来指定，所以沿着道路的N 个邮箱的序列可以用一个长为N 的由字母 A..Z 组成的字符串来表示。某些邮箱可能会有相同的颜色。Farmer John 想要知道最小的K 的值，使得他查看任意连续K个邮箱序列，他都可以唯一确定这一序列在道路上的位置。
例如，假设沿路的邮箱序列为 'ABCDABC' 。Farmer John 不能令K=3，因为如果他看到了 'ABC'，沿路有两个这一连续颜色序列可能所在的位置。最小可行的K 的值为K=4因为如果他查看任意连续 4 个邮箱，这一颜色序列可以唯一确定他在道路上的位置。
【输入格式】
输入的第一行包含N，第二行包含一个由N 个字符组成的字符串，每个字符均在 A..Z 之内。
【输出格式】
输出一行，包含一个整数，为可以解决 Farmer John 的问题的最小K 值。
【样例输入】
7 ABCDABC
【样例输出】
4