0x05 2021 花中一模題解

遊園車

給你一個長度為 \(N\) \(\small(N \le 10^5)\) 的陣列 \(g\) 以及一個長度為 \(K\) \(\small(K \le 100)\) 的權重陣列 \(r\)
你要求出所有可能的平移狀態下的最大連續和
- 選出一個連續子區間使裡面的元素和最大

遊園車 – Subtasks

\([23]\) \(N \le 2\,000\)、所有權重都是 \(1\)
\([29]\) \(N \le 10^5\)、所有權重都是 \(1\)
\([20]\) \(N \le 2\,000\)、\(K \le 100\)
\([24]\) \(N \le 10^5\)、\(K = 1\)
\([\hphantom{0}4]\) \(N \le 10^5\)、\(K \le 100\)

遊園車 – Subtask 2

「每個車廂都有一個擬真度，普通席的擬真度皆為 \(1\)，而特等席各有一個擬真度 \(r_1, r_2, \dots, r_K\)。」
注意到 \(K = 1\) 且 \(r_1 = 1\) 相當於所有席次都可以當作普通席
- 也就是說所有平移的狀況都跟原本一樣
使用雙層 \(\texttt{for}\) 迴圈來回答陣列中的最大連續和

暴力作法

 int max_sum = -1000000; /// 要設定一個足夠小的數字當最大值
for (int i = 1; i <= N; ++i) {
    int sum = 0; /// 計算從 g[i] 開始的和
    for (int j = i; j <= N; ++j) {
        sum += g[j]; /// 計算 g[i..j] 的和
        max_sum = max(max_sum, sum); /// 更新最大值
    }
}

\(\color{red}{\mbox{Wrong Answer}}\ 23/100\)

遊園車 – Subtask 3

這個子題就是經典的最大連續和問題
主要的解法有兩種
- 維護前綴最小值
- Kadane's algorithm

遊園車 – Subtask 3（續）

維護前綴最小值

假設現在固定右界 \(R\)，要怎麼求出以位置 \(R\) 結尾的最大連續和？
先觀察區間和的算式
- \(\sum\limits_{i=l}^{r}{a_i} = \color{red}{\sum\limits_{i=1}^{r}{a_i}} - \color{blue}{\sum\limits_{i=1}^{l-1}{a_i}}\)
- 第一項只跟右界有關
- 第二項只跟左界有關

遊園車 – Subtask 3（續）

維護前綴最小值

先假設你已經計算出所有前綴和 \(S_n = \sum\limits_{i=1}^{n}{a_i}\)
那麼以位置 \(R\) 結尾的最大連續和就是 \(\color{red}{S_R} - \color{blue}{\min\{0, S_1, S_2, \dots S_{R-1}\}}\)
\(S_n\) 跟 \(\color{blue}{\min\{0, S_1, S_2, \dots S_{R-1}\}}\) 都可以一邊計算答案一邊維護

維護前綴最小值

 int max_sum = -1000000;
int prefix_sum = 0, min_prefix_sum = 0; /// 記錄前綴和
for (int i = 1; i <= N; ++i) {
    prefix_sum += g[i];
    max_sum = max(max_sum, prefix_sum - min_prefix_sum);
    min_prefix_sum = min(min_prefix_sum, prefix_sum);
}

\(\color{red}{\mbox{Wrong Answer}}\ 52/100\)

Kadane's algorithm

實際上找最大連續和有一個很簡單的 greedy 作法

 int max_sum = -1000000, sum = 0;
for (int i = 1; i <= N; ++i) {
    sum += g[i];
    // if (sum < 0) sum = 0;
    max_sum = max(max_sum, sum);
    if (sum < 0) sum = 0;
}

每次維護當前前綴的最大後綴和
- 只要 \(> 0\)，繼續加下去一定會更好
- 只要 \(< 0\)，全部都丟掉一定會更好
根據 \(\texttt{if (sum < 0) sum = 0;}\) 的位置可以調整能不能取空區間

遊園車 – Subtask 4

總共有幾種可能的平移方式呢？
- \(N + K\) 種
  - 考慮 \(r_1 \sim r_K\) 對到 \(g_N\)
  - 接著 \(r_K\) 對到 \(g_{N-1} \sim g_1\)
  - 還有一種是完全沒蓋到的
直接暴力平移，配上剛剛 \(O(N)\) 的最大連續和
總複雜度是 \(O(N^2 + NK)\)

\(\color{blue}{\mbox{Time Limit Exceeded}}\ 76/100\)

平移實作

 /// 先令星街列車在 [-(K-1), 0] 的位置 ///
/// 接著每一單位時間往右移動直到完全離開 ///
for (int L = -K+1, R = 0; L <= N; ++L, ++R) {
    vector<int> tmp_g = g; /// 複製一份原本的陣列
    for (int i = max(L, (int)1); i <= min(R, N); ++i)
        tmp_g[i] *= r[i-L]; /// 對他加權
    int sum = 0; /// 使用 Kadane's Algorithm 計算最大連續和
    for (auto x : tmp_g) {
        sum += x;
        mss = max(mss, sum);
        sum = max(sum, 0);
    }
}

遊園車 – Subtask 5

只有一個位置會被修改 \(\rightarrow\) 把陣列切成修改的位置前後兩半
注意到正著做跟反著做會得到一樣的答案
- 先當作陣列空了一個位置，求出前綴跟後綴的答案
- 合併前綴、修改處、後綴的答案

遊園車 – Subtask 5（續）

具體來說，單純求最大連續和的作法基本上都是求出「以當前位置結尾的最大連續和」
不過，只要也考慮到「以當前位置開頭的最大連續和」
- 就是反過來做一遍
就能輕鬆處理只有一個位置被改變的答案了！

遊園車 – Subtask 5（續）

合併之後會有幾種新的值？
- 修改處
- 前綴的最大後綴 + 修改處
- 修改處 + 後綴的最大前綴
- 前綴的最大後綴 + 修改處 + 後綴的最大前綴
好好維護就能拿到這分數

\(\color{red}{\mbox{Wrong Answer}}\ (76 + 20)/100\)

遊園車 – Solution 1

首先，先來加速平移陣列的速度
每次平移都只會影響到至多 \(K+1\) 個數字
- 那麼其實就可以 \(O(K)\) 做到！
其實，只要在需要使用 \(g_p\) 的時候查詢他對應到的 \(r_{id}\) 就好了

遊園車 – Solution 1（續）

一樣，考慮合併之後會出現幾種新的答案
- 修改處的最大連續和
- 前綴的最大後綴 + 修改處的最大前綴
- 修改處的最大後綴 + 後綴的最大前綴
- 前綴的最大後綴 + 修改處的和 + 後綴的最大前綴
這個沒有很好寫，所以它只有 \(4\) 分
好好維護才能拿到這分數

\(\color{lime}{\mbox{Accepted}}\ 100/100\)

遊園車 – 額外注意事項

記得要開 \(\texttt{long long}\)
在對陣列加權時不能直接乘上去除回來
- 遇到 \(r_i = 0\) 就會吃 \(\color{orange}{\mbox{Runtime Error}}\)
選取的區間要非空，不要先把答案歸 \(0\) 再取 \(\max\)

	int tmp[N+1][M+1], score[N+1][M+1];
	int real_N = 0; /// 記錄正常表格的數量
	for (int i = 1; i <= N; ++i) {
	int flag = 0; /// 記錄有沒有個位數不等於十位數
	for (int j = 1; j <= M; ++j) {
	cin >> tmp[i][j];
	if (tmp[i][j] % 10 != (tmp[i][j] / 10) % 10)
	flag = 1;
	}
	if (flag == 1) {
	/// 正常表格 ///
	++real_N;
	for (int j = 1; j <= M; ++j)
	score[real_N][j] = tmp[i][j];
	}
	}

	vector<int> adj[N]; /// adj[i] 裡面存 i 可以到達的所有點
	int depth[N], subsize[N];

	void dfs(int now, int lst) {
	subsize[now] = 1; /// 自己
	for (int x : adj[i]) { /// 遍歷所有相鄰的點
	if (x == lst) continue; /// 如果跟來的點（父親）相同就繼續
	depth[x] = depth[now] + 1; /// 孩子的深度會 + 1
	dfs(x, now);
	subsize[now] += subsize[x]; /// 加上孩子的大小
	}
	}

	int max_sum = -1000000; /// 要設定一個足夠小的數字當最大值
	for (int i = 1; i <= N; ++i) {
	int sum = 0; /// 計算從 g[i] 開始的和
	for (int j = i; j <= N; ++j) {
	sum += g[j]; /// 計算 g[i..j] 的和
	max_sum = max(max_sum, sum); /// 更新最大值
	}
	}

	int max_sum = -1000000;
	int prefix_sum = 0, min_prefix_sum = 0; /// 記錄前綴和
	for (int i = 1; i <= N; ++i) {
	prefix_sum += g[i];
	max_sum = max(max_sum, prefix_sum - min_prefix_sum);
	min_prefix_sum = min(min_prefix_sum, prefix_sum);
	}

	int max_sum = -1000000, sum = 0;
	for (int i = 1; i <= N; ++i) {
	sum += g[i];
	// if (sum < 0) sum = 0;
	max_sum = max(max_sum, sum);
	if (sum < 0) sum = 0;
	}

	/// 先令星街列車在 [-(K-1), 0] 的位置 ///
	/// 接著每一單位時間往右移動直到完全離開 ///
	for (int L = -K+1, R = 0; L <= N; ++L, ++R) {
	vector<int> tmp_g = g; /// 複製一份原本的陣列
	for (int i = max(L, (int)1); i <= min(R, N); ++i)
	tmp_g[i] *= r[i-L]; /// 對他加權
	int sum = 0; /// 使用 Kadane's Algorithm 計算最大連續和
	for (auto x : tmp_g) {
	sum += x;
	mss = max(mss, sum);
	sum = max(sum, 0);
	}
	}

0x05 2021 花中一模 題解

0x05
2021 花中一模
題解