###### tags: `tutorial`
# 蛋餅已經在 ISSC 電爆我了 QQ 題解
## 題目背景
總之有點背包問題？一開始還被 `youou` 說題目太簡單了。
Subtask 也幾乎都是亂來的：
- Subtask 1 是 `8e7` 提議說要不要出一個所有拉麵都一樣重的 Subtask，但是好像有更好撈分的所以就這樣吧。
- Subtask 2 理論上是可以枚舉所有子集之類的，但是 Subtask 2 ~ 4 其實都是同一個解法。
- Subtask 5 是卡輸入輸出，防破台用（惡趣味）。
測資也總共才十一筆，希望是沒有人唬爛過的啦 ><
## 題解
### Subtask 1
定位在大家都要拿到的水水分。只要開一個變數數現在總共有幾碗拉麵，詢問時直接看拉麵碗數夠不夠即可。10分Get。
### Subtask 2 ~ 4
考慮 DP， $dp[i][j]$ 代表有前 $i$ 碗拉麵時，重量 $j$ 可不可以湊的出來。
加入一碗重量為 $x$ 拉麵的轉移式： $$dp[i][j] = dp[i-1][j] || dp[i-1][j-x]$$
查詢重量 $x$ 可不可以湊的出來：只要看 $dp[n][x]$ 即可，其中 $n$ 是現在擁有的拉麵總數。
這樣空間、時間複雜度都是 $O(拉麵碗數 \cdot 詢問最大重量 + 詢問次數)$，也就是 $O(nc + KYW)$。
簡單來說，就是不用紀錄價值的 0/1 背包問題。
#### 小技巧：滾動
這題在 dp 得時候可以發現都是從 $i-1$ 轉移，因此不用紀錄 $i < n-1$ 的任何東西。這樣可以把空間複雜度壓成 $O(c)$。扣的大概長這樣：
```cpp=1
bool dp[2][2001];
void modify(int x){
for(int i = x; i <= 2000; ++i){
dp[1][i] = dp[0][i] || dp[0][i - x];
}
for(int i = 0; i <= 2000; ++i){
dp[0][i] = dp[1][i];
}
}
```
或是有空間更小的做法（官解做法），dp[] 只開一維，由大到小轉移，這樣不會拿到已經轉移的資料（詳細內容可以找背包 DP 講師）。扣得如下：
```cpp=1
bool dp[2001];
void modify(int x){
for(int i = 2000 - x; i >= 0; --i)
dp[i + x] |= dp[i];
}
```
值得注意的有兩點：
- 題目沒有保證 $拉麵重量 \leq 2000$。實作時要小心。
- 題目裡其實應該要有特別說明「重量 0 是可以湊得出來的」，可是不知道為什麼沒有修改到 QWQ。有人在賽中因為這件事被卡了，大家要多注意喔。
### Subtask 5
核心做法和之前一樣，差別只在於輸入輸出要使用 `readint()` 和 `puts()`。使用方法介紹在[這裡](https://fhvirus.github.io/posts/io)。
## pA:
問題：給你一個正整數序列A,每次問你如果將A[l,r]翻轉，總和不超過k的最大前綴長度是多少。
### Subtask 1: $KYW = 1$
只有一次詢問，因此把詢問的地方翻轉後一個一個加就會過了。這裡要注意答案可以是0(一個都沒有)或是全部。
### Subtask 2 $n,KYW \leq 2000$
稍微改一下上面的解，每次先做一份新的陣列反轉然後照做(或是反轉處理完之後再把原區間反轉一次得到原陣列)
### Subtask 3 $r - l \leq 10$
這裡就不能硬做了，因為每次跑$O(n)$會炸。因此我們必須在每次詢問之間觀察一些可以保存的資料。
因為所有數字是正整數，前綴和會遞增，而這個問題的答案就有單調性(比那個位置小的前面都比他小)，因此可以用二分搜。
我們紀錄原序列的前綴和，如果答案在反轉的地方外面，就直接對前綴和二分搜就好，否則，我們每次詢問先對[l,r]更新前綴和再搜尋就可以。注意到$r$以後的前綴和不會改變。
### Subtask 4
延續前面的想法，可不可以全部都用二分搜呢？你會發現反轉那段區間在反轉之前也是連續區間，而連續區間的和可以用兩個前綴相減表示，所以我們在二分搜的時候利用原陣列前綴和計算出目前這個位置的前綴和就好了!AC!
~~~cpp
#include <iostream>
#include <algorithm>
#define maxn 1000005
#define ll long long
using namespace std;
int a[maxn];
ll pref[maxn];
int main() {
int n;
cin >> n;
for (int i = 0;i < n;i++) {
cin >> a[i];
pref[i] = a[i] + (i ? pref[i - 1] : 0);
}
int q;
cin >> q;
while (q--) {
int l, r, k;
cin >> l >> r >> k;
int low = -1, up = n, mid;
while (up - low > 1) {
mid = (low + up) / 2;
ll sum = 0;
if (mid < l || mid > r) sum = pref[mid];
else sum = (l ? pref[l - 1] : 0) + pref[r] - (l + r - mid ? pref[l + r - mid - 1] : 0);
//cout << mid << " " << sum << endl;
if (sum <= k) {
low = mid;
} else {
up = mid;
}
}
cout << low + 1 << endl;
}
}
~~~
## pD
這題的定位是全場最難的題目，大家沒有去做我也不太意外，不過仔細看的話可以發現有子問題可以拿的喔!
### Subtask 1：$Ai \leq 0$
換句話說，所有的格子要不然就是停下來的，要不然就是往後，而這也保證了不會出現環(走進去停不下來了)的狀況，只要判走不走得到底。
一個直觀的觀察就是，如果有連續$k$格都會往後走的話，他不管怎麼骰都無法往前。因此只要判這個就好了。
### Subtask 2: $n, k \leq 2000$
這題看到範圍可以猜複雜度是$O(nk)$，所以只要判好正確性照做理論上就會過。
要判斷環的話可以從一個點開始走，走回原本走過的點就是環(有可能原本不是然後走進去的)，我們用一個陣列紀錄走到那個位置會不會繞進環。
之後就像上面一樣BFS。用一個queue維護，遇到環的話就跳掉，否則將他所有可以走到的新的點加進queue。最後只要裡面出現終點的話答案就是YES。
注意：本題不能一遇到環就輸出NO，因為有環不代表走得到環。
### Subtask 3:
由題目名稱可以猜到這題能用$O(n)$做。只是要判很多東西。
首先，判環的部分要更快。先觀察到如果一個點會進入環，那麼他路徑上的所有點都會進入環。因此我們開一個陣列紀錄是不是環，遇到的話就設定沿路上的所有點，遇到已經設定成走進環的也照做。
接著，我們還要預處理不是環的路徑，方法跟前面類似。
最後，在BFS的時候，如果我們在枚舉骰子往前會遇到一個$Ai=0$，那後面就不用再繼續跑。原因是因為目前的點能跑到的地方，下一個$0$一定走得到。
這樣的複雜度是多少呢？好好維護走過的點的話，每個點都只會被處理一次，所以複雜度$O(n)$。
~~~cpp
#include <iostream>
#include <algorithm>
#include <queue>
#include <vector>
#define maxn 1000005
using namespace std;
int a[maxn], to[maxn];
bool vis[maxn], cycle[maxn];
int main() {
int t;
cin >> t;
//cin >> t;
while (t--) {
int n, k;
cin >> n >> k;
for (int i = 0;i < n;i++) {
a[i] = 0, to[i] = -1, vis[i] = 0, cycle[i] = 0;
}
for (int i = 0;i < n;i++) {
cin >> a[i];
}
for (int i = 0;i < n;i++) {
if (to[i] != -1 || cycle[i]) continue;
vector<int> v;
int ind = i, c = 0;
vis[ind] = 1;
v.push_back(ind);
ind += a[ind];
while (a[ind] != 0) {
vis[ind] = 1;
v.push_back(ind);
ind += a[ind];
if (vis[ind]) {
if (to[ind] != -1) {
ind = to[ind];
break;
} else {
c = 1;
break;
}
}
}
if (c) {
for (int i:v) cycle[i] = 1;
} else {
for (int i:v) to[i] = ind;
}
}
for (int i = 0;i < n;i++) vis[i] = 0;
int ans = 0;
queue<int> que;
que.push(0);
while (que.size()) {
int cur = que.front();
que.pop();
vis[cur] = 1;
if (cur == n - 1) {
ans = 1;
break;
}
int poss = 1;
for (int i = cur + 1;i <= min(n - 1, cur + k);i++) {
if (cycle[i]) {
poss = 0;
break;
} else {
if (a[i] == 0) {
if (!vis[i]) {
vis[i] = 1;
que.push(i);
}
break;
} else if (!vis[to[i]]) {
vis[to[i]] = 1;
que.push(to[i]);
}
}
}
if (!poss) {
break;
}
}
if (ans) {
cout << "YES" << "\n";
} else {
cout << "NO" << "\n";
}
}
}
~~~
Sign in with Wallet
Connect another wallet