题意是每组给定一个字符串，在有限查询次数内输出所要查询区间的字典序最小的子串个数。
字典序最小的子串，就是所查询区间中字典序最小的单个字符，问题就转化成了求一段区间内字典序最小的字符个数。
开始时盲目暴力，直接用桶排序的做法一段一段去求，果然t了（这种就不贴代码了）......
然后想到先扫一遍，求出从字符串首位到第 i 位的最小字符数，再用一个数组存第 0 位到第 i 位的最小字符，比较第 i 位的字符和前 i - 1 位的最小字符，第 i 位更小的话就更新最小字符和最小字符数......这样扫一遍后，问到哪个区间就比较区间左右端点的最小字符。若左侧较大，则直接输出右侧最小字符数；若两侧相等，则输出右侧的最小字符数减去左侧的最小字符数；左侧不可能小于右侧。
但是，这种想法有较大漏洞，不能说漏洞，这就是错误的想法，因为这样所记录的最小的字符未必会出现在所求区间内......
作为对自己的警示，把这种错误的东西挂出来侮辱下自己......
1 1 #include <iostream> 2 2 #include <cstdio> 3 3 #include <algorithm> 4 4 #include <cstring> 5 5 #include <queue> 6 6 #include <stack> 7 7 #include <cmath> 8 8 #include <map> 9 9 using namespace std; 1010 int num[100006]; 1111 char alp[100006]; 1212 int main() 1313 { 1414 std::ios::sync_with_stdio(false); 1515 int t,len,m,l,r; 1616 string s; 1717 cin >> t; 1818 for(int i = 1; i <= t; i++) 1919 { 2020 memset(num,0,sizeof(num)); 2121 cin >> len >> m; 2222 cin >> s; 2323 cout << "Case #"<< i <<":" << endl; 2424 num[0] = 1; 2525 alp[0] = s[0]; 2626 for(int i = 1; i < len; i++) 2727 { 2828 if(s[i]<alp[i-1]) 2929 { 3030 alp[i] = s[i]; 3131 num[i] = 1; 3232 } 3333 else if(s[i] == alp[i-1]) 3434 { 3535 alp[i] = s[i]; 3636 num[i] = num[i-1]+1; 3737 } 3838 else 3939 { 4040 alp[i] = alp[i-1]; 4141 num[i] = num[i-1]; 4242 } 4343 } 4444 while(m--) 4545 { 4646 cin >> l >> r; 4747 l--; 4848 r--; 4949 if(l==r) 5050 { 5151 cout << 1 << endl; 5252 continue; 5353 } 5454 if(alp[r] < alp[l]) 5555 cout << num[r] << endl; 5656 else if(alp[r] == alp[l]) 5757 { 5858 if(alp[l] < s[l] && alp[r] < s[r]) 5959 // bug在此: ACBBB...BBCA 查中间，前面白算 6060 6161 if(alp[l]==s[l]) 6262 cout << num[r]-num[l]+1 << endl; 6363 else 6464 cout << num[r]-num[l] << endl; 6565 } 6666 } 6767 } 6868 return 0; 6969 }
View Code
接着又想到可否将最小字符出现的位置记录下来，然后发现完全是在自己哄自己开心......
借助wjy的力量，用二维数组记录位置的似桶排序的做法完成了题目，路还很长......
1 1 #include <iostream> 2 2 #include <cstring> 3 3 using namespace std; 4 4 int rc[100100][26]; 5 5 int main() 6 6 { 7 7 std::ios::sync_with_stdio(false); 8 8 int n,t,q,l,r,j,i; 9 9 cin >> t; 1010 string s; 1111 for(int i=0;i<26;i++) 1212 { 1313 rc[0][i]=0; 1414 } 1515 for(int c=1;c<=t;c++) 1616 { 1717 cout << "Case #" << c << ":" << endl; 1818 cin >> n >> q; 1919 cin >> s; 2020 for(i=0;s[i];i++) 2121 { 2222 for(j=0;j<=25;j++) 2323 { 2424 rc[i+1][j]=rc[i][j]; 2525 } 2626 rc[i+1][s[i]-'A']++; 2727 } 2828 for(i=0;i<q;i++) 2929 { 3030 cin >> l >> r; 3131 int ans = 0; 3232 for(j = 0;ans==0;j++) 3333 { 3434 ans = rc[r][j]-rc[l-1][j]; 3535 } 3636 cout << ans << endl; 3737 } 3838 } 3939 return 0; 4040 }
View Code