CodeForces 669B

链接:http://codeforces.com/problemset/problem/669/B

本文链接:http://www.cnblogs.com/Ash-ly/p/5443086.html

题意:

　　有个闲的没事干的人找到了一个能跳的小动物,把它放到一个连续的格子中,每个格子都有两个属性,一个是方向">"和"<",分别表示如果到了该格子只能向左(<)跳或者相右跳(>).另外一个属性是能跳多远,比如这个属性是3,那么它到这个格子只能选择往左或者往右跳3步.开始时刻这个小动物在第一个格子,问最后能否调出这个连续的格子,还是永远在这个格子里跳来跳去的循环下去.

思路:

　　如果出不去则说明它跳的路径肯定在这些格子里面形成了一个循环节,而出现循环节的原因就是它又回到了某个它曾经走过的地方,所以如果某个格子它跳了两次,那么它肯定出不去了.

代码:

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 
 4 int main()
 5 {
 6     int n;
 7     scanf("%d", &n);
 8     char s[100000 + 7] = {0};
 9     scanf("%s", s);
10     int a[100000 + 7] = {0};
11     for(int i = 0; i < n ; i++)
12         scanf("%d", &a[i]);
13     int cnt = 0;
14     long long jmp = 0;
15     int flag[100000] = {0};
16     int ans = 0;
17     int i = 0;
18     while(true)
19     {
20         s[i] == '>' ? jmp += a[i] : jmp -= a[i];
21         if(jmp >= 0 && jmp < n)
22         {
23             i = (int)jmp;
24             if(flag[i] == 0) flag[i] = 1;
25             else    break;
26         }
27         else
28         {
29             ans = 1;
30             break;
31         }
32     }
33     if(ans) printf("FINITE
");
34     else printf("INFINITE
");
35     return 0;
36 }