| 题目名称 | 1569. [USACO Dec05]可疑的斑点 |
|---|---|
| 输入输出 | cpattern.in/out |
| 难度等级 | ★★☆ |
| 时间限制 | 1000 ms (1 s) |
| 内存限制 | 256 MiB |
| 测试数据 | 10 |
| 题目来源 |
 cstdio
于2014-03-30加入 |
| 开放分组 | 全部用户 |
| 提交状态 | |
| 分类标签 | |
| 分享题解 |
| 通过：7， 提交：16， 通过率：43.75% | ||||
 HZOI_蒟蒻一只 |
100 | 0.065 s | 5.88 MiB | C++ |
 Chenyao2333 |
100 | 0.086 s | 2.60 MiB | C++ |
 牧殇 |
100 | 0.142 s | 1.72 MiB | C++ |
 Wang Yen Jen |
100 | 0.168 s | 2.34 MiB | C++ |
 FoolMike |
100 | 0.222 s | 12.37 MiB | C++ |
 cstdio |
100 | 0.470 s | 1.65 MiB | C++ |
 mikumikumi |
100 | 0.471 s | 2.12 MiB | C++ |
|
Chenyao2333 |
70 | 0.082 s | 2.60 MiB | C++ |
|
Chenyao2333 |
70 | 0.084 s | 2.60 MiB | C++ |
|
mikumikumi |
70 | 0.478 s | 1.90 MiB | C++ |
| 本题关联比赛 | |||
| 20170519 | |||
| 关于 可疑的斑点 的近10条评论(全部评论) | ||||
|---|---|---|---|---|
|
百题斩！
这道题思路真的很有意思，用KMP解决数组问题…… HZOI_蒟蒻一只
2017-06-14 07:23
8楼
| ||||
|
子序列形dp+kmp验证？
| ||||
|
完全不知道自己都写了什么 树状数组+KMP
 牧殇
2016-11-12 07:01
6楼
| ||||
|
借鉴了一下梦迪的代码
| ||||
|
回复 @Chenyao :
犇！！！！！ | ||||
|
非主流方法写的,时间复杂度可以写到O(NS)
 (代码写的乱成屎了  ) | ||||
|
所以一开始看错题解了。。。。。。 (╯‘□′)╯（┻━┻
| ||||
【题目描述】
约翰的奶牛中有K(1≤K≤25,000)头格外喜欢闹事儿，排队时她们总是站在一起。为了找出她们，约翰让他所有的N(1≤N≤100,000)头奶牛排成一列进入牛棚，并希望你能告诉他队列中的长度为K的可疑群体。
约翰通过斑点数S(1≤S≤25)来辨别奶牛。他已经忘了那些爱闹事的奶牛身上具体有多少个斑点，但仍然记得在这些牛中谁的斑点更多、或者哪些牛的斑点数一样。于是他用一个由斑点数排名构成的序列描述出了这些奶牛排成的队伍。比如说”1,4,4,3,2,1”表示：第一头与最后一头牛斑点数相同，并且比所有其它牛少；第五头牛身上的斑点稍多一些；而第二头和第三头牛拥有最多的斑点。
请你帮助约翰在队伍中找出所有符合描述的子序列。
【输入格式】
第一行输入三个整数N,K,S，（每头牛身上的斑点个数为1~S的整数）接下来N行每行输入一只牛的斑点数。接下来K行每行输入一个排名序列。
【输出格式】
第1行输出一个整数B，即子序列个数。接下来B行每行一个整数，表示一种可能的子序列的起始位置。
【样例输入】
9 6 10
5
6
2
10
10
7
3
2
9
1
4
4
3
2
1
【样例输出】
1
3
【来源】
Brian Dean, 2005
Translate by: 贾由