再次介紹我自己，OI界摸爬滾打5年半的老菜鳥，ACM/ICPC摸爬滾打半年的09級新人……
為啥轉(zhuǎn)移到了javablog呢？
今后爭取把主語言轉(zhuǎn)為java……
不過這里的代碼不見得都是java，畢竟ICPC題，java的IO還是很吃虧的，TC爭取都java……
今天寫計(jì)算機(jī)科學(xué)概論論文，順道寫了個(gè)題：SPOJ 21
給出n條記錄(n<=100000)，形如 03 10103538 2222 1233 6160 0142
要求將它們按字典序排序，并且統(tǒng)計(jì)每組記錄的出現(xiàn)次數(shù)
例如：
6
03 10103538 2222 1233 6160 0142
03 10103538 2222 1233 6160 0141
30 10103538 2222 1233 6160 0141
30 10103538 2222 1233 6160 0142
30 10103538 2222 1233 6160 0141
30 10103538 2222 1233 6160 0142
輸出：
03 10103538 2222 1233 6160 0141 1
03 10103538 2222 1233 6160 0142 1
30 10103538 2222 1233 6160 0141 2
30 10103538 2222 1233 6160 0142 2
算法：10000為基的基數(shù)排序＋10000的計(jì)數(shù)排序
復(fù)雜度O（N）
1 #include <cstdio>
2 #include <cstring>
3
4 inline int nextInt()
5 {
6 int ans=0;
7 for (;;)
8 {
9 char c=getchar();
10 if (c<'0'||c>'9')
11 break;
12 ans=(ans<<3)+(ans<<1)+c-'0';
13 }
14 return ans;
15 }
16
17 struct node
18 {
19 int key[7];
20 };
21 bool operator ==(node a,node b)
22 {
23 for (int i=0;i<7;i++)
24 if (a.key[i]!=b.key[i])
25 return 0;
26 return 1;
27 }
28
29 inline void nextNode(node &ans)
30 {
31 ans.key[0]=nextInt();
32 int tmp=0;
33 for (int i=0;i<4;i++)
34 {
35 char c=getchar();
36 tmp=(tmp<<3)+(tmp<<1)+c-'0';
37 }
38 ans.key[1]=tmp;
39 for (int i=2;i<7;i++)
40 ans.key[i]=nextInt();
41 getchar();
42 }
43
44 node arr[100010];
45
46 int cnt[10010];
47 int n;
48 int arr1[100010];
49 int arr2[100010];
50 int *now;
51 int *sorted;
52
53 int KEY[100010];
54
55 void mysort(int s)
56 {
57 memset(cnt,0,sizeof(cnt));
58 for (int i=0;i<n;i++)
59 KEY[i]=arr[now[i]].key[s];
60 for (int i=0;i<n;i++)
61 cnt[KEY[i]]++;
62 for (int i=1;i<=10000;i++)
63 cnt[i]+=cnt[i-1];
64 for (int i=n-1;i>=0;i--)
65 sorted[--cnt[KEY[i]]]=now[i];
66 }
67
68 void printNode(node a)
69 {
70 printf("%02d ",a.key[0]);
71 printf("%04d%04d",a.key[1],a.key[2]);
72 for (int i=3;i<7;i++)
73 printf(" %04d",a.key[i]);
74 }
75
76 int main()
77 {
78 int nn=nextInt();
79 while (nn--)
80 {
81 n=nextInt();
82 now=arr1;
83 sorted=arr2;
84 for (int i=0;i<n;i++)
85 {
86 nextNode(arr[i]);
87 now[i]=i;
88 }
89 for (int i=6;i>=0;i--)
90 {
91 mysort(i);
92 int *tmp=now;
93 now=sorted;
94 sorted=tmp;
95 }
96 for (int i=0,j=i;i<n;i=j)
97 {
98 node Now=arr[now[i]];
99 int cnt=0;
100 for (;Now==arr[now[j]];j++,cnt++);
101 printNode(arr[now[i]]);
102 printf(" %d\n",cnt);
103 }
104 if (nn) putchar(10);
105 getchar();
106 }
107 return 0;
108 }