CodeFoeces GYM 101466A Gaby And Addition （字典树）

题目分析

题意：

给出n个数，找任意两个数 “相加”，求这个结果的最大值和最小值，注意此处的加法为不进位加法。

思路：

由于给出的数最多有 1e6 个，且每个数的值最大为 1e18 ，又因为特殊的加法运算，我们自然无法用常规的方法解决

注意到这个加法运算可以分配到每一位上进行运算，而且最大为1e18，十九位数，那么我们就可以用字典树来存储每个数，并进行计算，为了将字典树每个结点的深度和数的位数对应起来，我们可以将每个数都处理为19位数，从高位依次存入字典树，这样一来，就方便我们求最值了。

然后就是求最值的问题，我最初的想法是先将所有数存入字典树，随后枚举字典树的每条链（从根结点到叶子节点的路径），以求出最值，不过TLE了，想来这样写确实时间比较长，最坏的情况下查询用时：5 ^ 18 次，大约3.8e13次运算，妥妥地TLE。不过我们可以在插入某个数之前，求出这个数和字典树中存在的数“相加”的得到的最值，随后将这个数存入字典树，最后所有数存入字典树后，就可以得到最值了。

总结：

这个题目写了我近半天，确定是字典树后，由于求最值这里对原方法用时估计错误，导致自己一直TLE在第四组样例，后来请教同学才发现问题。

还有就是这个地方求最值的时候不要用递归，在这里递归的效率很低。

代码区

#include<iostream>

#include<cstdio>

#include<algorithm>

#include<cstring>

#include<queue>

#include<string>

#include<fstream>

#include<vector>

#include<stack>

#include <map>

#include <iomanip>

#define bug cout << "**********" << endl

#define show(x,y) cout<<"["<<x<<","<<y<<"] "

//#define LOCAL = 1;

using namespace std;

typedef long long ll;

typedef unsigned long long ull;

unsigned const long long inf = (ull);

const int mod = 1e9 + ;

const int Max = 2e7 + ;

struct Node

{

    int maps[];

}node[Max];

int n,id;

ull num[];

ull max_val, min_val;

char str[], str2[];

char lead[][]{ "","","","","","" ,"","","","",

    "","","","","","","",

    "",""};    //用于补充前导零，使得数凑成19位数

void insert()                                    //字典树常规插入操作

{

    int root = ;

    for (int i = ;i < ;i++)

    {

        if (node[root].maps[str[i] - ''] == ) node[root].maps[str[i] - ''] = ++id;

        root = node[root].maps[str[i] - ''];

    }

}

ull dfs(int mode)                                //mode == 1代表求最大值

{

    ull val = ;

    int root = ;

    for (int i = ; i <= ;i++)                //最大19位数

    {

        int id = -;

        ull t = ;                                //记录这个位置上的最大（小）值

        if (mode == ) t = ;

        for (int j = ;j <= ;j++)

        {

            if (mode && node[root].maps[j] && (j + str[i] - '') %  >= t)

            {

                id = j;t = (j + str[i] - '') % ;

            }

            else if (!mode && node[root].maps[j] && (j + str[i] - '') %  <= t)

            {

                id = j;t = (j + str[i] - '') % ;

            }

        }

        val += num[i] * t;

        root = node[root].maps[id];

    }

    return val;

}

int main()

{

#ifdef LOCAL

    freopen("input.txt", "r", stdin);

    freopen("output.txt", "w", stdout);

#endif

    num[] = ;

    for (int i = ;i >= ;i--)

    {

        num[i] = num[i + ] * ;    //预处理出1 ~ 1e18

    }

    id = ;                            //控制字典树结点数s

    min_val = inf;

    max_val = ;

    scanf("%d", &n);

    for (int i = ;i <= n;i++)

    {

        scanf("%s", str2);

        int len = strlen(str2);

        strcpy(str, lead[ - len]);

        strcat(str, str2);            //将数补充为19位数

        if (i != )                    //找最值的前提：至少有两个以上的数

        {

            max_val = max(max_val, dfs());

            min_val = min(min_val, dfs());

        }

        insert();

    }

    if (min_val == inf) min_val = ;

    printf("%llu %llu\n", min_val, max_val);

    return ;

}

/*

附上一组样例，如果 wrong on test 3 的话，可以用一下，这个是数极限大的情况

input

7

1000000000000000000

1000000000000000000

999999999999999999

1000000000000000000

1000000000000000000

1000000000000000000

1234567890987654321

output

1123456789876543210 2234567890987654321

 */

gym 101466A Gaby And Addition （字典树）