Hiho----微软笔试题《Combination Lock》

Combination Lock

时间限制:10000ms

单点时限:1000ms

内存限制:256MB

描述

Finally, you come to the interview room. You know that a Microsoft interviewer is in the room though the door is locked. There is a combination lock on the door. There are N rotators on the lock, each consists of 26 alphabetic characters, namely, 'A'-'Z'. You need to unlock the door to meet the interviewer inside. There is a note besides the lock, which shows the steps to unlock it.

Note: There are M steps totally; each step is one of the four kinds of operations shown below:

Type1: CMD 1 i j X: (i and j are integers, 1 <= i <= j <= N; X is a character, within 'A'-'Z')

This is a sequence operation: turn the ith to the jth rotators to character X (the left most rotator is defined as the 1st rotator)

For example: ABCDEFG => CMD 1 2 3 Z => AZZDEFG

Type2: CMD 2 i j K: (i, j, and K are all integers, 1 <= i <= j <= N)

This is a sequence operation: turn the ith to the jth rotators up K times ( if character A is turned up once, it is B; if Z is turned up once, it is A now. )

For example: ABCDEFG => CMD 2 2 3 1 => ACDDEFG

Type3: CMD 3 K: (K is an integer, 1 <= K <= N)

This is a concatenation operation: move the K leftmost rotators to the rightmost end.

For example: ABCDEFG => CMD 3 3 => DEFGABC

Type4: CMD 4 i j(i, j are integers, 1 <= i <= j <= N):

This is a recursive operation, which means:
If i > j:
	Do Nothing
Else:
	CMD 4 i+1 j
	CMD 2 i j 1
For example: ABCDEFG => CMD 4 2 3 => ACEDEFG

输入

1st line: 2 integers, N, M ( 1 <= N <= 50000, 1 <= M <= 50000 )

2nd line: a string of N characters, standing for the original status of the lock.

3rd ~ (3+M-1)th lines: each line contains a string, representing one step.

输出

One line of N characters, showing the final status of the lock.

提示

Come on! You need to do these operations as fast as possible.

样例输入

7 4
ABCDEFG
CMD 1 2 5 C
CMD 2 3 7 4
CMD 3 3
CMD 4 1 7

样例输出

HIMOFIN

Emacs Normal Vim

 1 import java.util.Scanner;
 2 
 3 
 4 public class Main {
 5     
 6     
 7     public static void main(String[] argv){
 8         
 9         Scanner in = new Scanner(System.in);
10         int M = in.nextInt();
11         int N = in.nextInt();
12         in.nextLine();
13         String source = in.nextLine();
14         String[] move= new String[N];
15         for(int i=0; i<N;i++){
16             move[i]=in.nextLine();
17         }
18         in.close();
19         int[] int_Source = new int[M];    
20         char[] c_Source = source.toCharArray(); 
21         for(int i=0; i<M;i++){
22             int_Source[i]= c_Source[i]-65;    
23         }
24         for(int i=0; i<N;i++){
25             String[] temp = move[i].split(" ");
26             switch(temp[1]){
27             case "1":
28                 if(temp[4].length()==1)
29                     oneMethod(int_Source,Integer.parseInt(temp[2]),Integer.parseInt(temp[3]),((int)(temp[4].toCharArray()[0]))-65);
30                 break;
31             case "2":
32                 secondMethod(int_Source,Integer.parseInt(temp[2]),Integer.parseInt(temp[3]),Integer.parseInt(temp[4]));
33                 break;
34             case "3":
35                 thirdMethod(int_Source,Integer.parseInt(temp[2]));
36                 break;
37             case "4":
38                 fourthMethod(int_Source,Integer.parseInt(temp[2]),Integer.parseInt(temp[3]));
39                 break;    
40             }
41             /*
42             for(int out:int_Source ){
43                 System.out.println(out+" ");
44             }
45             System.out.println();
46             */
47         }
48         for(int out:int_Source ){
49             System.out.print((char)(out+65));
50         }
51     }
52 
53     
54     
55     
56     
57 public static void oneMethod(int[] s, int i, int j,int k){
58     
59     for(int p=i-1; p<j; p++){
60         s[p]=k;
61         s[p]=s[p]%26;
62     }
63     
64 }
65 
66 public static void secondMethod(int[] s, int i, int j,int k){
67     
68     for(int p=i-1; p<j; p++){
69         s[p]=s[p]+k;
70         s[p]=s[p]%26;
71     }    
72 }
73 
74 public static void thirdMethod(int[] s, int i){
75     int[] temp =new int[s.length];
76     for(int q=0; q<s.length;q++){
77         temp[q]=s[q];
78     }
79     for(int p=0; p<s.length; p++){
80         if(i+p<s.length)
81             s[p]=temp[i+p];
82         else
83             s[p]=temp[(i+p)%s.length];
84         s[p]=s[p]%26;
85     }
86     
87 }
88 
89 public static void fourthMethod(int[] s, int i, int j){
90     
91     for(int p=i-1;p<j;p++ ){        
92         s[p]=s[p]+p-i+2;
93         s[p]=s[p]%26;
94     }
95 }
96 
97 }