acwing::acwing143 命名空间参考

1. 最大异或对

更多...

类
struct	TrieNode

函数
int	main (istream &cin, ostream &cout)
	TEST (acwing143, case1)

详细描述

1. 最大异或对

函数说明

main()

int acwing::acwing143::main	(	istream &	cin,
		ostream &	cout )

在文件 acwing.cpp 第 6958 行定义.

                                              {
            int n;
            cin >> n;
            vector<string> vec(n);
            TrieNode tn;
            for(int j = 0; j < n; j++) {
                unsigned a;
                cin >> a;
                ostringstream oss;
                for(int i = 30; i >= 0; i--) {
                    oss << ((a & 1 << i) != 0U ? '1' : '0');
                }
                string str = oss.str();
                vec[j]     = str;
                tn.insert(str, 0);
            }
            unsigned maximum = 0;
            for(const auto &str: vec) {
                const TrieNode *current = &tn;
                unsigned ans            = 0;
                for(int i = 0; i <= 30; i++) {
                    ans <<= 1;
                    if(current->next[str[i] - '0' == 0] != nullptr) {
                        current = current->next[str[i] - '0' == 0];
                        ans += 1;
                    } else {
                        current = current->next[str[i] - '0'];
                    }
                }
                maximum = max(maximum, ans);
            }
            cout << maximum;
            return 0;
        }

引用了 acwing::acwing143::TrieNode::insert() , 以及 acwing::acwing143::TrieNode::next.

被这些函数引用 TEST().

TEST()

acwing::acwing143::TEST	(	acwing143	,
		case1	)

在文件 acwing_test.cpp 第 3263 行定义.

                               {
            istringstream in("3\n"
                             "1 2 3");
            auto out = ostringstream();
            main(in, out);
            const auto ans = out.str();
            ASSERT_EQ("3", ans);
        }

引用了 main().