牛客 小米校招 找“异数” 高精度进制转化

题目描述
定义：数值序列中包含2~16进制整数，如果序列中有一个数，与序列中其他任何一个数大小都不相等，则这个数叫做“异数”。请找出给定数值序列中所有的“异数”.
输入描述:

输入数值序列i行(0<i)，每一行分别是进制和数值，以“#”分割。如：n#m, n是整数，代表n进制（1<n<17）,m是n进制下的数值.
输入序列以结束符”END”结束。
m的字符集为0-9和A-F，保证数值在十进制下不超过1e9，行数不超过100001行。

输出描述:

输出j行(0<j<=i),每一行都是输入序列的“异数”。要求：
1.按照输入序列的原序输出;
2.如果没有”异数”,输出字符串”None”
3.结束符“END”不用输出

示例1
输入
复制

10#15
4#32
4#33
8#17
END

输出
复制

4#32

#ifdef debug
#include <time.h>
#include "/home/majiao/mb.h"
#endif

#include <iostream>
#include <algorithm>
#include <vector>
#include <string.h>
#include <map>
#include <set>
#include <stack>
#include <queue>
#include <stdlib.h>
#include <math.h>

#define MAXN ((int)1e5+7)
#define ll long long int
#define INF (0x7f7f7f7f)
#define fori(lef, rig) for(int i=lef; i<=rig; i++)
#define forj(lef, rig) for(int j=lef; j<=rig; j++)
#define fork(lef, rig) for(int k=lef; k<=rig; k++)
#define QAQ (0)

using namespace std;

#define show(x...) \ do { \ cout << "\033[31;1m " << #x << " -> "; \ err(x); \ } while (0)

void err() { cout << "\033[39;0m" << endl; }
template<typename T, typename... A>
void err(T a, A... x) { cout << a << ' '; err(x...); }

namespace FastIO{

	char print_f[105];
	void read() {}
	void print() { putchar('\n'); }
	
	template <typename T, typename... T2>
		inline void read(T &x, T2 &... oth) {
			x = 0;
			char ch = getchar();
			ll f = 1;
			while (!isdigit(ch)) {
				if (ch == '-') f *= -1; 
				ch = getchar();
			}
			while (isdigit(ch)) {
				x = x * 10 + ch - 48;
				ch = getchar();
			}
			x *= f;
			read(oth...);
		}
	template <typename T, typename... T2>
		inline void print(T x, T2... oth) {
			ll p3=-1;
			if(x<0) putchar('-'), x=-x;
			do{
				print_f[++p3] = x%10 + 48;
			} while(x/=10);
			while(p3>=0) putchar(print_f[p3--]);
			putchar(' ');
			print(oth...);
		}
} // namespace FastIO
using FastIO::print;
using FastIO::read;

int n, m, Q, K;

string num_parse(int a, int b, string aline) {
	string bline;
	vector<int> num;
	for(auto c : aline)
		if(c>='0' && c<='9') num.push_back(c -= '0');
		else if(c>='A' && c<='Z') num.push_back(c - 'A' + 10);
	reverse(num.begin(), num.end());
	vector<int> res;
	while(num.size()) {
		int r = 0;
		for(int i=num.size()-1; i>=0; i--) {
			num[i] += r * a;
			r = num[i] % b;
			num[i] /= b;
		}
		res.push_back(r);
		while(num.size() && num.back() == 0) num.pop_back();
	}
	for(auto x : res) bline.push_back(x+'0');
	reverse(bline.begin(), bline.end());
	return bline;
}

int main() {
#ifdef debug
	freopen("test", "r", stdin);
	clock_t stime = clock();
#endif
	string str;
	map<string, int> mp;
	string arr[MAXN];
	while(cin >> str && str != "END") {
		arr[++n] = str;
		string a, aline;
		string* ptr = &a;
		for(auto ch : str) {
			if(ch == '#') 
				ptr = &aline;
			else 
				ptr->push_back(ch);
		}
		string bline = num_parse(atoi(a.data()), 10, aline);
		int& rx = mp[bline];
		rx ++;
	}
	bool flag = true;
	for(int i=1; i<=n; i++) {
		string a, aline;
		string* ptr = &a;
		for(auto ch : arr[i]) {
			if(ch == '#')
				ptr = &aline;
			else
				ptr->push_back(ch);
		}
		string bline = num_parse(atoi(a.data()), 10, aline);
		if(mp[bline] == 1) 
			cout << arr[i] << endl, flag = false;
	}
	if(flag) cout << "None" << endl;

	
#ifdef debug
	clock_t etime = clock();
	printf("rum time: %lf 秒\n",(double) (etime-stime)/CLOCKS_PER_SEC);
#endif 
	return 0;
}