10th 進階班上學期期末考題解

A. 為各位的期末考獻上祝福

這題直接用 long long 或 unsigned long long 都是 NA 59%

正解：

1. 兩數同號，用 unsigned long long
2. 兩數異號，直接 a + b
3. 若
   $a=b=-2^{63}$，需要特判，因為 unsigned long long 裝不下。

code

#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

為了讓各位覺得它有使用的價值，
先給各位看一下 main() 函數裡面的程式碼。

int main() {
	__int128 a, b;
	cin >> a >> b;
	cout << a+b << '\n';
}

是不是很簡短!!!
但是它全部的程式碼卻有點複雜，
有興趣的可以參考看看。

code

#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開始走的話，你只要從起點往回推就不用再把路徑翻轉一次了。

code

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. 一個音符不能跨越兩個小節
   $⟹$ DFS 時要有一個變數 cur 記錄當前拍數
2. 避免有「小數」拍子，可以將每個音節設定為
   $\frac{16n}{m}$ 個十六分音符拍
3. 相對地，
   $k$ 分音符變
   $\frac{16}{k}$ 拍

綜合以上

$3$ 點，我們可以知道 check 機制是：

$cur\le \frac{16n}{m}$

而這個 DFS 可以剪枝，如果當前節拍已經不符音譜規定，

那也不需要繼續遞迴後面的節拍了。

code

#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\mathrm{\%}$ 的 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\ge 0$

AC

先說一下，NA 60% 是給複雜度歪掉的人用的

直接來講如何 AC。

從 NA 40% 的解法可以知道：只差

$w[i]\ne ?$ 的轉移式就 AC 了。

不難理解，其實

$?$ 的轉移式就是把

$\{M,C,Q,S\}$ 的轉移式相加

把他們分開就好。

因此，所有

$DP$ 轉移式如下：

${\displaystyle \{\begin{array}{l}{\displaystyle \{\begin{array}{l}dp[i][j]=0\\ dp[i][j]=dp[i][j]+dp[i-1][j-8]ifj\ge 8\\ dp[i][j]=dp[i][j]+dp[i-1][j-4]ifj\ge 4\\ dp[i][j]=dp[i][j]+dp[i-1][j-2]ifj\ge 2\\ dp[i][j]=dp[i][j]+dp[i-1][j-1]ifj\ge 1\end{array}ifw[i]=?}\\ \\ dp[i][j]=dp[i-1][j-8]if(j\ge 8andw[i]=M)\\ dp[i][j]=dp[i-1][j-4]if(j\ge 4andw[i]=C)\\ dp[i][j]=dp[i-1][j-2]if(j\ge 2andw[i]=Q)\\ dp[i][j]=dp[i-1][j-1]if(j\ge 1andw[i]=S)\\ dp[i][j]=0else\end{array}}$

code_直觀

#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;
}

code_稍微包裝

#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\le p\le 30$，而 int 能儲存的最大值為
   $2^{31}-1$，代表有
   $31$ 個位元可以使用

觀察完以上三點性質後就會發現，
如果以

$0$ 當成偶數，

$1$ 當成奇數，
把每一組數列儲存到一個 int 裡面，
並將兩者取 xor 就可以達到奇偶數相加判斷的效果。

實作

這題因為是區間更新，
所以要處理一下

$r-l\ge 2$ 時的 xor 要怎麼處理。
其實使要記得一個性質

$a$^

$b$^

$a=b$，
也就是只要該數字被 xor 偶數次，
那可以視為沒有被運算過，
所以程式碼可以被這樣實作

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. 再次利用位元運算的性質

針對第一種解法，
其實就是在加上一個布林值來判斷是不是從出界的遞迴的回傳值。
所實作的資料結構如下

code

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$。

整體的程式碼的實作如下

solution1

#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';
		}
	}
}

solution2

#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%

照著題敘一個一個把人砍掉即可

code

#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$ 砍完，人會剩
   $[\frac{p}{2}]$ 人
3. 若
   $p$ 為奇數，則砍完人後，最小編號會變成
   $k+2^r$

如此就可以省去 for 迴圈從

$1$ 跑到

$n$ 的過程。

有趣的是，如果

$2^r$ 用 pow 的話，不僅慢，還可能有精度問題 (他是浮點數)

因此我們可以把

$2^0\sim 2^{30}$ 次方建出來，加快速度。

(由於

$n\in int$ 及第 3. 點證明，因此可以得知

$r\le 30$)

code

#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$

code

#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 水題

code

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\le j⟹C_{m_i}=S_j+F_k+j+m_i-2\times k$
2. $k<j\le m_i⟹C_{m_i}=S_j+F_k+j+m_i-2\times k$
3. $k>m_i\ge j⟹C_{m_i}=S_j+F_k-j-m_i+2\times k$
4. $k>m_i\ge j⟹C_{m_i}=S_j+F_k-j-m_i+2\times k$

分解完就會發現只要判斷

$m_i$ 和

$j$ 之間的關係不會影響答案，
只有

$k$ 為最大或最小會影響，
因此可以將

$m_i$、

$j$ 的部分做預處理，
再利用線段樹針對

$k$ 的大小做查詢就會找到答案。

預處理

其實就是窮舉

$j$ 所有的可能，
並針對每一種可能對

$m_i$ 做查詢。

code

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)$

solution1

#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';
	}
}

實作到這裡會突然意識到一件事，
因為這題根本不需要修改，
所以根本不用用到線段樹

，
直接用單調列隊就可以解了。

Time Complexity:

$O(N+Q)$

solution2

#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跑判斷，可以喇到一些分數。

cout << "YES" <<endl;

NA 90%

喇完55%後可以發現後面的幾乎都是NO，所以你可以再加個判斷

if(K == 1)　cout << "YES" <<endl;
else cout << "NO" << endl;

AC

這次單純是題目出爛，還是要學一下正解怎麼做的

如果你有仔細看題目的話你會發現複雜度的地方很奇怪
再仔細想想的話你會發現，如果前n-1個卡牌都已經決定好是否翻了，若第n-k個卡牌反面的話你就必須要翻第n個卡牌。
所以你只要對前k個卡牌的是否翻的可能性都做一遍，之後就可以不斷地維護左界。

code

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^{k}N)$