# 2024/11/08 選修期中考
## Scoreboad
:::spoiler **scoreboard**
:::
**一開始先寫掉了 pD**
**然後實作大燒雞pA pB pC**
**最後突然找到BUG**
**然後就三連破 (看起來超像在藏code www)**
## **題目**
### **各題連結**
* **[Sa 中譯](https://hackmd.io/@sa072686/HyI9cP9ZJe)**
* **[pA - AtCoder jsc2019_qual_b - Kleene Inversion](https://atcoder.jp/contests/jsc2019-qual/tasks/jsc2019_qual_b)**
* **[pB - AtCoder abc298_d - Writing a Numeral](https://atcoder.jp/contests/abc298/tasks/abc298_d)**
* **[pC - AtCoder abc147_c - HonestOrUnkind2](https://atcoder.jp/contests/abc147/tasks/abc147_c)**
* **[pD - AtCoder abc283_d - Scope](https://atcoder.jp/contests/abc283/tasks/abc283_d)**
### **pA**
:::success
**題意 :**
**有一長度為 $N$ 的陣列 $A$**
**今天有一長度為 $N \times K$ 的陣列 $B$**
**陣列 $B$ 是陣列 $A$ 循環 $K$ 次**
**求陣列 $B$ 中的 "逆序數對" 有幾個**
$1 \le N \le 2000$
$1 \le K \le 10^9$
:::
::::spoiler **想法 + code**
:::warning
**想法 :**
**乍一看，很像排列組合**
**但其實蠻單純的一題**
**看看 $N$ 的大小可以判斷出來應該是 $N^2$ 的解**
**然後再稍微通靈一下解法 :**
$$
Ans = \sum_{i=1}^n \sum_{j=1}^n
\begin{cases}
0 \quad, & \text{if } a[i] < a[j] \\[10pt]
\frac{k \times (k-1)}{2} +
\begin{cases}
k, & \text{if } i < j \\[5pt]
0, & \text{if } i \geq j
\end{cases}\quad, & \text{if } a[i] > a[j]
\end{cases}
$$
:::
:::danger
**CODE**
```cpp=
#include <iostream>
using namespace std;
const int mod = 1e9+7;
int v[2005];
int main() {
int n, k; cin >> n >> k;
long long ans = 0;
for(int i = 0; i < n; i++) cin >> v[i];
for(int i = 0; i < n; i++)
for(int j = 0; j < n; j++)
if(v[j] < v[i])
ans = (ans%mod + 1ll*(k-1)*k/2%mod + (i < j)*k)%mod;
cout << ans << '\n';
}
```
:::
::::
:::info
**賽後心得 :**
**這題有寫過，所以想說放到最後再來寫**
**結果同樣的思路，範例測資卻錯的很離譜**
**到最後才發現我沒開long long...**
:::
### **pB**
:::success
**有一字串 $S$**
**$S$ 初始為 $1$**
**接著會給你 $Q$ 次操作**
* **操作 1 : 將會輸入一數 $x$，將 $x$ 放到 $S$ 的最後面**
* **操作 2 : 將 $S$ 最前面的數字拿走**
* **操作 3 : 輸出以十進制表示 $S$ 的數字除以 $998244353$ 的餘數**
**$1 \le Q \le 6 \times 10^5$**
**$x \in \{1, 2, 3, 4, 5, 6, 7, 8, 9\}$**
**操作 2 只會在 $S$ 為二位數以上(含)時拿走數字**
:::
::::spoiler **想法 + code**
:::warning
**就簡單的字串處理**
**像是維護 $ans$ 值**
**當有一數 $X$ 加進來的時候，$ans = ans + x \pmod {998244353}$**
**當最前面的數字 $Y$ 拔除時，需要知道他後面的位數個數$Z$，將 $ans$ 維護為 $ans - Y \times 10^Z \pmod {998244353}$**
**小心負數取模**
:::
:::danger
```cpp=
#include <iostream>
#include <vector>
using namespace std;
const int mod = 998244353;
int main() {
int q; cin >> q;
vector<int> v{1}, pre{1};
// v -> 模擬 queue
// pre -> 紀錄10^n，且隨著 queue 大小而變動，所以當要拔除最前面的數時，要得10的冪次剛好在最後面那個元素
int ans = 1, now = 0;
while(q--) {
int c; cin >> c;
if(c == 1) {
int x; cin >> x;
v.push_back(x);
ans = (1ll*ans*10+x)%mod; // 維護元素，記得避免 overflow
pre.push_back(1ll*pre.back()*10%mod); // 將10^n 變為 10^{n+1}，因為數字長度 + 1
} else if(c == 2) {
ans = ((ans-1ll*v[now++]*pre.back())%mod+mod)%mod; // - {最高位} * 10^{那個數字後面的位數個數}
pre.pop_back(); // 將10^n -> 10^{n-1} 因為數字長度縮短
} else cout << ans << '\n';
}
}
```
:::
::::
:::info
**賽後心得 :**
**從開始就卡住的題目**
**丟了4次 WA**
**結果到最後才發現是我的快速冪沒取模**
**:jokerisme:**
:::
### **pC**
:::success
**題意 :**
**有 $N$ 個人**
**其中有會一直說真話的人**
**其他的人有可能會說真話或謊話**
**每個人會說 $A_i$ 句話**
**每句話的格式是 $X_i$ $Y_i$**
**代表 $X_i$ 的那個人是 $Y_i$ (1是會說真話的, 0相反)**
$1 \le N \le 15$
$0 \le A_i \le N-1$
:::
::::spoiler **想法 + code**
:::warning
**想法 :**
**因為 $N$ 超級小，所以合理推斷是枚舉的題目**
**枚舉又有分很多種枚舉方法**
**位元或者遞迴**
**我比較偏向位元**
**雖然位元常數有時候會比較大，但是好寫 哈哈**
:::
:::danger
**CODE :**
**大致上的結構**
```cpp=
#include <iostream>
#include <vector>
using namespace std;
int popcount(int i) {
int re = 0;
while(i) {
re += i&1;
i >>= 1;
}
return re;
}
int main() {
int n; cin >> n;
vector<vector<pair<int, int> > > v(n);
for(int i = 0; i < n; i++) {
int a; cin >> a;
v[i].resize(a);
for(int j = 0; j < a; j++) cin >> v[i][j].first >> v[i][j].second, v[i][j].first--;
}
/* 位元枚舉 */
int ans = 0;
for(int i = 0; i < (1 << n); i++) {
bool ok = true;
for(int j = 0; j < n; j++) if(i & (1 << j)) {
for(int k = 0; k < v[j].size(); k++) if(((i & (1<<v[j][k].first)) > 0) != v[j][k].second) {
/* 矛盾了 */
ok = false;
}
}
if(ok) ans = max(ans, popcount(i));
}
cout << ans << '\n';
}
```
**再運用一些簡單的函式與技巧可以使得code更加簡潔!**
```cpp=
#include <iostream>
#include <vector>
using namespace std;
int main() {
int n; cin >> n;
vector<vector<pair<int, int> > > v(n);
for(int i = 0; i < n; i++) {
int a; cin >> a;
v[i].resize(a);
for(auto &[c, d] : v[i]) cin >> c >> d, c--;
}
int ans = 0;
for(int i = 0; i < (1 << n); i++) {
bool ok = true;
for(int j = 0; j < n; j++) if(i & (1 << j))
for(auto &[a, b] : v[j]) ok = ok && (((i & (1<<a)) > 0) == b);
if(ok) ans = max(ans, __builtin_popcount(i));
}
cout << ans << '\n';
}
```
**__builtin_popcount 好用而且很快!**
:::
::::
:::info
**賽後心得 :**
**更新答案丟錯迴圈 根本輸光**
:::
### **pD**
:::success
**題意 :**
**給你一字串 $S$ 每一個字元代表當次操作內容**
**且你必須符合以下操作原則 :**
* **當字元為 '(' 時 "do nothing"**
* **當字元是小寫字母時 "do nothing"**
* **當字元為 ')' 時請往前找 '('**
**且必須保證在第一次碰到 '(' 之前的這整個字串須符合**
**一種字母只出現一次**
**不會遇到 ')'**
**且一定要找到 '('**
**符合上述規則則 $S$ 被視為"好字串"**
**假如 $S$ 是好字串輸出 "Yes" 反之則輸出 "No"**
$1 \le \vert S \vert \le 3 \times 10^5$
**$S$ 只會有上述所提到的這些字元種類**
:::
::::spoiler **想法 + code**
:::warning
**看到括號匹配問題基本上都要想到stack**
**然後小寫字母的部分有很多種作法**
**位元、bukket、(map、set 後面這兩個可以做，但是吃毒)**
**位元因為很抽象，我愛用**
:::
:::danger
**CODE**
```cpp=
#include <iostream>
#include <vector>
using namespace std;
int main() {
string s; cin >> s;
bool ok = true;
int instk = 0;
vector<char> stk;
for(char &c : s) {
if(c == ')') {
while(stk.back() != '(') {
instk ^= (1<<stk.back()-'a');
stk.pop_back();
}
stk.pop_back();
} else {
stk.push_back(c);
if(isalpha(c)) {
ok = ok && instk>>c-'a'&1^1;
instk |= 1<<c-'a';
}
}
}
cout << (ok ? "Yes" : "No") << '\n';
}
```
:::
::::
:::info
**賽後心得 :**
**把字母判成數字**
**:jokerismeagain:**
:::
## **賽後心得**
### **關於題目**
**整體比賽難度沒有到多難**
**除了第一題的公式 或者是 數字間的關係 很難想**
**其他題目就缺點實作而已**
**但大家好像都沒在刷atcoder**
**對於題目的梗不太了解XD**
### **關於我自己**
**這次實作超級爛**
**每一題都出BUG**
**然後一直都找不出來**
**原本可以20分鐘結束的東西**
**硬生生被搶走了兩個深綠...**
**真的要找時間再穩固一下實作了**
**我是小丑**
Sign in with Wallet
Connect another wallet