再次介绍我自己，OI界摸爬滚打5年半的老菜鸟，ACM/ICPC摸爬滚打半年的09级新人……
为啥转移到了javablog呢？
今后争取把主语言转为java……
不过这里的代码不见得都是java，毕竟ICPC题，java的IO还是很吃亏的，TC争取都java……
今天写计算机科学概论论文，顺道写了个题：SPOJ 21
给出n条记录(n<=100000)，形如 03 10103538 2222 1233 6160 0142
要求将它们按字典序排序，并且统计每组记录的出现次数
例如：
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为基的基数排序＋10000的计数排序
复杂度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 }