Codeforces 比賽記錄
Codeforces Round 990 (Div2)
E.Adventurers
平面上有若干點。選擇一個劃分點 \((x_0, y_0)\)。然后，對于坐標為 \((x_i, y_i)\) 的城市：
- 如果 \(x_0 \le x_i\) 且 \(y_0 \le y_i\)，第一個商人在此城市銷售商品；
- 如果 \(x_0 > x_i\) 且 \(y_0 \le y_i\)，第二個商人在此城市銷售商品；
- 如果 \(x_0 \le x_i\) 且 \(y_0 > y_i\)，第三個商人在此城市銷售商品；
- 如果 \(x_0 > x_i\) 且 \(y_0 > y_i\)，第四個商人在此城市銷售商品。
商人們希望選擇一個劃分點 \((x_0, y_0)\)，使得他們中任何一個人得到的城市數量盡可能公平（即最小化得到的城市數量的最大值）。請為他們找到這樣一個點。
hint
binary search
F.For the Emperor!
在古羅馬，為了擊敗野蠻人，制定了一項計劃，但要實施該計劃，每個城市都必須得到通知。
羅馬帝國的北部由 \(n\) 個城市組成，這些城市通過 \(m\) 條單向道路相連。起初，第 \(i\) 個城市有 \(a_i\) 名信使，每名信使可以沿著現有的道路自由地在城市間移動。一名信使可以攜帶一份計劃副本，并在他訪問的城市中傳達信息，并且可以在他當前所在的城市為其他信使制作無限多的副本。
開始時，你需要制作一定數量的計劃，并將它們交給選定的信使。你的目標是確保每座城市都被攜帶計劃的信使訪問過。找出最初需要制作的計劃的最小數量，以確保信使能夠將計劃送到每一個城市，或者確定根本無法做到這一點。
hint
costflow
sol
考慮建立費用流模型，核心思想是讓最大流量總是 \(\sum a_i\)，而經過一個點的費用是 \(-B\)（\(B\) 是一個極大的數），在一個點發放計劃的費用是 1，這樣求出最小費用之后，可以根據其除以 B 的整數部分計算其最多能讓多少個點收到計劃，根據余數計算出該前提下最小發放計劃的數量。
[VP] Educational Codeforces Round 176 (Rated for Div. 2)
F. Beautiful Sequence Returns
如果以下條件成立，我們就把一個整數序列稱為美麗：
- 除第一個元素外，每個元素的左邊都有一個比它小的元素；
- 除最后一個元素外，每個元素的右邊都有一個比它大的元素；
給你一個大小為 \(n\) 的整數數組 \(a\) 。請求出最長優美子序列的長度。\(n \leq 5 \times 10^5\)
sol
一個子序列合法，當且僅當第一個元素是嚴格最小值，最后一個元素是嚴格最大值。
將 \((i,a_i)\) 表示在二維平面，只有一些點能成為左下角，一些點能成為右上角。求出來。
對于某個點，會將它統計進去的左下角，一定是一段區間，預先求出。
枚舉右上角，線段樹動態維護貢獻。
Neowise Labs Contest 1 (Codeforces Round 1018, Div. 1 + Div. 2)
F. Wonderful Impostors
Today, you will play a game with \(n\) viewers numbered \(1\) to \(n\).Each player is either a crewmate or an impostor. You don't know the role of each viewer.
There are \(m\) statements numbered \(1\) to \(m\), which are either true or false. For each \(i\) from \(1\) to \(m\), statement \(i\) is one of two types:
- \(0\:a_i\:b_i\) (\(1 \leq a_i \leq b_i \leq n\)) — there are no impostors among viewers \(a_i, a_i + 1, \ldots, b_i\);
- \(1\:a_i\:b_i\) (\(1 \leq a_i \leq b_i \leq n\)) — there is at least one impostor among viewers \(a_i, a_i + 1, \ldots, b_i\).
Answer \(q\) questions of the following form:
- \(l\:r\) (\(1 \leq l \leq r \leq m\)) — is it possible that statements \(l, l + 1, \ldots, r\) are all true?
\(n,m,q \leq 200000\).
sol
We'll use the two pointers method. To answer a question \(s_l\,s_r\), we just check that \(s_l \geq low(s_r)\).
- When we add a \(1\)-segment \([b_l, b_r]\), we can use a segment tree to check if it will be fully covered by a \(0\)-component.
- When we add a \(0\)-segment \([a_l, a_r]\), it might merge several \(0\)-components. So first we need to find the \(0\)-component \([c_l, c_r]\) that contains \([a_l, a_r]\).
- \(c_l\) is the smallest value such that \(\min(count(c_l), count(c_l + 1), \ldots, count(a_l)) > 0\).
- \(c_r\) is the largest value such that \(\min(count(a_r), count(a_r + 1), \ldots, count(c_r)) > 0\).
- Both of these values can be found by performing a walk on the segment tree.
- Now we only need to check if there's a \(1\)-segment that's fully covered by \([c_l, c_r]\).
G. Wonderful Guessing Game
This is an interactive problem.
Alice is thinking of an integer from \(1\) to \(n\), and you must guess it by asking her some queries.To make things harder, she says you must ask all the queries first, and she will ignore exactly \(1\) query.
For each query, you choose an array of \(k\) distinct integers from \(1\) to \(n\), where \(k\) is even. Then, Alice will respond with one of the following:
- \(\texttt{L}\): the number is one of the first \(\frac{k}{2}\) elements of the array;
- \(\texttt{R}\): the number is one of the last \(\frac{k}{2}\) elements of the array;
- \(\texttt{N}\): the number is not in the array;
- \(\texttt{?}\): this query is ignored.
You must find a strategy that minimizes the number of queries. Can you do it? We can show that \(f(n) \leq 20\) for all \(n\) such that \(2 \le n \le 2 \cdot 10^5\).
sol
考慮如果 Alice 老老實實回答每個問題怎么做。
將 \(L\) 視作 \(-1\)，將 \(R\) 視作 \(1\)，將 \(N\) 視作 \(0\)。每次詢問和必須等于 \(0\)。
只要對于任意兩個數都滿足，存在一組詢問使得這兩個數對應的值不同，就可以根據回答的序列唯一確定每個數。
如果 Alice 忽略了某次詢問呢？想想怎么還原被忽略的詢問。
再添加一個詢問，使得對于任意權值，詢問的和模 \(3\) 都等于 \(0\)，這樣我們可以根據和求出被忽略的詢問，就可以做了。
浙公網安備 33010602011771號