首页 > 数据结构 > Hash表 > POJ 1706 References [解题报告] Java
2013
11-10

POJ 1706 References [解题报告] Java

References

问题描述 :

Editors of an electronic magazine make draft versions of the documents in the form of text files. However, publications should meet some requirements, in particular, concerning the rules of reference use. Unfortunately, lots of the draft articles violate some rules. It is desirable to develop a computer program that will make a publication satisfy all the rules from a draft version.

Let’s call a “paragraph” a set of lines in the article going one after another, so that paragraphs are separated by at least one empty line (an “empty line” is a line that containing no characters different from spaces). Any paragraph can contain an arbitrary number of references. A reference is a positive integer not greater than 999 enclosed in square brackets (for example: [23]). There will be no spaces between the brackets and the number. The square brackets are not used in any other context but reference.

There can be two types of paragraph – “regular” and “reference description”. Reference description differs from the regular paragraph because it begins with the reference it describes, for example:

[23] It is the description …

The opening square bracket will be at the first position of the first line of the “reference description” paragraph (i.e. there will be no spaces before it). No reference description paragraph will contain references inside itself.

Each reference will have exactly one corresponding description and each description will have at least one reference to it.

To convert a draft version to a publication you have to use the following rules.

  • References should be renumbered by the successive integer numbers starting from one in the order of their first appearance in the regular paragraphs of the source draft version of the document.
  • Reference descriptions should be placed at the end of the article ordered by their number.
  • The order of “regular” paragraphs in the document should be preserved.
  • Your program should not make any other changes to the paragraphs.

输入:

The input file will be a text file containing a draft article your program should process. All lines will be no more than 80 characters long. Any reference description will contain no more than 3 lines. The input file will contain up to 40000 lines.

输出:

The output file contains the result of processing. All paragraphs should be separated by one “true” empty line (i.e. a line that contains no characters at all). There should be no empty lines before the first paragraph.

样例输入:

[5] Brownell, D, "Dynamic Reverse Address Resolution Protocol
    (DRARP)", Work in Progress.

The Reverse Address Resolution Protocol (RARP) [10] (through the
extensions defined in the Dynamic RARP (DRARP) [5]) explicitly
addresses the problem of network address discovery, and includes an
automatic IP address assignment mechanism.

[10] Finlayson, R., Mann, T., Mogul, J., and M. Theimer, "A Reverse
        Address Resolution Protocol", RFC 903, Stanford, June 1984.

[16] Postel, J., "Internet Control Message Protocol", STD 5, RFC 792,
        USC/Information Sciences Institute, September 1981.


The Trivial File Transfer Protocol (TFTP) [20] provides for transport
of a boot image from a boot server.  The Internet Control Message
Protocol (ICMP) [16] provides for informing hosts of additional routers
via "ICMP redirect" messages.

[20] Sollins, K., "The TFTP Protocol (Revision 2)",  RFC 783, NIC,
     June 1981.

Works [10], [16] and [20] can be obtained via Internet.

样例输出:

The Reverse Address Resolution Protocol (RARP) [1] (through the
extensions defined in the Dynamic RARP (DRARP) [2]) explicitly
addresses the problem of network address discovery, and includes an
automatic IP address assignment mechanism.

The Trivial File Transfer Protocol (TFTP) [3] provides for transport
of a boot image from a boot server.  The Internet Control Message
Protocol (ICMP) [4] provides for informing hosts of additional routers
via "ICMP redirect" messages.

Works [1], [4] and [3] can be obtained via Internet.

[1] Finlayson, R., Mann, T., Mogul, J., and M. Theimer, "A Reverse
        Address Resolution Protocol", RFC 903, Stanford, June 1984.

[2] Brownell, D, "Dynamic Reverse Address Resolution Protocol
    (DRARP)", Work in Progress.

[3] Sollins, K., "The TFTP Protocol (Revision 2)",  RFC 783, NIC,
     June 1981.

[4] Postel, J., "Internet Control Message Protocol", STD 5, RFC 792,
        USC/Information Sciences Institute, September 1981.

解题代码:

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

public class Main 
{
    public static Map< Integer,Integer> mapOldToNew;
    public static Map< Integer,Integer> mapNewToOld;    
    public static int counter = 1;
    public static void main(String[] args) throws Exception
    {
        BufferedReader stdin = new BufferedReader(new InputStreamReader(System.in));
        Map< Integer, StringBuilder> references = new HashMap< Integer,StringBuilder>(1000);
        mapOldToNew = new HashMap< Integer,Integer>(1000);
        mapNewToOld = new HashMap< Integer,Integer>(1000);
        boolean isInsidePara = false;
        boolean isRegPara = true;
        boolean isBegin = true;
        String num = "";
        String line = null;
        StringBuilder para = null;
        String id = "";
        while(true)
        {
            line = stdin.readLine();
            if(line == null)
            {
                break;
            }
            if(line.trim().length() == 0)
            {
                if(isInsidePara)
                {
                    isInsidePara = false;
                    if(isRegPara)
                    {
                        //regulars[numReg++] = para;
                    }else
                    {
                        int in = Integer.parseInt(id);
                        references.put(in,para);
                    }
                }
            }else
            {
                if(!isInsidePara)
                {
                    isInsidePara = true;
                    if(line.startsWith("["))
                    {
                        
                        para = new StringBuilder(240);
                        isRegPara = false;
                        id = "";
                        for(int i = 1; i < line.length(); i++)
                        {
                            char ch = line.charAt(i);
                            if(ch == ']')
                            {
                                break;
                            }
                            id += ch;
                        }
                        para.append(line);
                        para.append("\n");
                    }else
                    {
                        isRegPara= true;
                        if(isBegin)
                        {
                            isBegin = false;
                        }else
                        {
                            System.out.write('\n');
                        }
                        printRegLine(line);
                    }
                }else
                {
                    if(isRegPara)
                    {
                        printRegLine(line);
                    }else
                    {
                        para.append(line);
                        para.append("\n");
                    }
                }
            }
        }
        
        if(isInsidePara)
        {
            if(isRegPara)
            {
                //regulars[numReg++] = para;
            }else
            {
                int in = Integer.parseInt(id);
                references.put(in,para);
            }
        }
        
        boolean insideRef = false;
        for(int j = 1; j < counter; j++)
        {
            StringBuilder sb = references.get(mapNewToOld.get(j));
            System.out.write('\n');
            
            num = "";
            insideRef = false;
            for(int i = 0; i < sb.length(); i++)
            {
                char ch = sb.charAt(i);
                if(ch == '[')
                {
                    insideRef = true;
                    System.out.write(ch);
                }else if(ch == ']')
                {
                    insideRef = false;
                    int in = Integer.parseInt(num);
                    num = "";
                    System.out.print(mapOldToNew.get(in));
                    System.out.write(ch);
                }else if(insideRef)
                {
                    num += ch;
                }else
                {
                    System.out.write(ch);
                }
            }
        }
    }
    
    public static void printRegLine(String sb)
    {
            String num = "";
            boolean insideRef = false;
            for(int i = 0; i < sb.length(); i++)
            {
                char ch = sb.charAt(i);
                if(ch == '[')
                {
                    insideRef = true;
                    System.out.write(ch);
                }else if(ch == ']')
                {
                    insideRef = false;
                    int in = Integer.parseInt(num);
                    Integer value = mapOldToNew.get(in);
                    if(value == null)
                    {
                        mapOldToNew.put(in,counter);
                        mapNewToOld.put(counter,in);
                        counter++;
                    }
                    num = "";
                    System.out.print(mapOldToNew.get(in));
                    System.out.write(ch);
                }else if(insideRef)
                {
                    num += ch;
                }else
                {
                    System.out.write(ch);
                }
            }
            System.out.write('\n');
    }
}

  1. 第二个方法挺不错。NewHead代表新的头节点,通过递归找到最后一个节点之后,就把这个节点赋给NewHead,然后一直返回返回,中途这个值是没有变化的,一边返回一边把相应的指针方向颠倒,最后结束时返回新的头节点到主函数。

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

  3. 站长好。我是一个准备创业的互联网小白,我们打算做一个有关国*际*游*学的平台。手上也有了一些境外资源。现阶段的团队现在没有cto.原意出让一些管理股寻找一个靠谱的技术专家做合伙人, 不知道是不是能得到您的帮助。发个帖子或者其他方式。期待您的回应。可以加我微信tianxielemon聊聊。