比賽：Codeforces Round 930 (Div. 2) (A~B)

目錄：A B

A題：Shuffle Party

標簽: 模擬

題目大意

• 給你一個數組 a₁,a₂,…,a_n。最初，每個 1 ≤ i ≤ n都有 a_i = i，整數 k ≥ 2的運算 swap(k)定義如下：
• • 設 d是不等于 k本身的最大除數 。然后交換元素 a_d 和 a_k 。
• 執行swap(2) swap(3) … swap(n)：問執行完后1在哪個位置

思路

• 只關注1的交換位置，2的最大除數是1，4的最大除數是2，8的最大除數是4…
• 所以1的位置會有1 -> 2 -> 4 -> 8 -> 16 … 一直到接近n的位置

AC代碼

#include <bits/stdc++.h>
using namespace std;
void solve()
{int n; cin >> n;int t = log2(n);	// 找到滿足 2^t <= n 最大的tcout << (1 << t) << endl; // 2^t即為答案
} 
int main()
{int T; cin >> T;while(T--)solve();return 0;
}

B題：Binary Path

標簽: 實現問題，編程技巧，模擬（implementation）

題目大意

• 給你一個 2×n 充滿了 0 和 1的 網格。 i 行和j列的數字是 a_ij。
• 從(1, 1)點開始只能向下或向右走，走到(2, n)，經過路徑上的數字拼接起來。
• 問：拼接后的數字 字典序最小的是什么，有幾種走法能得到這個字典序最小值。

思路

• 因為是2 * n的網格只能向下或向右走，所以只能向下走一次，走完一次向下后路線固定了因為只能向右走了
• 為了好說明，這里將那個向下走的位置稱為斷點
• 將1 ~ n 每一個點當作斷點枚舉，要字典序最小所以要走法有以下幾種情況：
• 1. 如果當前點右邊點小于下邊點那么一定向右走，繼續向后尋找斷點
• 2. 下面的點小于右邊的點，那么向下走。那么這個點就是斷點，并且只有這一種情況
• 3. 下面的點等于右邊的點，這時既可以向下又可以向右，但如果在之后遇到下面的點不等于右邊的點得情況那么路線會被確定到后面得點，沒有則當前點和右邊點都可以作為斷點
• 樣例3 斷點可為0011，即從0011往下字典序最小且一樣，如下：
• 001 0011 1
  111 011 01

AC代碼

#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 10;
vector<string> v;
void solve()
{int n; cin >> n;v.clear();for(int i = 0; i < 2; i++){string s; cin >> s;v.push_back(s);}	int res = 1, idx = 0;for(int i = 0; i < n-1; i++){if(v[0][i+1] == v[1][i])res ++;else {// 下面的點小于右邊的點，那么向下走，那么這個點就是斷點if(v[0][i+1] > v[1][i]) {idx = i; break;}// 如果當前點右邊點小于下邊點那么一定向右走，那么當前點不是斷點，繼續向后尋找斷點idx = i + 1;res = 1; // 上一步是向右走，路線時固定的刷新為一種情況}}// 斷點為idx輸出路徑for(int i = 0; i <= idx; i++)cout << v[0][i];for(int i = idx; i < n; i++)cout << v[1][i];cout << "\n" << res << "\n";
} 
int main()
{int T; cin >> T;while(T--)solve();return 0;
}

logo

//へ　　　　　／|
//　　/＼7　　　 ∠＿/
//　 /　│　　 ／　／
//　│　Z ＿,＜　／　　 /`ヽ
//　│　　　　　ヽ　　 /　　〉
//　 Y　　　　　`　 /　　/
//　ｲ●　､　●　　??〈　　/
//　()　 へ　　　　|　＼〈
//　　>ｰ ､_　 ィ　 │ ／／
//　 / へ　　 /　ﾉ＜| ＼＼
//　 ヽ_ﾉ　　(_／　 │／／
//	　　7　　　　　　　|／
//

/*__   _,--="=--,_   __/  \."    .-.    "./  \/  ,/  _   : :   _  \/` \\  `| /o\  :_:  /o\ |\__/`-'| :="~` _ `~"=: |\`     (_)     `/.-"-.   \      |      /   .-"-.
.---{     }--|  /,.-'-.,\  |--{     }---.)  (_)_)_)  \_/`~-===-~`\_/  (_(_(_)  (
(                         				))                                     (
'---------------------------------------'
*/