上海理工大学程序设计 F十六进制的异或

原题链接：F-十六进制的异或

题目大意：给定n个十六进制的数，再给q个10进制数。定义异或运算在十六进制下为a^b=(a+b)%16，问给出的十进制数和第几个十六进制数在十六进制异或后的数在十进制下最大，输出下标。

思路：要求十进制下最大，其实也就是求十六进制下最大。那么可以很很自然的想到，对于一个数的十六进制，高位越大值就越大。那么就可以对n个十六进制的数进行拆位处理，并存入trie树里面，对于q个十进制数就先转换为十六进制，再去trie树里面查找，贪心的找当前位置最大的。对于trie数组，题目会给出1e5个十六数，并且数的长度最多为20，所以第一维应该开2e6，第二维开十七就可以了。对于十进制的数，因为要拆位比较，并且这些数据最大为1e18，转换为十六进制最多也就15个数，所以开16就够了。

//冷静，冷静，冷静
//调不出来就重构 
#pragma GCC optimize(2)
#pragma GCC optimize("O3")
#include<bits/stdc++.h>
#define endl '\n'
using namespace std;
typedef long long ll;
typedef long double ld; 
typedef pair<ll,ll> pii;
const int N=2e6+10,mod=998244353;
ll f[N][17],idx=0,id[N],p[16];
void dfs(ll x,ll dep)//第一维是trie的层数，第二维是十进制数的位置
{
	if(!dep)
	{
		cout<<id[x]<<endl;//十进制数已经没有了，那么这个就是最大的
		return;
	}
	ll max1=-1,jl=-1;
	for(int i=0;i<17;i++)//找当前位不进位加法最大的数
	{
		if(f[x][i])
		{
			ll v=(p[dep]+i)%16;
			if(v>max1)
			{
				max1=v;jl=i;
			}
		}
	}
	dfs(f[x][jl],dep-1);
}
int main()
{
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	ll n,m;cin>>n>>m;
	for(int i=1;i<=n;i++)
	{
		string s;cin>>s;//字符串读入十六进制数 
		while(s.size()<16)s='0'+s;//因为要插入trie树里面，所以要统一长度,由于x最多也就1e18,所以只要长度到16就行了。
		ll k=0;
		for(int i=0;i<s.size();i++)//插入操作
		{
			ll v=(isdigit(s[i])?s[i]-'0':s[i]-'A'+10);
			if(!f[k][v])f[k][v]=++idx;
			k=f[k][v];
		}
		id[k]=i;//记录当前节点对应的下标
	}
	while(m--)
	{
		ll a;cin>>a;
		for(int i=1;i<=16;i++)
		{
			p[i]=a%16;a/=16;//对于十进制数拆成十六进制
		}
		dfs(0,16);
	}
    return 0;
}