ZOJ-1038

高效的做法应该是用前缀树，这里我直接暴力枚举模拟了，也能过。。

import java.util.Map;
import java.util.Scanner;
import java.util.TreeMap;
import java.util.regex.Pattern;public class Main
{public static void main(String[] args){Scanner sc = new Scanner(System.in);String[] ps = new String[] { "", "", "[abc]", "[def]", "[ghi]","[jkl]", "[mno]", "[pqrs]", "[tuv]", "[wxyz]" };int N = sc.nextInt();Map dict = new TreeMap();String line;for (int t = 1; t <= N; t++){System.out.format("Scenario #%d:\n", t);dict.clear();int w = sc.nextInt();sc.nextLine();while (w-- > 0){line = sc.nextLine();String[] ss = line.split(" ");dict.put(ss[0], Integer.valueOf(ss[1]));}int m = sc.nextInt();sc.nextLine();while (m-- > 0){line = sc.nextLine();String pattern = "";for (int i = 0; i < line.length() - 1; i++){pattern += ps[line.charAt(i) - '0'];Pattern p = Pattern.compile(pattern);String curr, prev = null, res = null;int prob = 0, max = -1;for (String key : dict.keySet()){if (key.length() >= (i + 1)&& p.matcher(key.substring(0, i + 1)).find()){curr = key.substring(0, i + 1);if (curr.equals(prev))prob += dict.get(key);elseprob = dict.get(key);if (prob > max){max = prob;res = curr;}prev = curr;}}if (res != null)System.out.println(res);elseSystem.out.println("MANUALLY");}System.out.println();}System.out.println();}sc.close();}
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！