AcWing 4269. 校庆(哈希 + 二分)
原题链接
简单
C++ 代码
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
typedef unsigned long long uLL;
const int N = 1e5 + 10;
int n, m, cnt;
string s, res;
uLL g[N];
string cmp(const string& a, const string& b)
{
if (a.empty()) return b;
string c = a.substr(6, 8), d = b.substr(6, 8);
return (max(c, d) == c ? b : a);
}
bool find(const uLL& tar)
{
int i = 0, j = n - 1;
while (i < j)
{
int mid = (i + j) >> 1;
if (g[mid] >= tar) j = mid;
else i = mid + 1;
}
return g[i] == tar;
}
int main()
{
cin >> n;
for (int i = 0; i < n; ++ i)
{
cin >> s;
uLL prefix = 0;
for (auto& c : s)
{
if (c == 'X') prefix = prefix * 100;
else prefix = prefix * 10 + c - '0';
}
g[i] = prefix;
}
sort(g, g + n);
cin >> m;
while (m --)
{
cin >> s;
uLL prefix = 0;
for (auto& c : s)
{
if (c == 'X') prefix = prefix * 100;
else prefix = prefix * 10 + c - '0';
}
if (find(prefix))
{
++ cnt;
if (cnt == 1)
res = s;
else res = cmp(res, s);
}
else
{
if (!cnt)
res = cmp(res, s);
}
}
cout << cnt << endl << res;
return 0;
}