XJTUOJ 首页 题库 比赛 评测 排名 讨论 帮助
登录 注册
编号 题目 状态 分数 总时间 内存 代码 / 答案文件 提交者 提交时间
#8943 #1060. 一姬的三倍满自动机 Accepted 100 14066 ms 90936 K C++ 11 / 1.5 K Komeiji Koishi 2019-07-02 12:25:29
显示原始代码 
#include <iostream>
#include <cstdio>
#include <cstring>

using namespace std;
typedef long long ll;

class Trie {
public:
    int next[2];
};

void insert(int a);
int search(int a);

const int MAXN = 1e6 + 5, MAX = 31 * MAXN;
int num[MAXN];
Trie trie[MAX];
int trcnt;

int main() {
    // freopen("test.txt", "r", stdin);
    int n, x;
    scanf("%d %d", &n, &x);
    // 初始化
    trcnt = 0;
    // 输入
    for (int i = 1; i <= n; i++) {
        scanf("%d", &num[i]);
    }
    // 建树并求解
    int res = 0;
    insert(num[1]);
    for (int i = 2; i <= n; i++) {
        // 查找
        int tmp = search(num[i] ^ x);
        res = max(res, tmp);
        // 插入
        insert(num[i]);
    }
    // 输出
    printf("%d\n", res);
    // 初始化
    memset(trie, 0, (trcnt + 1) * sizeof(Trie));
    return 0;
}
// 字典树：插入
void insert(int a) {
    // 按二进制从高位到低位插入
    int index = 0;
    for (int i = 30; i >= 0; i--) {
        // 获取子节点
        int k = (a >> i) & 1;
        int &pos = trie[index].next[k];
        // 插入
        if (!pos)
            pos = ++trcnt;
        // 递进
        index = pos;
    }
}
// 字典树：查找
int search(int a) {
    // 按二进制从高位到低位比较
    int b = 0;
    int index = 0;
    for (int i = 30; i >= 0; i--) {
        // 获取子节点
        int k = (a >> i) & 1;
        // 尽可能找当前位不同的数可使异或和更大
        if (trie[index].next[!k]) {
            k = !k;
        }
        // 保存
        b = b | (k << i);
        // 递进
        index = trie[index].next[k];
    }
    // 返回
    return (a ^ b);
}
子任务 #1
Accepted
得分：100
测试点 #1
Accepted
得分：100
用时：1363 ms
内存：90904 KiB

输入文件（1.in） 

1000000 632300339
116075074 933109782 359791507 357731405 156603278 7890374 135196806 465283541 596
<9870006 bytes omitted>

答案文件（1.out） 

1073741823

用户输出 

1073741823

系统信息 

Exited with return code 0
测试点 #2
Accepted
得分：100
用时：1482 ms
内存：90832 KiB

输入文件（2.in） 

1000000 86236384
350498708 808400473 284199510 14704301 574209556 287105633 327293235 94423487 7493
<9870486 bytes omitted>

答案文件（2.out） 

1073741823

用户输出 

1073741823

系统信息 

Exited with return code 0
测试点 #3
Accepted
得分：100
用时：1393 ms
内存：90800 KiB

输入文件（3.in） 

1000000 922128163
385885953 393846823 173715420 585844237 360738524 165957383 415856942 188513946 9
<9871467 bytes omitted>

答案文件（3.out） 

1073741823

用户输出 

1073741823

系统信息 

Exited with return code 0
测试点 #4
Accepted
得分：100
用时：1380 ms
内存：90904 KiB

输入文件（4.in） 

1000000 113578511
916477166 926881547 475647681 905604044 510421690 80679891 94960504 416530430 477
<9870060 bytes omitted>

答案文件（4.out） 

1073741823

用户输出 

1073741823

系统信息 

Exited with return code 0
测试点 #5
Accepted
得分：100
用时：1392 ms
内存：90820 KiB

输入文件（5.in） 

1000000 76398244
625715379 285062382 637187384 739325816 361138858 588393542 976639411 143052554 44
<9869787 bytes omitted>

答案文件（5.out） 

1073741823

用户输出 

1073741823

系统信息 

Exited with return code 0
测试点 #6
Accepted
得分：100
用时：1419 ms
内存：90920 KiB

输入文件（6.in） 

1000000 294143082
336405353 500760197 944925150 26367846 644813402 510993161 638174985 462432722 43
<9870678 bytes omitted>

答案文件（6.out） 

1073741823

用户输出 

1073741823

系统信息 

Exited with return code 0
测试点 #7
Accepted
得分：100
用时：1400 ms
内存：90936 KiB

输入文件（7.in） 

1000000 34781211
619891013 871819236 950214877 888862820 307719879 100754911 207001801 406390656 45
<9870836 bytes omitted>

答案文件（7.out） 

1073741823

用户输出 

1073741823

系统信息 

Exited with return code 0
测试点 #8
Accepted
得分：100
用时：1338 ms
内存：90904 KiB

输入文件（8.in） 

1000000 303918171
325684236 66931348 53858313 944976169 966864747 38954035 897133207 493077895 2434
<9870331 bytes omitted>

答案文件（8.out） 

1073741823

用户输出 

1073741823

系统信息 

Exited with return code 0
测试点 #9
Accepted
得分：100
用时：1369 ms
内存：90784 KiB

输入文件（9.in） 

1000000 704477350
733301642 808601666 102169199 785795653 184393163 924553686 18435876 475009932 28
<9870245 bytes omitted>

答案文件（9.out） 

1073741823

用户输出 

1073741823

系统信息 

Exited with return code 0
测试点 #10
Accepted
得分：100
用时：1421 ms
内存：90816 KiB

输入文件（10.in） 

1000000 358982781
80595805 830593290 545275206 291053325 296446708 407625387 554864283 833244781 64
<9870846 bytes omitted>

答案文件（10.out） 

1073741823

用户输出 

1073741823

系统信息 

Exited with return code 0
测试点 #11
Accepted
得分：100
用时：5 ms
内存：272 KiB

输入文件（11.in） 

10 262098800
921594609 31134248 7051222 978758743 398073587 233105189 152791401 525371113 441280254
<13 bytes omitted>

答案文件（11.out） 

1020430926

用户输出 

1020430926

系统信息 

Exited with return code 0
测试点 #12
Accepted
得分：100
用时：5 ms
内存：272 KiB

输入文件（12.in） 

10 752796139
85475752 975961725 212689650 824694282 527303094 56811491 730435914 455929570 69354221
<14 bytes omitted>

答案文件（12.out） 

1067688661

用户输出 

1067688661

系统信息 

Exited with return code 0
测试点 #13
Accepted
得分：100
用时：5 ms
内存：276 KiB

输入文件（13.in） 

10 654965086
94865720 543611765 85771297 245620677 291468655 207817215 181496038 367955914 79212353
<14 bytes omitted>

答案文件（13.out） 

1065325201

用户输出 

1065325201

系统信息 

Exited with return code 0
测试点 #14
Accepted
得分：100
用时：5 ms
内存：300 KiB

输入文件（14.in） 

10 335672002
169700610 631863505 555006455 601425354 304579373 648101312 213090263 596288206 800037
<16 bytes omitted>

答案文件（14.out） 

1057498679

用户输出 

1057498679

系统信息 

Exited with return code 0
测试点 #15
Accepted
得分：100
用时：5 ms
内存：348 KiB

输入文件（15.in） 

10 65920103
216780020 215124292 641827611 460836412 696148229 789187105 407219834 315014442 3916893
<14 bytes omitted>

答案文件（15.out） 

1054576960

用户输出 

1054576960

系统信息 

Exited with return code 0
测试点 #16
Accepted
得分：100
用时：4 ms
内存：348 KiB

输入文件（16.in） 

10 35632686
304792490 61714102 35801576 762153290 365519359 16098781 249168072 146429955 16720886 4
<10 bytes omitted>

答案文件（16.out） 

1029242062

用户输出 

1029242062

系统信息 

Exited with return code 0
测试点 #17
Accepted
得分：100
用时：5 ms
内存：276 KiB

输入文件（17.in） 

10 678082167
731725156 511446962 373889498 705283026 986637211 741046446 721498079 451018134 343985
<16 bytes omitted>

答案文件（17.out） 

1049570626

用户输出 

1049570626

系统信息 

Exited with return code 0
测试点 #18
Accepted
得分：100
用时：5 ms
内存：348 KiB

输入文件（18.in） 

10 684150809
245536656 869646884 421252634 504804423 237411619 774876831 539237249 452838475 226125
<16 bytes omitted>

答案文件（18.out） 

1073349408

用户输出 

1073349408

系统信息 

Exited with return code 0
测试点 #19
Accepted
得分：100
用时：5 ms
内存：300 KiB

输入文件（19.in） 

10 124165946
645111037 399914653 104158929 302210581 328458635 690961564 693253648 427426687 757959
<16 bytes omitted>

答案文件（19.out） 

1037713965

用户输出 

1037713965

系统信息 

Exited with return code 0
测试点 #20
Accepted
得分：100
用时：6 ms
内存：300 KiB

输入文件（20.in） 

10 351694400
503845124 146260067 485705266 638505358 620358099 799060587 732790849 809743426 133838
<16 bytes omitted>

答案文件（20.out） 

1017965353

用户输出 

1017965353

系统信息 

Exited with return code 0
测试点 #21
Accepted
得分：100
用时：6 ms
内存：520 KiB

输入文件（21.in） 

1000 497234818
877827424 54406462 797737485 846479797 570147956 935697495 902403735 60243779 548622
<9778 bytes omitted>

答案文件（21.out） 

1073738249

用户输出 

1073738249

系统信息 

Exited with return code 0
测试点 #22
Accepted
得分：100
用时：7 ms
内存：528 KiB

输入文件（22.in） 

1000 400565298
516791234 426512967 232726012 251805071 392442206 94212279 140077328 396493908 25055
<9771 bytes omitted>

答案文件（22.out） 

1073739913

用户输出 

1073739913

系统信息 

Exited with return code 0
测试点 #23
Accepted
得分：100
用时：6 ms
内存：476 KiB

输入文件（23.in） 

1000 990675483
875667814 352448844 580710574 473836400 804058470 577694339 791677399 754945529 1714
<9796 bytes omitted>

答案文件（23.out） 

1073734173

用户输出 

1073734173

系统信息 

Exited with return code 0
测试点 #24
Accepted
得分：100
用时：6 ms
内存：532 KiB

输入文件（24.in） 

1000 163995040
552309002 654583773 832530162 964609024 586228955 783677305 924203476 116332663 4402
<9790 bytes omitted>

答案文件（24.out） 

1073739603

用户输出 

1073739603

系统信息 

Exited with return code 0
测试点 #25
Accepted
得分：100
用时：5 ms
内存：532 KiB

输入文件（25.in） 

1000 496168721
979342348 590807693 342212763 404958593 452992962 549253121 413473863 274109548 4431
<9813 bytes omitted>

答案文件（25.out） 

1073735004

用户输出 

1073735004

系统信息 

Exited with return code 0
测试点 #26
Accepted
得分：100
用时：6 ms
内存：528 KiB

输入文件（26.in） 

1000 146897931
328236701 730009358 290051683 922182370 447236384 520004157 970199992 337802792 6221
<9777 bytes omitted>

答案文件（26.out） 

1073741488

用户输出 

1073741488

系统信息 

Exited with return code 0
测试点 #27
Accepted
得分：100
用时：6 ms
内存：528 KiB

输入文件（27.in） 

1000 780645752
407902409 900511804 621704702 779195958 17584505 713177983 634416583 242310429 65533
<9804 bytes omitted>

答案文件（27.out） 

1073740780

用户输出 

1073740780

系统信息 

Exited with return code 0
测试点 #28
Accepted
得分：100
用时：6 ms
内存：528 KiB

输入文件（28.in） 

1000 940443132
427176817 778776609 78627537 692645306 480627982 851692165 811390040 52008616 875427
<9789 bytes omitted>

答案文件（28.out） 

1073741750

用户输出 

1073741750

系统信息 

Exited with return code 0
测试点 #29
Accepted
得分：100
用时：6 ms
内存：524 KiB

输入文件（29.in） 

1000 917996225
281788142 51049435 803888966 741533676 469563058 868944569 179147001 970110453 15628
<9798 bytes omitted>

答案文件（29.out） 

1073739878

用户输出 

1073739878

系统信息 

Exited with return code 0
测试点 #30
Accepted
得分：100
用时：5 ms
内存：528 KiB

输入文件（30.in） 

1000 760159905
355720361 411926150 837671832 622577708 276875862 405634754 3429905 371142842 118487
<9791 bytes omitted>

答案文件（30.out） 

1073740828

用户输出 

1073740828

系统信息 

Exited with return code 0
XJTUOJ Powered by SYZOJ.