【HDOJ】3183 A Magic Lamp
RMQ。1 /* 3183 */
2 #include <cstdio>
3 #include <cstring>
4 #include <cstdlib>
5
6 #define MAXN 1005
7
8 char s, ans;
9 int dp;
10 int n,len,m;
11
12 int min(int x, int y) {
13 return s<=s ? x:y;
14 }
15
16 void RMQ_init() {
17 int i, j, k;
18
19 for (i=1; i<=len; ++i)
20 dp = i;
21 for (j=1; (1<<j)<=len; ++j)
22 for (i=1; i+(1<<j)-1<=len; ++i)
23 dp = min(dp, dp);
24 }
25
26 int RMQ(int l, int r) {
27 int k = 0;
28
29 while ((1<<(k+1)) <= r-l+1)
30 ++k;
31 return min(dp, dp);
32 }
33
34 int main() {
35 int i, j, k;
36 int l;
37
38 #ifndef ONLINE_JUDGE
39 freopen("data.in", "r", stdin);
40 freopen("data.out", "w", stdout);
41 #endif
42
43 while (scanf("%s %d", s+1, &m)!=EOF) {
44 len = strlen(s+1);
45 RMQ_init();
46 m = len - m;
47 l = k = 1;
48 while (m--) {
49 k = RMQ(k, len-m);
50 ans = s;
51 }
52 for (i=1; i<l; ++i)
53 if (ans != '0')
54 break;
55 ans = '\0';
56 if (i == l)
57 puts("0");
58 else
59 puts(ans+i);
60 }
61
62 return 0;
63 }
页:
[1]