diss_quack and Array GameAI (CI翻译)
You are given an array $a$ of $n$ integers. Alice and Bob will play a game with this array.
Before the game with Bob starts, Alice can increment any element of the array any number of times, each increment taking one move. One increment consists of a single addition by $1$ to one index.
After that, the game starts and Bob and Alice take turns, with Bob making the first move. On Bob's turn, he can choose any two indices $i$ and $j$ and swap the array elements at these indices (note that Bob may choose $i = j$, in which case the array remains unchanged after the swap).
On Alice's turn, if $a_1$ is even, she finds the largest $j \leq |a|$ such that $a_i$ is even for all $i \leq j,$ then sets $a_i := a_i/2$ for $i \leq j.$ Otherwise she sets $a_1 := a_1 - 1.$ If any element becomes zero, it automatically gets erased from the array (and the other elements are re-indexed accordingly).
The game ends when the array is empty.
Alice wants to minimize the number of moves she makes, while Bob wants to maximize the number of moves Alice makes. Note that the number of moves is the sum of the number of initial additions and the number of turns Alice plays after.
How many moves will Alice make with optimal play?
Input
Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 10^4$). The description of the test cases follows.
The first line of each test case contains a single integer $n \, (1 \le n \le 10^5)$ — the length of the array.
The second line of each test case contains $n$ integers $a_1, a_2, \ldots, a_{n}\,(1 \le a_i \le 10^5)$ — the elements of the array.
It is guaranteed that the sum of $n$ over all test cases does not exceed $10^5$.
Output
For each test case, output a single integer — the number of moves Alice will make if both players play optimally.
Note
In the first case, Alice chooses not to add to any element initially. On the first move, Bob chooses $i = j = 1$ (not swapping any elements). Then Alice subtracts $1$ from $a_1,$ making the array $[2,3]$. Next, Bob again chooses $i = j = 1.$ Alice divides $a_1$ by $2$, and the array becomes $[1,3]$. Bob again chooses $i = j = 1.$ Alice subtracts from $a_1,$ and the array becomes $[3]$. Bob must now choose $i = j = 1,$ and Alice takes $3$ more moves to make the array empty. In total, Alice takes $6$ moves. It can be shown that this is the result of optimal play.
In the second test case, Alice again chooses not to add to any element initially. It can be shown that with optimal play, Alice takes $5$ moves.
{"titleZh":"diss_quack 与数组游戏","bodyZh":"给定一个包含 $n$ 个整数的数组 $a$。Alice 和 Bob 将使用这个数组进行游戏。\n\n在与 Bob 的游戏开始前，Alice 可以对数组中的任意元素进行任意次加一操作，每次加一操作需要进行一次移动。一次加一操作是指将某个下标处的元素加 $1$。\n\n随后游戏开始，Bob 和 Alice 轮流行动，Bob 先手。在 Bob 的回合中，他可以选择任意两个下标 $i$ 和 $j$，交换这两个下标处的数组元素（注意，Bob 可以选择 $i = j$，此时交换后数组不变）。\n\n在 Alice 的回合中，如果 $a_1$ 是偶数，她会找到满足对于所有 $i \leq j$，$a_i$ 都是偶数的最大 $j \leq |a|$，然后令 $i \leq j$ 的所有 $a_i := a_i/2$。否则，她会令 $a_1 := a_1 - 1$。如果某个元素变为零，它会自动从数组中删除（数组中的其他元素会相应地重新编号）。\n\n当数组为空时，游戏结束。\n\nAlice 希望使自己进行的移动次数最少，而 Bob 希望使 Alice 进行的移动次数最多。注意，移动次数等于初始加一操作的次数与之后 Alice 进行回合的次数之和。\n\n在双方都采取最优策略的情况下，Alice 将进行多少次移动？\n\n## 输入格式\n\n每个测试包含多个测试用例。第一行包含测试用例的数量 $t$（$1 \\leq t \\leq 10^4$）。接下来描述各个测试用例。\n\n每个测试用例的第一行包含一个整数 $n$（$1 \\leq n \\leq 10^5$），表示数组的长度。\n\n每个测试用例的第二行包含 $n$ 个整数 $a_1, a_2, \\ldots, a_{n}\\,(1 \\leq a_i \\leq 10^5)$，表示数组中的元素。\n\n保证所有测试用例的 $n$ 之和不超过 $10^5$。\n\n## 输出格式\n\n对于每个测试用例，输出一个整数——在双方都采取最优策略的情况下，Alice 将进行的移动次数。\n\n## 说明\n\n在第一个测试用例中，Alice 选择一开始不对任何元素进行加一操作。第一步，Bob 选择 $i = j = 1$（不交换任何元素）。随后 Alice 将 $a_1$ 减 $1$，数组变为 $[2,3]$。接下来，Bob 再次选择 $i = j = 1$。Alice 将 $a_1$ 除以 $2$，数组变为 $[1,3]$。Bob 再次选择 $i = j = 1$。Alice 将 $a_1$ 减 $1$，数组变为 $[3]$。此时 Bob 只能选择 $i = j = 1$，而 Alice 还需要进行 $3$ 次移动才能使数组为空。总计 Alice 进行 $6$ 次移动。可以证明，在最优策略下结果就是如此。\n\n在第二个测试用例中，Alice 同样选择一开始不对任何元素进行加一操作。可以证明，在最优策略下，Alice 进行 $5$ 次移动。"}AI (CI翻译)
样例
4
3
1 2 3
4
2 2 2 2
5
6 8 2 4 1
8
1 3 5 7 9 11 13 15
6
5
12
35
题面与样例版权归 Codeforces 及出题人所有；中文翻译由 AI 生成（gpt-6.1-sol），如有出入请以原文为准。