首页 > 专题系列 > Java解POJ > POJ 3749 破译密码 [解题报告] Java
2013
11-13

POJ 3749 破译密码 [解题报告] Java

破译密码

问题描述 :

据说最早的密码来自于罗马的凯撒大帝。消息加密的办法是:对消息原文中的每个字母,分别用该字母之后的第5个字母替换(例如:消息原文中的每个字母A都分别替换成字母F)。而你要获得消息原文,也就是要将这个过程反过来。

密码字母:A B C D E F G H I J K L M N O P Q R S T U V W X Y Z M

原文字母:V W X Y Z A B C D E F G H I J K L M N O P Q R S T U

注意:只有字母会发生替换,其他非字母的字符不变,并且消息原文的所有字母都是大写的。

输入:

最多不超过100个数据集组成,每个数据集之间不会有空行,每个数据集由3部分组成:

  1. 起始行:START
  2. 密码消息:由1到200个字符组成一行,表示凯撒发出的一条消息.
  3. 结束行:END

在最后一个数据集之后,是另一行:ENDOFINPUT

输出:

每个数据集对应一行,是凯撒的原始消息。

样例输入:

START
NS BFW, JAJSYX TK NRUTWYFSHJ FWJ YMJ WJXZQY TK YWNANFQ HFZXJX
END
START
N BTZQI WFYMJW GJ KNWXY NS F QNYYQJ NGJWNFS ANQQFLJ YMFS XJHTSI NS WTRJ
END
START
IFSLJW PSTBX KZQQ BJQQ YMFY HFJXFW NX RTWJ IFSLJWTZX YMFS MJ
END
ENDOFINPUT

样例输出:

IN WAR, EVENTS OF IMPORTANCE ARE THE RESULT OF TRIVIAL CAUSES
I WOULD RATHER BE FIRST IN A LITTLE IBERIAN VILLAGE THAN SECOND IN ROME
DANGER KNOWS FULL WELL THAT CAESAR IS MORE DANGEROUS THAN HE

解题代码:

import java.io.BufferedInputStream;   
import java.util.Scanner;   
  
/**  
 *  
 *poj  
 * @author NC  
 */  
public class Main {   
  
    public static void main(String[] args) {   
        Scanner scan = new Scanner(new BufferedInputStream(System.in));   
        while (scan.hasNext()) {   
            String s = scan.nextLine();   
            if (s.equals("ENDOFINPUT")) {   
                break;   
            }   
            while (s.equals("START")) {   
                s = scan.nextLine();   
                if (s.equals("END")) {   
                    break;   
                }   
                char[] cs = s.trim().toCharArray();   
                for (int i = 0; i < cs.length; i++) {   
                    char c = cs[i];   
                    if (c >= 'a' && c <= 'z') {   
                        c = (char) (c - 32);   
                    }   
                    if (c >= 'A' && c <= 'Z') {   
                        c = (char) ('A' + (c - 'A' - 5 + 26) % 26);   
                        System.out.print(c);   
                    } else {   
                        System.out.print(c);   
                    }   
                }   
                System.out.println();   
                s = scan.nextLine();   
            }   
  
        }   
    }   
}

  1. 可以参考算法导论中的时间戳。就是结束访问时间,最后结束的顶点肯定是入度为0的顶点,因为DFS要回溯

  2. 换句话说,A[k/2-1]不可能大于两数组合并之后的第k小值,所以我们可以将其抛弃。
    应该是,不可能小于合并后的第K小值吧