题意大概就是:给出n个字符串,有m个询问:每次给出字符串s,整数k,问在所有以s为前缀的字符串中,字典序第k大的,是那n个串中的第几个。
我一开始做的时候忽略了一个问题:就是对于两个串a,b,你直接输出 a > b 是有值的。也就是说,字符串是可以直接比较的,我们能O(1)两个串比较大小(因为就是asic码不是嘛)。
显然,我们是要在以s为前缀的这个连续的整体里去判断。那么既然字符串的比较和整型变量一样,可以排序——这样就得到了连续的一段。
这之后,我们只需要二分找第一个前缀 >= k 的,判断从这个开始第k个,和s是否相等就可以了。
复杂度:O(1000 m log(n) ),没有问题。
代码时间——
#include<cstdio> #include<iostream> #include<algorithm> #include<cstring> #include<queue> #include<string> #include<vector> using namespace std; #define maxn 50000 struct node { string s; int id; friend bool operator < (node a,node b) { return a.s < b.s; } } q[maxn]; int n,m; int match(int p,string s) { if(s.length()>q[p].s.length()) return -1; bool flag=0; for(int i=0;i<s.length();i++) if(q[p].s[i]!=s[i]) { flag=1; break; } if(flag) return -1; return q[p].id; } int find(string s) { int L=1,R=n; int ans=0; while(L<=R) { int mid=(L+R)>>1; if(q[mid].s>=s) { ans=mid; R=mid-1; } else L=mid+1; } return ans; } int solve(string s,int x) { int p=find(s); if(p>n) return -1; p+=x-1; return match(p,s); } int main() { scanf("%d%d",&n,&m); for(int i=1;i<=n;i++) { cin>>q[i].s; q[i].id=i; } sort(q+1,q+n+1); for(int i=1;i<=m;i++) { string s; int x; cin>>x>>s; cout<<solve(s,x)<<endl; } return 0; }