---
tags: 進階班
---
# 10th 進階班上學期期末考題解
## A. 為各位的期末考獻上祝福
這題直接用 `long long` 或 `unsigned long long` 都是 `NA 59%`
正解：
1. 兩數同號，用 `unsigned long long`
2. 兩數異號，直接 `a + b`
3. 若 $a = b = -2^{63}$，需要特判，因為 `unsigned long long` 裝不下。
:::spoiler `code`
```cpp=
#include<bits/stdc++.h>
#define LL long long
using namespace std;
int main() {
LL a, b;
cin >> a >> b;
if (a < 0 ^ b < 0) cout << a + b;
else {
if (a == b && a == LLONG_MIN) cout << "-18446744073709551616";
else {
unsigned LL pa = abs(a), pb = abs(b);
if (a < 0) cout << '-';
cout << pa + pb;
}
}
return 0;
}
```
:::
另解：
使用毒瘤資料型態 `__int128` :poop:
為了讓各位覺得它有使用的價值，
先給各位看一下 `main()` 函數裡面的程式碼。
```cpp=
int main() {
__int128 a, b;
cin >> a >> b;
cout << a+b << '\n';
}
```
是不是很簡短!!!
但是它全部的程式碼卻有點複雜，
有興趣的可以參考看看。
:::spoiler `code`
```cpp=
#include <bits/stdc++.h>
using namespace std;
namespace int128IO {
istream& operator>>(istream& is, __int128& i) {
string s; is>>s; i = 0;
auto c=s.begin(); c+=(s[0]=='-');
for(; c!=s.end(); ++c) i=i*10+(*c-'0');
if(s[0]=='-') i=-i;
return is;
}
ostream& operator<<(ostream& os, __int128 i) {
string s; bool neg=false; if(i<0) neg=true, i=-i;
while(i) s+=('0'+i%10), i/=10;
if(neg) os<<'-';
for(auto c=s.rbegin();c!=s.rend();++c) os<<*c;
return os;
}
}
using namespace int128IO;
int main() {
__int128 a, b;
cin >> a >> b;
cout << a+b << '\n';
}
```
:::
## B. 迷宮
看到迷宮應該第一個會想到的是`BFS`，而既然題目需要問的是路徑，那麼只要在走的過程中把路徑記錄下來，最後在反推回去就可以得到答案了。
另外有一個小技巧就是如果從`B`開始走的話，你只要從起點往回推就不用再把路徑翻轉一次了。
:::spoiler `code`
```cpp=
pii d[4]{{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
char unpth[4]{'L', 'R', 'U', 'D'};
inline void solve() {
int N, M; cin >> N >> M;
pii st, ed;
bool ch = 1;
vector<vector<pair<char ,int>>> vis(N, vector<pair<char, int>> (M, {' ', -1}));
for(int i = 0 ;i < N; i++)
for(int j = 0; j < M;j++) {
cin >> vis[i][j].f;
if(vis[i][j].f == 'A') st = MP(j, i); // make_pair
if(vis[i][j].f == 'B') ed = MP(j, i), vis[i][j].s = 1;
}
queue<pii> qq;
qq.EP(ed);
while(ch && !qq.empty()) {
pii a = qq.front(); qq.pop();
for(int i = 0; i < 4; i++) {
int mx = a.f + d[i].f;
int my = a.s + d[i].s;
if(mx < 0 || my < 0 || mx == M || my == N) continue;
if(vis[my][mx].f == '#') continue;
if(vis[my][mx].s != -1) continue;
qq.EP(mx, my);
vis[my][mx].s = i;
if(vis[my][mx].f == 'A') {ch = 0; break;}
}
}
if(!ch) {
string s1;
while(st != ed) {
auto a = vis[st.s][st.f];
s1 += unpth[a.s];
st.f -= d[a.s].f; st.s -= d[a.s].s;
}
cout << "YES" << endl << s1.size() << endl << s1;
}
else cout << "NO";
}
```
:::
## C. 持續演奏，直至心願實現
#### NA 10%
很簡單，把整個音譜跑過去，符合規則就是 $1$，不符合就是 $0$
#### NA 20%
暴搜 $w[i] = ?$ 的所有可能性
但是暴搜時，要記得：
1. 一個音符不能跨越兩個小節 $\implies$ `DFS` 時要有一個變數 `cur` 記錄當前拍數
2. 避免有「小數」拍子，可以將每個音節設定為 $\cfrac {16n}{m}$ 個十六分音符拍
3. 相對地，$k$ 分音符變 $\cfrac {16} k$ 拍
綜合以上 $3$ 點，我們可以知道 `check` 機制是：$cur \leq \cfrac{16n}{m}$
而這個 `DFS` 可以剪枝，如果當前節拍已經不符音譜規定，
那也不需要繼續遞迴後面的節拍了。
:::spoiler `code`
```cpp=
#include<bits/stdc++.h>
using namespace std;
constexpr int mod = 1e9 + 7;
int sum = 0, n, m, len, check;
string str;
void dfs(int i, int cur) {
if (i == len && cur == check) {sum++; return;}
cur %= check;
if (str[i] != '?') {
if (str[i] == 'M' && cur + 8 <= check) dfs(i + 1, cur + 8);
else if (str[i] == 'C' && cur + 4 <= check) dfs(i + 1, cur + 4);
else if (str[i] == 'Q' && cur + 2 <= check) dfs(i + 1, cur + 2);
else if (str[i] == 'S' && cur + 1 <= check) dfs(i + 1, cur + 1);
else return;
}
else {
if (cur + 8 <= check) dfs(i + 1, cur + 8);
if (cur + 4 <= check) dfs(i + 1, cur + 4);
if (cur + 2 <= check) dfs(i + 1, cur + 2);
if (cur + 1 <= check) dfs(i + 1, cur + 1);
}
}
int main() {
cin >> n >> m;
cin.get(), cin >> str;
len = str.size(), check = 16 / m * n;
dfs(0, 0), cout << sum;
return 0;
}
```
:::
#### NA 40%
從這裡開始就是使用 `DP` 了
在剛剛的 NA 20% 解中，我們可以發現：當前節拍數 `cur` 是很重要的，
所以我們可以建一個陣列，存下當前音符之下，各種拍數的可能數各為多少。
前 $20\%$ 的 `DP` 測資只有 $?$，所以只要知道 $?$ 的轉移式即可：
$dp[i][j] = dp[i - 1][j - 8] + dp[i - 1][j - 4] + dp[i - 1][j - 2] + dp[i - 1][j - 1]$
$i$ 是指當前第幾音符，$j$ 是指第幾節拍，
但是要注意溢位問題喔！
需判斷 $j - 8,\;j - 4,\;j - 2,\;j - 1\geq 0$
#### AC
先說一下，NA 60% 是給複雜度歪掉的人用的
直接來講如何 AC。
從 NA 40% 的解法可以知道：只差 $w[i]\neq \;?$ 的轉移式就 AC 了。
不難理解，其實 $?$ 的轉移式就是把 $\{M,\;C,\;Q,\;S\}$ 的轉移式相加
把他們分開就好。
因此，所有 $DP$ 轉移式如下：
$\displaystyle \begin{cases} \displaystyle \begin{cases} dp[i][j] = 0\\
dp[i][j] = dp[i][j] + dp[i - 1][j - 8]
\quad\quad if\quad j \geq 8\\
dp[i][j] = dp[i][j] + dp[i - 1][j - 4]
\quad\quad if\quad j \geq 4\\
dp[i][j] = dp[i][j] + dp[i - 1][j - 2]
\quad\quad if\quad j \geq 2\\
dp[i][j] = dp[i][j] + dp[i - 1][j - 1]
\quad\quad if\quad j \geq 1\\
\end{cases}
\quad\quad if\quad w[i] =\;?\\\\
dp[i][j] = dp[i - 1][j - 8]
\quad\quad if\quad (j \geq 8\quad and\quad w[i]=\;M)\\
dp[i][j] = dp[i - 1][j - 4]\quad\quad if\quad (j \geq 4\quad and\quad w[i]=\;C)\\
dp[i][j] = dp[i - 1][j - 2]\quad\quad if\quad (j \geq 2\quad and\quad w[i]=\;Q)\\dp[i][j] = dp[i - 1][j - 1]\quad\quad if\quad (j \geq 1\quad and\quad w[i]=\;S)\\dp[i][j] = 0\quad\quad\quad\quad\quad\;\;\;\quad\quad else \end{cases}$
:::spoiler `code_直觀`
```cpp=
#include<bits/stdc++.h>
#define LL long long
using namespace std;
constexpr int mod = 1e9 + 7;
LL dp[2][145] = {1}; //dp[0][0] = 1, 16 * n / m <= 144
int main() {
int n, m;
cin >> n >> m;
int p = 16 * n / m;
string w; cin >> w;
const int len = w.size();
for (size_t i = 0; i < w.size(); i++) {
for (int j = 1; j <= p; j++) {
if(w[i] == '?'){
dp[~i & 1][j] = 0;
if(j >= 8) dp[~i & 1][j] += dp[i & 1][j - 8];
if(j >= 4) dp[~i & 1][j] += dp[i & 1][j - 4];
if(j >= 2) dp[~i & 1][j] += dp[i & 1][j - 2];
if(j >= 1) dp[~i & 1][j] += dp[i & 1][j - 1];
dp[~i & 1][j] %= mod;
}
else if(w[i] == 'M' && j >= 8)
dp[~i & 1][j] = dp[i & 1][j - 8];
else if(w[i] == 'C' && j >= 4)
dp[~i & 1][j] = dp[i & 1][j - 4];
else if(w[i] == 'Q' && j >= 2)
dp[~i & 1][j] = dp[i & 1][j - 2];
else if(w[i] == 'S' && j >= 1)
dp[~i & 1][j] = dp[i & 1][j - 1];
else dp[~i & 1][j] = 0;
}
dp[~i & 1][0] = dp[~i & 1][p];
}
cout << dp[len & 1][0];
return 0;
}
```
:::
:::spoiler `code_稍微包裝`
```cpp=
#include<bits/stdc++.h>
#define LL long long
using namespace std;
constexpr int mod = 1e9 + 7;
int dp[2][145] = {1}; //dp[0][0] = 1, 16 * n / m <= 144
int main() {
int n, m; const int num[4] = {1, 2, 4, 8};
const string tile = "SQCM";
cin >> n >> m;
int p = 16 * n / m;
string w; cin >> w;
const int len = w.size();
for (size_t i = 0; i < w.size(); i++) {
for (int j = 1; j <= p; j++) {
bool flag = false;
if (w[i] == '?') dp[~i & 1][j] = 0, flag = true;
for (int k = 0; k < 4; k++) {
if (w[i] == tile[k] && j >= num[k]) {
dp[~i & 1][j] = dp[i & 1][j - num[k]];
flag = true; break;
}
else if (w[i] == '?' && j >= num[k]) {
dp[~i & 1][j] += dp[i & 1][j - num[k]];
dp[~i & 1][j] %= mod;
}
}
if (!flag) dp[~i & 1][j] = 0;
}
dp[~i & 1][0] = dp[~i & 1][p], dp[~i & 1][p] = 0;
}
cout << dp[len & 1][0];
return 0;
}
```
:::
## D. 簡單的奇偶問題
### 觀念
這題有三個重點**奇偶數的性質**、**位元運算**和**p的範圍**。
1. **奇偶數的性質**: ($O=odd$、$E=even$)
1. $O+O=E$
2. $O+E=O$
3. $E+O=O$
4. $E+E=E$
2. **位元運算**: (`xor` 的性質)
1. $1$^$1 = 0$
2. $1$^$0 = 1$
3. $0$^$1 = 1$
4. $0$^$0 = 0$
3. **p的範圍**: $1\leq p\leq 30$，而 `int` 能儲存的最大值為 $2^{31}-1$，代表有 $31$ 個位元可以使用
觀察完以上三點性質後就會發現，
如果以 $0$ 當成偶數，$1$ 當成奇數，
把每一組數列儲存到一個 `int` 裡面，
並將兩者取 `xor` 就可以達到奇偶數相加判斷的效果。
### 實作
這題因為是區間更新，
所以要處理一下 $r-l\geq 2$ 時的 `xor` 要怎麼處理。
其實使要記得一個性質 $a$^$b$\^$a = b$，
也就是只要該數字被 `xor` 偶數次，
那可以視為沒有被運算過，
所以程式碼可以被這樣實作
```cpp=
int update(int origin_value, int l, int r, int update_value) { // [l, r]
if((r-l+1)&1)
orgin_value ^= update_value;
return origin_value;
}
```
這時還有另一個問題，
當在查詢時，
如果發生了 `ql > r || l > qr` 的情況，
那要回傳甚麼?
這個問題有兩個解法
1. 直接寫一個新的資料結構
2. 再次利用位元運算的性質
針對第一種解法，
其實就是在加上一個布林值來判斷是不是從出界的遞迴的回傳值。
所實作的資料結構如下
:::spoiler `code`
```cpp=
template<class T> struct Num {
bool NaN; // false -> is NaN
T num;
Num(pair<bool, T> __init) {
NaN = __init.first;
num = __init.second;
}
Num(T __value) {*this = Num({true, __value});}
Num(bool __NaN) {*this = Num({__NaN, T()});}
Num() {*this = Num({false, T()});}
friend Num operator^(const Num a, const Num b) {
return a.NaN||b.NaN ? Num(a.NaN&&b.NaN?a.num^b.num:(a.NaN?a.num:b.num)) : Num(false);
}
bool isNaN() {return !NaN;}
T getV() {return num;}
};
```
:::
第二種解法可以觀察一下位元運算，
1. $0$^$0 = 0$
2. $1$^$0 = 1$
可以看到不管什麼數字 `xor` $0$ 還是原本的數字，
所以可以直接回傳 $0$。
整體的程式碼的實作如下
:::spoiler `solution1`
```cpp=
#include <bits/stdc++.h>
using namespace std;
template<class T> struct Num {
bool NaN; // false -> is NaN
T num;
Num(pair<bool, T> __init) {
NaN = __init.first;
num = __init.second;
}
Num(T __value) {*this = Num({true, __value});}
Num(bool __NaN) {*this = Num({__NaN, T()});}
Num() {*this = Num({false, T()});}
friend Num operator^(const Num a, const Num b) {
return a.NaN||b.NaN ? Num(a.NaN&&b.NaN?a.num^b.num:(a.NaN?a.num:b.num)) : Num(false);
}
bool isNaN() {return !NaN;}
T getV() {return num;}
};
using Int = Num<int>;
const int mxN = 1e5;
struct segtree {
#define lc (id<<1)
#define rc (id<<1|1)
#define mid ((l+r)/2)
int sz;
Int seg[mxN<<2], tag[mxN<<2];
void pull(int id, int l, int r) {
if(l != r) {
seg[id] = seg[lc]^seg[rc];
}
}
void push(int id, int l, int r) {
if(l != r) {
if((mid-l+1)&1)
seg[lc] = seg[lc]^tag[id];
if((r-mid)&1)
seg[rc] = seg[rc]^tag[id];
tag[lc] = tag[lc]^tag[id];
tag[rc] = tag[rc]^tag[id];
}
tag[id] = Int(false);
}
void build(vector<Int>& vt, int id, int l, int r) {
if(l == r) {
seg[id] = vt[l-1];
return;
}
build(vt, lc, l, mid), build(vt, rc, mid+1, r);
pull(id, l, r);
}
Int qry(int id, int l, int r, int ql, int qr) {
push(id, l, r);
if(ql <= l && r <= qr)
return seg[id];
if(ql > r || l > qr)
return Int(false);
return qry(lc, l, mid, ql, qr)^qry(rc, mid+1, r, ql, qr);
}
void upd(int id, int l, int r, int ql, int qr, Int v) {
push(id, l, r);
if(ql <= l && r <= qr) {
if((r-l+1)&1)
seg[id] = seg[id]^v;
tag[id] = tag[id]^v;
return;
}
if(ql > r || l > qr)
return;
upd(lc, l, mid, ql, qr, v), upd(rc, mid+1, r, ql, qr, v);
pull(id, l, r);
}
segtree(int _sz, vector<Int>& vt) {
sz = _sz;
build(vt, 1, 1, sz);
}
Int qry(int ql, int qr) {return qry(1, 1, sz, ql, qr);}
void upd(int ql, int qr, Int v) {upd(1, 1, sz, ql, qr, v);}
#undef lc
#undef rc
#undef mid
};
int calc(Int num, int p) {
int ret = 0, x = num.getV();
for(int i = 0; i < p; ++i) {
if(x&(1<<i))
++ret;
}
return ret;
}
int main() {
cin.tie(0), ios_base::sync_with_stdio(0);
int n, q, p;
cin >> n >> q >> p;
vector<Int> vt(n);
for(auto& num : vt) {
int t = 0;
for(int x, i = 0; i < p; ++i) {
cin >> x;
if(x&1)
t|=(1<<i);
}
num = Int(t);
}
segtree tree(n, vt);
while(q--) {
int o, l, r;
cin >> o;
if(o) {
cin >> l >> r;
int t = 0;
for(int x, i = 0; i < p; ++i) {
cin >> x;
if(x&1)
t|=(1<<i);
}
tree.upd(l, r, t);
} else {
cin >> l >> r;
cout << calc(tree.qry(l, r), p) << '\n';
}
}
}
```
:::
:::spoiler `solution2`
```cpp=
#include <bits/stdc++.h>
using namespace std;
const int mxN = 1e5;
struct segtree {
#define lc (id<<1)
#define rc (id<<1|1)
#define mid ((l+r)/2)
int sz;
int seg[mxN<<2], tag[mxN<<2];
void pull(int id, int l, int r) {
if(l != r) {
seg[id] = seg[lc]^seg[rc];
}
}
void push(int id, int l, int r) {
if(l != r) {
if((mid-l+1)&1)
seg[lc] ^= tag[id];
if((r-mid)&1)
seg[rc] ^= tag[id];
tag[lc] ^= tag[id];
tag[rc] ^= tag[id];
}
tag[id] = 0;
}
void build(vector<int>& vt, int id, int l, int r) {
if(l == r) {
seg[id] = vt[l-1];
return;
}
build(vt, lc, l, mid), build(vt, rc, mid+1, r);
pull(id, l, r);
}
int qry(int id, int l, int r, int ql, int qr) {
push(id, l, r);
if(ql <= l && r <= qr)
return seg[id];
if(ql > r || l > qr)
return 0;
return qry(lc, l, mid, ql, qr)^qry(rc, mid+1, r, ql, qr);
}
void upd(int id, int l, int r, int ql, int qr, int v) {
push(id, l, r);
if(ql <= l && r <= qr) {
if((r-l+1)&1)
seg[id] ^= v;
tag[id] ^= v;
return;
}
if(ql > r || l > qr)
return;
upd(lc, l, mid, ql, qr, v), upd(rc, mid+1, r, ql, qr, v);
pull(id, l, r);
}
segtree(int _sz, vector<int>& vt) {
sz = _sz;
build(vt, 1, 1, sz);
}
int qry(int ql, int qr) {return qry(1, 1, sz, ql, qr);}
void upd(int ql, int qr, int v) {upd(1, 1, sz, ql, qr, v);}
#undef lc
#undef rc
#undef mid
};
int calc(int num) {
int ret = 0;
while(num) {
if(num&1)
++ret;
num >>= 1;
}
return ret;
}
int main() {
cin.tie(0), ios_base::sync_with_stdio(0);
int n, q, p;
cin >> n >> q >> p;
vector<int> vt(n);
for(auto& num : vt) {
int t = 0;
for(int x, i = 0; i < p; ++i) {
cin >> x;
if(x&1)
t|=(1<<i);
}
num = t;
}
segtree tree(n, vt);
while(q--) {
int o, l, r;
cin >> o;
if(o) {
cin >> l >> r;
int t = 0;
for(int x, i = 0; i < p; ++i) {
cin >> x;
if(x&1)
t|=(1<<i);
}
tree.upd(l, r, t);
} else {
cin >> l >> r;
cout << calc(tree.qry(l, r)) << '\n';
}
}
}
```
:::
## E. 金斧頭一砍八
#### NA 60%
照著題敘一個一個把人砍掉即可
:::spoiler `code`
```cpp=
#include<bits/stdc++.h>
using namespace std;
constexpr int mod = 1e9 + 7;
int main() {
int T, n;
cin >> T;
while (T--) {
cin >> n;
bool alive[n + 1];
memset(alive, 1, sizeof(alive));
bool flag = true;
for (int i = 1, tmp = 0; tmp < n - 1; i == n ? i = 1 : i++) {
if (alive[i]) {
flag = !flag;
if (flag) alive[i] = 0, tmp++;
}
}
for (int i = 1; i <= n; i++) {
if (alive[i]) {cout << i << '\n'; break;}
}
}
return 0;
}
```
:::
#### AC
##### solve 1
其實砍人有其規律：
如果把編號 $1\sim n$ 砍完一圈算一輪，
假設現在是第 $r$ 輪，還有 $p$ 人未蹲下，且未蹲下的人中，編號最小的是 $k$，則：
1. 未蹲下的人中，相鄰編號差距為 $2^{r - 1}$
2. 從編號 $1\sim n$ 砍完，人會剩 $[\cfrac p2]$ 人
3. 若 $p$ 為奇數，則砍完人後，最小編號會變成 $k + 2^r$
如此就可以省去 `for` 迴圈從 $1$ 跑到 $n$ 的過程。
有趣的是，如果 $2^r$ 用 `pow` 的話，不僅慢，還可能有精度問題 (他是浮點數)
因此我們可以把 $2^0\sim 2^{30}$ 次方建出來，加快速度。
(由於 $n\in int$ 及第 3. 點證明，因此可以得知 $r\leq 30$)
:::spoiler `code`
```cpp=
#include<bits/stdc++.h>
#define LL long long
#define mem(x) memset(x, 0, sizeof(x))
#define all(x) x.begin(), x.end()
#define f first
#define s second
using namespace std;
constexpr int mod = 1e9 + 7;
int main() {
cin.tie(0), ios_base::sync_with_stdio(false);
int pow[31] = {1};
for(int i = 1; i <= 30; i++) pow[i] = pow[i - 1] * 2;
int T, n;
cin >> T;
while (T--) {
cin >> n;
int k = 1, r = 1;
while (n > 1) {
if (n % 2 == 1) { // if(n & 1)
k += pow[r]; // k += (1 << r)
}
n /= 2, r++; // n >>= 1, r++
}
cout << k << '\n';
}
return 0;
//上方程式碼註解是給進階班的 code，進階班可以不用建表就 AC
}
```
:::
##### solve 2
如果你花了很久的時間找數列的規律，
可以發現答案是：${1}, \{1, 3\}, \{1, 3, 5, 7\}, \{1, 3, 5, 7, 9, 11, 13, 15\}...$
可以轉換成數學式：$(n - 2^{[{\log_2}^n]})\times 2 + 1$
:::spoiler `code`
```cpp=
#include<bits/stdc++.h>
#define LL long long
using namespace std;
constexpr int mod = 1e9 + 7;
int main() {
cin.tie(0), ios_base::sync_with_stdio(false);
int pow[31] = {1};
for (int i = 1; i <= 30; i++) pow[i] = pow[i - 1] * 2;
int T, n;
cin >> T;
while (T--) {
cin >> n;
cout << (n - pow[__lg(n)]) * 2 + 1 << '\n';
//cout << (n - (1 << __lg(n)) << 1 | 1) << '\n';
}
return 0;
//上方程式碼註解是給進階班的 code，進階班可以不用建表就 AC
}
```
:::
## F. 么棟陸砲彈
#### AC
簡化這題題目：給定一陣列，有區間修改和單點查值的操作，輸出查值。
這題既然是區間修改和單點查值，顯然是 `BIT` 水題
:::spoiler `code`
```cpp=
int arr[200001], bit[200001], p;
int lowbit(int x) {return x & -x;}
void build() {
for (int i = 1; i <= p; i++) {
int tmp = i;
while (tmp <= p) bit[tmp] += arr[i], tmp += lowbit(tmp);
}
}
int query(int x) {return x ? bit[x] + query(x - lowbit(x)) : 0;}
void upd(int l, int r, int x) {
while (l <= p) bit[l] += x, l += lowbit(l);
while (r <= p) bit[r] -= x, r += lowbit(r);
}
int main() {
cin.tie(nullptr), ios_base::sync_with_stdio(false);
int q, s, l, r, x;
bool f, op;
cin >> p >> q >> s;
for (int i = 1; i <= p; i++) cin >> arr[i];
for (int i = p; i; i--) arr[i] -= arr[i - 1];
build();
for (int i = q + s; i; i--) {
cin >> op;
if (op) cin >> x, cout << query(x) << '\n';
else cin >> l >> r >> x >> f, upd(l, r + 1, f ? x : x / -4);
}
return 0;
}
```
:::
## G. Gura's Factory
### 觀念
這題的重點就是如何處理
$$ C_{m_i} = (S_j + 1\times |j-k|) + (F_k + 1\times |k-m_i|) $$
這串看起來頗複雜的數學式子。
因為造成數學式子複雜的原因是絕對值，
我們就先討論並分解，
討論時要注意 $k < m_i \wedge k < j$ 和 $k > m_i \wedge k > j$ 的條件。
1. $k < m_i \leq j\implies C_{m_i} = S_j + F_k + j + m_i - 2\times k$
2. $k < j \leq m_i\implies C_{m_i} = S_j + F_k + j + m_i - 2\times k$
3. $k > m_i \geq j\implies C_{m_i} = S_j + F_k - j - m_i + 2\times k$
4. $k > m_i \geq j\implies C_{m_i} = S_j + F_k - j - m_i + 2\times k$
分解完就會發現只要判斷 $m_i$ 和 $j$ 之間的關係不會影響答案，
只有 $k$ 為最大或最小會影響，
因此可以將 $m_i$、$j$ 的部分做預處理，
再利用線段樹針對 $k$ 的大小做查詢就會找到答案。
### 預處理
其實就是窮舉 $j$ 所有的可能，
並針對每一種可能對 $m_i$ 做查詢。
:::spoiler `code`
```cpp=
int s[mxN], f[mxN], ki[mxN], ik[mxN], saj[mxN], smj[mxN]; // ki -> k>i, ik -> i>k, saj -> s+j, smj -> s-j
for(int j = 0; j < n; ++j) {
saj[j] = s[j] + (j+1);
smj[j] = s[j] - (j+1);
}
segtree tsa(saj, n), tsm(smj, n);
for(int k = 1; k <= n; ++k) {
ik[k-1] = ki[k-1] = INT_MAX;
if(k+1 <= n)
ik[k-1] = tsa.qry(k+1, n) + (f[k-1]-2*k);
if(k-1 >= 1)
ki[k-1] = tsm.qry(1, k-1) + (f[k-1]+2*k);
}
```
:::
### 實作
跟預處理的概念一模一樣，
只是這次會給定 $k$ 的值，
所以只要針對該值進行查詢就好。
`Time Complexity`: $O(N\log N + Q\log N)$
:::spoiler `solution1`
```cpp=
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int mxN = 1e5;
int s[mxN], f[mxN], ki[mxN], ik[mxN], saj[mxN], smj[mxN]; // ki -> k>i, ik -> i>k, saj -> s+j, smj -> s-j
struct segtree {
#define lc (id<<1)
#define rc (id<<1|1)
#define mid ((l+r)/2)
int sz;
int seg[mxN<<2];
void pull(int id, int l, int r) {
if(l != r)
seg[id] = min(seg[lc], seg[rc]);
}
void build(int *dt, int id, int l, int r) {
if(l == r) {
seg[id] = dt[l-1];
return;
}
build(dt, lc, l, mid), build(dt, rc, mid+1, r);
pull(id, l, r);
}
segtree(int *dt, int _sz) : sz(_sz) {build(dt, 1, 1, sz);}
int qry(int id, int l, int r, int ql, int qr) {
if(ql <= l && r <= qr)
return seg[id];
if(ql > r || l > qr)
return INT_MAX;
return min(qry(lc, l, mid, ql, qr), qry(rc, mid+1, r, ql, qr));
}
int qry(int ql, int qr) {return qry(1, 1, sz, ql, qr);}
#undef lc
#undef rc
#undef mid
};
int main() {
cin.tie(0), ios_base::sync_with_stdio(0);
int n, q;
cin >> n >> q;
for(int i = 0; i < n; ++i)
cin >> s[i];
for(int i = 0; i < n; ++i)
cin >> f[i];
for(int j = 0; j < n; ++j) {
saj[j] = s[j] + (j+1);
smj[j] = s[j] - (j+1);
}
segtree tsa(saj, n), tsm(smj, n);
for(int k = 1; k <= n; ++k) {
ik[k-1] = ki[k-1] = INT_MAX;
if(k+1 <= n)
ik[k-1] = tsa.qry(k+1, n) + (f[k-1]-2*k);
if(k-1 >= 1)
ki[k-1] = tsm.qry(1, k-1) + (f[k-1]+2*k);
}
segtree tik(ik, n), tki(ki, n);
while(q--) {
int m;
cin >> m;
int q1 = INT_MAX, q2 = INT_MAX;
if(m-1 >= 1)
q1 = tik.qry(1, m-1)+m;
if(m+1 <= n)
q2 = tki.qry(m+1, n)-m;
cout << min(q1, q2) << '\n';
}
}
```
:::
實作到這裡會突然意識到一件事，
因為這題根本不需要修改，
所以根本不用用到線段樹 :poop:，
直接用**單調列隊**就可以解了。
`Time Complexity`: $O(N+Q)$
:::spoiler `solution2`
```cpp=
#include<bits/stdc++.h>
#define LL long long
#define mem(x) memset(x, 0, sizeof(x))
#define all(x) x.begin(), x.end()
#define f first
#define s second
using namespace std;
constexpr int mod = 1e9 + 7;
int n, q, s[100001], f[100001];
vector<int> jk(100002, 2e9), kj(100002, 2e9);
int main() {
cin.tie(nullptr), ios_base::sync_with_stdio(false);
cin >> n >> q;
for (int i = 1; i <= n; i++) cin >> s[i];
for (int i = 1; i <= n; i++) cin >> f[i];
int mi;
for(int i = 1; i <= n; i++){
jk[i] = s[i] + i;
kj[i] = s[i] - i;
}
for(int i = 1; i <= n; i++){
jk[n - i + 1] = min(jk[n - i + 2], jk[n - i + 1]);
kj[i] = min(kj[i - 1], kj[i]);
}
vector<int> pre_k(n + 2, 2e9), suf_k(n + 2, 2e9);
for (int k = 1; k <= n; k++) {
pre_k[k] = kj[k - 1] + 2 * k + f[k]; //mi, j < k
suf_k[k] = jk[k + 1] - 2 * k + f[k]; //k < mi, j
}
for (int i = 1; i <= n; i++) {
suf_k[i] = min(suf_k[i - 1], suf_k[i]);
pre_k[n - i + 1] = min(pre_k[n - i + 2], pre_k[n - i + 1]);
}
while (q--) {
cin >> mi;
cout << min(-mi + pre_k[mi + 1], mi + suf_k[mi - 1]) << '\n';
}
return 0;
}
```
:::
## H. 神奇的卡牌遊戲
### NA 55%
比賽的時候，如果你看到單筆測資，判斷又只有少數個的話，**在競賽容許的情況下**，你可以直接丟判斷，或是用`random`跑判斷，可以喇到一些分數。
```cpp=
cout << "YES" <<endl;
```
### NA 90%
喇完55%後可以發現後面的幾乎都是`NO`，所以你可以再加個判斷
```cpp=
if(K == 1) cout << "YES" <<endl;
else cout << "NO" << endl;
```
### AC
這次單純是題目出爛，還是要學一下正解怎麼做的:poop:
如果你有仔細看題目的話你會發現`複雜度`的地方很奇怪
再仔細想想的話你會發現，如果前`n-1`個卡牌都已經決定好是否翻了，若第`n-k`個卡牌反面的話你就必須要翻第`n`個卡牌。
所以你只要對前`k`個卡牌的是否翻的可能性都做一遍，之後就可以不斷地維護左界。
:::spoiler `code`
```cpp=
void upd(int K, int pos, vector<bool> &vc) {
vc[pos] = !vc[pos];
for (int i = 1; i <= K; i++) {
if (pos + i < int(vc.size())) vc[i + pos] = !vc[i + pos];
if (pos - i >= 0) vc[pos - i] = !vc[pos - i];
}
}
int main () {
int N, K;
cin >> N >> K;
vector<bool> vc(N), cmp;
string st;
cin >> st;
bool ok = false;
for (int i = 0; i < N; i++) vc[i] = (st[i] - '0');
for (int i = 0; i < (1 << K); i++) {
cmp = vc;
for (int j = 0; j < K; j++)
if ((i >> j) & 1) upd(K, j, cmp);
for (int j = K; j < N; j++)
if (!cmp[j - K]) upd(K, j, cmp);
int cnt = 0;
for (auto i : cmp) cnt += i;
if (cnt == N) {ok = true; break;}
}
if (ok) cout << "YES" << endl;
else cout << "NO" << endl;
}
```
:::
複雜度 : $O(2^kN)$
Sign in with Wallet
Connect another wallet