Codeforces Round 1034 (Div. 3)

比賽鏈接如下：https://codeforces.com/contest/2123?

A. Blackboard Game

Initially, the integers from?00?to n?1?are written on a blackboard.

In one round,

Alice chooses an integer?a?on the blackboard and erases it;
then Bob chooses an integer?b?on the blackboard such that?a+b≡3(mod4) and erases it.

Rounds take place in succession until a player is unable to make a move — the first player who is unable to make a move loses. Determine who wins with optimal play.

We define that x≡y(mod m)?whenever x?y?is an integer multiple of?mm.

解題思路：

其實根據輸入輸出也能大概猜出來

(a+b-3)%4=0, Alice去拿一個數, 然后Bob去進行配對, 誰先操作不了, 誰就輸了

eg:

n=4, 0 1 2 3

Alice拿0, Bob拿3進行配對

Alice拿1, Bob拿2進行配對

Bob贏

n=5, 0 1 2 3 4

這里Alice先拿0還是4無所謂，

Alice贏

n=8 0 1 2 3 ; 4 5 6 7

Bob贏

n%4==0, Bob贏

n%4!=0, Alice贏

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
void solve() {ll n;cin >> n;if (n % 4 == 0) {cout << "Bob" << endl;} else {cout << "Alice" << endl;}
}
int main() {int t;cin >> t;while (t--) {solve();}return 0;
}

?B. Tournament

You are given an array of integers a1,a2,…,an. A tournament is held with?nn?players. Player?i?has strength?aiai.

While more than?k?players remain,

Two remaining players are chosen at random;
Then the chosen player with the lower strength is eliminated. If the chosen players have the same strength, one is eliminated at random.

Given integers?j?and?k?(1≤j,k≤n), determine if there is any way for player?j?to be one of the last?k?remaining players.

解題思路：

當k=1時, aj要想留下來, 只能是數組最大值,?

k>1時, aj肯定是能留下來的

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
void solve() {int n, j, k;cin >> n >> j >> k;j--;vector<int> a(n);for (int i = 0; i < n; i++) {cin >> a[i];}if (k == 1) {int mx = *max_element(a.begin(), a.end());if (a[j] == mx) {cout << "YES" << endl;} else {cout << "NO" << endl;}} else {cout << "YES" << endl;}
}
int main() {int t;cin >> t;while (t--) {solve();}return 0;
}

?C. Prefix Min and Suffix Max

You are given an array?aa?of?distinct?integers.

In one operation, you may either:

choose a nonempty?prefix?of?aa?and replace it with its minimum value, or
choose a nonempty?suffix?of?aa?and replace it with its maximum value.

Note that you may choose the entire array?a.

For each element?ai, determine if there exists some sequence of operations to transform?aa?into?[ai]; that is, make the array?a?consist of only one element, which is?aiai. Output your answer as a binary string of length?nn, where the?ii-th character is?1?if there exists a sequence to transform?aa?into [ai], and?0?otherwise.

A?prefix?of an array is a subarray consisting of the first?kk?elements of the array, for some integer?k.

A?suffix?of an array is a subarray consisting of the last?k?elements of the array, for some integer?k.

給你一個不同整數的數組。
在一個操作中，您可以選擇a的非空前綴*并將其替換為其最小值，或者選擇a的非空前綴*并將其替換為其最大值。
注意，您可以選擇整個數組a。對于每個元素a?，確定是否存在一些操作序列將a轉換為[a′]；
也就是說，使數組只包含一個元素，即a。將您的答案輸出為長度為n的二進制字符串，如果存在將a轉換為[ai]的序列，則第i個字符為1，否則為0。
對于整數k，數組的前綴是由數組的前k個元素組成的子數組。數組的后綴是由數組的最后k個元素組成的子數組。?

解題思路：
??????1.前綴最小值：元素 ai?是從數組開頭到 i?位置（a1?到 ai）的最小值。
2.后綴最大值：元素 ai?是從 i?位置到數組結尾（ai?到 an）的最大值。

3.可保留條件：如果 ai?是前綴最小值或后綴最大值，則存在操作序列將數組縮減為 [ai]；否則，無法保留。

eg:?數組 [1, 3, 5, 4, 7, 2]，輸出?100011

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
void solve() {int n;cin >> n;vector<int> a(n + 1), pre(n + 1, INT_MAX), suf(n + 2);for (int i = 1; i <= n; i++) {cin >> a[i];pre[i] = min(pre[i - 1], a[i]);}for (int i = n; i >= 1; i--) {suf[i] = max(suf[i + 1], a[i]);}for (int i = 1; i <= n; i++) {cout << (a[i] == pre[i] || a[i] == suf[i] ? 1 : 0);}cout << endl;
}int main() {int t;cin >> t;while (t--) {solve();}return 0;
}

?D. Binary String Battle

Alice and Bob are given a binary string?s?of length?n, and an integer?k?(1≤k<n).

Alice wins if she is able to transform all characters of?ss?into zeroes. If Alice is unable to win in a finite number of moves, then Bob wins.

Alice and Bob take turns, with Alice going first.

On Alice's turn, she may choose any?subsequence???of length?k?in?s, then set all characters in that subsequence to zero.
On Bob's turn, he may choose any?substring???of length?k?in?ss, then set all characters in that substring to one.

Note that Alice wins if the string consists of all zeros at any point during the game, including in between Alice's and Bob's turns.

Determine who wins with optimal play.

??A?subsequence?of a string?s?is a set of characters in?s. Note that these characters do not have to be adjacent.

??A?substring?of a string?s?is a contiguous group of characters in?s. Note that these characters must be adjacent.

解題思路：

1.Alice必贏的條件：
如果初始 cnt（s 中 1 的數量） ≤ k，Alice 一次就能把所有 1 清掉 —— 贏。
如果 n < 2*k，則 Bob 無法每次維護 cnt > k 的策略（因為沒地方藏一個"額外的 1"）—— Alice?
2. Bob必贏的條件：
如果 cnt > k 且 n ≥ 2*k，Bob 總能維護至少一個額外的 1，并總能抵消 Alice 的操作 —— 贏。?

因為你要找兩個不重疊的長度為 k 的子串，至少需要長度 2k

否則他怎么也得和 Alice 的[清除區]發生重疊，Alice 就能全清了

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
void solve(){int n, k, cnt = 0;string s;cin >> n >> k >> s;for(char c : s){if(c == '1'){cnt++;}}cout << (cnt <= k || n < 2*k ? "Alice" : "Bob") << '\n';
}int main(){int t;cin >> t;while(t--) {solve();}return 0;
}

E. MEX Count

Define the?MEX (minimum excluded value) of an array to be the smallest nonnegative integer not present in the array. For example,

MEX([2,2,1])=0 because?0?is not in the array.
MEX([3,1,0,1])=2 because?0?and?1?are in the array but?2?is not.
MEX([0,3,1,2])=4 because?0,?1,?2, and?3?are in the array but?44?is not.

You are given an array?aa?of size?n?of nonnegative integers.

For all?k?(0≤k≤n), count the number of possible values of MEX(a)?after removing exactly?kk?values from?a.

解題思路：MEX是數組a中的最小非負整數

eg:

數組a:?

0 1 2 3 4 5 .. n

出現次數分別為:

1 2 1 3 0 2 .. 5

比如MEX=1, 我們最少需要刪除2個1

最多為n-1 （1之前每個數字次數剩1個,1后面全刪了，最后剩1個數字，刪除n-1個）

就是你刪除任意個[cntx, n-x] 都能得到x

題目是刪除k個數字, mex的可能性

然后差分即可

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int main() {int t;cin >> t;while (t--) {int n;cin >> n;vector<int> a(n), cnt(n + 1, 0);for (int i = 0; i < n; i++) {cin >> a[i];if (a[i] <= n) {cnt[a[i]]++;}}vector<int> ok(n + 1, false);ok[0] = true;for (int m = 1; m <= n; m++) {ok[m] = ok[m - 1] && (cnt[m - 1] > 0);}vector<int> diff(n + 2, 0);for (int m = 0; m <= n; m++) {if (!ok[m])break;int L = cnt[m];int R = n - m;if (L <= R) {diff[L] += 1;diff[R + 1] -= 1;}}vector<int> ans(n + 1);int cur = 0;for (int k = 0; k <= n; k++) {cur += diff[k];ans[k] = cur;}for (int k = 0; k <= n; k++) {cout << ans[k] << (k == n ? '\n' : ' ');}}return 0;
}

?F. Minimize Fixed Points

Call a permutation??p?of length?nn?good?if?gcd(pi,i)>1?for all?2≤i≤n. Find a good permutation with the?minimum?number of?fixed points???across all good permutations of length?n. If there are multiple such permutations, print any of them.

???A permutation of length?nn?is an array that contains every integer from?1?to?n?exactly once, in any order.

gcd(x,y)?denotes the?greatest common divisor (GCD)?of?x?and?y.

??A?fixed point?of a permutation?p?is an index?j?(1≤j≤n) such that?pj=j.

解題思路：

n=6,

1 4 6 2 5 3

1 2 3 4 5 6

gcd:

1 2 3 2 5 3

fixed points = 2

gcd(pi,i)>1, i>1

i=0, a[0]=1

當n=13,

質數2及其倍數為：2? 4? 6? 8 10 12?

數左移一位, 就可以和下標形成 gcd(pi,i)=2

2 4 6 8 10 12

4 6 8 10 12 2

prime = 3

3 6 9 12

素數越大, 在1-n這個序列中, 倍數的出現次數越少??

prime=5

5 10

只能這兩進行輪換, 因此我們從prime比較大 -> prime比較小

prime在比較大的數輪換過后, 后續就不需要進行輪換了

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int MAXN = 1000005;
vector<bool> isp(MAXN, true); // isp[i] = true 表示是素數
void init(int n) {isp[0] = isp[1] = false;for (int i = 2; i * i <= n; i++) {if (isp[i]) {for (int j = i * i; j <= n; j += i) {isp[j] = false;}}}
}void solve() {int n;cin >> n;init(n);vector<int> a(n + 1, -1);vector<bool> vis(n + 1, false);for (int i = n / 2; i >= 2; i--) {if (!isp[i]) {continue;}vector<int> c;    收集所有 i 的倍數for (int j = i; j <= n; j += i) {if (vis[j]) {continue;}vis[j] = true;c.push_back(j);}// // 構造一個環：c[0]->c[1]->...->c[k-1]->c[0]for (int j = 0; j < c.size(); j++) {a[c[j]] = c[(j + 1) % c.size()];}}for (int i = 1; i <= n; i++) {cout << (a[i] == -1 ? i : a[i]) << " ";}cout << '\n';
}
int main() {int t;cin >> t;while (t--) {solve();}return 0;
}

G. Modular Sorting

?You are given an integer?m?(2≤m≤5?105) and an array?aa?consisting of nonnegative integers smaller than?m.

Answer queries of the following form:

1?i?x: assign ai:=x
2?k: in one operation, you may choose an element?aiai?and assign?ai:=(ai+k)(modm)a — determine if there exists some sequence of (possibly zero) operations to make?a?nondecreasing.

Note that instances of query?2?are independent; that is, no actual operations are taking place. Instances of query?1?are persistent.

a(modm)?is defined as the unique integer?bb?such that 0≤b<m?and a?b?is an integer multiple of?m.

An array?a?of size?n?is called nondecreasing if and only if ai≤ai+1?for all?1≤i<n.

解題思路：

(ai+k)%m?

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int MAXN = 1000100;
vector<bool> isp;
vector<int> primes;void init(int top) {isp.assign(top + 1, true);isp[0] = isp[1] = false;for (int i = 2; i <= top; ++i) {if (isp[i])primes.push_back(i);for (int j = 0; j < (int)primes.size(); ++j) {int p = primes[j];if (i * p > top)break;isp[i * p] = false;if (i % p == 0)break;}}
}map<int, int> factorize(int v) {map<int, int> res;for (int i = 0; i < (int)primes.size(); ++i) {int p = primes[i];if (1LL * p * p > v)break;int cnt = 0;while (v % p == 0) {cnt++;v /= p;}if (cnt)res[p] = cnt;}if (v > 1)res[v] = 1;return res;
}vector<int> get_divisors(int v) {map<int, int> f = factorize(v);vector<int> res;res.push_back(1);for (map<int, int>::iterator it = f.begin(); it != f.end(); ++it) {int p = it->first, c = it->second;int sz = res.size();int base = 1;for (int i = 0; i < c; ++i) {base *= p;for (int j = 0; j < sz; ++j) {res.push_back(res[j] * base);}}}return res;
}int gcd(int a, int b) { return b == 0 ? a : gcd(b, a % b); }void solve() {int n, m, qn;cin >> n >> m >> qn;vector<int> a(n);for (int i = 0; i < n; i++)cin >> a[i];vector<array<int, 3>> q(qn);for (int i = 0; i < qn; i++) {cin >> q[i][0];if (q[i][0] == 1) {cin >> q[i][1] >> q[i][2];} else {cin >> q[i][1];}}vector<int> res(qn, -1);vector<int> b(n);vector<int> divisors = get_divisors(m);for (int d_index = 0; d_index < (int)divisors.size(); ++d_index) {int d = divisors[d_index];for (int i = 0; i < n; i++) {b[i] = a[i] % d;}int sum = 0;for (int i = 0; i + 1 < n; i++) {if (b[i] > b[i + 1])sum++;}for (int i = 0; i < qn; i++) {if (q[i][0] == 1) {int w = q[i][1] - 1;int v = q[i][2];if (w - 1 >= 0 && b[w - 1] > b[w])sum--;if (w + 1 < n && b[w] > b[w + 1])sum--;b[w] = v % d;if (w - 1 >= 0 && b[w - 1] > b[w])sum++;if (w + 1 < n && b[w] > b[w + 1])sum++;} else {if (gcd(q[i][1], m) == d) {res[i] = sum < m / d;}}}}for (int i = 0; i < qn; i++) {if (res[i] != -1) {cout << (res[i] ? "YES" : "NO") << '\n';}}
}int main() {init(MAXN);int t;cin >> t;while (t--) {solve();}return 0;
}