Codeforces Round 803 (Div. 2)

A. XOR Mixup

题目:

Limit:

time limit per test: 1 second
memory limit per test: 256 megabytes

Describe:

There is an array $a$ with $n-1$ integers. Let $x$ be the bitwise XOR of all elements of the array. The number $x$ is added to the end of the array $a$ (now it has length $n$), and then the elements are shuffled.
You are given the newly formed array $a$. What is $x$? If there are multiple possible values of $x$, you can output any of them.

Input:

The input consists of multiple test cases. The first line contains an integer $t$ ($1 \leq t \leq 1000$) — the number of test cases. The description of the test cases follows.
The first line of each test case contains an integer $n$ ($2 \leq n \leq 100$) — the number of integers in the resulting array $a$.
The second line of each test case contains $n$ integers $a_1, a_2, \ldots, a_n$ ($0 \le a_i \le 127$) — the elements of the newly formed array $a$.
Additional constraint on the input: the array $a$ is made by the process described in the statement; that is, some value of $x$ exists.

output:

Input-describe:

Output-describe:

For each test case, output a single integer — the value of $x$, as described in the statement. If there are multiple possible values of $x$, output any of them.

Example:

Input:

444 3 2 556 1 10 7 1066 6 6 6 6 63100 100 0

Output:

3
7
6
0

思路

简单暴力

代码

#include<bits/stdc++.h>
using namespace std;

void solve(){
    int n;
    cin >> n;
    vector<int> a(n);
    for(auto &x: a){
        cin >> x;
    }

    int ans;
    for(int i = 0; i < n; i++){
        int x = a[i];
        int sum = 0;
        for(int j = 0; j < n; j++){
            if(i != j){
                sum ^= a[j];
            }
        }
        if(sum == x){
            cout << x << "\n";
            return;
        }
    }
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int t;
    cin >> t;
    while(t--){
        solve();
    }

    return 0;
}

B. Rising Sand

题目:

Limit:

time limit per test: 1 second
memory limit per test: 256 megabytes

Describe:

There are $n$ piles of sand where the $i$-th pile has $a_i$ blocks of sand. The $i$-th pile is called too tall if $1 < i < n$ and $a_i > a_{i-1} + a_{i+1}$. That is, a pile is too tall if it has more sand than its two neighbours combined. (Note that piles on the ends of the array cannot be too tall.)
You are given an integer $k$. An operation consists of picking $k$ consecutive piles of sand and adding one unit of sand to them all. Formally, pick $1 \leq l,r \leq n$ such that $r-l+1=k$. Then for all $l \leq i \leq r$, update $a_i \gets a_i+1$.
What is the maximum number of piles that can simultaneously be too tall after some (possibly zero) operations?

Input:

The input consists of multiple test cases. The first line contains an integer $t$ ($1 \leq t \leq 1000$) — the number of test cases. The description of the test cases follows.
The first line of each test case contains two integers $n$ and $k$ ($3 \leq n \leq 2 \cdot 10^5$; $1 \leq k \leq n$) — the number of piles of sand and the size of the operation, respectively.
The second line of each test case contains $n$ integers $a_1, a_2, \ldots, a_n$ ($1 \le a_i \le 10^9$) — the sizes of the piles.
It is guaranteed that the sum of $n$ over all test cases does not exceed $2 \cdot 10^5$.

output:

The input consists of multiple test cases. The first line contains an integer $t$ ($1 \leq t \leq 1000$) — the number of test cases. The description of the test cases follows.
The first line of each test case contains two integers $n$ and $k$ ($3 \leq n \leq 2 \cdot 10^5$; $1 \leq k \leq n$) — the number of piles of sand and the size of the operation, respectively.
The second line of each test case contains $n$ integers $a_1, a_2, \ldots, a_n$ ($1 \le a_i \le 10^9$) — the sizes of the piles.
It is guaranteed that the sum of $n$ over all test cases does not exceed $2 \cdot 10^5$.

Input-describe:

The input consists of multiple test cases. The first line contains an integer $t$ ($1 \leq t \leq 1000$) — the number of test cases. The description of the test cases follows.
The first line of each test case contains two integers $n$ and $k$ ($3 \leq n \leq 2 \cdot 10^5$; $1 \leq k \leq n$) — the number of piles of sand and the size of the operation, respectively.
The second line of each test case contains $n$ integers $a_1, a_2, \ldots, a_n$ ($1 \le a_i \le 10^9$) — the sizes of the piles.
It is guaranteed that the sum of $n$ over all test cases does not exceed $2 \cdot 10^5$.

Output-describe:

For each test case, output a single integer — the maximum number of piles that are simultaneously too tall after some (possibly zero) operations.

Example:

Input:

35 22 9 2 4 14 41 3 2 13 11 3 1

Output:

2
0
1

思路

可以知道性质：

当k = 1时，可以得到最优情况，ans = (n - 1) // 2
当k > 1时，每次操作会连带邻居一起增大，所以对于答案不会有任何改变，ans = 为操作时的答案

代码

#include<bits/stdc++.h>
using namespace std;

void solve(){
    int n, k;
    cin >> n >> k;
    vector<int> a(n);
    for(auto &x: a){
        cin >> x;
    }

    if(k == 1){
        cout << (n - 1) / 2 << "\n";
    }
    else{
        int ans = 0;
        for(int i = 1; i < n - 1; i++){
            if (a[i] > a[i - 1] + a[i + 1]){
                ans++;
            }
        }
        cout << ans << "\n";
    }
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int t;
    cin >> t;
    while(t--){
        solve();
    }

    return 0;
}

C. 3SUM Closure

题目:

Limit:

time limit per test: 1 second
memory limit per test: 256 megabytes

Describe:

You are given an array $a$ of length $n$. The array is called 3SUM-closed if for all distinct indices $i$, $j$, $k$, the sum $a_i + a_j + a_k$ is an element of the array. More formally, $a$ is 3SUM-closed if for all integers $1 \leq i < j < k \leq n$, there exists some integer $1 \leq l \leq n$ such that $a_i + a_j + a_k = a_l$.
Determine if $a$ is 3SUM-closed.

Input:

The first line contains an integer $t$ ($1 \leq t \leq 1000$) — the number of test cases.
The first line of each test case contains an integer $n$ ($3 \leq n \leq 2 \cdot 10^5$) — the length of the array.
The second line of each test case contains $n$ integers $a_1, a_2, \dots, a_n$ ($-10^9 \leq a_i \leq 10^9$) — the elements of the array.
It is guaranteed that the sum of $n$ across all test cases does not exceed $2 \cdot 10^5$.

output:

Input-describe:

Output-describe:

For each test case, output “YES” (without quotes) if $a$ is 3SUM-closed and “NO” (without quotes) otherwise.
You can output “YES” and “NO” in any case (for example, strings “yEs”, “yes” and “Yes” will be recognized as a positive response).

Example:

Input:

43-1 0 151 -2 -2 1 -360 0 0 0 0 04-1 2 -3 4

Output:

YES
NO
YES
NO

思路

三重循环的朴素做法会炸时间，没找到好的优化方法，所以选择换一种思路

对于n <= 6的情况，直接暴力三重循环判断是否符合条件
对于6 < n 的情况，可以知道，如果最大的三个数都是正数，那么相加起来会是一个更大的正数，所以最大的三个数的符号为 (-, 未知, +)，其中， -/+ 包含等于零的情况。对最小的三个数也有类似的判断。从而能够知道，最小的数 <= 0, 最大的数 >= 0，中间的数一定等于0。同时判断一下最大和最小的两个数相加之后能不能在原本的数列中找到。

代码

#include<bits/stdc++.h>
using namespace std;

using i64 = long long;

void solve(){
    int n;
    cin >> n;
    vector<i64> a(n);
    set<i64> st;
    for(auto &x: a){
        cin >> x;
        st.insert(x);
    }

    if(n <= 6){
        for(int i = 0; i < n; i++){
            for(int j = i + 1; j < n; j++){
                for(int k = j + 1; k < n; k++){
                    if(! st.count(a[i] + a[j] + a[k])){
                        cout << "NO\n";
                        return;
                    }
                }
            }
        }
        cout << "YES\n";
    }
    else{
        sort(a.begin(), a.end());
        if (! st.count(a[0] + a.back())){
            cout << "NO\n";
            return;
        }
        for(int i = 1; i < n - 1; i++){
            if (a[i] != 0){
                cout << "NO\n";
                return;
            }
        }
        cout << "YES\n";
    }
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int t;
    cin >> t;
    while(t--){
        solve();
    }

    return 0;
}

D. Fixed Point Guessing

题目:

Limit:

time limit per test: 1 second
memory limit per test: 256 megabytes

Describe:

This is an interactive problem.
Initially, there is an array $a = [1, 2, \ldots, n]$, where $n$ is an odd positive integer. The jury has selected $\frac{n-1}{2}$ disjoint pairs of elements, and then the elements in those pairs are swapped. For example, if $a=[1,2,3,4,5]$, and the pairs $1 \leftrightarrow 4$ and $3 \leftrightarrow 5$ are swapped, then the resulting array is $[4, 2, 5, 1, 3]$.
As a result of these swaps, exactly one element will not change position. You need to find this element.
To do this, you can ask several queries. In each query, you can pick two integers $l$ and $r$ ($1 \leq l \leq r \leq n$). In return, you will be given the elements of the subarray $[a_l, a_{l + 1}, \dots, a_r]$ sorted in increasing order.
Find the element which did not change position. You can make at most $\mathbf{15}$ queries.
The array $a$ is fixed before the interaction and does not change after your queries.
Recall that an array $b$ is a subarray of the 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.

Input:

Each test contains multiple test cases. The first line contains an integer $t$ ($1 \leq t \leq 500$) — the number of test cases. The description of the test cases follows.
The first line of each test case contains an integer $n$ ($3 \leq n < 10^4$; $n$ is odd) — the length of the array $a$.
After reading the first line of each test case, you should begin the interaction.
It is guaranteed that the sum of $n$ over all test cases does not exceed $10^4$.

output:

Input-describe:

Output-describe:

For each test case, begin the interaction by reading the integer $n$.
To make a query, output “$\texttt{?};l;r$” ($1 \leq l \leq r \leq n$) without quotes. Afterwards, you should read in $r-l+1$ integers — the integers $a_l, a_{l + 1}, \dots, a_r$, in increasing order. You can make at most $15$ such queries in a single test case.
If you receive the integer $-1$ instead of an answer or the integer $n$, it means your program has made an invalid query, has exceed the limit of queries, or has given incorrect answer on the previous test case. Your program must terminate immediately to receive a Wrong Answer verdict. Otherwise you can get an arbitrary verdict because your solution will continue to read from a closed stream.
When you are ready to give the final answer, output “$\texttt{!};x$” ($1 \leq x \leq n$) without quotes — the element that did not change position. Giving this answer does not count towards the limit of $15$ queries. Afterwards, your program must continue to solve the remaining test cases, or exit if all test cases have been solved.
After printing a query do not forget to output end of line and flush the output. Otherwise, you will get Idleness limit exceeded. To do this, use:
fflush(stdout) or cout.flush() in C++; System.out.flush() in Java; flush(output) in Pascal; stdout.flush() in Python; see documentation for other languages.
Hacks
To make a hack, use the following format. The first line must contain an integer $t$ ($1 \leq t \leq 500$) — the number of test cases. The description of the test cases follows.
The first line of each test case must contain an integer $n$ ($3 \leq n < 10^4$; $n$ is odd) — the length of the array $a$.
The second line of each test case must contain $n$ space-separated integers $a_1, a_2, \ldots, a_n$ ($1 \le a_i \le n$) — the elements of $a$. The array $a$ should be the result of $\frac{n-1}{2}$ disjoint swaps on the array $[1,2,\dots,n]$.

Example:

Input:

2
5

1 2 4 5

1 3 5

Output:

? 1 4

? 3 5

! 2

? 1 1

! 1

思路

赛时没写出来。

二分的思路对了，性质判错了，二分写挂了。

首先通过数据范围可以猜到做法是二分。

设最后未交互的点的位置为fixed，对于一个给定的子序列，有没有在O(n)的时间内判断是否包含fixed的方法？

如果$a[x] = x\in [l,r]$ 与$a[y] = y \in[l,r]$ 交换，那么$cnt += 2$
如果$a[x]=x\in[l,r]$与$a[y] = y\in [l,r]$交换，那么$cnt += 0$
如果$fixed\in[l,r]$，那么$cnt += 1$

所以

如果$cnt % 2 == 0$ 那么$fixed \notin [l,r]$
如果$cnt% 2 == 1$，那么$fixed \in [l,r]$

证毕

代码

#include<bits/stdc++.h>
using namespace std;

using i64 = long long;

void solve(){
    int n;
    cin >> n;

    int l = 1, r = n;
    while(l < r){
        int mid = (l + r) / 2;
        cout << "? " << l << " " << mid << "\n";
        int x, cnt = 0;
        for(int i = 0; i < mid - l + 1; i++){
            cin >> x;
            assert(x != -1);
            if(l <= x && x <= mid){
                cnt++;
            }
        }
        if(cnt % 2 == 0){
            l = mid + 1;
        }
        else{
            r = mid;
        }
    }

    cout << "! " << l << "\n";
}

int main(){
    //ios::sync_with_stdio(false);
    //cin.tie(nullptr);

    int t;
    cin >> t;
    while(t--){
        solve();
    }

    return 0;
}