# Cheng的競程日記！
###### tags: `C++` `競程` `日記`
:::danger
此筆記由 @Cheng0928 編寫，請尊重作者**著作財產權**
:::
:::danger
因為 @Cheng0928 是 113 會考戰士，暫時停止更新啦！
:::
:::info
## 製作本筆記的初衷
我在準備 2023 TOI初選 跟各種競程比賽時想為自己做過的題目做點紀錄
之前我就有把各個平台我寫過的 AC code 放在 Github 上面，但光看程式碼真的有點難理解
不如把解題思路寫下來吧！
:::
:::spoiler 本文目錄
[TOC]
:::
## Who Am I
我是Cheng，本名叫潘鈺程，是個熱愛競程的國中生！
:::spoiler 興趣
* 打音遊
* 打競程
* 聽音樂
* 寫 code
* 參加各種資訊社群活動
:::
:::spoiler 比賽經歷
* NPSC 2022 國中組 初賽 第十一名
* NPSC 2022 國中組 決賽 第十八名
* AIS3 2023 EOF 參賽
* TOI 2023 初選 參賽
:::
:::spoiler 社群貢獻
* SITCON HoC 2022 台南場助教
* SCINT 北臺灣學生資訊社群負責人
:::
:::spoiler 其他個人資料
* Instagram: Weak._.Cheng0928
* APCS: 觀念3級分(68) / 實作3級分(215)
* 各大OJ暱稱: Cheng0928
* 生日: 2008/09/28
* 感情狀況: 可悲單身
:::
## 解題！
### 枚舉 --- Enumeration
#### 基本題
:::spoiler Matrix Reducing (ABC264 C)
###### tags: `位元枚舉` `矩陣`
給你高為 $H_1$ 寬為 $W_1$ 的矩陣 $A$
高為 $H_2$ 寬為 $W_2$ 的矩陣 $B$
問你是否有辦法將矩陣 $A$ 減少一些行與列來形成B矩陣
這題可利用位元枚舉的技巧來表示要刪減的行或列
AC code
```cpp
#include <bits/stdc++.h>
#define int long long //TLE or MLE remove
#define F first
#define S second
#define Cheng0928 ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define SIZE(a) signed(a.size())
using namespace std;
void sol(){
//freopen("cereal.in", "r", stdin);
//freopen("cereal.out", "w", stdout);
int ha, wa;
cin >> ha >> wa;
vector<vector<int>> A(ha, vector<int>(wa));
for(auto &v : A) for(int &it : v) cin >> it;
int hb, wb;
cin >> hb >> wb;
vector<vector<int>> B(hb, vector<int>(wb));
for(auto &v : B) for(int &it : v) cin >> it;
bool ok = 0;
for(int h = 0; h < (1 << ha); h++){
for(int w = 0; w < (1 << wa); w++){
vector<vector<int>> tmp;
for(int i = 0; i < ha; i++){
if(!((h >> i) & 1)) continue;
vector<int> col;
for(int j = 0; j < wa ; j++){
if((w >> j) & 1) col.push_back(A[i][j]);
}
tmp.push_back(col);
}
if(tmp == B) ok = 1;
}
}
if(ok) cout << "Yes\n";
else cout << "No\n";
}
signed main()
{
Cheng0928
/*int t;
cin >> t;
while(t--)*/ sol();
return 0;
}
```
:::
### 數學 --- Math
#### 基本題
:::spoiler TOI 2022 初選 A. 迷宮入口(TIOJ 2246)
###### tags: `枚舉` `記數`
設 $(u, v)$ 為詠唱的座標
每讀入一個目標點後，去枚舉以此點為中心畫的 $(2r)^2$ 方格中的座標當作 $(u, v)$
因為 $r$ 的範圍只有 $1 \leq r \leq 10$ 所以不會 TLE
那只要去計算符合條件的 $(u, v)$ 有幾個就好了
AC code
```cpp
#include <bits/stdc++.h>
#define int long long //TLE or MLE remove
#define F first
#define S second
#define Cheng0928 ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define SIZE(a) signed(a.size())
using namespace std;
int sqr(int x){
return x*x;
}
void sol(){
//freopen("cereal.in", "r", stdin);
//freopen("cereal.out", "w", stdout);
int n, r;
cin >> n >> r;
map<pair<int,int>, int> cnt;
while(n--){
int x, y;
cin >> x >> y;
for(int dx = -r; dx <= r; dx++){
for(int dy = -r; dy <= r; dy++) if(sqr(dx) + sqr(dy) <= sqr(r)) cnt[{x + dx, y + dy}]++;
}
}
int ans = 0;
for(auto it : cnt){
if(it.S & 1) ans++;
}
cout << ans << '\n';
}
signed main()
{
Cheng0928
/*int t;
cin >> t;
while(t--)*/ sol();
return 0;
}
```
:::
### 位元運算 --- Binary System
#### 基本題
:::spoiler TOI 2021 初選 A. 原始人排序(TIOJ 2193)
###### tags: `自訂排序`
做一個自訂排序函式，先判斷哪個數字的 $1$ 較多
用一個陣列去維護每個數字輸入順序
AC code
```cpp
#include <bits/stdc++.h>
#define int long long //TLE or MLE remove
#define F first
#define S second
#define Cheng0928 ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define SIZE(a) signed(a.size())
using namespace std;
int pos[1025];
bool cmp(int a, int b){
bitset<11> x, y;
x = a, y = b;
//cout << x << ' ' << y <<'\n';
if(x.count() != y.count()) return x.count() < y.count();
return pos[a] < pos[b];
}
void sol(){
//freopen("cereal.in", "r", stdin);
//freopen("cereal.out", "w", stdout);
int n;
cin >> n;
vector<int> vec(n);
int i = 0;
for(int &it : vec) cin >> it, pos[it] = i, i++;
sort(vec.begin(), vec.end(), cmp);
for(auto it = vec.begin(); it != vec.end(); it++) cout << *it << (it != prev(vec.end()) ? ' ' : '\n');
}
signed main()
{
Cheng0928
/*int t;
cin >> t;
while(t--)*/ sol();
return 0;
}
```
:::
### 貪心 --- Greedy
#### 基本題
:::spoiler Contrast (ABC178 F)
給你兩個由小排到大的序列 $A$ 與 $B$
問你是否能排出所有 $A_i \not= B_i$ 的解
從直覺來看，我們可以嘗試把 $B$ 序列反過來，盡可能的讓他們不相同
接下來我用一個範例測資來模擬一次會比較好懂
$A = 1, 2, 2, 2, 3$
$B = 1, 2, 2, 3, 3$
把 $B$ 反過來
$A = 1, 2, 2, 2, 3$
$B = 3, 3, 2, 2, 1$
我們可以發現現在序列分成三個部分
1. $A_1B_1$ 到 $A_2B_2$ ：不相同
2. $A_3B_3$ 到 $A_4B_4$ ：相同
3. $A_5B_5$：不相同
我們要處理的就是 $3$ 到 $4$ 的部分
但要怎麼做呢？我們可以用一個迴圈來跑相同的範圍，對這相同的數值與其他數字進行交換
但要與哪個數字交換？
設相同的數字為 $z$
那我們只要找到滿足 $A_i \not= z$ 或是 $B_i \not= z$ 的位置交換即可
AC code
```cpp
#include "bits/stdc++.h"
#define int long long //TLE or MLE remove
#define F first
#define S second
#define Cheng0928 ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define SIZE(a) signed(a.size())
using namespace std;
bool vailed(int x, int l, int r){
return x > l && x < r;
}
void sol(){
//freopen("cereal.in", "r", stdin);
//freopen("cereal.out", "w", stdout);
int n;
cin >> n;
vector<int> a(n), b(n);
for(int &it : a) cin >> it; for(int &it : b) cin >> it;
reverse(b.begin(), b.end());
int l = 0, r = -1, x;
for(int i = 0; i < n; i++){
if(a[i] == b[i]){
x = a[i];
l = r = i;
while(a[r + 1] == b[r + 1]) r++;
break;
}
}
int ptr = 0;
for(; l <= r; l++, ptr++){
while(a[ptr] == x || b[ptr] == x) ptr++;
if(ptr >= n){
cout << "No\n";
return;
}
swap(b[l], b[ptr]);
}
cout << "Yes\n";
for(int it : b) cout << it << ' ';
}///////
signed main()
{
Cheng0928
/*int t;
cin >> t;
while(t--)*/ sol();
return 0;
}
```
:::
## 競賽心得
## 社群活動心得
## 課程心得
Sign in with Wallet
Connect another wallet