校庆
题目描述
$2019$ 年浙江大学将要庆祝成立 $122$ 周年。
为了准备校庆,校友会收集了所有校友的身份证号。
现在需要请你编写程序,根据来参加校庆的所有人士的身份证号,统计来了多少校友。
输入格式
输入在第一行给出正整数 $N$。
随后 $N$ 行,每行给出一位校友的身份证号($18$ 位由数字和大写字母 $X$ 组成的字符串)。题目保证身份证号不重复。
随后给出前来参加校庆的所有人士的信息:
首先是一个正整数 $M$。
随后 $M$ 行,每行给出一位人士的身份证号。题目保证身份证号不重复。
输出格式
首先在第一行输出参加校庆的校友的人数。
然后在第二行输出最年长的校友的身份证号 —— 注意身份证第 $7 \sim 14$ 位给出的是 yyyymmdd
格式的生日。
如果没有校友来,则在第二行输出最年长的来宾的身份证号。题目保证这样的校友或来宾必是唯一的。
数据范围
$1 \le N, M \le 10 ^ 5$
输入样例:
5
372928196906118710
610481197806202213
440684198612150417
13072819571002001X
150702193604190912
6
530125197901260019
150702193604190912
220221196701020034
610481197806202213
440684198612150417
370205198709275042
输出样例:
3
150702193604190912
正解(STL set
或 hash
)
STL set
很多题解都有,这里就不说了。
首先,我们建立一个哈希表
(我建了六个,三个存普通身份证号,三个存末尾是 ,将 $N$ 位校友的身份证号(字符串、X
的身份证号)long long
)存进哈希表
中。
查找时,我们看一下哈希表
里有没有这个身份证号就行了。最年长就比较第 $7 \sim 14$ 位取最小值即可。
#include <iostream>
#define p 18
#define div_ 10000
#define mod_ 100000000
#define inf 999999990000
#define SIZE 10000019
#define SIZE_ 10000079
#define SIZE__ 10000103
#define h(x) ((x)%SIZE)
#define h_(x) ((x)%SIZE_)
#define h__(x) ((x)%SIZE__)
using namespace std;
int n, m, cnt;
long long x, ans = inf, ans_ = inf;
bool b, X, X_, v[SIZE], v_[SIZE], _v[SIZE_], _v_[SIZE_], __v[SIZE__], __v_[SIZE__];
int get (long long x)
{
x /= div_, x %= mod_;
return x;
}
int count (long long x)
{
int res = 0;
while (x)
{
res ++, x /= 10;
}
return res;
}
int main ()
{
cin >> n;
bool flag = n == 100000;
while (n --)
{
cin >> x;
if (cin.get () == 'X')
{
v_[h (x * 10)] = _v_[h_ (x * 10)] = __v_[h__ (x * 10)] = 1;
}
else
{
v[h (x)] = _v[h_ (x)] = __v[h__ (x)] = 1;
}
}
cin >> m;
while (m --)
{
cin >> x, b = 0;
if (cin.get () == 'X')
{
x *= 10, b = 1;
}
if (b && v_[h (x)] && _v_[h_ (x)] & __v_[h__ (x)] || !b && v[h (x)] && _v[h_ (x)] && __v[h__ (x)])
{
cnt ++;
if (get (x) < get (ans_ * (X_ ? 10 : 1)))
{
ans_ = x / (b ? 10 : 1), X_ = b;
}
}
if (get (x) < get (ans * (X ? 10 : 1)))
{
ans = x / (b ? 10 : 1), X = b;
}
}
cout << cnt << endl;
if (cnt)
{
ans = ans_, X = X_;
}
for (int i = 1; i <= p - count (ans) - X; i ++)
{
cout << 0;
}
cout << ans << (X ? 'X' : '\0');
return 0;
}