1. Hello 2025

A. MEX Table（800）

（constructive algorithms）（math）

Ques

题意

One day, the schoolboy Mark misbehaved, so the teacher Sasha called him to the whiteboard.

Sasha gave Mark a table with rows and columns. His task is to arrange the numbers in the table (each number must be used exactly once) in such a way as to maximize the sum of MEX across all rows and columns. More formally, he needs to maximize

$\sum\limits_{i = 1}^{n} \operatorname{mex}(\{a_{i,1}, a_{i,2}, \ldots, a_{i,m}\}) + \sum\limits_{j = 1}^{m} \operatorname{mex}(\{a_{1,j}, a_{2,j}, \ldots, a_{n,j}\}),$

where is the number in the -th row and -th column.

Sasha is not interested in how Mark arranges the numbers, so he only asks him to state one number — the maximum sum of MEX across all rows and columns that can be achieved.

The minimum excluded (MEX) of a collection of integers is defined as the smallest non-negative integer which does not occur in the collection .

For example:

, since does not belong to the array.
, since and belong to the array, but does not.
, since , , , and belong to the array, but does not.

Input

Each test contains multiple test cases. The first line contains a single integer () — the number of test cases. The description of the test cases follows.

The first line of each test case contains two integers and () — the number of rows and columns in the table, respectively.

Output

For each test case, output the maximum possible sum of across all rows and columns.

Example

1
2
3

2
3
6

Note

In the first test case, the only element is , and the sum of the of the numbers in the first row and the of the numbers in the first column is .

In the second test case, the optimal table may look as follows:

Then $\sum\limits{i = 1}^{n} \operatorname{mex}({a{i,1}, a{i,2}, \ldots, a{i,m}}) + \sum\limits{j = 1}^{m} \operatorname{mex}({a{1,j}, a{2,j}, \ldots, a{n,j}}) = \operatorname{mex}({3, 0}) + \operatorname{mex}({2, 1})+ \operatorname{mex}({3, 2}) + \operatorname{mex}({0, 1}) = 1 + 0 + 0 + 2 = 3$.

Ans

画图模拟下，马上就能出

void solve(){
    int n,m; cin >> n >> m;
    cout << 1 + max(n,m) << '\n';
    return;
}

B. Gorilla and the Exam（1000）

（greedy）（sortings）

Ques

门钥匙

题意

Due to a shortage of teachers in the senior class of the “T-generation”, it was decided to have a huge male gorilla conduct exams for the students. However, it is not that simple; to prove his competence, he needs to solve the following problem.

For an array , we define the function as the smallest number of the following operations required to make the array empty:

take two integers and , such that , and let be the $\min(bl, b{l+1}, \ldots, b_r)$; then
remove all such that and from the array, the deleted elements are removed, the indices are renumerated.

You are given an array of length and an integer . No more than times, you can choose any index () and any integer , and replace with .

Help the gorilla to determine the smallest value of that can be achieved after such replacements.

Input

Each test contains multiple test cases. The first line contains a single integer () — the number of test cases. The description of the test cases follows.

The first line of each set of input data contains two integers and (, ) — the length of the array and the maximum number of changes, respectively.

The second line of each set of input data contains integers () — the array itself.

It is guaranteed that the sum of the values of across all sets of input data does not exceed .

Output

For each set of input data, output a single integer on a separate line — the smallest possible value of .

Example

6
1 0
48843
3 1
2 3 2
5 3
1 2 3 4 5
7 0
4 7 1 3 2 4 1
11 4
3 2 1 4 4 3 4 2 1 3 3
5 5
1 2 3 4 5

Note

In the first set of input data, , since the array consists of a single number, and thus it can be removed in one operation.

In the second set of input data, you can change the second number to , resulting in the array , where , since you can take the entire array as a subarray, the minimum on it is , so we will remove all the s from the array, and the array will become empty.

Ans

尽量不要想着排序map的key

void solve(){
    int n,k; cin >> n >> k;
    unordered_map<ll,int> mp;
    mp.reserve(2*n);
    while(n--){
        ll x; cin >> x;
        mp[x]++;
    }

    vector<int> freq;
    freq.reserve(mp.size());
    for(const auto& [x,y] : mp){
        freq.push_back(y);
    }
    sort(freq.begin(),freq.end());

    int res = mp.size();
    for(auto& c : freq){
        if(res == 1 || c > k) break;
        res--;
        k -= c;
    }
    cout << res << '\n';
    // for(int i = 0;i < (int)freq.size();++i){
    //     if(freq[i] <= k){
    //         res--;
    //         k -= freq[i];
    //     }else break;
    // }
    // cout << max(res,1) << '\n';
    return;
}

C. Trip to the Olympiad（1500）

（bitmasks）（constructive algorithms）（greedy）（math）

Ques

门钥匙

题意

In the upcoming year, there will be many team olympiads, so the teachers of “T-generation” need to assemble a team of three pupils to participate in them. Any three pupils will show a worthy result in any team olympiad. But winning the olympiad is only half the battle; first, you need to get there…

Each pupil has an independence level, expressed as an integer. In “T-generation”, there is exactly one student with each independence levels from to , inclusive. For a team of three pupils with independence levels , , and , the value of their team independence is equal to , where denotes the bitwise XOR operation.

Your task is to choose any trio of students with the maximum possible team independence.

Input

Each test contains multiple test cases. The first line contains a single integer () — the number of test cases. The description of the test cases follows.

The first line of each test case set contains two integers and (, ) — the minimum and maximum independence levels of the students.

Output

For each test case set, output three pairwise distinct integers , and , such that and the value of the expression is maximized. If there are multiple triples with the maximum value, any of them can be output.

Example

8
0 2
0 8
1 3
6 22
128 137
69 98
115 127
0 1073741823

1 2 0
8 7 1
2 1 3
7 16 11
134 132 137
98 85 76
123 121 118
965321865 375544086 12551794

Note

In the first test case, the only suitable triplet of numbers () (up to permutation) is ().

In the second test case, one of the suitable triplets is (), where . It can be shown that is the maximum possible value of for .

Ans

这道题的核心是看二进制最高不同位

对于第i位：

三个数这一位全相同（要么全是0 要么全是1），这一位贡献0
不是全相同，即三对异或里刚好有两对不同，贡献

也就是说只要三个数这一位不是全一样，这一位就拿满分

现在看 l 和 r，比方说 l = 6 = 00110，r = 22 = 10110

从最高位看，最高不同位是第4位。当然，比第4位更高的位，整个区间[l,r]里的数都是一样的，不可能贡献，所以我们最多只能让0 1 2 3 4位贡献，即让0…k这些位每一位都产生贡献，所以理论上最大值的上限应该是，即。

那怎么构造呢？

我们可以找到跨过最高不同位边界的两个连续数，比方说01111和10000，这两个数0…4位每一位都相反，那么接下来我们只需在这个区间随便取一个数

思路已经很明了了，那我们该怎么写呢？

有个特别好的代码int a = l | ((1<<k)-1);

这行代码的意思是把 l 的低 k 位全部变成 1，比方说 l = 6：

l = 00110
k = 4
(1 << k) - 1 = 01111

00110
01111
-----
01111 = 15

所以a = 15，b = a+1 = 16

而对于第三个数，如果 a 已经等于 l 了，第三个数不能再选 l 了，那就选r，反之选l

void solve(){
    int l,r; cin >> l >> r;

    int k = 31-__builtin_clz(l^r);
    int a = l | ((1 << k) - 1);
    int b = a+1;
    int c = (a == l ? r : l);
    cout << a << ' ' << b << ' ' << c << '\n';
    return;
}