北仑建设局质监站网站,小学生入门编程用什么软件,设计素材免费下载,水安建设集团网站题意大概就是#xff1a;给出n个字符串#xff0c;有m个询问#xff1a;每次给出字符串s#xff0c;整数k#xff0c;问在所有以s为前缀的字符串中#xff0c;字典序第k大的#xff0c;是那n个串中的第几个。 我一开始做的时候忽略了一个问题#xff1a;就是对于两个串… 题意大概就是给出n个字符串有m个询问每次给出字符串s整数k问在所有以s为前缀的字符串中字典序第k大的是那n个串中的第几个。 我一开始做的时候忽略了一个问题就是对于两个串ab你直接输出 a b 是有值的。也就是说字符串是可以直接比较的我们能O1两个串比较大小因为就是asic码不是嘛。 显然我们是要在以s为前缀的这个连续的整体里去判断。那么既然字符串的比较和整型变量一样可以排序——这样就得到了连续的一段。 这之后我们只需要二分找第一个前缀 k 的判断从这个开始第k个和s是否相等就可以了。 复杂度O1000 m log(n) 没有问题。 代码时间—— #includecstdio
#includeiostream
#includealgorithm
#includecstring
#includequeue
#includestring
#includevector
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 flag0;for(int i0;is.length();i)if(q[p].s[i]!s[i]) {flag1;break;}if(flag) return -1;return q[p].id;
}
int find(string s)
{int L1,Rn;int ans0;while(LR){int mid(LR)1;if(q[mid].ss) {ansmid;Rmid-1;}else Lmid1;}return ans;
}
int solve(string s,int x)
{int pfind(s);if(pn) return -1;px-1;return match(p,s);
}
int main()
{scanf(%d%d,n,m);for(int i1;in;i){cinq[i].s;q[i].idi;}sort(q1,qn1);for(int i1;im;i){string s;int x;cinxs;coutsolve(s,x)endl;}return 0;
} 转载于:https://www.cnblogs.com/popo-black-cat/p/10887011.html
