A Magic Lamp

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 4694    Accepted Submission(s): 1947

• 長度為n的數串去掉m個數問剩下的數的最小值是多少
• 等價於求長度為n的數挑（n-m）個數使得其值最小
• 那麼我們只要從高位開始每次挑選最小數一共挑（n-m）個就是結果
• 用ST表計算區間min
• 註意前導零的處理

 1 #include <iostream>
 2 #include <string>
 3 #include <cstdio>
 4 #include <cstring>
 5 #include <algorithm>
 6 #include <climits>
 7 #include <cmath>
 8 #include <vector>
 9 #include <queue>
10 #include <stack>
11 #include <set>
12 #include <map>
13 using namespace std;
14 typedef long long           LL ;
15 typedef unsigned long long ULL ;
16 const int    maxn = 1e3 + 10   ;
17 const int    inf  = 0x3f3f3f3f ;
18 const int    npos = -1         ;
19 const int    mod  = 1e9 + 7    ;
20 const int    mxx  = 100 + 5    ;
21 const double eps  = 1e-6       ;
22 const double PI   = acos(-1.0) ;
23 
24 int n, m, fac[10], dp[maxn][10], l, r, p, ans[maxn], tot, rec;
25 char str[maxn];
26 int main(){
27     // freopen("in.txt","r",stdin);
28     // freopen("out.txt","w",stdout);
29     for(int i=0;i<10;i++)
30         fac[i]=(1<<i);
31     while(~scanf("%s %d",str+1,&m)){
32         n=strlen(str+1);
33         m=n-m;
34         rec=m;
35         int k=(int)(log((double)n)/log(2.0));
36         for(int i=1;i<=n;i++)
37             dp[i][0]=i;
38         for(int j=1;j<=k;j++)
39             for(int i=1;i+fac[j]-1<=n;i++){
40                 int pl=dp[i][j-1], pr=dp[i+fac[j-1]][j-1];
41                 if(str[pl]<=str[pr])
42                     dp[i][j]=pl;
43                 else
44                     dp[i][j]=pr;
45             }
46         l=1;
47         tot=0;
48         while(m){
49             r=n-m+1;
50             k=(int)(log((double)(r-l+1))/log(2.0));
51             int pl=dp[l][k], pr=dp[r-fac[k]+1][k];
52             if(str[pl]<=str[pr])
53                 p=pl;
54             else
55                 p=pr;
56             ans[tot++]=p;
57             l=p+1;
58             m--;
59         }
60         int flag=0;
61         for(int i=0;i<tot;i++){
62             if(!(str[dp[ans[i]][0]]-'0')){
63                 if(flag)
64                     printf("%c",str[ans[i]]);
65             }else{
66                 flag=1;
67                 printf("%c",str[ans[i]]);
68             }
69         }
70         if(!flag)
71             printf("0");
72         cout<<endl;
73     }
74     return 0;
75 }