# K-th good string

*10*

Problem Description

One day, Lord gave you a string S. Let’s define the pair(x, p) represent the substring S[p-x+1,p-x+2,…,p]. The index of S counts from 0. Then, Lord will tell you some information about this string.

There are three types of the information:

1. Lord will give you a pair(x, p) and then says I think the substring is good.(Only consider the substring (x, p) is good, not include the substring of (x, p))

2. Lord will give you a pair(x, p) and then says I think the substring is not good.

3. Lord will give you a pair(x, p) and a integer K, then you should answer the length of the K-th good string. The K-th good string means that if you list all the distinct good strings which contain pair(x, p) as suffix, then sort them by their length in ascending order, the K-th string is K-th good string.

Now, can you hold the information from Lord? Yon can consider all the substring is not good initially.

Input

First line is a integer T, means the number of test case, T<=10.

In every test case, there is a string S in the first line, composed by lowercase letters, |S|<=100000.

An integer q in the second line (q<=200000), and q lines follow. Every line has an integer t, means the type of the message. If t equals 3, then three integers x, p, K follow, else two integers x, p follow.

The pair (x, p) will always represent a substring of S.

Output

For each case, output “Case #k:” one line first, where k means the case number count from 1.

For every message of type 3, print the answer one line. If there is no such K-th good string, print -1.

Sample Input

1

aaaaa

4

2 1 0

1 3 2

3 2 4 1

3 4 3 1

Sample Output

Case #1:

3

-1

- 点赞
- 写回答
- 关注问题
- 收藏
- 复制链接分享
- 邀请回答

*1*条回答

#### 相关推荐

- 4年前回答 1 已采纳 Problem Description One day, Lord gave you a string S. Let’s define the pair(x, p) represent the substring S[p-x+1,p-x+2,…,p]. The index of S counts from 0. Then, Lord will tell you some information about this string. There are three types of the information: 1. Lord will give you a pair(x, p) and then says I think the substring is good.(Only consider the substring (x, p) is good, not include the substring of (x, p)) 2. Lord will give you a pair(x, p) and then says I think the substring is not good. 3. Lord will give you a pair(x, p) and a integer K, then you should answer the length of the K-th good string. The K-th good string means that if you list all the distinct good strings which contain pair(x, p) as suffix, then sort them by their length in ascending order, the K-th string is K-th good string. Now, can you hold the information from Lord? Yon can consider all the substring is not good initially. Input First line is a integer T, means the number of test case, T<=10. In every test case, there is a string S in the first line, composed by lowercase letters, |S|<=100000. An integer q in the second line (q<=200000), and q lines follow. Every line has an integer t, means the type of the message. If t equals 3, then three integers x, p, K follow, else two integers x, p follow. The pair (x, p) will always represent a substring of S. Output For each case, output “Case #k:” one line first, where k means the case number count from 1. For every message of type 3, print the answer one line. If there is no such K-th good string, print -1. Sample Input 1 aaaaa 4 2 1 0 1 3 2 3 2 4 1 3 4 3 1 Sample Output Case #1: 3 -1
- 4年前回答 2 已采纳 Description You are working for Macrohard company in data structures department. After failing your previous task about key insertion you were asked to write a new data structure that would be able to return quickly k-th order statistics in the array segment. That is, given an array a[1...n] of different integer numbers, your program must answer a series of questions Q(i, j, k) in the form: "What would be the k-th number in a[i...j] segment, if this segment was sorted?" For example, consider the array a = (1, 5, 2, 6, 3, 7, 4). Let the question be Q(2, 5, 3). The segment a[2...5] is (5, 2, 6, 3). If we sort this segment, we get (2, 3, 5, 6), the third number is 5, and therefore the answer to the question is 5. Input The first line of the input file contains n --- the size of the array, and m --- the number of questions to answer (1 <= n <= 100 000, 1 <= m <= 5 000). The second line contains n different integer numbers not exceeding 109 by their absolute values --- the array for which the answers should be given. The following m lines contain question descriptions, each description consists of three numbers: i, j, and k (1 <= i <= j <= n, 1 <= k <= j - i + 1) and represents the question Q(i, j, k). Output For each question output the answer to it --- the k-th number in sorted a[i...j] segment. Sample Input 7 3 1 5 2 6 3 7 4 2 5 3 4 4 1 1 7 3 Sample Output 5 6 3
- 回答 1 已采纳 The K-th Distance Time Limit: 8000/4000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others) Total Submission(s): 27 Accepted Submission(s): 5 Problem Description Given a tree, which has n node in total. Define the distance between two node u and v is the number of edge on their unique route. So we can have n(n-1)/2 numbers for all the distance, then sort the numbers in ascending order. The task is to output the sum of the first K numbers. Input There are several cases, first is the number of cases T. (There are most twenty cases). For each case, the first line contain two integer n and K (2≤n≤100000,0≤K≤min(n(n−1)/2,106) ). In following there are n-1 lines. Each line has two integer u , v. indicate that there is an edge between node u and v. Output For each case output the answer. Sample Input 2 3 3 1 2 2 3 5 7 1 2 1 3 2 4 2 5 Sample Output 4 10
- 回答 1 已采纳 Problem Description One day, Lord gave you a string S. Let’s define the pair(x, p) represent the substring S[p-x+1,p-x+2,…,p]. The index of S counts from 0. Then, Lord will tell you some information about this string. There are three types of the information: 1. Lord will give you a pair(x, p) and then says I think the substring is good.(Only consider the substring (x, p) is good, not include the substring of (x, p)) 2. Lord will give you a pair(x, p) and then says I think the substring is not good. 3. Lord will give you a pair(x, p) and a integer K, then you should answer the length of the K-th good string. The K-th good string means that if you list all the distinct good strings which contain pair(x, p) as suffix, then sort them by their length in ascending order, the K-th string is K-th good string. Now, can you hold the information from Lord? Yon can consider all the substring is not good initially. Input First line is a integer T, means the number of test case, T<=10. In every test case, there is a string S in the first line, composed by lowercase letters, |S|<=100000. An integer q in the second line (q<=200000), and q lines follow. Every line has an integer t, means the type of the message. If t equals 3, then three integers x, p, K follow, else two integers x, p follow. The pair (x, p) will always represent a substring of S. Output For each case, output “Case #k:” one line first, where k means the case number count from 1. For every message of type 3, print the answer one line. If there is no such K-th good string, print -1. Sample Input 1 aaaaa 4 2 1 0 1 3 2 3 2 4 1 3 4 3 1 Sample Output Case #1: 3 -1
- 回答 1 已采纳 Isaac is tired of his daily trip to his office, using the same shortest route everyday. Although this saves his time, he must see the same scenery again and again. He cannot stand such a boring commutation any more. One day, he decided to improve the situation. He would change his route everyday at least slightly. His new scheme is as follows. On the first day, he uses the shortest route. On the second day, he uses the second shortest route, namely the shortest except one used on the first day. In general, on the k-th day, the k-th shortest route is chosen. Visiting the same place twice on a route should be avoided, of course. You are invited to help Isaac, by writing a program which finds his route on the k-th day. The problem is easily modeled using terms in the graph theory. Your program should find the k-th shortest path in the given directed graph. Input The input consists of multiple datasets, each in the following format. n m k a b x1 y1 d1 x2 y2 d2 �� xm ym dm Every input item in a dataset is a non-negative integer. Two or more input items in a line are separated by a space. n is the number of nodes in the graph. You can assume the inequality 2 �� n �� 50. m is the number of (directed) edges. a is the start node, and b is the goal node. They are between 1 and n, inclusive. You are required to find the k-th shortest path from a to b. You can assume 1 �� k �� 200 and a �� b. The i-th edge is from the node xi to yi with the length di (1 �� i �� m). Both xi and yi are between 1 and n, inclusive. di is between 1 and 10000, inclusive. You can directly go from xi to yi, but not from yi to xi unless an edge from yi to xi is explicitly given. The edge connecting the same pair of nodes is unique, if any, that is, if i �� j, it is never the case that xi equals xj and yi equals yj. Edges are not connecting a node to itself, that is, xi never equals yi. Thus the inequality 0 �� m �� n(n − 1) holds. Note that the given graph may be quite unrealistic as a road network. Both the cases m = 0 and m = n(n − 1) are included in the judges�� data. The last dataset is followed by a line containing five zeros (separated by a space). Output For each dataset in the input, one line should be output as specified below. An output line should not contain extra characters such as spaces. If the number of distinct paths from a to b is less than k, the string None should be printed. Note that the first letter of None is in uppercase, while the other letters are in lowercase. If the number of distinct paths from a to b is k or more, the node numbers visited in the k-th shortest path should be printed in the visited order, separated by a hyphen (minus sign). Note that a must be the first, and i must be the last in the printed line. In this problem the term shorter (thus shortest also) has a special meaning. A path P is defined to be shorter than Q, if and only if one of the following conditions holds. The length of P is less than the length of Q. The length of a path is defined to be the sum of lengths of edges on the path. The length of P is equal to the length of Q, and P��s sequence of node numbers comes earlier than Q��s in the dictionary order. Let��s specify the latter condition more precisely. Denote P��s sequence of node numbers by p1, p2, ��, ps, and Q��s by q1, q2, ��, qt. p1 = q1 = a and ps = qt = b should be observed. The sequence P comes earlier than Q in the dictionary order, if for some r (1 �� r �� s and r �� t), p1 = q1, ��, pr − 1 = qr − 1, and pr < qr (pr is numerically smaller than qr). A path visiting the same node twice or more is not allowed. Sample Input 5 20 10 1 5 1 2 1 1 3 2 1 4 1 1 5 3 2 1 1 2 3 1 2 4 2 2 5 2 3 1 1 3 2 2 3 4 1 3 5 1 4 1 1 4 2 1 4 3 1 4 5 2 5 1 1 5 2 1 5 3 1 5 4 1 4 6 1 1 4 2 4 2 1 3 2 1 2 1 1 4 3 2 3 1 3 4 1 3 3 5 1 3 1 2 1 2 3 1 1 3 1 0 0 0 0 0 Sample Output 1-2-4-3-5 1-2-3-4 None
- 4年前回答 1 已采纳 We will construct an infinitely long string from two short strings: A = "^__^" (four characters), and B = "T.T" (three characters). Repeat the following steps: Concatenate A after B to obtain a new string C. For example, if A = "^__^" and B = "T.T", then C = BA = "T.T^__^". Let A = B, B = C -- as the example above A = "T.T", B = "T.T^__^". Your task is to find out the n-th character of this infinite string. Input The input contains multiple test cases, each contains only one integer N (1 <= N <= 2^63 - 1). Proceed to the end of file. Output For each test case, print one character on each line, which is the N-th (index begins with 1) character of this infinite string. Sample Input 1 2 4 8 Sample Output T . ^ T
- 4年前回答 1 已采纳 Description Bill is developing a new mathematical theory for human emotions. His recent investigations are dedicated to studying how good or bad days influent people's memories about some period of life. A new idea Bill has recently developed assigns a non-negative integer value to each day of human life. Bill calls this value the emotional value of the day. The greater the emotional value is, the better the daywas. Bill suggests that the value of some period of human life is proportional to the sum of the emotional values of the days in the given period, multiplied by the smallest emotional value of the day in it. This schema reflects that good on average period can be greatly spoiled by one very bad day. Now Bill is planning to investigate his own life and find the period of his life that had the greatest value. Help him to do so. Input The first line of the input contains n - the number of days of Bill's life he is planning to investigate(1 <= n <= 100 000). The rest of the file contains n integer numbers a1, a2, ... an ranging from 0 to 106 - the emotional values of the days. Numbers are separated by spaces and/or line breaks. Output Print the greatest value of some period of Bill's life in the first line. And on the second line print two numbers l and r such that the period from l-th to r-th day of Bill's life(inclusive) has the greatest possible value. If there are multiple periods with the greatest possible value,then print any one of them. Sample Input 6 3 1 6 4 5 2 Sample Output 60 3 5
- 5年前回答 2 已采纳 The Company Dynamic Rankings has developed a new kind of computer that is no longer satisfied with the query like to simply find the k-th smallest number of the given N numbers. They have developed a more powerful system such that for N numbers a[1], a[2], ..., a[N], you can ask it like: what is the k-th smallest number of a[i], a[i+1], ..., a[j]? (For some i<=j, 0<k<=j+1-i that you have given to it). More powerful, you can even change the value of some a[i], and continue to query, all the same. Your task is to write a program for this computer, which - Reads N numbers from the input (1 <= N <= 50,000) - Processes M instructions of the input (1 <= M <= 10,000). These instructions include querying the k-th smallest number of a[i], a[i+1], ..., a[j] and change some a[i] to t. Input The first line of the input is a single number X (0 < X <= 4), the number of the test cases of the input. Then X blocks each represent a single test case. The first line of each block contains two integers N and M, representing N numbers and M instruction. It is followed by N lines. The (i+1)-th line represents the number a[i]. Then M lines that is in the following format Q i j k or C i t It represents to query the k-th number of a[i], a[i+1], ..., a[j] and change some a[i] to t, respectively. It is guaranteed that at any time of the operation. Any number a[i] is a non-negative integer that is less than 1,000,000,000. There're NO breakline between two continuous test cases. Output For each querying operation, output one integer to represent the result. (i.e. the k-th smallest number of a[i], a[i+1],..., a[j]) There're NO breakline between two continuous test cases. Sample Input 2 5 3 3 2 1 4 7 Q 1 4 3 C 2 6 Q 2 5 3 5 3 3 2 1 4 7 Q 1 4 3 C 2 6 Q 2 5 3 Sample Output 3 6 3 6
- weixin_30955341的博客 3968: The K-th Substring 时间限制(普通/Java):1000MS/3000MS 内存限制:65536KByte 描述 bdep__ gets a string of length N (1 ≤ N ≤ 100) today. And he needs its K-th (0 < K ≤ N*(N+1)/2) ...
- tomjobs的博客 Let’s call left cyclic shift of some string ????1????2????3…????????−1???????? as string ????2????3…????????−1????????????1. Analogically, let’s call right cyclic shift of string ???? as string ...
- equation_H的博客 Let’s call left cyclic shift of some string t1t2t3…tn−1tn as string t2t3…tn−1tnt1 . Analogically, let’s call right cyclic ...is good if its left cyclic shift is equal to its right cyclic shift. Yo
- 龍木的博客 You are given a garland consisting ofnnlamps. States of the lamps are represented by the stringssof ... Theii-th character of the stringsisiequals '0' if theii-th lamp is turned off or '1' if t...
- tokers的博客 Good Article Good sentence Time Limit: 6000/3000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 2586 Accepted Submission(s): 728Problem Description In middle s
- 2年前Ashley3082的博客 Time Limit: 1000ms Problem Description: Let's call a number k-good if it contains all digits not exceeding k (0, ..., k). You've got a number k and an array a containing n numbers. Find out...
- Curren.wong的博客 题目只要求所有相邻的亮着的灯之间的相隔距离为 k，所有灯都灭 (000) 和只有一盏灯亮 (010) 的情况都符合要求。
- starlet_kiss的博客 You are given a garland consisting of n lamps.... The i-th character of the string si equals ‘0’ if the i-th lamp is turned off or ‘1’ if the i-th lamp is turned on. You are also given a positiv
- 寒江雪里独钓着的蓑笠翁的博客 Feel Good Time Limit: 3000MS Memory Limit: 65536K Total Submissions: 14288 Accepted: 3951 Case Time Limit: 1000MS Special Judge Description Bi
- anmob303090的博客 1218. Episode N-th: The Jedi Tournament Time limit: 1.0 secondMemory limit: 64 MB Decided several Jedi Knights to organize a tournament once. To know, accumulates who the largest amount o...
- 4年前回答 1 已采纳 Problem Description Lweb has a string S. Oneday, he decided to transform this string to a new sequence. You need help him determine this transformation to get a sequence which has the longest LIS(Strictly Increasing). You need transform every letter in this string to a new number. A is the set of letters of S, B is the set of natural numbers. Every injection f:A→B can be treat as an legal transformation. For example, a String “aabc”, A={a,b,c}, and you can transform it to “1 1 2 3”, and the LIS of the new sequence is 3. Now help Lweb, find the longest LIS which you can obtain from S. LIS: Longest Increasing Subsequence. (https://en.wikipedia.org/wiki/Longest_increasing_subsequence) Input The first line of the input contains the only integer T,(1≤T≤20). Then T lines follow, the i-th line contains a string S only containing the lowercase letters, the length of S will not exceed 105. Output For each test case, output a single line "Case #x: y", where x is the case number, starting from 1. And y is the answer. Sample Input 2 aabcc acdeaa Sample Output Case #1: 3 Case #2: 4
- 0k-ok的博客 In the first line, print one integer kk (0≤k≤n0≤k≤n) — the minimum number of characters you have to delete from ss to make it good. In the second line, print the resulting string ss. If ...