2013-06-24 15:55:20| 人氣1,656| 回應0 | 上一篇 | 下一篇

[UVA][二分] 10567 - Helping Fill Bates

推薦 0 收藏 0 轉貼0 訂閱站台

Problem A
Helping Fill Bates
Input: Standard Input

Output: Standard Output

Time Limit: 10 Seconds

Everyone knows Fill Bates but I guess fewer people know that he was famous in his high school days for a different reason. I just put below the exact lines from one of his short biographies:

Before high-school graduation, Bates was renowned for designing the class scheduling software that placed him in a class full of girls. With his present success, those girls are probably mutilating themselves for not buying in on an early investment.

Now you are to help him with a completely different purpose. His company has initiated a talent search program in QSA. It has 52 states (the original 50 states plus the two recent troublesome additions Oraq and Malistan). The candidates from the 52 states are given a state identity and a serial number (The serial number is unique). The state identities for the 52 states are the 52 ASCII characters A..Z and a..z. The talent search process is a bit strange. At most 1 million candidates stand in a single line according to the increasing order their serial number (Starting with 0 and then 1, 2, 3 …etc) with a placard showing only their state identity (After all who wants to hire employees from Oraq and Malistan). Mr. Fill Gates then writes a sequence of characters (Only alphabets). If candidates are found in that order of states with increasing serial numbers (Some candidates may be skipped for this purpose) then those candidates are taken. Other wise an appropriate message is given.

Input

The input file contains only one set of input. First line of the input file contains a string S containing only alphabets. The length of this string is at most 1000000. The next line contains an integer Q (0<Q<3501) which indicates the number of queries. Each of the next Q lines contain one string SS of length less than 101. These strings are the strings written by Fill Bates.

Output

For each query you should output one line. If candidates are not found in the order written by Fill Bates then you should output a string “Not matched” (Without the quotes), otherwise you should print “Matched “ (Note that an space is printed after “Matched”) and then the serial of the first candidate in the subsequence and the serial of the last candidate of the subsequence. These two integers should be separated by a single space. If there is more than one such subsequence then choose the one which has smallest starting serial number. If there is a tie choose the one with the smallest ending serial number.

Sample Input Output for Sample Input

aaaaaaaaaaaaaabbbbbbbbbdddddddddddccccccccccccc

aaaaaaaaaaaaaaaaaaa

aaaaaaaaaaabbbbbbbbbbbc

abccc

Not matched

Not matched

Matched 0 36

Problemsetter: Shahriar Manzoor, Member of Elite Problemsetters' Panel

題目描述：
基本上可以想像成，現在有一排選單，根據優先順序先排好，
接著詢問挑的種類('a'-'z') 挑的順序可能比較特別。
盡可能挑排比較前面的來符合詢問要求的種類。

題目解法：
由於字串長度很長，盡可能先進行壓縮(run-length)。
然後挑的時候先進行一次壓縮，然後用二分詢尋找匹配的。

區間的方式按照字典順序，左區間越小越好，右區間越小越好。

#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <vector>
using namespace std;
char s[1048576];
struct E {
    int l, r;
    E(int a, int b):
        l(a), r(b) {}
    bool operator<(const E &a) const {
        return l < a.l;
    }
};
vector<E> RECORD[52];
vector<int> SUM[52];
void build() {
    int i, j, l, r, node;
    char val;
    for(i = 0; i < 52; i++) {
        RECORD[i].clear();
        SUM[i].clear();
    }
    for(i = 0; s[i]; i++) {
        val = s[i];
        l = i, r = i;
        while(s[r] == val) r++;
        r--, i = r;
        if(val >= 'A' && val <= 'Z')
            node = val - 'A';
        else
            node = val - 'a' + 26;
        RECORD[node].push_back(E(l, r));
        SUM[node].push_back(r-l+1);
    }
}
void sol(char str[]) {
    int i, j, l, r;
    int pos = -1, node, cnt;
    char val;
    int first = -1, second = -1;
    for(i = 0; str[i]; i++) {
        val = str[i];
        l = i, r = i;
        while(str[r] == val) r++;
        r--, i = r;
        if(val >= 'A' && val <= 'Z')
            node = val - 'A';
        else
            node = val - 'a' + 26;
        cnt = r-l+1;
        int next = lower_bound(RECORD[node].begin(), RECORD[node].end(), E(pos+1, pos)) - RECORD[node].begin();
        while(cnt) {
            if(next >= RECORD[node].size()) {
                puts("Not matched");
                return;
            }
            if(first < 0) {
                first = RECORD[node][next].l;
            }
            if(SUM[node][next] > cnt) {
                pos = RECORD[node][next].l + cnt - 1;
                break;
            }
            cnt -= SUM[node][next];
            pos = RECORD[node][next].r;
            if(cnt <= 0)    cnt = 0;
            next++;
        }
    }
    second = pos;
    printf("Matched %d %d\n", first, second);
}
int main() {
    int n;
    char str[105];
    while(scanf("%s", s) == 1) {
        build();
        scanf("%d", &n);
        while(n--) {
            scanf("%s", str);
            sol(str);
        }
    }
    return 0;
}

我要檢舉

#10567#Helping Fill Bates#二分

台長： Morris

您可能對以下文章有興趣

[UVA] 517 - Word

[UVA] 11835 - Formula 1

[UVA][Math] 10994 - Simple Addition

[UVA][Math] 12444 - Bits and Pieces

人氣(1,656) | 回應(0)| 推薦 (0)| 收藏 (0)| 轉寄
全站分類: 不分類 | 個人分類: UVA |
此分類下一篇:[UVA][博奕dp] 1500 - Alice and Bob
此分類上一篇:[UVA] 10742 - The New Rule in Euphomia

回應(0)