AtCoder Regular Contest 179 （ABC题）视频讲解

本文主要是介绍AtCoder Regular Contest 179 （ABC题）视频讲解，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

A - Partition

Problem Statement

You are given integers $N$ and $K$.
The cumulative sums of an integer sequence $X=(X_1,X_2,\dots ,X_N)$ of length $N$ is defined as a sequence $Y=(Y_0,Y_1,\dots ,Y_N)$ of length $N+1$ as follows:
$Y_0=0$
$Y_i=\sum _{j=1}^i{X}_j(i=1,2,\dots ,N)$
An integer sequence $X=(X_1,X_2,\dots ,X_N)$ of length $N$ is called a good sequence if and only if it satisfies the following condition:
Any value in the cumulative sums of $X$ that is less than $K$ appears before any value that is not less than $K$.
Formally, for the cumulative sums $Y$ of $X$, for any pair of integers $(i,j)$ such that $0\le i,j\le N$, if KaTeX parse error: Expected 'EOF', got '&' at position 6: (Y_i &̲lt; K and $Y_j\ge K)$, then KaTeX parse error: Expected 'EOF', got '&' at position 3: i &̲lt; j.
You are given an integer sequence $A=(A_1,A_2,\dots ,A_N)$ of length $N$. Determine whether the elements of $A$ can be rearranged to a good sequence. If so, print one such rearrangement.

Constraints

$1\le N\le 2\times 10^5$
$-10^9\le K\le 10^9$
$-10^9\le A_i\le 10^9$
All input values are integers.

Input

The input is given from Standard Input in the following format:

$N$ $K$
$A_1$ $A_2$ $\cdots$ $A_N$

Output

If the elements of $A$ can be rearranged to a good sequence, print the rearranged sequence $(A_1^{\prime },A_2^{\prime },\dots ,A_N^{\prime })$ in the following format:

Yes
$A_1^{\prime }$ $A_2^{\prime }$ $\cdots$ $A_N^{\prime }$

If there are multiple valid rearrangements, any of them is considered correct.
If a good sequence cannot be obtained, print No.

Sample Input 1

4 1
-1 2 -3 4

Sample Output 1

Yes
-3 -1 2 4

If you rearrange $A$ to $(-3,-1,2,4)$, the cumulative sums $Y$ in question will be $(0,-3,-4,-2,2)$. In this $Y$, any value less than $1$ appears before any value not less than $1$.

Sample Input 2

4 -1
1 -2 3 -4

Sample Output 2

No

Sample Input 3

10 1000000000
-1000000000 -1000000000 -1000000000 -1000000000 -1000000000 1000000000 1000000000 1000000000 1000000000 1000000000

Sample Output 3

Yes
-1000000000 -1000000000 -1000000000 -1000000000 -1000000000 1000000000 1000000000 1000000000 1000000000 1000000000

Solution

具体见文末视频。

---

Code

#include <bits/stdc++.h>
#define fi first
#define se second
#define int long longusing namespace std;typedef pair<int, int> PII;
typedef long long LL;signed main() {cin.tie(0);cout.tie(0);ios::sync_with_stdio(0);int n, k, sum = 0;cin >> n >> k;std::vector<int> a(n);for (int i = 0; i < n; i ++)cin >> a[i], sum += a[i];if (sum < k	&& k <= 0) {cout << "No" << endl;return 0;}if (k > 0) sort(a.begin(), a.end());else sort(a.begin(), a.end(), greater<int>());cout << "Yes" << endl;for (int i = 0; i < n; i ++)cout << a[i] << " ";cout << endl;return 0;
}

B - Between B and B

Problem Statement

You are given a sequence $(X_1,X_2,\dots ,X_M)$ of length $M$ consisting of integers between $1$ and $M$, inclusive.
Find the number, modulo $998244353$, of sequences $A=(A_1,A_2,\dots ,A_N)$ of length $N$ consisting of integers between $1$ and $M$, inclusive, that satisfy the following condition:
For each $B=1,2,\dots ,M$, the value $X_B$ exists between any two different occurrences of $B$ in $A$ (including both ends).
More formally, for each $B=1,2,\dots ,M$, the following condition must hold:
For every pair of integers $(l,r)$ such that KaTeX parse error: Expected 'EOF', got '&' at position 10: 1 \leq l &̲lt; r \leq N and $A_l=A_r=B$, there exists an integer $m$ ($l\le m\le r$) such that $A_m=X_B$.

Constraints

$1\le M\le 10$
$1\le N\le 10^4$
$1\le X_i\le M$
All input values are integers.

Input

The input is given from Standard Input in the following format:

$M$ $N$
$X_1$ $X_2$ $\cdots$ $X_M$

Output

Print the answer.

Sample Input 1

3 4
2 1 2

Sample Output 1

14

Here are examples of sequences $A$ that satisfy the condition:
$(1,3,2,3)$
$(2,1,2,1)$
$(3,2,1,3)$
Here are non-examples:
$(1,3,1,3)$
There is no $X_3=2$ between the $3$s.
$(2,2,1,3)$
There is no $X_2=1$ between the $2$s.

Sample Input 2

4 8
1 2 3 4

Sample Output 2

65536

All sequences of length $8$ consisting of integers between $1$ and $4$ satisfy the condition.
Note that when $X_B=B$, there is always a $B$ between two different occurrences of $B$.

Sample Input 3

4 9
2 3 4 1

Sample Output 3

628

Solution

具体见文末视频。

Code

#include <bits/stdc++.h>
#define fi first
#define se second
#define int long longusing namespace std;typedef pair<int, int> PII;
typedef long long LL;const int N = 1e4 + 10, M = 11, mod = 998244353;int n, m;
int a[M], f[N][1 << M], mask[M];signed main() {cin.tie(0);cout.tie(0);ios::sync_with_stdio(0);cin >> m >> n;for (int i = 1; i <= m; i ++)cin >> a[i], mask[a[i]] |= 1ll << i - 1;f[0][(1 << m) - 1] = 1;for (int i = 0; i < n; i ++)for (int j = 1; j <= m; j ++)for (int k = 0; k < 1 << m; k ++)if ((k >> j - 1) & 1)f[i + 1][(k ^ (1 << j - 1)) | mask[j]] = (f[i + 1][(k ^ (1 << j - 1)) | mask[j]] + f[i][k]) % mod;int res = 0;for (int i = 0; i < 1 << m; i ++)res = (res + f[n][i]) % mod;cout << res << endl;return 0;
}

C - Beware of Overflow

Problem Statement

This is an interactive problem (where your program interacts with the judge via input and output).
You are given a positive integer $N$.
The judge has a hidden positive integer $R$ and $N$ integers $A_1,A_2,\dots ,A_N$. It is guaranteed that $|A_i|\le R$ and $\left|\sum _{i=1}^N{A}_i\right|\le R$.
There is a blackboard on which you can write integers with absolute values not exceeding $R$. Initially, the blackboard is empty.
The judge has written the values $A_1,A_2,\dots ,A_N$ on the blackboard in this order. Your task is to make the blackboard contain only one value $\sum _{i=1}^N{A}_i$.
You cannot learn the values of $R$ and $A_i$ directly, but you can interact with the judge up to $25000$ times.
For a positive integer $i$, let $X_i$ be the $i$-th integer written on the blackboard. Specifically, $X_i=A_i$ for $i=1,2,\dots ,N$.
In one interaction, you can specify two distinct positive integers $i$ and $j$ and choose one of the following actions:
Perform addition. The judge will erase $X_i$ and $X_j$ from the blackboard and write $X_i+X_j$ on the blackboard.
$|X_i+X_j|\le R$ must hold.
Perform comparison. The judge will tell you whether KaTeX parse error: Expected 'EOF', got '&' at position 5: X_i &̲lt; X_j is true or false.
Here, at the beginning of each interaction, the $i$-th and $j$-th integers written on the blackboard must not have been erased.
Perform the interactions appropriately so that after all interactions, the blackboard contains only one value $\sum _{i=1}^N{A}_i$.
The values of $R$ and $A_i$ are determined before the start of the conversation between your program and the judge.

Constraints

$2\le N\le 1000$
$1\le R\le 10^9$
$|A_i|\le R$
$\left|\sum _{i=1}^N{A}_i\right|\le R$
$N$, $R$, and $A_i$ are integers.

Input and Output

This is an interactive problem (where your program interacts with the judge via input and output).
First, read $N$ from Standard Input.

$N$

Next, repeat the interactions until the blackboard contains only one value $\sum _{i=1}^N{A}_i$.
When performing addition, make an output in the following format to Standard Output. Append a newline at the end. Here, $i$ and $j$ are distinct positive integers.

• $i$ $j$

The response from the judge will be given from Standard Input in the following format:

$P$

Here, $P$ is an integer:
If $P\ge N+1$, it means that the value $X_i+X_j$ has been written on the blackboard, and it is the $P$-th integer written.
If $P=-1$, it means that $i$ and $j$ do not satisfy the constraints, or the number of interactions has exceeded $25000$.
When performing comparison, make an output in the following format to Standard Output. Append a newline at the end. Here, $i$ and $j$ are distinct positive integers.

? $i$ $j$

The response from the judge will be given from Standard Input in the following format:

$Q$

Here, $Q$ is an integer:
If $Q=1$, it means that KaTeX parse error: Expected 'EOF', got '&' at position 5: X_i &̲lt; X_j is true.
If $Q=0$, it means that KaTeX parse error: Expected 'EOF', got '&' at position 5: X_i &̲lt; X_j is false.
If $Q=-1$, it means that $i$ and $j$ do not satisfy the constraints, or the number of interactions has exceeded $25000$.
For both types of interactions, if the judge’s response is $-1$, your program is already considered incorrect. In this case, terminate your program immediately.
When the blackboard contains only one value $\sum _{i=1}^N{A}_i$, report this to the judge in the following format. This does not count towards the number of interactions. Then, terminate your program immediately.

!

If you make an output in a format that does not match any of the above, -1 will be given from Standard Input.

-1

In this case, your program is already considered incorrect. Terminate your program immediately.

Notes

For each output, append a newline at the end and flush Standard Output. Otherwise, the verdict may be TLE.
Terminate your program immediately after outputting the result (or receiving -1). Otherwise, the verdict will be indeterminate.
Extra newlines will be considered as malformed output.

Sample Input and Output

Here is a possible conversation with $N=3,R=10,A_1=-1,A_2=10,A_3=1$.

Input	Output	Explanation
3		First, the integer $N$ is given.
	? 1 2	Perform a comparison.
1		The judge returns $1$ because $X_1\lt X_2\ (-1\lt 10)$.
	+ 1 3	Perform an addition.
4		The judge erases $X_1 = -1$ and $X_3 = 1$ from the blackboard and writes $X_1 + X_3 = 0$. This is the fourth integer written.
	+ 2 4	Perform an addition.
5		The judge erases $X_2 = 10$ and $X_4 = 0$ from the blackboard and writes $X_2 + X_4 = 10$. This is the fifth integer written.
	!	The blackboard contains only one value $\displaystyle\sum_{i=1}^{N}A_i$, so report this to the judge.

Solution

具体见文末视频。

---

Code

#include <bits/stdc++.h>
#define fi first
#define se second
#define int long longusing namespace std;typedef pair<int, int> PII;
typedef long long LL;bool cmp(int a, int b) {cout << "? " << a << " " << b << endl;int ok;cin >> ok;return ok;
}signed main() {cin.tie(0);cout.tie(0);ios::sync_with_stdio(0);int n;cin >> n;std::vector<int> id;for (int i = 1; i <= n; i ++)id.push_back(i);sort(id.begin(), id.end(), cmp);while (n > 1) {cout << "+ " << id[0] << " " << id.back() << endl;int p;cin >> p;id.erase(id.begin()), id.pop_back();n --;if (n == 1) break;int l = 0, r = id.size() - 1;while (l < r) {int mid = l + r >> 1;if (cmp(p, id[mid])) r = mid;else l = mid + 1;}if (!cmp(p, id[r])) r ++;id.insert(id.begin() + r, p);}cout << "!\n";return 0;
}

---

视频题解

---

最后祝大家早日

这篇关于AtCoder Regular Contest 179 （ABC题）视频讲解的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---