-
Notifications
You must be signed in to change notification settings - Fork 6
/
Copy path1002(Simulation,Hash)
130 lines (116 loc) · 2.77 KB
/
1002(Simulation,Hash)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
import java.io.*;
import java.util.*;
import java.util.ArrayList.*;
public class Main {
static int partion(String[] array, int p, int r) {
String x = array[r];
int i = p - 1;//注意这点,把i设成负值,然后作为移动的标志
int j;
for (j = p; j < r; j++) {
if (array[j].compareTo(x) < 0) {
i++;
String temp = array[j];
array[j] = array[i];
array[i] = temp;
}
}
String temp = array[j];
array[j] = array[i + 1];
array[i + 1] = temp;
return i+1;//返回的应该是交换后的哨兵的位置
}
//递归解决每个划分后的小数组
static void quickSort(String[] array, int p, int r) {
if (p < r) {
int q = partion(array, p, r);
quickSort(array, p, q - 1);
quickSort(array, q + 1, r);
}
}
public static String toNorm(String s){
String res = "";
for(int i = 0; i < s.length(); i++){
char c = s.charAt(i);
if('0' <= c && c <= '9'){
res += c;
}
if('A' <= c && c <= 'C'){
res += '2';
}
if('D' <= c && c <= 'F'){
res += '3';
}
if('G' <= c && c <= 'I'){
res += '4';
}
if('J' <= c && c <= 'L'){
res += '5';
}
if('M' <= c && c <= 'O'){
res += '6';
}
if('P' <= c && c <= 'S'){
res += '7';
}
if('T' <= c && c <= 'V'){
res += '8';
}
if('W' <= c && c <= 'Z'){
res += '9';
}
}
return res;
}
public static String output(String s){
return s.substring(0, 3) + '-' + s.substring(3, 7);
}
public static int mod = 23333;
public static int eval(String s){
return Integer.parseInt(s)%mod;
}
public static void main(String args[]) throws Exception
{
Scanner cin=new Scanner(System.in);
int a = cin.nextInt();
ArrayList<ArrayList<String>> aas = new ArrayList<ArrayList<String>>();
for(int i = 0; i < mod; i++){
aas.add(new ArrayList<String>());
}
for(int i = 0; i < a; i++){
String temp = cin.next();
String tempN = toNorm(temp);
int eval = eval(tempN);
aas.get(eval).add(tempN);
}
ArrayList<String> res = new ArrayList<String>();
for(int i = 0; i < mod; i++){
ArrayList<String> thisAl = aas.get(i);
int num = thisAl.size();
int[] state = new int[num];
for(int i1 = 0; i1 < num; i1 ++) state[i1] = 1;
for(int i1 = 0; i1 < num-1; i1++){
if(state[i1] == 0) continue;
for(int j = i1+1; j < num; j++){
if(thisAl.get(j).equals(thisAl.get(i1))){
state[j] = 0;
state[i1]++;
}
}
if(state[i1]>1){
res.add(output(thisAl.get(i1)) + " " + state[i1]);
}
}
}
if(res.size() == 0){
System.out.println("No duplicates. ");
}
else{
//res.sort(null);
String[] array = (String[])res.toArray(new String[res.size()]);
quickSort(array, 0, array.length - 1);
for(int i = 0; i < res.size(); i++){
System.out.println(array[i]);
}
}
}
}