Codeforces Round 1034(Div.3)[A-F]
A. Blackboard Game
題意
有 \(0\) 到 \(n - 1\)的整數。兩人輪流操作：
- \(A\) 選擇 一個整數 \(a\) 刪除
- \(B\) 選擇一個整數 \(b\) 滿足 \(a + b \equiv 3 (mod 4)\) 刪除他
當一方無法操作時，另一方獲勝。
tag: 博弈論
思路
可以看出，\(0,1,2,3\) 可以湊兩對三，也就是不管 \(A\) 怎么選 \(B\) 都有的選，然后直到全部選完 \(A\) 落敗。
當 \(n-1\)是 \(3\) 的倍數時 \(Bob\) 勝利
Code (C++)
void whx()
{
int n;
cin >> n;
if(n % 4 != 0) cout << "Alice\n";
else cout << "Bob\n";
}
B. Tournament
題意
給你一個長度為 \(n\) 的數組 \(a\) ，\(a_i\) 對應的是 \(i\) 的實力。
當剩下的人超過 \(k\) 時會進行淘汰。
淘汰規則：
- 隨機挑選兩個人
- 然后把兩人中實力較弱的淘汰，若兩人實力相等隨機淘汰一個人
給你 \(j\) 和 \(k\) ，判斷第 \(j\) 個人有沒有可能是最后剩下的 \(k\) 個人之一。
tag: 貪心，思維
思路
如果兩個人值一樣那么肯定優先留下要求的那個人。
那么我們可以記錄下來 \(j\) 對應的值 \(v\)。
可以發現大部分情況下想留下的人都能留下:
\(k > 1\) 的時候，只要死保想要的一個就一定行。
分析什么情況下留不下想留的人：
\(k = 1\) 的時候，除非 \(v\) 是最大值，能活到最后，不然留不下來。
Code (C++)
void whx()
{
int n, j, k, target;
cin >> n >> j >> k;
int v = -1, ma = -1;
for (int i = 1, a; i <= n; i ++ )
{
cin >> a;
if (i == j) v = a;
ma = max(ma, a);
}
if (v != ma && k == 1) cout << "NO\n";
else cout << "YES\n";
}
C. Prefix Min and Suffix Max
題意
給你一個長度為 n 的數組 a， 在一次操作中，你可以：
- 選擇 a 的非空前綴，用他的最小值來替換。
- 選擇 b 的非空后綴， 用他的最大值來替換。
輸出一個 01串 表示數組 a 對應位置的值能夠通過若干次操作實現全覆蓋。
tag: 前后綴數組
思路
預處理第 i 位前綴最小值，后綴最大值。
如果第 \(i\) 位的值和前綴最小值相等 或 和 后綴最大值相等，那么就可以全覆蓋。
Code (C++)
、
void whx()
{
int n;
cin >> n;
vector a(n + 1);
for (int i = 1; i <= n; i ++ ) cin >> a[i];
int pre_min = 1e6 + 7;
vector suf_max(n + 2, 0);
for (int i = n; i >= 1; i -- ) suf_max[i] = max(suf_max[i + 1], a[i]);
string ans = "";
for (int i = 1; i <= n; i ++ )
{
pre_min = min(pre_min, a[i]);
if (pre_min == a[i] || a[i] == suf_max[i]) ans += '1';
else ans += '0';
}
cout << ans << "\n";
}
D. Binary String Battle
題意
給你一個長度為 \(n\) 的二進制字符串 \(s\)，和一個整數 \(k\) (\(1 \leq k < n\))。
如果 \(A\) 能把所有字符轉化為零 \(A\) 就贏了。
\(A\) 和 \(B\) 輪流下棋， \(A\) 先下：
- \(A\) 可以選擇一個長度為 \(k\) 的任意子序列，全部置零。
- \(B\) 可以選擇一格長度為 \(k\) 的任意字串，全部置零。
問誰能獲勝。
tag: 博弈論
思路
從 \(1\) 個數的角度來分析：
如果 \(1\) 的個數 \(c1 \leq k\) ，那么 \(A\) 直接就可以獲勝。
然后分析，\(A\) 每次操作可以讓 \(1\) 減少 \(k\) 個，那什么是 \(A\) 的最優策略：
\(A\) 會努力 cut \(B\) 的恢復數，也就是盡量讓 \(B\) 能選的字串中都包含 \(1\)。
上述情況只有 \(k * 2 > n\) 的時候存在，也只有這種情況 \(A\)可以獲勝。
Code (C++)
void whx()
{
int n, k;
cin >> n >> k;
string s;
cin >> s;
int c1 = 0;
for (int i = 0; i < n; i ++ ) c1 += (s[i] == '1');
if (c1 <= k) cout << "Alice\n";
else
{
if (k * 2 > n) cout << "Alice\n";
else cout << "Bob\n";
}
}
E. MEX Count
題意
給你一個大小為 \(n\) 的非負整數數組 \(a\)。
對于所有的 \(k\) (\(0\leq k \leq n\))，計算移除k個值后，\(MEX(a)\) 可能的個數
tag: 差分
思路
MEX 的值域為 \([0, n]\)
統計每個值 \(v\) 的出現個數 \(cnt[v]\)
可以發現每個 \(v\) 會對于 不同的 \(k\) 產生一段連續的貢獻。
遍歷 \(v\) 從 \(0\) 開始到 \(n\):
\(v\) 可以在 \(k \in [cnt[v], n - v]\) 中作為 MEX。可以用差分進行區間 \(+1\)。
如果遇到了沒有出現過的 \(v\) 那么跳出循環，因為后續不可能產生貢獻了，后面 MEX 全是 前面這個每出現的了。
Code (C++)
void whx()
{
int n;
cin >> n;
vector a(n + 1, 0);
for (int i = 1, x; i <= n; i ++ )
{
cin >> x;
a[x] ++;
}
vector ans(n + 2);
for (int i = 0; i <= n; i ++ )
{
int k = a[i], t = n - i;
ans[k] ++, ans[t + 1] --;
if (!a[i]) break;
}
for (int i = 0; i <= n; i ++ )
{
if(i) ans[i] += ans[i - 1];
cout << ans[i] << " \n"[i == n];
}
}
F. Minimize Fixed Points
題意
輸入一個 n ，構造長度為 n 的好排列 \(p\)。
-
對于 \(i > 1\)，都有 \(gcd(p_i,i) > 1\) 記為好排列。
-
在長度為 n 的所有好排列中，找出一個固定點數最少的良好排列
-
如果 \(p_i = i\) 記為一個固定點數。
tag: 構造，質因數
思路
盡量讓 \(i\) 的最大質因數的倍數來表示 \(p_i\)
1 2 3 4 5 6 7 8 9 10
? 3 6 9
如上，可以發現把 3 6 9錯位一下9 3 6就可以把三個位置全變成非固定點數
而且對于一個數能拆出來的大數一定比小數少，應該先把大數能表示的表示了。
比如 \(10\) 可以用 \(2\) 的倍數表示，可以用 \(5\) 的倍數表示，優先用 \(5\) ，然后你這里用了 \(2\) ，后面出現一個不是 \(5\) 的倍數但是 \(2\) 的倍數的數，你的 \(2\) 數量不夠了。
預處理 \(n\) 內的所有質數，然后倒著遍歷，錯位賦給對應位置的 \(p\) 排列。
Code (C++)
void whx()
{
int n;
cin >> n;
if (n <= 3)
{
for (int i = 1; i <= n; i ++ ) cout << i << " \n"[i == n];
}
else
{
vector a;
auto is_prime = [&](int x) -> bool
{
if (x <= 2) return true;
for (int i = 2; i <= x / i; i ++ )
{
if (x % i == 0) return false;
}
return true;
};
for (int i = n; i >= 2; i -- )
{
if (is_prime(i)) a.push_back(i);
}
vector ans(n + 1, 0);
ans[1] = 1;
for (auto p : a)
{
int last = 0;
for (int i = p; i <= n; i += p)
{
if (ans[i]) continue;
ans[i] = last;
last = i;
}
ans[p] = last;
}
for (int i = 1; i <= n; i ++ ) cout << ans[i] << " \n"[i == n];
}
}
浙公網安備 33010602011771號