首页 > 代码库 > UVa 11988 破损的键盘(链表)

UVa 11988 破损的键盘(链表)

原题链接:https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=3139

题意就是输入文本,若是遇到"["光标就移到最前面,遇到“]”光标就移到最后。

在这段代码中,在for循环中如果不用n来代替strlen(s+1),最后就会超时,以后写代码的时候我会注意到这点。

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 using namespace std;
 5 
 6 const int maxn = 100005;
 7 int cur, last, nex[maxn];
 8 char s[maxn];
 9 
10 int main()
11 {
12     while (scanf("%s",s+1)==1)
13     {
14         cur = last = 0;
15         nex[0] = 0;
16         int n = strlen(s + 1);
17         for (int i = 1; i <= n; i++)
18         {
19             if (s[i] == [)  cur = 0;
20             else if (s[i] == ]) cur = last;
21             else
22             {
23                 nex[i] = nex[cur];
24                 nex[cur] = i;
25                 if (cur == last)  last = i;
26                 cur = i;
27             }
28         }
29         for (int i = nex[0]; i != 0; i = nex[i])
30             cout << s[i];
31         cout << endl;
32     }
33     return 0;
34 }

 

UVa 11988 破损的键盘(链表)