| 题目名称 | 280. [USACO Dec08] 奶牛的糖果 |
|---|---|
| 输入输出 | treat.in/out |
| 难度等级 | ★☆ |
| 时间限制 | 1000 ms (1 s) |
| 内存限制 | 128 MiB |
| 测试数据 | 10 |
| 题目来源 |
 zqzas
于2009-02-22加入 |
| 开放分组 | 全部用户 |
| 提交状态 | |
| 分类标签 | |
| 分享题解 |
| 通过：61， 提交：231， 通过率：26.41% | ||||
 水中音 |
100 | 0.135 s | 1.55 MiB | C++ |
 赵日天 |
100 | 0.142 s | 2.39 MiB | C++ |
 cctype |
100 | 0.145 s | 2.29 MiB | C++ |
 天空非翔 |
100 | 0.146 s | 1.82 MiB | C++ |
 ...... |
100 | 0.149 s | 1.82 MiB | C++ |
 RP++ |
100 | 0.152 s | 1.40 MiB | C++ |
|
RP++ |
100 | 0.152 s | 1.55 MiB | C++ |
 hzoi55223 |
100 | 0.153 s | 1.55 MiB | C++ |
 苜 |
100 | 0.157 s | 1.55 MiB | C++ |
 starsing |
100 | 0.157 s | 3.20 MiB | C++ |
| 本题关联比赛 | |||
| 20130729 | |||
| 20130729 | |||
| 关于 奶牛的糖果 的近10条评论(全部评论) | ||||
|---|---|---|---|---|
|
Tarjan缩点
| ||||
|
NOIP2015的“信息传递”基本是这道题简化版。。。
 liu_runda
2015-12-08 10:28
13楼
| ||||
|
注意到每个点出度为1。。。分析一下就会发现问题实际上特别简单。。简单的模拟一下那个过程就好了，分析完即：随便抓一个没到过的点一直走，总会走到一个环，即便这个环可能只有自身，然后即可更新路上所有点的答案。代码的实现本质上感觉就是模拟。。。
| ||||
|
深搜撸过
| ||||
|
| ||||
|
mark
 Ezio
2014-09-24 23:00
9楼
| ||||
|
写的太复杂了，简直不能忍。。。还好过了
 wolf
2014-07-18 14:53
8楼
| ||||
|
我想到了几个优化点，第一个是每算完一头牛后把它经过牛棚的牛顺便也给算了，第二个是算的时候借用之前的答案，第三个是如果算过了就别算了。
| ||||
|
求大神讲解倒数第二个点啊!
| ||||
|
| ||||
HZOI_RXR
乌龙猹
FoolMike
‘’在威斯康星州每年万圣节前夕奶牛们要通过盛装打扮和收集糖果进行庆祝，农夫约翰把奶牛们留在了他的N (1 <= N <= 100,000)个牛栏中。
因为牛栏不是足够的大，约翰让奶牛按指定的路线在牛栏间行走。他在牛栏i布置下一个牛栏号next_i (1 <= next_i <= N)，以告诉奶牛要怎么行走到下一个牛栏。奶牛需要这样行走以搜集更多的糖果。
约翰要求奶牛i从i号牛栏开始行走搜集糖果。一头奶牛一旦返回她访问过的牛栏时将停止行走。
计算每头奶牛访问过的牛栏数，也就是每头奶牛曾经搜集糖果的位置数。
输入格式：
第一行：一个单独的整数N
第2..N+1行：第i+1行包含一个单独的整数next_i
SAMPLE INPUT (file treat.in):
4
1
3
2
3
输入解释:
四个牛栏.
* 牛栏 1 直接让奶牛返回 牛栏 1.
* 牛栏 2 让奶牛去 牛栏 3
* 牛栏 3 让奶牛去 牛栏 2
* 牛栏 4 让奶牛去 牛栏 3
输出格式:
* 第1..N行: 行 i 包含一个单独的整数表示曾经访问牛栏的总数
SAMPLE OUTPUT (file treat.out):
1
2
2
3
输出解释:
奶牛1: 开始于 1, 下一个是 1. 总共访问数是 1.
奶牛2: 开始于 2, 下一个是 3, 下一个是 2. 总共访问数是 2.
奶牛3: 开始于 3, 下一个是 2, 下一个是 3. 总共访问数是 2.
奶牛4: 开始于 4, 下一个是 3, 下一个是 2, 下一个是 3. 总共访问数是 3.