Location>code7788 >text

Codeforces 777 Topic Seminar

Popularity：92 ℃/2024-11-11 09:54:52

title link

A B C D E

Title Analysis

A

Difficulty:Universalization -
Translation of the title page:

Give you three cards:\(0\)，\(1\)，\(2\)。
Pick one initially, then proceed in order\(n\) Sub-exchange, the exchange rules are: one in the center and one on the left, one in the center and one on the right, one in the center and one on the left ......
Finally ask where the chosen one is located.

Algorithm tags: simulation, enumeration, construction, mathematics
Problem solving:
Noting that each\(6\) The sequence is reduced to its pre-operation form after one cycle. So make a table and then just do it and be done with it.

B

Difficulty:Universalization -
Translation of the title page:

There are two persons, S and M, each of whom has a segment of length\(N\) Both players can take out a number in order in each round of the game, and whoever has the smaller number receives a penalty. If equal neither is penalized. Alternatively, M can rearrange the order of his numbers. Ask what is the minimum number of times M is penalized and the maximum number of times S is penalized.

Algorithm Labeling:game theory, Data Structures, Greedy, Sorting
Problem solving:
First in order.
According to a famous game theory paper\(^{[1]}\), there are the following strategies:

  1. If the round is winnable, use the smallest card that will win the round.
  2. If you cannot win this round, play the smallest current card.

The proof is within the original paper and is omitted here.
Let the card of S be\(s_i\)M's card is\(m_i\). Obviously, for the first question, as long as\(s_i \ge m_i\) I'll be able to get out.\(m_i\) The card.
And for the second question, the condition for playing the card is changed to\(s_i>m_i\) Ready to go.

References:
[1] Sima Biography of Sun Wu & Wu Qi[A]Records of the Grand Historian[C].Chang'an:Yang Yun,91BCE:1-2

C

Difficulty:Universalization +/- Increase
Translation of the title page:

give\(n\times m\) of the matrix. For the first\(j\) columns if they satisfy\(\forall i \in [1,n-1],a_{i,j} \leq a_{i+1,j}\), on the other hand, claims that the column is not declining.
\(k\) The second query asks if it would be better to keep only the matrix's first\(L\)~\(R\) row, whether there is a column in the matrix that does not descend.

Algorithm tags: bisection, data structures, dynamic programming, greedy, double pointer
Problem solving:
Notice that this question is related to the longest non-decreasing substring. Use\(b_{i,j}\) expressed in terms of\(a_{i, j}\) longest non-decreasing substring at the endStarting position subscript(note not the length), and then preprocesses each line with the smallest\(b\) can be found in the\(O(1)\) Inside Query.

D

Difficulty:Universalization +/- Increase
Translation of the title page:

give\(n\) It starts with# You need to manipulate the strings so that they are sorted in dictionary order from smallest to largest.
For each operation, you can remove any suffix from a particular string (you can even remove the entire string, of course), requiring you to remove the minimum number of characters.
Output your completed operation of this\(n\) A string.

Algorithm tags: bisection, greedy, string
Problem solving:
It is easy to see that this question and the sortingIt doesn't matter.。
Notice that removing the suffix makes the dictionary order of the string smaller, so the\(s_n\) No changes are needed. And for the\(s_i(1\le i\le n-1)\), which can be manipulated greedily so that it is just less than or equal to\(s_{i+1}\). So just operate from back to front.

E

Difficulty:Improvement+/provincial selection-
Translation of the title page:

give\(n\) The thickness, inner diameter, and outer diameter of the individual ring parts are required to form the tallest tower when a number of disks are assembled according to the following conditions.

  • The disk should be laid flat. That is, for each placed part, the side view should be rectangular and the top view should be circular.
  • The disks should be stacked, while the outer diameter of the disk below should be greater than or equal to the outer diameter of the disk above.
  • The outer diameter of the upper disk should be strictly larger than the inner diameter of the lower disk (otherwise the upper disk will fall into the hole of the lower disk by gravity).

Algorithm tags: enumeration, sorting
Problem solving:
This question is a bit like the longest ascending subsequence. First follow the\(b_i\) Descending ordering of circles for easy transfer.
found\(\text{dp}_i\) so as to\(i\) For the maximum tower height at the top, there is a transfer:

\[\text{dp}_i=\text{max}\{\text{dp}_j+h_i\} (j < i, b_i > a_j) \]

So you T'd. So you T'd.
Therefore consider introducing heap optimization. The previous state is pressed into the big-root heap (according to the\(h\) Sort), which pops up directly\(a \ge b_i\) (because if the top of the stack is not legal at this point, the top of the stack must be even less legal next) until it is legal, and then just update the answer.
time complexity\(O(n\text{log}{n})\), can be passed.

#include <bits/stdc++.h>
using namespace std;
#define int long long
struct dat {
	int a, b, h;
} ring[100010];
int n, dp[100010];
bool cmp(dat a, dat b) {
	if ( != ) return  > ;
	return  > ;
}
bool operator < (dat x, dat y) { return  < ; }
priority_queue<dat> q;
signed main() {
	scanf("%lld", &n);
	for (int i = 1; i <= n; i++) {
		scanf("%lld%lld%lld", &ring[i].a, &ring[i].b, &ring[i].h);
	}
	sort(ring + 1, ring + n + 1, cmp);
	({0, 0, 0});
	long long ans = 0;
	for (int i = 1; i <= n; i++) {
		while (().a >= ring[i].b) ();
		dp[i] = ().h + ring[i].h;
		({ring[i].a, ring[i].b, ().h + ring[i].h});
		ans = max(ans, dp[i]);
	}
	printf("%lld\n", ans);
	return 0;
}

summarize

This set is at the easier level of Codeforces, and there is hope for an AK on the test (just hope).

<Previous Next>