---
tags: SCINT_Activity
description: SCINT 2023聯合程式競賽Q1 題解
---
<!-- # SCINT 聯合程式競賽 #1 題解 -->
:::spoiler 目錄
[TOC]
:::
## 比賽資訊
出題者：<b style="color:gray">Cheng0928</b>、<b style="color:green">lai.abc8660</b>、<b style="color:blue">temmieowo</b>、<b style="color:green">Dada878</b>
驗題者：<b style="color:blue">sakinu080712345</b>、<b style="color:blue">Ststone</b>
Group 連結：[連結](https://scint.contest.codeforces.com/)
新手組連結：[連結](https://codeforces.com/group/Ba2l82Zipr/contest/441755)
進階組連結：[連結](https://codeforces.com/group/Ba2l82Zipr/contest/441758)
---
## 新手組
### [pA 不一般的 a + b ?](https://codeforces.com/group/Ba2l82Zipr/contest/441755/problem/A)
:::spoiler 題目資訊
出題者：<b style="color:gray">Cheng0928</b>
首殺：jaychen0609，00:01
考點：[輸入出](https://emanlaicepsa.github.io/2020/10/26/0-2/)、[資料範圍](https://emanlaicepsa.github.io/2020/10/23/0-1/)
:::
:::spoiler 子題一
照著題目執行即可。
```cpp=
#include <iostream>
using namespace std;
int main(){
// declare
int a, b;
// input
cin >> a >> b;
// output
cout << a+b << endl;
return 0;
}
```
:::
:::spoiler 子題二
可以發現 $a,\ b$ 的最大值可能是 $2^{31}-1$，若兩者相加會大於 C++ 語言中 `int` 的上限，因此得改使用 `long long` 儲存 a 和 b。
```cpp=
#include <iostream>
using namespace std;
int main(){
// declare
long long a, b;
// input
cin >> a >> b;
// output
cout << a+b << endl;
return 0;
}
```
:::
:::spoiler 毒瘤小技巧
不想被卡 `long long`？
把這行加進去你的程式裡面，以下程式會將程式中所使用的 `int` 都替換成 `long long`，此外 main 函式必須使用 `signed` 才不會發生錯誤。
```cpp=
#define int long long
signed main(void){
}
```
:::
### [pB 量子數檢查](https://codeforces.com/group/Ba2l82Zipr/contest/441755/problem/B)
:::spoiler 題目資訊
出題者：<b style="color:blue">temmieowo</b>
首殺：<b style="color:#a0a">kenkenken</b>，00:04
考點：[選擇結構](https://emanlaicepsa.github.io/2020/10/27/0-4/)
:::
:::spoiler 子題一、二
根據題目敘述，可以發現如果所有條件都通過就是合法的量子數，否則是不合法的，這種 **如果... 就... 否則...** 的情況，就可以用選擇結構解決，以下使用的是 if-else 結構。
（子題一為可容錯版本）
```cpp=
#include <bits/stdc++.h>
using namespace std;
int main(){
// declare
int n, l, ml;
double ms;
// input
cin >> n >> l >> ml >> ms;
// output
if (0<n && (0<=l && l<n) && (-l<=ml && ml<=l) && (ms==0.5 || ms==-0.5)){
cout << "Yes" << endl;
}else{
cout << "No" << endl;
}
return 0;
}
```
:::
### [pC 警察抓元元](https://codeforces.com/group/Ba2l82Zipr/contest/441755/problem/C)
:::spoiler 題目資訊
出題者：<b style="color:gray">Cheng0928</b>
首殺：<b style="color:gray">Whale120</b>，00:05
考點：[迴圈結構](https://emanlaicepsa.github.io/2020/11/06/0-8/)
:::
:::spoiler 子題一
可以發現 $N=1$ 的情況，分身即為 $a_1$ 的數值，因此直接輸出即可。
```cpp=
#include <iostream>
using namespace std;
int main(){
// declare
int n, a1;
// input
cin >> n >> a1;
// output
cout << a1 << endl;
return 0;
}
```
:::
:::spoiler 子題二
根據題目敘述，可以發現 $a_i$ 的總和即為答案，對於**有多個變數要輸入**的情況，就可以用迴圈結構解決，以下使用的是 for 迴圈。
```cpp=
#include <iostream>
using namespace std;
int main(){
// declare
int n, ai, total=0; // total 紀錄分身數量
// input
cin >> n;
for (int i=0 ; i<n ; i++){
cin >> ai;
total+=ai;
}
// output
cout << total << endl;
return 0;
}
```
:::
### [pD 機器人操控](https://codeforces.com/group/Ba2l82Zipr/contest/441755/problem/D)
:::spoiler 題目資訊
出題者：<b style="color:green">lai.abc8660</b>
首殺：<b style="color:#a0a">kenkenken</b>，00:57
考點：[選擇結構](https://emanlaicepsa.github.io/2020/10/27/0-4/)、[二維陣列](https://emanlaicepsa.github.io/2020/11/05/0-7/)、實作
:::
:::spoiler 子題一
單純的實作題，照著題目針對每個方向操作即可。
在實作上會有**走到新的座標才要更新計數器**的細節，因此可以透過比對新的座標和舊的座標是否相同來確定有沒有移動過。
```cpp=
#include <iostream>
using namespace std;
int main(){
// declare
int n, m, k, s, t;
int arr[1005][1005];
string op;
int ans=1; // 最終計數器的答案
// input
cin >> n >> m >> k >> s >> t;
for (int i=1 ; i<=n ; i++){
for (int j=1 ; j<=m ; j++){
cin >> arr[i][j]; // 請注意，這裡將數值儲存在 [1, n], [1, m] 的範圍內
}
}
cin >> op;
// process
int now_x=s, now_y=t; // 現在 x, y 的位置
int pre_x=-1, pre_y=-1; // 前一步 x, y 的位置
ans+=arr[now_x][now_y]; // 初始座標也算是新的座標
for (int i=0 ; i<k ; i++){
// 更新舊的位置資訊
pre_x=now_x;
pre_y=now_y;
// 移動機器人
if (op[i]=='U'){
if (now_x-1>=1){ // 確保移動後不會出界
now_x--;
}
}else if (op[i]=='D'){
if (now_x+1<=n){ // 確保移動後不會出界
now_x++;
}
}else if (op[i]=='R'){
if (now_y+1<=m){ // 確保移動後不會出界
now_y++;
}
}else if (op[i]=='L'){
if (now_y-1>=1){ // 確保移動後不會出界
now_y--;
}
}
// 更新答案
if (now_x!=pre_x || now_y!=pre_y){
ans+=arr[now_x][now_y];
}
}
// output
cout << ans << endl;
return 0;
}
```
:::
:::spoiler 子題二
可以發現加上乘法之後，數值很有可能超過 `long long` 的範圍，會使得題目要求的**輸出計數器的數字除以 $10^9+7$ 的餘數**無法執行，
在這裡要提到模運算的性質，對於加法、減法、乘法而言，先做取餘和後做取餘的結果是一樣的，例如：
$5+7 \pmod{3} \equiv (5 \pmod{3} + 7 \pmod{3}) \pmod{3}$
> $(5+7) \div 3$ 餘數等於 $5 \div 3$ 餘數加上 $7 \div 3$ 餘數的結果再除以 $3$ 的餘數
$5 \times 7 \pmod{3} \equiv (5 \pmod{3} \times 7 \pmod{3}) \pmod{3}$
> $(5 \times 7) \div 3$ 餘數等於 $4 \div 3$ 餘數乘上 $7 \div 3$ 餘數的結果再除以 $3$ 的餘數
透過上面的性質可以發現，只要計數器有進行到加法和減法的操作都對計數器取餘，仍然可以達到題目要求。
```cpp=
#include <iostream>
using namespace std;
int main(){
// declare
int n, m, k, s, t;
int arr[1005][1005];
string op;
long long ans=1; // 最終計數器的答案，答案的儲存有可能會超過 int 範圍
// input
cin >> n >> m >> k >> s >> t;
for (int i=1 ; i<=n ; i++){
for (int j=1 ; j<=m ; j++){
cin >> arr[i][j]; // 請注意，這裡將數值儲存在 [1, n], [1, m] 的範圍內
}
}
cin >> op;
// process
int now_x=s, now_y=t; // 現在 x, y 的位置
int pre_x=-1, pre_y=-1; // 前一步 x, y 的位置
if (arr[now_x][now_y]>0){ // 初始座標也算是新的座標
ans+=arr[now_x][now_y];
ans%=1000000007;
}else if (arr[now_x][now_y]<0){
ans*=-arr[now_x][now_y];
ans%=1000000007;
arr[now_x][now_y]=min(-1, arr[now_x][now_y]+1);
}
for (int i=0 ; i<k ; i++){
// 更新舊的位置資訊
pre_x=now_x;
pre_y=now_y;
// 移動機器人
if (op[i]=='U'){
if (now_x-1>=1){ // 確保移動後不會出界
now_x--;
}
}else if (op[i]=='D'){
if (now_x+1<=n){ // 確保移動後不會出界
now_x++;
}
}else if (op[i]=='R'){
if (now_y+1<=m){ // 確保移動後不會出界
now_y++;
}
}else if (op[i]=='L'){
if (now_y-1>=1){ // 確保移動後不會出界
now_y--;
}
}
// 更新答案
if (now_x!=pre_x || now_y!=pre_y){
if (arr[now_x][now_y]>0){
ans+=arr[now_x][now_y];
ans%=1000000007;
}else if (arr[now_x][now_y]<0){
ans*=-arr[now_x][now_y];
ans%=1000000007;
arr[now_x][now_y]=min(-1, arr[now_x][now_y]+1);
}
}
}
// output
cout << ans << endl;
return 0;
}
```
:::
:::spoiler 實作小技巧
可以看到下面的程式碼總共出現了兩次（24、60行）。
```cpp=24
if (arr[now_x][now_y]>0){
ans+=arr[now_x][now_y];
ans%=1000000007;
}else if (arr[now_x][now_y]<0){
ans*=-arr[now_x][now_y];
ans%=1000000007;
arr[now_x][now_y]=min(-1, arr[now_x][now_y]+1);
}
```
這時候建議透過函式來縮減城程式的長度，同時也比較容易維護。
```cpp=
void add(int x, int y){
if (arr[x][y]>0){
ans+=arr[x][y];
ans%=1000000007;
}else if (arr[x][y]<0){
ans*=-arr[x][y];
ans%=1000000007;
arr[x][y]=min(-1, arr[x][y]+1);
}
}
```
此外，如果有大量的模運算，建議使用 `const int` 先儲存該值，可以節省一些常數的時間。
```cpp=
const int MOD=1000000007;
ans%=MOD; // 等價於 ans%=1000000007;
```
:::
### [pE 喪屍病毒 (easy version)](https://codeforces.com/group/Ba2l82Zipr/contest/441755/problem/E)
:::spoiler 題目資訊
出題者：<b style="color:blue">temmieowo</b>
首殺：<b style="color:#a0a">kenkenken</b>，00:19
考點：[前綴和](https://usaco.guide/silver/prefix-sums?lang=cpp)
:::
:::spoiler 子題一
可以發現 $n \times q$ 為 $10^7$，因此可以透過暴力處理每個查詢，時間複雜度：$O(n \times q)$。
```cpp=
#include <iostream>
using namespace std;
int main(){
// declare
int n, q;
string ss[100005];
int l, r, k;
char c;
// input
cin >> n >> q;
for (int i=1 ; i<=n ; i++){
cin >> ss[i]; // 請注意，這裡將字串儲存在 [1, n] 的範圍內
}
// queries
for (int i=0 ; i<q ; i++){
cin >> l >> r >> c >> k;
int ans=0; // 紀錄 [l, r] 的字串裡面有多少個 c
for (int j=l ; j<=r ; j++){
for (int p=0 ; p<ss[j].size() ; p++){
if (ss[j][p]==c) ans++;
}
}
// output
if (ans>=k){
cout << "Yes" << endl;
}else{
cout << "No" << endl;
}
}
return 0;
}
```
:::
:::spoiler 子題二
可以發現題目基本上是求很多區間和的問題，這時候就可以使用**前綴和**這個技巧，將原本枚舉所使用的時間複雜度 $O(q)$ 壓到 $O(1)$。
由於這題只會有一個字元，可以用陣列儲存該基因片段的長度，就可以套前綴和解決此問題。
（如果要獲得 60 分的話得手動分 case 處理）
```cpp=
#include <iostream>
using namespace std;
int main(){
// declare
int n, q;
string ss[100005];
int pre[100005]={0};
int l, r, k;
char c;
// input
cin >> n >> q;
for (int i=1 ; i<=n ; i++){
cin >> ss[i]; // 請注意，這裡將字串儲存在 [1, n] 的範圍內
pre[i]=pre[i-1]+ss[i].size();
}
// queries
for (int i=0 ; i<q ; i++){
cin >> l >> r >> c >> k;
int ans=pre[r]-pre[l-1];
// output
if (k==0 || (c==ss[1][0] && ans>=k)){ // 記得判斷 c 是不是和基因單元相同，如果不相同但是 k=0 也是合法的
cout << "Yes" << endl;
}else{
cout << "No" << endl;
}
}
return 0;
}
```
:::
:::spoiler 子題三
加上了有不同基因單元的限制，可以把基因片段裡的不同基因單元分開處理，也就是轉換成 26 個不同的前綴和陣列，這樣就和子題二一樣了。
```cpp=
#include <iostream>
#include <vector>
using namespace std;
int main(){
// declare
int n, q;
string ss[100005];
vector<vector<int>> pre(26, vector<int>(100005));
int l, r, k;
char c;
// init
for (int i=0 ; i<26 ; i++){
pre[i][0]=0;
}
// input
cin >> n >> q;
for (int i=1 ; i<=n ; i++){
cin >> ss[i]; // 請注意，這裡將字串儲存在 [1, n] 的範圍內
for (int j=0 ; j<26 ; j++){
pre[j][i]=pre[j][i-1];
}
for (int j=0 ; j<ss[i].size() ; j++){
int id=ss[i][j]-'a'; // 該字元的索引值
pre[id][i]++;
}
}
// queries
for (int i=0 ; i<q ; i++){
cin >> l >> r >> c >> k;
int id=c-'a'; // 該字元的索引值
int ans=pre[id][r]-pre[id][l-1];
// output
if (ans>=k){
cout << "Yes" << endl;
}else{
cout << "No" << endl;
}
}
return 0;
}
```
:::
### [pF 廣告遊戲](https://codeforces.com/group/Ba2l82Zipr/contest/441755/problem/F)
:::spoiler 題目資訊
出題者：<b style="color:green">Dada878</b>
首殺：<b style="color:#a0a">kenkenken</b>，00:32
考點：[貪心](https://usaco.guide/bronze/intro-greedy?lang=cpp)
:::
:::spoiler 子題一
透過貪心的想法，可以知道選擇最小的敵人攻擊一定是最好的，因此可以直接將敵人的能力值由小到大排序，再跟著題目操作即可，時間複雜度：$O(n)$。
```cpp=
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
signed main(void){
// declare
int n, m, tmp;
long long p;
int v[100005];
// input
cin >> n >> m >> p;
for (int i=0 ; i<n ; i++){
cin >> v[i];
}
// process
sort(v, v+n);
int ptr=0; // 將要攻擊的敵人
while (ptr<n && p>v[ptr]){
p+=v[ptr];
ptr++;
}
// output
cout << ptr << endl;
return 0;
}
```
:::
:::spoiler 子題二
由於會增加增援軍，可以發現要 `sort` 方式是行不通的，這時候就可以考慮使用動態排序結構例如 `priority_queue` 或是 `multiset` 來操作，時間複雜度：$O(nm\log(n+m))$。
```cpp=
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
using namespace std;
signed main(void){
// declare
int n, m, p, tmp;
int ptr=0, ans=0;
vector<int> c;
priority_queue<int, vector<int>, greater<int>> pq;
vector<pair<int, int>> k;
// input
cin >> n >> m >> p;
for (int i=0 ; i<n ; i++){
cin >> tmp;
pq.push(tmp);
}
for (int i=0 ; i<m ; i++){
cin >> tmp;
c.push_back(tmp);
}
for (int i=0 ; i<m ; i++){
cin >> tmp;
k.push_back({c[i], tmp});
}
// 先將增援軍以出場時間排序
sort(k.begin(), k.end()); // k = vector<pair<int, int>>, <出場時間, 增援軍能力值>
// 只攻擊能力值最小的敵人
while (p>pq.top() && pq.size()){
p+=pq.top();
ans++;
pq.pop();
// 將增援軍加入到 pq 裡面
while (ptr<m && ans==k[ptr].first){
pq.push(k[ptr].second);
ptr++;
}
}
// output
cout << ans << endl;
return 0;
}
```
:::
### [pG 行列式操作](https://codeforces.com/group/Ba2l82Zipr/contest/441755/problem/G)
:::spoiler 題目資訊
出題者：<b style="color:green">lai.abc8660</b>
首殺：<b style="color:#a0a">kenkenken</b>，00:52
考點：[二維陣列](https://emanlaicepsa.github.io/2020/11/05/0-7/)、實作
:::
:::spoiler 子題一
單純的實作題，照著題目針對每個方向操作即可。
對於第二個操作，可以發現 $k$ 即為該行（列）的最小公因數，可以使用內建的 `__gcd()` 函式操作。
```cpp=
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
// declare
int n, q;
int arr[305][305];
int op, rc, x, y;
long long cnt=1;
// function
void f1(){
for (int j=0 ; j<n ; j++){
for (int k=j ; k<n ; k++){
swap(arr[j][k], arr[k][j]);
}
}
}
void f2(){
int k=arr[0][x];
for (int j=0 ; j<n ; j++){
k=__gcd(k, arr[j][x]); // 可以使用內建的求最小公因數函式
}
for (int j=0 ; j<n ; j++){
arr[j][x]/=k;
}
cnt=cnt*k%1000000007;
}
signed main(void){
// input
cin >> n >> q;
for (int i=0 ; i<n ; i++){
for (int j=0 ; j<n ; j++){
cin >> arr[i][j];
}
}
// queries
for (int i=0 ; i<q ; i++){
cin >> op;
if (op==1){
f1();
}else if (op==2){
cin >> rc >> x;
if (rc) f1();
f2();
if (rc) f1();
}
}
// output
cout << cnt << endl;
for (int i=0 ; i<n ; i++){
for (int j=0 ; j<n ; j++){
cout << arr[i][j] << " ";
}
cout << endl;
}
return 0;
}
```
:::
:::spoiler 子題二
對於第三個操作，可以發現 $k$ 即為 $\min\limits_{i=0}^{n} \lfloor \frac{a_{y,\ i}-1} {a_{x,\ i}} \rfloor$，公式中的 $-1$ 是為了確保兩行（列）相減後，不會出現 $0$。
```cpp!
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
// declare
int n, q;
int arr[305][305];
int op, rc, x, y;
long long cnt=1;
// function
void f1(){
for (int j=0 ; j<n ; j++){
for (int k=j ; k<n ; k++){
swap(arr[j][k], arr[k][j]);
}
}
}
void f2(){
int k=arr[0][x];
for (int j=0 ; j<n ; j++){
k=__gcd(k, arr[j][x]); // 可以使用內建的求最小公因數函式
}
for (int j=0 ; j<n ; j++){
arr[j][x]/=k;
}
cnt=cnt*k%1000000007;
}
void f3(){
int k=1000000000;
for (int j=0 ; j<n ; j++){
k=min(k, arr[j][y]/arr[j][x]);
}
bool flag=0;
for (int j=0 ; j<n ; j++){
arr[j][y]-=arr[j][x]*k;
if (arr[j][y]<=0) flag=1;
}
if (flag){
for (int j=0 ; j<n ; j++){
arr[j][y]+=arr[j][x];
}
}
}
signed main(void){
// input
cin >> n >> q;
for (int i=0 ; i<n ; i++){
for (int j=0 ; j<n ; j++){
cin >> arr[i][j];
}
}
// queries
for (int i=0 ; i<q ; i++){
cin >> op;
if (op==1){
f1();
}else if (op==2){
cin >> rc >> x;
if (rc) f1();
f2();
if (rc) f1();
}else if (op==3){
cin >> rc >> x >> y;
if (rc) f1();
f3();
if (rc) f1();
}
}
// output
cout << cnt << endl;
for (int i=0 ; i<n ; i++){
for (int j=0 ; j<n ; j++){
cout << arr[i][j] << " ";
}
cout << endl;
}
return 0;
}
```
:::
---
## 進階組
### [pA 廣告遊戲](https://codeforces.com/group/Ba2l82Zipr/contest/441758/problem/A)
:::spoiler 題目資訊
出題者：<b style="color:green">Dada878</b>
首殺：<b style="color:blue">nicky_</b>，00:05
:::
<br>
**題目同新手組 pF。**
### [pB 密室問題](https://codeforces.com/group/Ba2l82Zipr/contest/441758/problem/B)
:::spoiler 題目資訊
出題者：<b style="color:gray">Cheng0928</b>
首殺：<b style="color:blue">rt200505</b>，00:06
考點：[Flood fill](https://usaco.guide/silver/flood-fill?lang=cpp)
練習題：[Counting Rooms](https://cses.fi/problemset/task/1192)、[Icy Perimeter](http://www.usaco.org/index.php?page=viewproblem2&cpid=895)
:::
:::spoiler 子題一
可以發現當 $m=1$ 的情況下，迷宮會是一個橫排，這時候只要判斷所有的 `P` 之間是否有牆壁即可。
```cpp!
#include <bits/stdc++.h>
using namespace std;
// declare
int n, m;
bool P=false, wall=false, ans=true; // 判斷是否有 P 出現，判斷 P 出現後是否有牆出現，答案
string s;
int main(){
// input
cin >> n >> m >> s;
for (int i=0 ; i<n ; i++){
if (s[i]=='P'){
if (wall==false) P=true;
else ans=false; // 如果兩個 P 之間有牆，則將答案設為 No
}else if (s[i]=='#'){
if (P==true) wall=true; // 如果已經有 P 了，才需要設置 wall
}
}
// output
cout << (ans ? "Yes" : "No") << endl;
return 0;
}
```
:::
:::spoiler 子題二
在 $n=2,\ m=2$ 的情況下，可以發現如果 `P` 出現了 $0,\ 1,\ 3,\ 4$ 次就必定是 `Yes`，因此只要對於 `P` 出現 $2$ 次的情況判斷是否為下面兩種情況即可。
```
P# | #P
#P | P#
```
```cpp!
#include <bits/stdc++.h>
using namespace std;
// declare
int n, m, total_P=0;
string s1, s2;
int main(){
// input
cin >> n >> m >> s1 >> s2;
// process
for (int k=0 ; k<2 ; k++){
if (s1[k]=='P') total_P++;
if (s2[k]=='P') total_P++;
}
// output
if (total_P!=2){
cout << "Yes" << endl;
}else{
if (s1=="#P" && s2=="P#"){
cout << "No" << endl;
}else if (s1=="P#" && s2=="#P"){
cout << "No" << endl;
}else{
cout << "Yes" << endl;
}
}
return 0;
}
```
:::
:::spoiler 子題三
對於這個問題，我們可以先找到第一個人的座標，並透過 DFS 的方式將他所在的密室填滿，以及計算這個密室有多少個 `P`，和原輸入 `P` 的數量比較後即可求解，時間複雜度：$O(nm)$
```cpp!
#include <bits/stdc++.h>
using namespace std;
// declare
int n, m, get_P=0, total_P=0;
string s;
char arr[1005][1005];
bool vis[1005][1005]; // 紀錄是否走過該點
// function
void dfs(int x, int y){
vis[x][y]=1; // 將目前走的該點紀錄已經走過
if (arr[x][y]=='P') get_P++;
// 往四周去填充空間
// 需要判斷三件事：不要出界、不要是牆壁、不要走過已經走過的點
if (x+1<=m && arr[x+1][y]!='#' && vis[x+1][y]==0) dfs(x+1, y);
if (x-1>=1 && arr[x-1][y]!='#' && vis[x-1][y]==0) dfs(x-1, y);
if (y+1<=n && arr[x][y+1]!='#' && vis[x][y+1]==0) dfs(x, y+1);
if (y-1>=1 && arr[x][y-1]!='#' && vis[x][y-1]==0) dfs(x, y-1);
}
int main(){
// init
memset(arr, '#', sizeof(arr)); // 先將地圖設成全部都是牆
// input
cin >> n >> m;
for (int i=1 ; i<=m ; i++){
cin >> s;
for (int j=1 ; j<=n ; j++){
if (s[j-1]=='P') total_P++;
arr[i][j]=s[j-1]; // 請注意，這裡將字元儲存在 [1, m], [1, n] 的範圍內
}
}
// process
for (int i=1 ; i<=m ; i++){
for (int j=1 ; j<=n ; j++){
if (arr[i][j]=='P'){
dfs(i, j);
goto out;
}
}
}
out:;
// output
cout << (get_P==total_P ? "Yes" : "No") << endl;
return 0;
}
```
:::
:::spoiler 實作小技巧
在這種**會移動到不同座標**的時候，可以使用以下的方式簡化程式碼。
這種方式很常出現在這類型的**平面上 DFS / BFS**做使用。
```cpp!
// 以下儲存座標的位移
const int mx[4]={1, 0, -1, 0};
const int my[4]={0, 1, 0, -1};
// function
bool out(int x, int y){
return x<1 || x>m || y<1 || y>n; // 回傳是否出界
}
void dfs(int x, int y){
vis[x][y]=1; // 將目前走的該點紀錄已經走過
if (arr[x][y]=='P') get_P++;
for (int i=0 ; i<4 ; i++){
int new_x=x+mx[i];
int new_y=y+my[i];
if (!out(new_x, new_x) && arr[new_x][new_x]!='#' && vis[new_x][new_y]==0) dfs(new_x, new_y);
}
}
```
:::
### [pC 文民帝國](https://codeforces.com/group/Ba2l82Zipr/contest/441758/problem/C)
:::spoiler 題目資訊
出題者：<b style="color:green">lai.abc8660</b>
首殺：<b style="color:blue">nicky_</b>，00:18
考點：[DP](https://usaco.guide/gold/intro-dp?lang=cpp)（[最大全一矩形](https://www.geeksforgeeks.org/maximum-size-rectangle-binary-sub-matrix-1s/)）
學習資源：[DP]
練習題：[Maximal Square
](https://leetcode.com/problems/maximal-square/)
:::
:::spoiler 子題一
可以發現 $n$ 和 $m$ 的最大值只有 $100$，因此可以透過枚舉所有矩形檢查是否大於 $k$ 的矩形，最後紀錄最大的面積即可，時間複雜度：$O(n^2m^2)$
```cpp!
#include <bits/stdc++.h>
using namespace std;
// declare
int n, m, k, ma=0;
int a[2005][2005];
bool check(int xa, int ya, int xb, int yb){
bool flag=1;
// 檢查矩形是否全部都>=k
for (int i=xa ; i<=xb ; i++){
for (int j=ya ; j<=yb ; j++){
if (a[i][j]<k){
flag=0;
goto end;
}
}
}
end:;
return flag;
}
int main(){
// input
cin >> n >> m >> k;
for (int i=0 ; i<n ; i++){
for (int j=0 ; j<m ; j++){
cin >> a[i][j];
}
}
// process
for (int k=1 ; k<=min(n, m) ; k++){ // 矩形的邊長
for (int i=0 ; i+k-1<n ; i++){ // 矩形的左上頂點
for (int j=0 ; j+k-1<m ; j++){ // 矩形的右下頂點
if (check(i, j, i+k-1, j+k-1)){
ma=max(ma, k);
}
}
}
}
// output
cout << ma*ma << endl;
return 0;
}
```
:::
:::spoiler 子題二
我們可以先定義 $b_{i, j}$ 為 $a_{i,\ j} \geq k$ 的 01 矩陣，那此問題就被轉換成：尋找最大的全一矩形。
對於這個問題可以透過 DP 處理，這是本題的 DP 狀態以及轉移式。
狀態：$dp_{i,\ j} = b_{i,\ j}$ 到左上的最大全一矩形邊長。
轉移式：
$$
dp_{i,\ j} = \begin{cases}
0 &\text{if } i=0\ \text{or } j=0\\
0 &\text{if } b_{i,\ j}=0\\
min(dp_{i-1,\ j},\ dp_{i,\ j-1},\ dp_{i-1,\ j-1}) &\text{otherwise}
\end{cases}
$$
下圖是我們定義的三個矩陣
```cpp!
#include <bits/stdc++.h>
using namespace std;
// declare
int n, m, k, ma=0;
int a[2005][2005], b[2005][2005], dp[2005][2005];
int main(){
// input
cin >> n >> m >> k;
for (int i=1 ; i<=n ; i++){
for (int j=1 ; j<=m ; j++){
cin >> a[i][j]; // 請注意，這裡將字元儲存在 [1, n], [1, m] 的範圍內
b[i][j]=(a[i][j]>=k);
}
}
// process
for (int i=1 ; i<=n ; i++){
for (int j=1 ; j<=m ; j++){
if (b[i][j]==1){
dp[i][j]=min({dp[i-1][j], dp[i][j-1], dp[i-1][j-1]})+1;
ma=max(ma, dp[i][j]);
}else{
dp[i][j]=0;
}
}
}
// output
cout << ma*ma << endl;
return 0;
}
```
:::
### [pD 喪屍病毒 (hard version)](https://codeforces.com/group/Ba2l82Zipr/contest/441758/problem/D)
:::spoiler 題目資訊
出題者：<b style="color:blue">temmieowo</b>
首殺：<b style="color:#ff8c00">becaido</b>，00:26
考點：[BIT](https://usaco.guide/gold/PURS?lang=cpp#solution---dynamic-range-sum-queries)
練習題：[Dynamic Range Sum Queries](https://cses.fi/problemset/task/1648)、[Range Update Queries](https://cses.fi/problemset/task/1651)、[逆序數對](https://tioj.ck.tp.edu.tw/problems/1080)
:::
:::spoiler 子題一
可以發現 $n \times q$ 為 $10^7$，因此可以透過暴力處理每個查詢，時間複雜度：$O(n \times q)$。
```cpp!
#include <bits/stdc++.h>
using namespace std;
// declare
int n, q;
string t, ss[100005];
int op, l, r, k, p;
char c;
int main(){
// input
cin >> n >> q;
for (int i=1 ; i<=n ; i++){
cin >> ss[i]; // 請注意，這裡將字串儲存在 [1, n] 的範圍內
}
// queries
for (int i=0 ; i<q ; i++){
cin >> op;
if (op==1){
// queries
cin >> l >> r >> c >> k;
int ans=0; // 紀錄 [l, r] 的字串裡面有多少個 c
for (int j=l ; j<=r ; j++){
for (int p=0 ; p<ss[j].size() ; p++){
if (ss[j][p]==c) ans++;
}
}
// output
if (ans>=k){
cout << "Yes" << endl;
}else{
cout << "No" << endl;
}
}else{
// update
cin >> p >> t;
ss[p]=t;
}
}
return 0;
}
```
:::
:::spoiler 子題二
**題目同新手組 pE。**
:::
:::spoiler 子題三
這種**動態更新，求區間和**的題目可以使用 BIT 或是線段樹實作，官解是使用較輕量級且常數較小的 BIT 實作。
對於每次的更新先將基因片段裡面的每個基因單元數量統計出來，再進行更新。而對於每次的查詢則是針對查詢的 $c$，直接去找對應的 BIT 即可。
時間複雜度： $O(n \log (n) + q \log (n) )$。
```cpp!
#include <bits/stdc++.h>
using namespace std;
// declare
int n, q;
int cmd, l, r, k, p;
char c;
string s, t;
vector<string> ss(1);
vector<vector<int>> BIT(26, vector<int>(100005));
void update(vector<int> &v, int pos, int val){
for (int i=pos ; i<100005 ; i+=i&-i){
v[i]+=val;
}
}
int query(vector<int> &v, int pos){
if (pos<=0) return 0;
int ret=0;
for (int i=pos ; i>0 ; i-=i&-i){
ret+=v[i];
}
return ret;
}
int main(){
// input
cin >> n >> q;
for (int i=1 ; i<=n ; i++){
cin >> s;
vector<int> cnt(26);
for (auto x : s){
cnt[x-'a']++;
}
for (int j=0 ; j<26 ; j++){
update(BIT[j], i, cnt[j]);
}
ss.push_back(s);
}
// queries
for (int i=0 ; i<q ; i++){
cin >> cmd;
if (cmd==1){
cin >> l >> r >> c >> k;
cout << (query(BIT[c-'a'], r)-query(BIT[c-'a'], l-1)>=k ? "Yes" : "No") << endl;
}else if (cmd==2){
cin >> p >> t;
vector<int> cnt(26);
for (auto x : ss[p]){
cnt[x-'a']--;
}
for (auto x : t){
cnt[x-'a']++;
}
for (int j=0 ; j<26 ; j++){
update(BIT[j], p, cnt[j]);
}
ss[p]=t;
}
}
return 0;
}
```
:::
### [pE 樂透](https://codeforces.com/group/Ba2l82Zipr/contest/441758/problem/E)
:::spoiler 題目資訊
出題者：<b style="color:green">Dada878</b>
首殺：<b style="color:#ff8c00">becaido</b>，00:42
考點：[動態規劃](https://usaco.guide/gold/intro-dp?lang=cpp)
:::
:::spoiler 子題一
由於購買每個方案的價格都相同
所以我們發現只需要每次挑可以選擇最多號碼的方案就可以得到最佳解
因此可以得到一個貪心演算法來解決這個子題
時間複雜度: $O(m)$
空間複雜度: $O(max(m, k))$
```cpp=
#include <bits/stdc++.h>
#define int long long
#define endl "\n"
#define pii pair<int, int>
#define ff first
#define ss second
using namespace std;
signed main() {
ios::sync_with_stdio(0); cin.tie(0);
int n, m, k;
cin >> n >> m >> k;
vector<int> count(k); // 每種樂透可以選幾個號碼
vector<int> price(k); // 每種樂透的價格
for (int i = 0; i < k; i++) cin >> count[i];
for (int i = 0; i < k; i++) cin >> price[i];
vector<int> needs(m); // 每個需要被選擇的號碼
vector<pair<int, int>> plan(k); // 每個購買方案的資料
for (int i = 0; i < k; i++) plan[i] = {price[i], count[i]};
sort(plan.begin(), plan.end(), greater<pii>()); // 可以選最多號碼數量的優先被考慮
for (int i = 0; i < m; i++) cin >> needs[i];
sort(needs.begin(), needs.end());
int ans = 0; // 所需要花費的金額
int last = 0;// 最後被選到的號碼
int idx = 0; // 目前考慮到 needs 的哪一項
for (int i = 0; i < m; i++) {
if (needs[i] <= last) continue; // 如果被選過就跳過
ans += plan[idx].ff;
last = needs[i] + plan[idx++].ss;
}
cout << ans << endl;
}
```
:::
:::spoiler 子題二
根據題目敘述我們可以推導出此 dp 轉換式
$dp[i]$ 為考慮前 $i$ 個數字最少需要花多少錢
$$
dp_i = \begin{cases}
0 &\text{if } i = 0\\
\displaystyle\min_{j=1}^{k} \{dp_{i - \text{c}_j} + \text{p}_j\} &\text{if } \text{i } \in \text{r}\\
dp_{i-1} &\text{otherwise}
\end{cases}
$$
時間複雜度: $O(nm)$
空間複雜度: $O(n)$
```cpp=
#include <bits/stdc++.h>
#define int long long
#define endl "\n"
using namespace std;
int dp[1000005];
bool num[1000005];
signed main() {
ios::sync_with_stdio(0); cin.tie(0);
int n, m, k;
cin >> n >> m >> k;
vector<int> count(k); // 每種樂透可以選幾個號碼
vector<int> price(k); // 每種樂透的價格
for (int i = 0; i < k; i++) cin >> count[i];
for (int i = 0; i < k; i++) cin >> price[i];
for (int i = 0; i <= n; i++) {
dp[i] = 8e18; // 將 dp 每項初始化為 INF
num[i] = false; // 初始化每個號碼為不需要選擇
}
for (int i = 0; i < m; i++) {
int tmp;
cin >> tmp;
num[tmp] = true; // 把所有需要選擇的數字設為 true
}
dp[0] = 0;
for (int i = 1; i <= n; i++) {
if (!num[i]) dp[i] = dp[i-1];
else {
for (int j = 0; j < k; j++) {
// 使用剛剛推導的 DP 式進行轉移
dp[i] = min(dp[i], dp[max(i - count[j], (long long)0)] + price[j]);
}
}
}
cout << dp[n] << endl;
}
```
:::
### [pF 筆記資訊](https://codeforces.com/group/Ba2l82Zipr/contest/441758/problem/F)
:::spoiler 題目資訊
出題者：<b style="color:blue">temmieowo</b>
首殺：<b style="color:#ff8c00">becaido</b>，00:36
考點：[DSU](https://codeforces.com/edu/course/2/lesson/7)
:::
:::spoiler 子題一
對於 $n$ 最大只到 $1000$ 的情況，可以對於每次的查詢直接對目前的筆記做一次 DFS，總時間複雜度是 $O(n^2)$
```cpp!
#include <bits/stdc++.h>
using namespace std;
// declare
int n;
int op, a, x, y, color;
vector<int> id, cc(100005); // 儲存編號, 顏色資訊
vector<vector<int>> G(100005); // 目前儲存的圖
bitset<100005> vis;
// function
int dfs1(int now){ // 回傳 now 連通塊的大小
int ret=1;
vis[now]=1;
for (auto x : G[now]){
if (vis[x]==0){
ret+=dfs1(x);
}
}
return ret;
}
int dfs2(int now){ // 回傳和 color 相同的連通塊大小
int ret=1;
vis[now]=1;
for (auto x : G[now]){
if (vis[x]==0 && cc[x]==color){
ret+=dfs2(x);
}
}
return ret;
}
int main(){
// input
cin >> n;
// queries
for (int i=0 ; i<n ; i++){
cin >> op;
if (op==1){
// add color node
cin >> a >> color;
id.push_back(a);
cc[a]=color;
}else if (op==2){
// add edge
cin >> x >> y;
G[x].push_back(y);
G[y].push_back(x);
}else if (op==3){
// query color
cin >> color;
int ma=0;
vis=0;
for (auto x : id){ // 枚舉目前儲存的所有點
if (cc[x]==color && vis[x]==0){
ma=max(ma, dfs2(x));
}
}
cout << ma << endl;
}else if (op==4){
// query id
cin >> x;
vis=0;
cout << dfs1(x) << endl;
}
}
return 0;
}
```
:::
:::spoiler 子題二
可以用 DSU 來解決這個問題。對於查詢三，可以維護一個 $color$ 數量的 DSU，每個 DSU 都有筆記總數的節點。
如果是相同顏色的筆記再進行相連，否則忽略，在相連的過程中紀錄該顏色的最大值即可。
此外，別忘記加上啟發式合併或是路徑壓縮。
||由於題目設計不良，此題需要先讀入測資後，再對 DSU 的大小進行分配，導致程式碼會變得相當冗長，我很抱歉 ;-;。||
```cpp!
#include <bits/stdc++.h>
using namespace std;
// declare
const int MAX_N = 1e5+5;
const int MAX_COLOR = 500+5;
int n, op, a, b;
struct query{
int op, a, b;
};
vector<query> qq;
int cnt_id=1, cnt_color=1; // 目前數量
map<int, int> conv_id, conv_color; // 將 id 和 color 做離散化
vector<int> color(MAX_N); // 用索引去找顏色
vector<vector<int>> color_dsu, color_sz; // 儲存相同顏色的 dsu, 大小
vector<int> note_dsu, note_sz; // 儲存所有筆記的 dsu, 大小
vector<int> ma_color; // 記錄每個節點的大小, 紀錄該顏色的最大值
// function
int Find(vector<int> &dsu, int x){
if (dsu[x]!=x) dsu[x]=Find(dsu, dsu[x]);
return dsu[x];
}
void Union(vector<int> &dsu, vector<int> &sz, int x, int y){
x=Find(dsu, x);
y=Find(dsu, y);
if (x!=y){
if (sz[x]>sz[y]){
swap(x, y);
}
dsu[x]=y;
sz[y]+=sz[x];
}
}
int main(){
// input
cin >> n;
for (int i=0 ; i<n ; i++){
op=0, a=0, b=0;
cin >> op;
if (op==1){
// 取得節點數跟顏色數
cin >> a >> b;
if (conv_id.find(a)==conv_id.end()){
conv_id[a]=cnt_id;
cnt_id++;
}
if (conv_color.find(b)==conv_color.end()){
conv_color[b]=cnt_color;
cnt_color++;
}
qq.push_back({op, a, b});
}else if (op==2){
cin >> a >> b;
qq.push_back({op, a, b});
}else if (op==3){
cin >> a;
qq.push_back({op, a, b});
}else if (op==4){
cin >> a;
qq.push_back({op, a, b});
}
}
// build
color.resize(cnt_id);
color_dsu.resize(cnt_color, vector<int>(cnt_id));
color_sz.resize(cnt_color, vector<int>(cnt_id));
note_dsu.resize(cnt_id);
note_sz.resize(cnt_id);
ma_color.resize(cnt_id);
// queries
for (int i=0 ; i<n ; i++){
op=qq[i].op;
if (op==1){
// 更新 dsu 資訊
int a=conv_id[qq[i].a];
int c=conv_color[qq[i].b];
color[a]=c;
color_dsu[c][a]=a;
color_sz[c][a]=1;
ma_color[c]=max(ma_color[c], 1);
note_dsu[a]=a;
note_sz[a]=1;
}else if (op==2){
// add edge
int x=conv_id[qq[i].a];
int y=conv_id[qq[i].b];
// 如果相同顏色，則將它們相連
if (color[x]==color[y]){
int nc=color[x]; // now_color
Union(color_dsu[nc], color_sz[nc], x, y);;
ma_color[nc]=max(ma_color[nc], color_sz[nc][Find(color_dsu[nc], x)]); // 更新答案
}
Union(note_dsu, note_sz, x, y);
}else if (op==3){
// query color
int c=conv_color[qq[i].a];
cout << ma_color[c] << endl;
}else if (op==4){
// query index
int x=qq[i].a;
x=conv_id[x];
cout << note_sz[Find(note_dsu, x)] << endl;
}
}
return 0;
}
```
:::
:::spoiler 子題三
可以發現子題二無法通過是因為顏色數量的過多，導致無法一一儲存每個顏色的 DSU，不過可以發現到每個節點只會有一個顏色，根本不需要將所有顏色都進行儲存，只要將顏色相同的節點建成一顆 DSU 樹即可。
```cpp!
#include <bits/stdc++.h>
using namespace std;
// declare
const int MAX_N=100005, MAX_C=100005;
int n;
int op, a, x, y, color;
vector<int> cc(MAX_N); // 顏色資訊
vector<int> dsu1(MAX_N), dsu2(MAX_N); // 相同顏色, 全部筆記
vector<int> sz1(MAX_N), sz2(MAX_N); // 編號的最大連通塊
vector<int> max_color(MAX_C); // 顏色的最大連通塊
// function
int Find(vector<int> &dsu, int x){
if (dsu[x]!=x) return dsu[x]=Find(dsu, dsu[x]);
return dsu[x];
}
void Union(vector<int> &dsu, vector<int> &sz, int x, int y){
x=Find(dsu, x);
y=Find(dsu, y);
if (x!=y){
dsu[x]=y;
sz[y]+=sz[x];
}
}
int main(){
// init
for (int i=0 ; i<MAX_N ; i++){
dsu1[i]=i;
dsu2[i]=i;
sz1[i]=1;
sz2[i]=1;
}
// input
cin >> n;
// queries
for (int i=0 ; i<n ; i++){
cin >> op;
if (op==1){
// add color node
cin >> a >> color;
cc[a]=color;
max_color[color]=max(max_color[color], 1);
}else if (op==2){
// add edge
cin >> x >> y;
if (cc[x]==cc[y]){
Union(dsu1, sz1, x, y);
max_color[cc[x]]=max(max_color[cc[x]], sz1[Find(dsu1, x)]);
}
Union(dsu2, sz2, x, y);
}else if (op==3){
// query color
cin >> color;
cout << max_color[color] << endl;
}else if (op==4){
// query id
cin >> x;
cout << sz2[Find(dsu2, x)] << endl;
}
}
return 0;
}
```
:::
Sign in with Wallet
Connect another wallet