题解:Codeforce Goodbay 2019 A~D
KONGJUNE / / ACM / 阅读量

为什么只有 A ~ D?因为后面的我不会。QAQ

慢慢啃,啃完再加。QAQ

比赛传送门:🚪

A - Card Game

这道题题目太长了(迷惑),不往上贴了。

大意就是两个人打牌,每局两人都出一张牌,谁大谁赢,赢者可直接得到本局出出来的两个牌。最终谁没牌了谁输。

所以,拥有最大牌面的玩家一定会赢……

完全水题就不上代码了。

B - Intersting Subarray

For an array $a$ of integers let's denote its maximal element as $\max(a)$, and minimal as $\min(a)$. We will call an array $a$ of $k$ integers interesting if $\max(a)−\min(a)\geq k$. For example, array $[1,3,4,3]$ isn't interesting as $\max(a)−\min(a)=4−1=3<4$ while array $[7,3,0,4,3]$ is as $\max(a)−\min(a)=7−0=7\geq 5$.

You are given an array $a$ of $n$ integers. Find some interesting nonempty subarray of $a$

, or tell that it doesn't exist.

An array $b$ is a subarray of an array $a$ if $b$ can be obtained from $a$ by deletion of several (possibly, zero or all) elements from the beginning and several (possibly, zero or all) elements from the end. In particular, an array is a subarray of itself.

Input

The first line contains integer number $t$ $(1\leq t\leq 10000)$. Then $t$ test cases follow.

The first line of each test case contains a single integer $n$ $(2≤n≤2⋅10^5)$ — the length of the array.

The second line of each test case contains $n$ integers $a_1,a_2,\dots ,a_n (0≤a_i≤10^9)$ — the elements of the array.

It is guaranteed that the sum of $n$ over all test cases does not exceed $2⋅10^5$.

Output

For each test case, output "NO" in a separate line if there is no interesting nonempty subarray in $a$.

Otherwise, output "YES" in a separate line. In the next line, output two integers $l$ and $r$ $(1≤l≤r≤n)$ — bounds of the chosen subarray. If there are multiple answers, print any.

You can print each letter in any case (upper or lower).

Example

Input

3
5
1 2 3 4 5
4
2 0 1 9
2
2019 2020

Output

NO
YES
1 4
NO

Note

In the second test case of the example, one of the interesting subarrays is $a=[2,0,1,9]$: $\max(a)−\min(a)=9−0=9≥4$.

当有子序列使得 $\max(a)−\min(a)\geq k$ 存在时,必定有 $\max(a)−\min(a)\geq |\mathrm{index}_{\max(a) -} \mathrm{index}_{\min(a)}|$ 。我们可以将每一个元素看作一个坐标,横坐标为当前数的序号,纵坐标为当前数的值。从斜率的角度来考虑数列的增长,当有 $\max(a)−\min(a)\geq |\mathrm{index}_{\max(a) -} \mathrm{index}_{\min(a)}|$ 成立,必然有整个图像每一小段的斜率都 $< 1$。所以只需要以 $O(n)$ 刷一遍数组,看相邻元素的差值绝对值是否大于 $1$ 即可。

AC代码:

#include <iostream>
using namespace std;
int a[200005];
int main(){
    ios::sync_with_stdio(false);
    int T;
    cin >> T;
    while(T--) {
        int n;
        cin >> n;
        int l, r;
        bool yes = 0;
        for (int i = 0; i < n; i++) {
            cin >> a[i];
            if (i && abs(a[i] - a[i - 1]) > 1) {
                l = i;
                r = i + 1;
                yes = 1;
            }
        }
        if (yes) {
            cout << "YES" << endl << l << " " << r << endl;
        } else cout << "NO" << endl;
        
    }
}

C - Make Good

Let's call an array $a_1,a_2,…,a_m$ of nonnegative integer numbers good if $a_1+a_2+⋯+a_m=2⋅(a_1⊕a_2⊕⋯⊕a_m)$, where $⊕$ denotes the bitwise XOR operation.

For example, array $[1,2,3,6]$ is good, as $1+2+3+6=12=2⋅6=2⋅(1⊕2⊕3⊕6)$. At the same time, array $[1,2,1,3]$ isn't good, as $1+2+1+3=7≠2⋅1=2⋅(1⊕2⊕1⊕3)$.

You are given an array of length $n$ : $a_1,a_2,…,a_n$. Append at most 3 elements to it to make it good. Appended elements don't have to be different. It can be shown that the solution always exists under the given constraints. If there are different solutions, you are allowed to output any of them. Note that you don't have to minimize the number of added elements! So, if an array is good already you are allowed to not append elements.

Input

Each test contains multiple test cases. The first line contains the number of test cases $t$
$(1≤t≤10000)$. The description of the test cases follows.

The first line of each test case contains a single integer $n(1≤n≤105)$ — the size of the array.

The second line of each test case contains $n$ integers $a_1,a_2,…,a_n (0≤a_i≤109)$ — 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 two lines.

In the first line, output a single integer $s$ $(0≤s≤3)$ — the number of elements you want to append.

In the second line, output $s$ integers $b_1,…,b_s (0≤b_i≤1018)$ — the elements you want to append to the array.

If there are different solutions, you are allowed to output any of them.

Example

Input

3
4
1 2 3 6
1
8
2
1 1

Output

0

2
4 4
3
2 6 2

Note

In the first test case of the example, the sum of all numbers is $12$, and their $⊕$ is $6$ , so the condition is already satisfied.

In the second test case of the example, after adding $4$, $4$, the array becomes $[8,4,4]$. The sum of numbers in it is $16$, $⊕$ of numbers in it is $8$.

这道题告诉我,不要过于受样例影响。看到样例后我就认为是根据数列的和与异或和的关系来判断情况,就是两个相同数只用来增加和而不改变异或和,另外一个数来改变异或和。我好天真,按照这种想法还推了半天……

其实完成这个问题最多加两个数字就可以了。我们设数列的和为 $\mathrm{sum}$,异或和为 $\mathrm{xorSum}$。首先我们加入一个数让右侧的值变为零,显然这个数会是 $\mathrm{xorSum}$,及 $x = \mathrm{xorSum}$。再加上 $y$,我们希望以下式子成立:
$$
x + y + \mathrm{sum} = 2 \cdot (x⊕y⊕\mathrm{xorSum})
$$
解得 $y = x + \mathrm{sum} =\mathrm{xorSum} + \mathrm{sum}$。所以只需要输出这两个数就可以了。

AC代码:

#include <iostream>
using namespace std;
int a[200005];
int main(){
    ios::sync_with_stdio(false);
    int T;
    cin >> T;
    while(T--) {
        long long sum = 0;
        long long xorV = 0;
        int n;
        cin >> n;
        for (int i = 0; i < n; i++){
            cin >> a[i];
            sum += a[i];
            xorV ^= a[i];
        }
        long long x, y;
        if(sum == 2 * xorV){
            cout << 0 << endl << endl;
        } else  {
            x = xorV;
            y = xorV + sum;
            if (x){
                cout << 2 << endl << x << " " << y << endl;
            } else cout << 1 << endl << y << endl;
        }
    }
}

D - Strange Device

题目太长就不粘了。这是一个交互题目,大意是指:

一个机器,内有一个数组和两个固定的值$k$、$m$。憨憨运货丢掉了机器的说明书,所以只知道 $k$ 不知道 $m$。

为了知道 $m$,你可以问他最多 $n$ 个问题。你随意地抽取 $k$ 个数字,然后机器会告诉你数组中序号为这 $k$ 个数字地 $k$ 个值升序排序下第 $m$ 个数在原数组中的下标与具体值(这句话有点绕)。提问按照$? \ x_1\ x_2\ x_3\ \dots\ x_k$ 的格式提问,回答会按照 $pos\ value$ (其中 $pos$ 指在原数组中的下标)的方式回答。当你确定了 $m$ 的指的时候就直接输出 $!\ m$。有关系 $1\leq m\leq k \leq n \leq 500$ 成立。

仔细研究,就可以发现在提问输入的过程中,这 $k$ 个值中的每一位只会有两种可能的值,其中$m$对应的位置的一个值出现的次数对应着正确的 $m$ 值。所以只需要统计返回值中较大者出现的次数就可以了。(为什么是较大值?找规律可以发现,这两个值中,较大值出现的次数对应着 $m$ 的正确值。如 $m$ 等于 $1$ 时,出现的大多都是较小值而最大值只出现 $1$ 次。)

AC代码:

#include <iostream>
using namespace std;
int main(){
    int n, k;
    cin >> n >> k;
    int m = k;
    for (int i = 1; i <= k; i++) {
        a[i] = i + 1;
    }
    int maxV = 0;
    int cnt = 0;
    fflush(stdout);
    for (int i = 1; i <= k + 1; i++) {
        cout << "?";
        for (int i = 1; i <= k; i++) {
            cout << " " << a[i];
        }
        cout << endl;
        int n, v;
        cin >> n >> v;
        if (v > maxV) {
            maxV = v;
            cnt = 1;
        } else if (v == maxV) {
            cnt++;
        }
        a[i] = i;
    }
    cout << "! " << cnt << endl;
}
支付宝捐赠
请使用支付宝扫一扫进行捐赠
微信捐赠
请使用微信扫一扫进行赞赏
有 0 篇文章