178543 4 1000001 1 100001 2 12345 2 54321 2
13 1 0 123 321
#include<cstdio> #include<cstring> #include<cmath> char s[1010]; char ans[1020]; int st[1010][20]; int Min(int x,int y) { return s[x] <= s[y] ? x : y; } void RMQ_Init(int len) { for(int i = 0; i < len; i++) st[i][0] = i; for(int j = 1; (1<<j) < len; j++) for(int i = 0; i+(1<<j)-1 < len;i++) st[i][j] = Min(st[i][j-1],st[i+(1<<(j-1))][j-1]); } int Query(int l,int r) { int k = (int)(log((double)(r-l+1))/log(2.0)); return Min(st[l][k],st[r-(1<<k)+1][k]); } int main() { int len, m, i; while(scanf("%s%d",s, &m)!=EOF) { len = strlen(s); RMQ_Init(len); m = len - m; int pos = 0, num = 0; while(m--) { pos = Query(pos, len - m - 1); ans[num++] = s[pos++]; } for(i = 0; i < num; i++) if(ans[i]!='0') break; if(i == num) printf("0"); else { while(i < num) printf("%c",ans[i++]); } puts(""); } return 0; }
#include<cstdio> #include<iostream> #include<cstring> #include<string> #include<algorithm> using namespace std; int main() { string s; int m; while(cin >> s >> m) { int len = s.length(), i, j; int p = 0, tmp_pos = m, flag = 0; for(i = 0; i < len - m; i++) { char mmin = s[p]; for(j = p + 1; j <= tmp_pos; j++) if(s[j] < mmin) { mmin = s[j]; p = j; } tmp_pos++; p++; if(!flag) { if(mmin == '0') continue; else { cout << mmin; flag = 1; } } else { cout << mmin; } } if(!flag) cout << "0"; cout << endl; } return 0; }
hdu 3183 A Magic Lamp(RMQ),布布扣,bubuko.com
原文:http://blog.csdn.net/lyhvoyage/article/details/38379685