首页 > 数据结构 > Hash表 > POJ 1366 Word [解题报告] Java
2013
11-09

POJ 1366 Word [解题报告] Java

Word

问题描述 :

Dr. R. E. Wright’s class was studying modified L-Systems. Let us explain necessary details. As a model let us have words of length n over a two letter alphabet {a, b}. The words are cyclic, this means we can write one word in any of n forms we receive by cyclic shift, whereby the first and the last letters in the word are considered to be neighbours.

Rewriting rules rewrite a letter at a position i, depending on letters at the positions i – 2, i, i+1. We rewrite all letters of the word in one step. When we have a given starting word and a set of rewriting rules a natural question is: how does the word look after s rewriting steps?

Help Dr. R. E. Wright and write a program which solves this task.

输入:

There are several blocks in the input, each describing one system. There is an integer number n, 2 < n < 16 the length of the input word in the first line. There is a word in the next line. The word contains only lowercase letters a and b. There are four characters c1 c2 c3 c4 in the next eight lines. Each quadruple represents one rewriting rule with the following meaning: when the letter at the position i - 2 is c1 and the letter at the position i is c2 and the letter at the position i + 1 is c3 then the letter at the position i after rewriting will be c4. Rewriting rules are correct and complete. There is an integer number s, 0 <= s <= 2000000000, in the last line of the block.

输出:

There is one line corresponding to each block of the input. The line contains a word which we receive after s rewriting steps from the corresponding starting word using given rewriting rules. As we mentioned above, the word can be written in any of n cyclic shifted forms. The output file contains the lexicographically smallest word, assuming that a < b.

样例输入:

5
aaaaa
aaab
aabb
abab
abbb
baab
babb
bbab
bbbb
1

样例输出:

bbbbb

解题代码:

//* @author: Yeming Hu"[email protected]"
import java.util.*;
import java.io.*;

public class Main
{
    public static BufferedInputStream bis;
    public static StringBuilder str;
    public static char[][] rules;
    public static StringBuilder[] words;
    public static int k;
    public static void main(String[] args) throws Exception
    {
        bis = new BufferedInputStream(System.in);
        
	rules = new char[8][4];
	Map< String,Boolean> exist = new HashMap< String,Boolean>();
	words = new StringBuilder[40000];
	StringBuilder start,result, previous, key;
        str = new StringBuilder();
        start = new StringBuilder();
	result = new StringBuilder();
	previous = new StringBuilder();
        key = new StringBuilder();
        for(int i = 0; i < 40000; i++)
        {
            words[i] = new StringBuilder();
        }
	while(true)
	{
	    int n = (int)readLong();
            if(n == -1)
            {
                break;
            }
            k = 0;
            start.delete(0,start.length());
	    start.append(readString());
            readRules();
	    long s = readLong();
            result.delete(0,result.length());
	    result.append(start);
	    exist.clear();

            words[k].delete(0,words[k].length());
            words[k].append(lowest(result));
            k++;
	    for(int j=0;j< s;j++)
	    {
                previous.delete(0,previous.length());
		previous.append(result);
		result.delete(0,result.length());
	        for(int i=0;i< n;i++)
	        {
	            int i1 = (i-2+n)%n;
		    int i2 = i;
		    int i3 = (i+1)%n;
                    key.delete(0,key.length());
		    key.append(previous.charAt(i1));
		    key.append(previous.charAt(i2));
		    key.append(previous.charAt(i3));
		    result.append(getKey(key));
	        }
		String lw = lowest(result);
                
		if(exist.get(lw) == null)
		{
		    exist.put(lw,true);
		    words[k].delete(0,words[k].length());
                    words[k].append(lw);
                    k++;
		}else
		{
		    int index = find(lw);
		    int p = j + 1 - index;
		    long resultIndex = ((s - j) % p - 1 + p)%p  + index;
                    result.delete(0,result.length());
                    result.append(words[(int)resultIndex]);
		    break;
		}
	    }

	    System.out.println(lowest(result));
	}
    }
    
    public static int find(String lw)
    {
        int index = 0;
        for(int i = 0; i < k; i++)
        {
            boolean reached = true;
            for(int j = 0; j < lw.length(); j++)
            {
                if(lw.charAt(j) != words[i].charAt(j))
                {
                    reached = false;
                    break;
                }
            }
            if(reached)
            {
                index = i;
                break;
            }
        }
        return index;
    }
    
    public static char getKey(StringBuilder sb)
    {
        char result = '\0';
        for(int i = 0; i < 8; i++)
        {
            boolean reached = true;
            for(int j = 0; j < 3; j++)
            {
                if(rules[i][j] != sb.charAt(j))
                {
                    reached = false;
                    break;
                }
            }
            if(reached)
            {
                result = rules[i][3];
                break;
            }
        }
        return result;
    }
    
    public static void readRules() throws Exception
    {
        for(int i = 0; i < 8; i++)
	{
            for(int j = 0; j < 4; j++)
            {
                while(true)
                {
                    int bt = bis.read();
                    if(Character.isLetter(bt))
                    {
                        rules[i][j] = (char)bt;
                        break;
                    }
                }
            }
	}
    }
    
    static String lowest(StringBuilder sb)
    {
        String p = sb.toString();
	String min = p;
	int n = p.length();
	for(int i=0;i< n;i++)
	{
	    String next = p.substring(n-1,n) + p.substring(0,n-1);
	    if(next.compareTo(min) < 0)
	    {
	        min = next;
	    }
	    p = next;
	}
	return min;
    }
    
    public static long readLong() throws Exception
    {
        long num = 0;
        while(true)
        {
            int bt = bis.read();
            if(bt == -1)
            {
                return -1;
            }
            if(Character.isDigit(bt))
            {
                num = num*10 + bt - '0';
                break;
            }
        }
        
        while(true)
        {
            int bt = bis.read();
            if(!Character.isDigit(bt))
            {
                break;
            }
            num = num*10 + bt - '0';
        }
        return num;
    }
    
    public static StringBuilder readString() throws Exception
    {
        str.delete(0,str.length());
        while(true)
        {
            int bt = bis.read();
            if(Character.isLetter(bt))
            {
                str.append((char)bt);
                break;
            }
        }
        
        while(true)
        {
            int bt = bis.read();
            if(!Character.isLetter(bt))
            {
                break;
            }
            str.append((char)bt);
        }
        
        return str;
    }
}

  1. 约瑟夫也用说这么长……很成熟的一个问题了,分治的方法解起来o(n)就可以了,有兴趣可以看看具体数学的第一章,关于约瑟夫问题推导出了一系列的结论,很漂亮

  2. 嗯 分析得很到位,确实用模板编程能让面试官对你的印象更好。在设置辅助栈的时候可以这样:push时,比较要push的elem和辅助栈的栈顶,elem<=min.top(),则min.push(elem).否则只要push(elem)就好。在pop的时候,比较stack.top()与min.top(),if(stack.top()<=min.top()),则{stack.pop();min.pop();},否则{stack.pop();}.