---
# System prepended metadata

title: 2021/6/2 社內賽題解

---

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