# 2021/6/2 社內賽題解
[TOC]
---
## pA 泡泡與她的小餅乾
**出題者:謝師誠**
- 首殺:潘勁諺
給$a, b$的值，問你$N$有多少種分配方式使$a>b$
其實有兩種做法:$O(1)$數學解 or $O(\log N)$的二分搜
* 數學解
先把$N$全部給$a$，再看$a$多$b$多少，也就是$a-b$的值，令為cou，觀察可知，若cou為奇數，可以有cou/2+1種作法，若為偶數，有cou/2種作法
:::spoiler 數學解
```cpp=
#include<iostream>
using namespace std;
int main()
{
long long a,b,k,t,cou;
cin >> t;
while(t--)
{
cin >> a >> b >> k;
cou = a+k-b;
if(cou <= 0) cout << 0 << '\n';
else if(b+k < a) cout << k+1 << '\n';
else cout << (cou+1)/2 << '\n';
}
return 0;
}
```
:::
## pB 泡泡與她的小石頭
**出題者:謝師誠**
- 首殺:Alan990118
可以發現如果要最大化取的次數，每次要從最多的兩堆去取，而這可以用sort或priority_queue做到(當然也可以直接比三個變數的大小，可是好麻煩喔><)
:::spoiler priority_queue
```cpp=
#include<iostream>
#include<queue>
using namespace std;
int main()
{
int a,b,c,ans;
int tp,tp2;
priority_queue<int> pq;
cin >> a >> b >> c;
if(a) pq.push(a);
if(b) pq.push(b);
if(c) pq.push(c);
ans = 0;
while(pq.size() > 1)
{
ans++;
tp = pq.top();
pq.pop();
tp2 = pq.top();
pq.pop();
tp--;
tp2--;
if(tp > 0) pq.push(tp);
if(tp2 > 0) pq.push(tp2);
}
cout << ans << endl;
return 0;
}
```
:::
## pC 泡泡與她的小迷宮
**出題者:謝師誠**
- 首殺:滅台QQ
這題其實就是走迷宮加上傳送門，可以先bfs走，如果遇到傳送門可選傳或不傳，不傳就繼續bfs，若要傳送就將目的地push進queue裡面。最先走到終點的即為最短路徑
傳送門的部分可以開個vector紀錄位置
```c++=
vector<pair<int,int>> door[26];
```
:::spoiler bfs
```cpp=
#include<iostream>
#include<vector>
#include<queue>
#include<string>
using namespace std;
struct node
{
int x,y;
int time;
};
vector<pair<int,int>> door[26];
string s[2005];
node start,lst;
queue<node> q;
bool vis[2005][2005]; // 紀錄是否來過，若已來過代表這條不是最短路徑
int dx[4] = {1,0,-1,0};
int dy[4] = {0,1,0,-1};
int n;
bool check(int x, int y) // 確認是否能走
{
return x<0 || x>=n || y<0 || y>=n || s[x][y]=='#';
}
void bfs()
{
int i,x,y;
pair<int,int> tps;
node tp,now;
while(!q.empty())
{
now = q.front();
q.pop();
if(now.x == lst.x && now.y == lst.y)
{
cout << now.time << endl;
return; // 找到最短路徑立刻輸出，結束搜尋
}
if(vis[now.x][now.y]) continue;
vis[now.x][now.y] = 1;
for(i=0;i<4;i++) // 嘗試向上下左右走
{
tp.x = now.x + dx[i];
tp.y = now.y + dy[i];
if(check(tp.x,tp.y) || vis[tp.x][tp.y]) continue;
tp.time = now.time + 1;
q.push(tp);
}
if(s[now.x][now.y] >= 'a' && s[now.x][now.y] <= 'z') // 嘗試用傳送門
{
for(int len=door[s[now.x][now.y]-'a'].size(),i=0;i<len;i++)
{
tps = door[s[now.x][now.y]-'a'][i];
if(vis[tps.first][tps.second]) continue;
tp.x = tps.first;
tp.y = tps.second;
tp.time = now.time + 1;
q.push(tp);
}
door[s[now.x][now.y]-'a'].clear();
}
}
cout << -1 << endl; // 找不到路輸出-1
return;
}
int main()
{
int i,k;
node tp;
cin >> n;
for(i=0;i<n;i++)
{
cin >> s[i];
for(k=0;k<n;k++)
{
if(s[i][k] == 'S')
{
start.x = i;
start.y = k;
start.time = 0;
}
else if(s[i][k] >= 'a' && s[i][k] <= 'z')
{
door[s[i][k]-'a'].push_back(make_pair(i,k));
}
}
}
lst.x = n-1;
lst.y = n-1;
q.push(start);
bfs();
return 0;
}
```
:::
## pD 泡泡與迴文小字串
**出題者:謝師誠**
- 首殺:潘勁諺
可以先用string存下輸入，用迴圈判斷是否為迴文:從第$1$個字元與第$n$個開始比對是否為同一字元，再來第$2$個與第$n-1$個$......$，直到第$n/2$個
若前後不同，可以全部改成"a"，花費1，即使前後都不為"a"也是，因為修改成其他字元至少需花2以上。
但本題要注意一件事，最後一次修改不用花時間，因為改完就是迴文了，所以我們讓修改代價最高的最後修改，即可算出最少時間
:::spoiler code
```cpp=
#include <iostream>
#include <string>
#include <algorithm>
using namespace std;
int main() {
int n;
cin >> n;
string s;
cin >> s;
int cost = 0, g = 0;
for(int i = 0; i < n / 2; i++) {
if(s[i] == s[n - i - 1])
continue;
int w = 0;
if(s[i] != 'a')
cost++, w++;
if(s[n - i - 1] != 'a')
cost++, w++;
g = min(g, -w);
}
cout << cost + g << '\n';
}
```
:::
## pE 泡泡與她的小數列
**出題者:謝師誠**
- 首殺:lovemilk_1209
可以觀察到最多只需3次操作即可達成題目要求:
若原本就排列好了 $\rightarrow$ 0次
若最前面$=n$，且最後面$=1$ $\rightarrow$ 3次
若最前面$=n$，或最後面$=1$ $\rightarrow$ 1次
其餘情況 $\rightarrow$ 2次
:::spoiler code
```cpp=
#include<iostream>
using namespace std;
int a[200005];
int main()
{
int n,m,i,k;
bool flag = 1; // 紀錄原本是否就排好
cin >> n;
for(i=0;i<n;i++)
{
cin >> a[i];
if(a[i] != i+1) flag = 0; // 若不等於flag = 0
}
if(flag == 1) cout << 0 << endl;
else if(a[0] == n && a[n-1] == 1) cout << 3 << endl;
else if(a[0] == 1 || a[n-1] == n) cout << 1 << endl;
else cout << 2 << endl;
return 0;
}
```
:::
## pF 泡泡家中的小夢境
**出題者:陳泰穎**
- 首殺: yehray0528 (居然被唬爛掉了 QQ)
### 關鍵想法
有一個不難想的 greedy 就是把所有`MF`都給匹配，然後拿掉。
例如長這樣的話`MMFMFF`，把二跟三配，四跟五配，最後一跟六配。
於是我們可以歸納出`YES`的條件為：
* 對於任一個人，他左邊的`M`數量必須大於等於`F`（否則就會出現有`F`沒有`M`可以配的情況）。
* 總共`M`的數量必須與`F`的數量相等。
### 解法
接下來我們可以考慮一個數列 $a$，並且
$$
a_i=\begin{cases} 1 & ,s_i=M \\ -1 & ,s_i=F \end{cases}
$$
那只要定義前綴和 $S_i$ 代表 $a_1+a_2+a_3+\dots +a_i$，則上述兩個條件會變成：
* $s_i-s_{l-1}\ge 0,\ \forall l\le i\le r$
* $s_r-s_{l-1}=0$
需要扣掉 $s_{l-1}$ 是因為我們只在乎區間內的，要把區間左邊的資訊都拿掉。
#### 如何區間詢問
所有 $i$ 都要滿足第一條，等價於只要有一個 $i$ 不滿足就會是`NO`。
既然只要找一個，那就找 $[l, r]$ 中最小的那個 $i$ 來檢查就好了！
所以就變成把 $S$ 丟進任何一種資結，然後RMQ。
#### 修改
注意到如果把 $a_i$ 給 $+1$，那就等同 $S_i, S_{i+1},\dots,S_n$ 都要 $+1$。
所以把 $s_i$ 從`F`變成`M`相當於區間 $[i, n]$ 都要 $+2$（從 $-1$ 變 $1$），把 $s_i$ 從`M`變成`F`相當於區間 $[i, n]$ 都要 $-2$。
於是修改就會變成區間加值。
能夠區間加值並且 RMQ 的資料結構？線段樹！
#### 事實上
如果把`M`替換成`(`，然後`F`替換成`)`，那這題就會變成詢問是否為合法括號匹配。
### codes
:::spoiler solution
```cpp
#include <iostream>
using namespace std;
const int N = 200025, INF = 100000000;
struct segtree {
int arr[N * 4], tag[N * 4], n;
void init(int _n) {
n = _n;
}
void push(int p) {
arr[p * 2] += tag[p];
tag[p * 2] += tag[p];
arr[p * 2 + 1] += tag[p];
tag[p * 2 + 1] += tag[p];
tag[p] = 0;
}
void edt(int l, int r, int id, int ql, int qr, int v) {
if(r <= ql || qr <= l)
return;
if(ql <= l && r <= qr) {
tag[id] += v;
arr[id] += v;
return;
}
push(id);
int m = (l + r) / 2;
edt(l, m, id * 2, ql, qr, v);
edt(m, r, id * 2 + 1, ql, qr, v);
arr[id] = min(arr[id * 2], arr[id * 2 + 1]) + tag[id];
}
void edt(int l, int r, int v) {
edt(0, n, 1, l, r, v);
}
int query(int l, int r, int id, int ql, int qr) {
if(r <= ql || qr <= l)
return INF;
if(ql <= l && r <= qr)
return arr[id];
push(id);
int m = (l + r) / 2;
return min(query(l, m, id * 2, ql, qr), query(m, r, id * 2 + 1, ql, qr));
}
int query(int l, int r) {
return query(0, n, 1, l, r);
}
} tree;
int arr[N];
int main() {
int n;
string s;
cin >> n >> s;
tree.init(n + 1);
for(int i = 1; i <= n; i++) {
if(s[i - 1] == 'M')
tree.edt(i, n + 1, 1);
else
tree.edt(i, n + 1, -1);
}
int q;
cin >> q;
while(q--) {
int t;
cin >> t;
if(t == 1) {
int p;
cin >> p;
if(s[p - 1] == 'M') {
tree.edt(p, n + 1, -2);
s[p - 1] = 'F';
}
else {
tree.edt(p, n + 1, 2);
s[p - 1] = 'M';
}
}
if(t == 2) {
int l, r;
cin >> l >> r;
r++;
int x = tree.query(l - 1, l);
if(tree.query(l, r) - x >= 0 && tree.query(r - 1, r) - x == 0)
cout << "YES\n";
else
cout << "NO\n";
}
}
}
```
:::
## pG 泡泡與她的彈簧床
**出題者:謝師誠**
### easy
- 首殺: lovemilk_1209
照著題目做，小心實作細節
時間複雜度$O(nq)$
:::spoiler code
```cpp=
#include<iostream>
using namespace std;
int main()
{
int n,q,l,r,k,i,tp,ans;
int a[1005];
cin >> n >> q;
for(i=1;i<=n;i++)
{
cin >> a[i];
}
while(q--)
{
cin >> tp;
if(tp == 1)
{
cin >> l >> r >> k;
ans = 0;
for(i=l;i<=r;i+=k)
{
ans += a[i];
}
cout << ans << endl;
}
else
{
cin >> l >> k;
a[l] = k;
}
}
}
```
:::
### hard
- 首殺: 滅台QQ
注意到$N,Q$的範圍到$2\times10^5$，$O(nq)$一定會TLE
所以要換個方法:
#### 首先思考 $k$ 是定值的話？
我們維護 $k$ 條長度為 $\frac{N}{k}$ 的前綴和，第 $i$ 條代表 $\bmod k = i$ 的所有位置的值的前綴和。
注意到跳的過程中 $\bmod k$ 的值不會動，這樣就是單純的區間和詢問，這裡鍵表複雜度會是 $\mathcal{O}(N)$。
#### $k$ 不是定值
那就得對每個 $k$ 都蓋一個，這樣光建表就要花 $\mathcal{O}(N^2)$ 了。
#### 分塊
每 $M$ 個分一塊，這樣會有 $\frac{N}{M}$ 塊，接下來對於每塊都可以像上面那樣建表，複雜度為$\mathcal{O}(M^2)\cdot \mathcal{O}(\frac{N}M)=\mathcal{O}(NM)$。
詢問時，我們需要遍歷最多全部 $\mathcal{O}(\frac{N}{M})$ 塊，頭尾的兩塊可能需要硬掃，總共的詢問複雜度是 $\mathcal{O}(Q(M+\frac{N}{M}))$。
那修改呢?
可以發現每個查詢的位置$\bmod$ $k$都會是一樣的餘數
所以修改也只要對那一塊的那個餘數做就好了，複雜度會是 $\mathcal{O}(QM)$。
總複雜度為 $\mathcal{O}(NM+Q(M+\frac{N}{M}))$，根據算幾不等式，我們得到在 $M=\sqrt{N}$ 時可以有複雜度 $\mathcal{O}(N\sqrt N + Q\sqrt N)$。
(然後這題好像太難了，不小心放進來了QQ)
::: spoiler code
```cpp=
#include <bits/stdc++.h>
#define int long long
using namespace std;
int n, q, arr[200005], t, l, r, k, v, sqrtn, block[500][500][500], bi[200005];
int nxt(int i, int k)
{
int ti = bi[i];
i += (sqrtn - sqrtn % k);
if(i <= ti * sqrtn) return i + k;
return i;
}
int main()
{
cin >> n >> q;
for (int i = 1; i <= n; i++) cin >> arr[i];
sqrtn = sqrt(n);
for (int i = 1, j = 1; i <= n; j++)
{
for (; i <= min(j * sqrtn, n); i++)
{
bi[i] = j;
for (int k = 1; k < sqrtn; k++)
{
block[j][k][i % k] += arr[i];
}
}
}
for (int i = 1; i <= q; i++)
{
cin >> t;
if (t == 1)
{
int ans = 0;
cin >> l >> r >> k;
int i = l;
if (bi[l] == bi[r] || k >= sqrtn)
{
for (int i = l; i <= r; i += k) ans += arr[i];
}
else
{
for (; i <= min(r, bi[l] * sqrtn); i += k) ans += arr[i];
for (; i <= (bi[r] - 1) * sqrtn; i = nxt(i, k)) ans += block[bi[i]][k][i % k];
for (; i <= r; i += k) ans += arr[i];
}
cout << ans << '\n';
}
else
{
cin >> l >> v;
for (int k = 1; k < sqrtn; k++) block[bi[l]][k][l % k] += (v - arr[l]);
arr[l] = v;
}
}
}
```
:::
Google Drive
Gist
Clipboard
Sign in with Wallet
