It can be shown that after operations, exactly one element remains in the array. Your task is to determine the maximum possible value of this final remaining element if you perform the operations optimally.
structnode{ int ch[2]; node(){ ch[0] = ch[1] = -1;} };
建立节点数组
初始的trie[0]是根节点，后续再加新节点就emplace_back()，索引代表节点编号
1
vector<node> trie(1);
创建插入函数
把数字x插入Trie时，从最高位b=30到最低位b=0，先通过bit = (x >> b) & 1取第b位，如果当前节点没有这条边，就新建节点，同时，让p走到对应的儿子，继续下一位的操作
1 2 3 4 5 6 7 8 9 10 11
auto insert = [&](int x){ int p = 0; for(int b = 30;b >= 0;--b){ int bit = (x >> b)&1; if(trie[p].ch[bit] == -1){ trie[p].ch[bit] = (int)trie.size(); trie.emplace_back(); } p = trie[p].ch[bit]; } };
(根) └─0→ A ├─0→ B │ └─1→ C (路径 0-0-1，对应数字 1) └─1→ D └─0→ E (路径 0-1-0，对应数字 2)
query_max_xor(3=011) 从高位到低位走：
1. b=2，x这一位是 0，想走 1（反位） - 根没有 1 边，只能走 0 到 A - 这一位异或是 0，res 不变 2. b=1，x这一位是 1，想走 0（反位） - A 有 0 边，走到 B - 这一位异或是 1，res += 2^1 3. b=0，x这一位是 1，想走 0（反位） - B 没有 0 边，只能走 1 到 C - 这一位异或是 0
最终： - 走到的数是路径 001，也就是 y=1 - x ^ y = 3 ^ 1 = 2 - res=2
1 2 3 4 5 6 7 8 9 10 11 12 13 14
auto query = [&](int x){ int p = 0,res = 0; for(int b = 30;b >= 0;--b){ int bit = (x>>b)&1; int want = bit^1; if(trie[p].ch[want] != -1){ res |= (1<<b); p = trie[p].ch[want]; }else{ p = trie[p].ch[bit]; } } return res; };
voidsolve(){ int n; cin >> n; vector<int> a(n); for(int i = 0;i < n;++i) cin >> a[i];
vector<node> trie(1); auto insert = [&](int x){ int p = 0; for(int b = 30;b >= 0;--b){ int bit = (x >> b) & 1; if(trie[p].ch[bit] == -1){ trie[p].ch[bit] = (int)trie.size(); trie.emplace_back(); } p = trie[p].ch[bit]; } };
auto query = [&](int x){ int p = 0,res = 0; for(int b = 30;b >= 0;--b){ int bit = (x >> b) & 1; int want = bit ^ 1; if(trie[p].ch[want] != -1){ res |= (1 << b); p = trie[p].ch[want]; }else{ p = trie[p].ch[bit]; } } return res; }; int res = 0; insert(a[0]); for(int i = 1;i < n;++i){ res = max(res,query(a[i])); insert(a[i]); } cout << res << '\n'; return; }
Given an array , let be the number of ways to partition into one or more subarrays such that:
Each element appears in exactly one subarray.
All subarrays have the same sum.
For example, if , then , because there are two such ways to partition :
, where the only subarray has sum .
, where both subarrays have sum .
You are given two integers and . Find the minimum value of over all arrays of length , consisting of copies of the number , and copies of the number in some order. Since this answer may be large, output the answer modulo . Additionally, you should construct one array that achieves this minimal value.
An array is a subarray of an array if can be obtained from by the deletion of several (possibly, zero or all) elements from the beginning and several (possibly, zero or all) elements from the end.
Input
Each test contains multiple test cases. The first line contains the number of test cases (). The description of the test cases follows.
The first line of each test case contains two integers and (). It is guaranteed that .
It is guaranteed that the sum of over all test cases does not exceed , and the sum of over all test cases does not exceed .
Output
For each test case, output two lines: the minimum value of over all valid arrays modulo , and an example of an array that achieves the minimal result. Note you are minimizing , and taking that minimum value modulo , not finding the minimal possible result of mod .
In the first test case, and . The only possible array is , with as explained above.
In the second case, and . One possible array that minimizes is , where (as the only way to partition into subarrays with all subarrays having equal sum is ).
You are given a binary string of length . You can perform the following operation on the string:
Choose an index , and flip the bit present at all other indices except for the index . In other words, choose an integer (), and for all such that and , if , then set , otherwise set .
You can perform the operation any number of times, but each index can be chosen by at most one operation.
Your task is to make all bits present in the string equal , or report that it is impossible to do so. You don’t have to minimize the number of operations.
Input
Each test contains multiple test cases. The first line contains the number of test cases (). The description of the test cases follows.
The first line of each test case contains a single integer ().
The second line of each test case contains the binary string of length .
It is guaranteed that the sum of over all test cases does not exceed .
Output
For each test case, output if it is impossible to transform all bits to . Otherwise, output two lines in the following format:
In the first line, print the number of operations ().
In the second line of each test case, print numbers – the indices you select in each operation in order. You should guarantee that each index is chosen at most once.
If there are multiple possible solutions, you may output any.
Example
1 2 3 4 5 6 7 8 9
4 3 101 3 100 4 0000 4 1010
1 2 3 4 5 6
1 2 -1 0 2 1 3
Note
In the first test case, performing the operation on index means flipping bits present at index and . So the new string formed will be .
In the second test case, it can be shown that we cannot make string equal to using the described operations.
You are given an integer array consisting of elements. Denote $f(l, r) = \operatorname{MEX}([al, a{l + 1}, \ldots, a_r])$$^{\text{∗}}$.
Determine if there is a way to reorder the array such that for every (), . In other words, for every split point , the of the prefix must be different from the of the suffix.
The minimum excluded (MEX) of a collection of integers is defined as the smallest non-negative integer which does not occur in the collection .
Input
Each test contains multiple test cases. The first line contains the number of test cases (). The description of the test cases follows.
The first line of each test case contains a single integer () — the length of the array.
The second line of each test case contains integers ().
Output
Output “YES” if you can reorder so that the condition from the statement is satisfied, and “NO” otherwise. You can output the answer in any case (upper or lower). For example, the strings “yEs”, “yes”, “Yes”, and “YES” will be recognized as positive responses.
Example
1 2 3 4 5 6 7
3 2 1 0 3 0 3 0 6 1 0 5 0 6 1
1 2 3
YES NO YES
Note
In the first example, the initial ordering of already satisfies the condition. The only choice for is . Then , and . Since , the condition is satisfied.
In the second example, it can be shown that there is no way to reorder to satisfy the condition. As an example, consider the order and . We have , and , hence , so the choice of reordering is invalid.
In the third example, we can reorder into . When , , , so the condition is satisfied for this . It can be verified that the condition is also satisfied for all other .
Alice and Bob play a game on a binary string of length (a string consisting only of characters and ). Alice moves first, and the players take alternate turns.
In one turn, a player chooses a sequence of indices $i1, i_2, \ldots, i_m1 \le i_1 \lt i_2 \lt \ldots \lt i_m \le n$) such that the characters at these positions form a non-increasing sequence (that is, $s{i1} \ge s{i2} \ge \ldots \ge s{i_m}$). The player then rearranges the characters at these positions to be sorted in non-decreasing order.
Formally, let the chosen characters consist of zeros and ones (where ). The move replaces the characters at positions with a sequence of zeros followed by ones. A move is valid if and only if it strictly modifies the string (which implies and ).
The player who cannot make a valid move loses.
Assuming both players play optimally, determine the winner. If Alice wins, output a valid first move that is part of a winning strategy.
Input
Each test contains multiple test cases. The first line contains the number of test cases (). The description of the test cases follows.
The first line of each test case consists of a single integer () — the length of the string .
The second line of each test case contains a binary string of length consisting of only characters and .
It is guaranteed that the sum of over all test cases does not exceed .
Output
For each test case, output one or three lines:
If Bob wins with optimal play, print a single line containing “Bob”.
Otherwise, print three lines. On the first line print “Alice”. On the second line print an integer (), and on the third line print distinct integers () — the indices chosen for Alice’s first move.
The sequence of indices you print must form a valid move according to the rules described in the statement. The indices must be printed in increasing order. If there are multiple winning moves, you may output any of them.
Example
1 2 3 4 5 6 7
3 3 000 2 10 3 101
1 2 3 4 5 6 7
Bob Alice 2 1 2 Alice 2 1 2
Note
In the first example, there is no way to make a move after which will change, so Bob wins immediately.
In the third example, Alice can choose a subsequence and sort it, after which will turn into . After that, Bob can’t make a move, so Alice wins.
Ans
设 t 是 s 排序后得到的结果，如果在游戏一开始就存在 s = t，那么答案就是bob，反之就是alice。
On an infinite number line, at point , sits a frog. After many years of meditation, the frog has mastered unique types of magical jumps. The -th type of jump allows it to jump forward by no more than units. In other words, if it was at integer point , after the jump it can land at any integer point from to .
But magic always comes with a price; it has been cursed. Before each -th attempt (before -th, -th, -th etc. attempt among the jumps of type ) to use the -th type of jump, the frog rolls back units! In other words, if it was at point , it will first find itself at point , and after the jump, it can land at any integer point from to .
The frog’s goal is to reach the point with the number , using jumps while minimizing the number of rollbacks. Help the frog — find the minimum number of rollbacks it will have to endure on its way to the goal, or determine that it cannot reach point .
Input
Each test contains multiple test cases. The first line contains the number of test cases (). The description of the test cases follows.
In the first line of each test case, there are integers and (, ) — the number of types of jumps the frog can make and its final target.
In the following lines, the description of the jump types is provided; the -th line contains integers , , and ().
It is guaranteed that the sum of across all test cases does not exceed .
Output
For each test case, if the frog can reach point , find the smallest number of rollbacks it must endure to do so. If it cannot reach point , output .
In the first test case, the frog can jump forward by unit and will end up at point . Thus, the answer is .
In the third test case, it can be shown that the frog cannot reach point .
In the fourth test case, the frog can reach point , for example, as follows: jump using the -st type by , jump using the -th type by , and jump using the -nd type by . Then it will sequentially be at the following points .
In the sixth test case, the frog can reach point , for example, as follows: jump times by and time by . Then it will sequentially be at the following points .
You are given an array of length , and an integer . Let be the value of $\operatorname{mex}(al,a{l+1},\ldots,a_r)$$^{\text{∗}}n-k+1$ times:
Let the current length of the sequence be . You need to find an interval of length such that $\operatorname{max}{i=1}^{|a|-k+1} f(i, i+k-1) = f(l, r).kk\operatorname{mex}[l,r]il \leq i \leq ra_ia[a_1, a_2, \ldots, a{i-1}, a{i+1}, a{i+2}, \ldots, a_n]$.
For example, in the array with , the two possible pairs are and (since they each have , which is the maximum among all windows of size ). Therefore, you can remove any one of the indices in your next move.
After operations, you will have a sequence of length . Your objective is to maximize the of the remaining elements. Please output the maximum possible.
The minimum excluded (MEX) of a collection of integers is defined as the smallest non-negative integer which does not occur in the collection .
Input
Each test contains multiple test cases. The first line contains the number of test cases (). The description of the test cases follows.
The first line of each test case contains two positive integers and ().
The second line of each test case contains integers ().
It is guaranteed that the sum of over all test cases does not exceed .
Output
Output a single non-negative integer representing your answer.
Penguins are civilized creatures that communicate using permutations. Blackslex, as a penguin researcher, must study their means of communication.
For a given integer , consider permutations of the array . Define
where is the number of -bits in the binary representation of (for instance, because has two -bits in the binary representation), and denotes the bitwise AND operation. .
A permutation is considered sacred if it maximizes . Find the lexicographically minimal sacred permutation.
A permutation of length is an array consisting of distinct integers from to in arbitrary order. For example, is a permutation, but is not a permutation ( appears twice in the array), and is also not a permutation ( but there is in the array).
An array is lexicographically smaller than an array of the same size if and only if the following holds:
in the first position where and differ, the array has a smaller element than the corresponding element in .
Input
The first line contains a single integer () — the number of test cases.
Each test case contains a single integer ().
It is guaranteed that the sum of over all test cases does not exceed .
Output
For each test case, output integers $p0, p_1, \ldots, p{2^n-1}$ — the required permutation.
Example
1 2 3
2 1 2
1 2
1 0 3 1 0 2
Note
For the first test case, there are two possible permutations.
,
,
For the second test case, is sacred. There are other permutations that are sacred, such as , but those are not lexicographically minimal.
After performing a sequence of operations, you want the value of to become exactly .
Find a sequence of at most operations (values of used in each operation) that transforms into , or report that it is impossible.
Note that you are not required to find the minimum number of operations, but any valid sequence of at most operations.
Input
The first line of input contains a single integer () — the number of test cases.
Each test case contains two integers and ().
Output
For each test case, if it is impossible to obtain from using the allowed operations, print a single line containing .
Otherwise, on the first line print a single integer () — the number of operations. On the second line print integers () — the chosen values of in the order you apply them.
If there are multiple valid sequences, you may print any one of them.
微信