# Algorithm Notebook 2（2.1.2026~2.28.2026）

Canonical: https://www.mirstar.net/2026/02/01/alogorithm-notebook-2/
Author: onlymatt
Published: 2026-02-01T14:56:43.000Z
Updated: 2026-10-21T11:21:55.739Z
Categories: Programming, Algorithms
Tags: Algorithm Notes

## CF 266B - Queue at the School (800)
题意：队伍只含 B/G，进行 $t$ 秒；每秒同时把所有 "BG" 变成 "GB"。输出最终队形。
思路：模拟 $t$ 轮；每轮从左到右扫描，遇到 `BG` 交换，并 `i += 2` 跳过下一位，避免本秒重复参与。

```cpp
#include<iostream>
#include<string>
using namespace std;
int main(){
    string s;
    int n,t;
    cin >> n >> t;
    cin >> s;
    while(t--){
        for(int i=0;i<n;){
            if(s[i]=='B'&&s[i+1]=='G'){
                s[i]='G';
                s[i+1]='B';
                i+=2;
            }
            else
                i++;
        }
    }
    cout << s;
    return 0;
}
```

## CF 228A - Is your horseshoe on the other hoof? (800)
题意：给定4个整数，表示4只马蹄铁的颜色，求至少需要换多少只马蹄铁，使得4只马蹄铁颜色都不同。
思路：用 `set` 存颜色，最后 `4 - set.size()` 即为答案。
```cpp
#include<iostream>
#include<set>
using namespace std;
int main(){
    set<int> colors;
    for(int i=1;i<=4;i++){
        int x;
        cin >> x;
        colors.insert(x);
    }
    cout << 4 - colors.size();
    return 0;
}
```

不用set也可以：可以使用排序

```cpp
#include<iostream>
#include<algorithm>
using namespace std;
int main(){
    int a[4];
    for(int i=0;i<4;i++){
        cin >> a[i];
    }
    sort(a,a+4);
    int count=0;
    for(int i=1;i<4;i++){
        if(a[i]==a[i-1])count++;
    }
    cout << count;
    return 0;
}
```

## CF 977B - Two-gram (800)
题意：给定一个字符串，找出出现次数最多的连续两个字符组成的的子串。
思路：遍历字符串，统计每个长度为2的子串出现次数，最后找出出现次数最多的子串。
"最优解":unordered_map 统计频次，遍历字符串时直接更新频次并记录最大值对应的子串。

```cpp
#include<iostream>
#include<string>
#include<unordered_map>
using namespace std;
int main(){
    string s,res;
    unordered_map<string,int> cnt;
    int n,best=-1;
    cin >> n >> s;
    for(int i=0;i<n-1;i++){
        string temp = s.substr(i,2);
        int c = ++cnt[temp];
        if(c>best)best=c,res=temp;
    }
    cout << res;
    return 0;
}
```

也可以使用map

```cpp
#include<iostream>
#include<string>
#include<map>
using namespace std;
int main(){
    string s,res;
    map<string,int> cnt;
    int n,best=0;
    cin >> n >> s;
    for(int i=0;i+1<n;i++)
        cnt[s.substr(i,2)]++;
    for(auto &kv:cnt){
        if(kv.second>best){
            res=kv.first;
            best=kv.second;
        }
    }
    cout << res;
    return 0;
}
```

其中

```cpp
for(auto &kv:cnt){
    if(kv.second>best){
        res=kv.first;
        best=kv.second;
    }
}
```
的部分是现代写法，等价于
```cpp
    for(map<string,int>::iterator it=cnt.begin();it!=cnt.end();it++)
        res=max(res,it->second);
```

## CF 443A - Anton and Letters (800)
题意：给定一个字符串，统计其中不同的小写字母数量。
思路：使用 `set` 存储不同的字母，最后输出 `set.size()` 即为答案。
```cpp
#include<iostream>
#include<string>
#include<set>
#include<cctype>
using namespace std;
int main(){
    string s;
    getline(cin, s); // 读整行，保留逗号和空格
    set<char> a;
    for(char c : s){
        if(c >= 'a' && c <= 'z') a.insert(c);
    }
    cout << a.size();
    return 0;
}
```

可能读题不仔细，没有发现输入字符串中包含逗号和空格，所以需要使用 `getline` 读整行，并在统计时过滤掉非小写字母。
```cpp
cin >> s;
```
这种写法会默认以空格为分隔符，所以只能读到第一个单词，无法处理题目中包含空格的情况。

如果不想使用set，也可以从题目都是小写字母入手，使用一个bool数组记录每个字母是否出现：

```cpp
#include<iostream>
#include<string>
using namespace std;
int main(){
    bool is[26+1]={};
    string s;
    getline(cin,s);
    for(int i=0;i<s.length();i++){
        if('a'<=s[i]&&s[i]<='z')is[s[i]-'a']=true;
    }
    int res=0;
    for(int i=0;i<26;i++){
        if(is[i])res++;
    }
    cout << res;
    return 0;
}
```

注意事项：创建bool数组的时候不要忘记初始化为空，否则默认值可能是true，导致统计结果错误。

## CF 2197B - B.Arrary and Permutation
给定两个数组 $a$ 和 $p$,其中 $p$ 是 $1$ 到 $n$ 的一个排列，判断$a$是不是由$p$通过复制得到的

思路：维护位置数组pos，pos[i]表示数字i在p中的位置。对于a中的每个元素x，检查它在p中的位置pos[x]是否大于上一个元素在p中的位置，如果不是则返回NO。

```cpp
#include<iostream>
#include<vector>
using namespace std;
const int MAXN = 2e5+2;
int n,a[MAXN],b[MAXN],pos[MAXN];
int main(){
    int t;
    cin >> t;
    while(t--){
        cin >> n;
        for(int i=1;i<=n;i++){
            cin >> a[i];
            pos[a[i]]=i;
        }
        for(int i=1;i<=n;i++)
            cin >> b[i];
        
        vector<int> blocks;
        
        for(int i=1;i<=n;i++)
            if(i==1||b[i]==b[i-1])
                blocks.push_back(b[i]);

        bool flag=true;
        for(int i=0;i<blocks.size();i++){
            if(pos[blocks[i]]<pos[blocks[i-1]]){
                flag = false;
                break;
            }           
        }
        cout << (flag?"YES":"NO") << endl;
    }
    return 0;
}
```

## 洛谷 P1042 - 乒乓球（WA 错误复盘）
这题我一开始能过样例，但提交 WA。根因是：

```cpp
#include<iostream>
using namespace std;
const int MAXN = 25*2500+2;
bool w[MAXN]={};
int main(){
    int index=0;
    while(true){
        char c;
        cin >> c;
        if(c=='W')w[index++]=true;
        else if(c=='E')break;
    }
    int f[2]={11,21};
    int w_=0,l_=0;
    for(int k=0;k<2;k++){
        for(int i=0;i<index;i++){
            if (w[i]) w_++;
            else l_++;
            if(max(w_,l_)>=f[k]&&abs(w_-l_)>=2){
                cout<< w_ << ":" << l_ << endl;
                w_=0,l_=0;
            }
        }
        cout << w_ << ":" << l_ << endl << endl;
        w_=0,l_=0;
    }

    return 0;
}
```

- 读入时只在 `W` 时才 `index++`；
- 遇到 `L` 没有入序列，导致后续统计循环 `for(i=0;i<index;i++)` 直接漏掉所有输球记录。

最小反例：输入 `L E`。

- 正确输出应包含 `0:1`；
- 错误写法会输出 `0:0`。

修正要点：`W` 和 `L` 都必须进入序列（只是值不同）。

```cpp
if(c=='W') w[index++]=true;
else if(c=='L') w[index++]=false;
else if(c=='E') break;
```

结论：样例通过不等于逻辑完整，模拟题要先检查“每类输入字符是否都被处理”。

## 洛谷 P2670 - 扫雷游戏 （方法总结）

### 遍历方法
在遍历网格（坐标系）的四周要使用多个$\Delta$坐标，通常为8个方向：
```cpp
int dx[]={-1,-1,-1,0,0,1,1,1},dy[]={-1,0,1,-1,1,-1,0,1};
```
对于每个格子$(x,y)$，可以通过循环访问周围8个格子：
```cpp
for(int k=0;k<8;k++){
    int nx=x+dx[k],ny=y+dy[k];
    // 检查(nx,ny)是否在边界内
    if(nx>=0&&nx<n&&ny>=0&&ny<m){
        // 处理(nx,ny)格子
    }
}
```

### 边界处理

- 1. **直接检查边界**：在访问周围格子时，先检查坐标是否越界。
- 2. **添加边界保护**：在原始网格外围添加一圈哨兵（如全0或全-1），这样访问周围格子时就不需要每次都检查边界，简化代码逻辑。本题中可以直接使用一个更大的数组，初始化为0，输入时从1开始填充，这样访问周围格子时就不会越界。属于一种“偷懒”技巧，适合竞赛中快速实现。

## 高精度专题复盘（P1303 / P1009）

这几天重点复盘了高精度乘法与运算符重载，踩坑主要集中在“下标、进位、const、累加方式”。

### 1) 乘法累加一定是 `+=`，不能写成 `=`

高精度乘法里，很多项会落在同一位：

```cpp
c[i + j - 1] += a[i] * b[j];
```

如果写成 `=`，会把之前累积值覆盖，结果会明显偏小。

### 2) 进位传播也要用 `+=`

在 `flatten()` 里：

```cpp
a[i+1] += a[i] / 10;
a[i] %= 10;
```

如果写成 `a[i+1] = a[i] / 10`，同样会覆盖原值，导致高位丢失。

### 3) `const Bigint&` 需要 `const` 版下标运算符

当运算符写成：

```cpp
Bigint operator+(const Bigint& a, const Bigint& b)
```

访问 `a[i]`、`b[i]` 时会要求只读成员函数，因此要补：

```cpp
int operator[](int i) const { return a[i]; }
```

否则会出现 *passing 'const Bigint' as 'this' argument discards qualifiers*。

### 4) `Bigint(0)` 的长度要处理好

构造函数遇到 `x=0` 时，建议保证 `len=1` 且 `a[1]=0`，否则可能出现空输出。

### 5) `fac * i` 合法的原因

因为有构造函数 `Bigint(int x=0)`，编译器会把 `i` 隐式转换成 `Bigint(i)`，再调用 `operator*(Bigint, Bigint)`。

---

### 最终体会

高精度题不难在思路，难在细节一致性。只要固定：

- 位序（低位在前还是高位在前）
- 下标起点（0-based 或 1-based）
- 所有“累加”场景都用 `+=`

代码稳定性就会明显提升。

## 洛谷 P1007 - 魔法少女Scarlet

题意：给定m个操作，旋转矩阵中的子矩阵

思路：模拟每个操作，旋转子矩阵。旋转时可以使用一个临时数组存储当前子矩阵的值，然后按照旋转规则重新赋值回原矩阵。

```cpp
#include<iostream>
using namespace std;
const int MAXN = 500 + 5;
int a[MAXN][MAXN];
int b[MAXN][MAXN];
int main(){
    int n,m;
    cin >> n >> m;
    int cnt = 1;
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= n; j++)
            a[i][j] = cnt++;
    while(m--){
        int x,y,r,z;
        cin >> x >> y >> r >> z;
        for(int i = x-r; i <= x+r; i++)
            for(int j = y-r; j<= y+r; j++)
                if (!z) b[x+j-y][y+x-i] = a[i][j];
                else b[x+y-j][y-x+i] = a[i][j];
        for(int i = x-r; i <= x+r; i++)
            for(int j = y-r; j<= y+r; j++)
               a[i][j] = b[i][j];
    }
    for(int i = 1; i <= n; i++){
        for(int j = 1; j<= n; j++)
            cout << a[i][j] << " ";
        cout << endl;
    }
    return 0;
}
```

寻找这个映射关系的过程还是很曲折的，我在纸上画了很多例子，最终由向量分解得到了结果：

- 顺时针：$(i,j) \to (x+j-y, y+x-i)$
- 逆时针：$(i,j) \to (x+y-j, y-x+i)$

线代本质：

$$\begin{bmatrix}
i-x \\
j-y
\end{bmatrix} \to
\begin{bmatrix} 0 & 1 \\ -1 & 0 \end{bmatrix}
\begin{bmatrix}i-x \\
j-y\end{bmatrix} =
\begin{bmatrix}j-y \\
x-i\end{bmatrix}$$

## 洛谷 P1328 生活大爆炸版石头剪刀布

题意：给定两个人的出拳序列，统计每个人赢了多少次。

难点在于如何判断谁赢了，有两种方法：

- 写一个win函数用大量的if-else判断每种情况（难点在于可能会忘记在表格的另一边取反）；
- 使用一个映射关系，构造一个二维数组或哈希表，直接查询结果。（矩阵形式）

```cpp
#include<iostream>
using namespace std;
const int MAXN = 200 + 5;


//原方法（递归判定，保留对比）：
bool win_old(int a, int b){
    if (a == 0){
        if (b == 2 || b == 3) return true;
        if (b == 1 || b == 4) return false;
        else return !win_old(b,a);
    }
    if(a == 1){
        if (b == 2 || b == 4) return false;
        if (b == 3) return true;
        else return !win_old(b,a);
    }
    if(a == 2){
        if (b == 4) return true;
        if (b == 3) return false;
        else return !win_old(b,a);
    }
    if(a == 3){
        if(b == 4) return true;
        else return !win_old(b,a);
    }
    if(a == 4) return !win_old(b,a);
    return false;
}


// 对比版：查表法（更稳，避免递归漏判）
// 0:剪刀 1:石头 2:布 3:蜥蜴人 4:斯波克
// winTable[x][y] = 1 表示 x 赢 y；0 表示 x 不赢 y（平局或输）
int winTable[5][5] = {
    {0, 0, 1, 1, 0},
    {1, 0, 0, 1, 0},
    {0, 1, 0, 0, 1},
    {0, 0, 1, 0, 1},
    {1, 1, 0, 0, 0}
};

int a[MAXN],b[MAXN];

int main(){
    int n,na,nb;
    cin >> n >> na >> nb;
    for(int i = 1; i <= na; i++)
        cin >> a[i];
    for(int i = 1; i <= nb; i++)
        cin >> b[i];
    int i = 1, j = 1;
    int res_a = 0, res_b = 0;
    while(n--){
        if(i > na) i = 1;
        if(j > nb) j = 1;
        if(a[i] == b[j]){
            i++, j++;
            continue;
        }
        if(winTable[a[i]][b[j]]) res_a++;
        else res_b++;
        i++, j++;
    }
    cout << res_a << " " << res_b;
    return 0;
}
```
## 洛谷 P1598 [USACO03FEB] 垂直柱状图

题意：输入四行只包含大写字符的字符串，输出一个垂直柱状图，每列对应一个字符，柱子高度等于该字符在四行中出现的次数。

思路：统计每个字符出现的次数，找到最大值作为柱状图的高度，然后从上到下输出柱状图。

```cpp
#include<iostream>
#include<string>
#include<algorithm>
using namespace std;
string s1, s2, s3, s4;
const int MAXN = 26 + 2;
int cnt[MAXN];
int main(){
    getline(cin, s1);
    getline(cin, s2);
    getline(cin, s3);
    getline(cin, s4);
    auto s = s1 + s2 + s3 + s4;
    for(int i = 0; i < s.length(); i++){
        if(s[i] >= 'A' && s[i] <= 'Z')
            cnt[s[i]-'A']++;
    }
    int height = 0;
    for(int i = 0; i <= 26 - 1; i++)
        height = max(height, cnt[i]);
    
    for(int i = 0; i < height; i++){
        for(int j = 0; j <= 26 - 1; j++){
            if(j!=0) cout << " ";
            if(cnt[j] >= height - i) cout << "*";
            else cout << " ";
        }
        cout << endl;
    }
    cout << "A B C D E F G H I J K L M N O P Q R S T U V W X Y Z";
    return 0;
}
```

但是这一版不够优雅，有一个更优雅的方法，使用了 `max_element` 来找到最大值，和一些现代写法：

```cpp
#include<iostream>
#include<string>
#include<algorithm>
#include<vector>
using namespace std;
int main(){
    vector<int> cnt(26, 0);
    string s;
    for (int k = 0; k < 4; k++){
        getline(cin, s);
        for(char c : s)
            if('A' <= c && c <= 'Z')
               cnt[c - 'A']++;
    }

    int h = *max_element(cnt.begin(), cnt.end());

    for(int level = h; level >= 1; level--){
        for(int k = 0; k < 26; k++){
            if (k) cout << " ";
            cout << (cnt[k] >= level ? "*" : " ");
        }
        cout << endl;
    }
    for(int i = 0; i < 26; i++){
        if (i) cout << " ";
        cout << char('A' + i);
    }
    return 0;
}
```

## 洛谷 P1518 两只塔姆沃斯牛

题意：给定一个10*10的网格，包含牛和Farmer的位置，每秒牛和Farmer都可以向上下左右四个方向移动一格，或者转向，求牛和Farmer相遇的时间， 也许不会相遇。

思路：模拟每秒的移动，直到牛和Farmer相遇或者达到400 * 400（Magic Number）。每个实体都有一个方向，按照规则移动或转向。

```cpp
#include<iostream>
#include<string>
using namespace std;
const int MAXN = 10 + 1;
bool a[MAXN][MAXN];

struct P{
    int x, y;
    int head = 0;
};

int dx[] = {-1,0,1,0};
int dy[] = {0,1,0,-1};
int main(){
    P C,F;
    for(int i = 0; i < 10; i++){
        string s;
        cin >> s;
        for(int j = 0; j < s.length(); j++){
            if(s[j] == 'C') C.x = i, C.y = j, a[i][j] = false;
            else if (s[j] == 'F') F.x = i, F.y = j, a[i][j] = false;
            else a[i][j] = (s[j] == '*' ? true : false);
        }
    }
    int res = 0;
    while(res <= 160000){
        res++;
        // 处理C
        int x = C.x + dx[C.head];
        int y = C.y + dy[C.head];
        if (x >=0 && x < 10 && y >= 0 && y < 10 && !a[x][y])
            C.x = x, C.y = y;
        else
            C.head = (C.head + 1) % 4;

        x = F.x + dx[F.head];
        y = F.y + dy[F.head];
        if (x >=0 && x < 10 && y >= 0 && y < 10 && !a[x][y])
            F.x = x, F.y = y;
        else
            F.head = (F.head + 1) % 4;

        if(C.x == F.x && C.y == F.y)
            break;
    
    }
    if (res > 160000) cout << 0;
    else cout << res;
    return 0;
}
```

Magic Number 的选取：因为每个实体有4个方向，网格是10*10，所以状态空间大小为 $10 \times 10 \times 4 = 400$。两者的组合状态空间为 $400 \times 400 = 160000$，因此设置一个上限为160000的循环次数，如果超过这个次数还没有相遇，就认为永远不会相遇。

其实还可以使用一个 `set` 来记录每一轮的状态（牛和Farmer的位置和方向），如果出现重复状态，说明进入了循环，也可以判断永远不会相遇。

```cpp
#include <iostream>
#include <set>
#include <string>
using namespace std;

struct Node {
	int x, y, dir;
};

int dx[4] = {-1, 0, 1, 0};
int dy[4] = {0, 1, 0, -1};

void moveOne(Node &p, bool block[10][10]) {
	int nx = p.x + dx[p.dir];
	int ny = p.y + dy[p.dir];
	if (nx < 0 || nx >= 10 || ny < 0 || ny >= 10 || block[nx][ny]) {
		p.dir = (p.dir + 1) % 4;
	} else {
		p.x = nx;
		p.y = ny;
	}
}

int main() {
	bool block[10][10] = {};
	Node C{0, 0, 0}, F{0, 0, 0};

	for (int i = 0; i < 10; ++i) {
		string s;
		cin >> s;
		for (int j = 0; j < 10; ++j) {
			if (s[j] == '*') block[i][j] = true;
			else if (s[j] == 'C') C = {i, j, 0};
			else if (s[j] == 'F') F = {i, j, 0};
		}
	}

	set<string> vis;
	int step = 0;

	while (true) {
		if (C.x == F.x && C.y == F.y) {
			cout << step;
			return 0;
		}

		string key = to_string(C.x) + "," + to_string(C.y) + "," + to_string(C.dir) + "|" +
					 to_string(F.x) + "," + to_string(F.y) + "," + to_string(F.dir);
		if (vis.count(key)) {
			cout << 0;
			return 0;
		}
		vis.insert(key);

		moveOne(C, block);
		moveOne(F, block);
		++step;
	}
}
```

这一版虽然要长一点，但是更优雅和显然。

## 洛谷 P1098 字符串展开

题意：给定一个字符串，包含字母和数字还有减号，若减号前后都是小写字母或者数字且前者小于后者，则将它们之间的字符展开输出。

1. 遇到下面的情况需要做字符串的展开。在输入的字符串中，出现了减号 `-`，减号两侧同为小写字母或同为数字，且按照 ASCII 码的顺序，减号右边的字符严格大于左边的字符。

2. 参数 $p_1$：展开方式。$p_1=1$ 时，对于字母子串，填充小写字母；$p_1=2$ 时，对于字母子串，填充大写字母。这两种情况下数字子串的填充方式相同；$p_1=3$ 时，不论是字母子串还是数字字串，都用与要填充的字母个数相同的星号 `*` 来填充。

3. 参数 $p_2$：填充字符的重复个数。$p_2=k$ 表示同一个字符要连续填充 $k$ 个。例如，当 $p_2=3$ 时，子串`d-h` 应扩展为 `deeefffgggh`。减号两边的字符不变。

4. 参数 $p_3$：是否改为逆序。$p_3=1$ 表示维持原来顺序；$p_3=2$ 表示采用逆序输出。注意这时候仍然不包括减号两端的字符。例如，当 $p_1=1$、$p_2=2$、$p_3=2$ 时，子串 `d-h` 应扩展为 `dggffeeh`。

5. 如果减号右边的字符恰好是左边字符的后继，只删除中间的减号。例如：`d-e` 应输出为 `de`，`3-4` 应输出为 `34`。如果减号右边的字符按照 ASCII 码的顺序小于或等于左边字符，输出时，要保留中间的减号。例如：`d-d` 应输出为 `d-d`，`3-1` 应输出为 `3-1`。

重点应该是明白各个条件的前后关系：1 -> 5 -> 2 -> 3 -> 4

```cpp
#include<iostream>
#include<string>
#include<algorithm>
using namespace std;
int p1, p2, p3;
string s, res;
bool is_alpha(char a) {return a >= 'a' && a <= 'z';}
bool is_digit(char a) {return a >= '0' && a <= '9';}
bool need(char a, char b) {return (is_alpha(a) && is_alpha(b)) || (is_digit(a) && is_digit(b));}
string multiply(char c, int n){
    string out;
    for (int i = 1; i <= n; i++) out += c;
    return out;
}
string expand(char l, char r){
    string out;
    if (r - l == 1) return "";
    else if (r <= l) return "-";
    // l = tolower(l), r = tolower(r); 可以保证其为小写字母
    if (is_alpha(l)){
        for (char c = l + 1; c <= r - 1; c++){
            if (p1 == 1) out += multiply(c,p2);
            else if (p1 == 2) out += multiply(toupper(c),p2);
            else out += multiply('*',p2);
        }
    }
    else{
        for (char c = l +1; c <= r - 1; c++){
            if (p1 != 3) out.append(p2,c);
            else out.append(p2,'*');
        }
    }
    if (p3 == 2)
        reverse(out.begin(),out.end());
    return out;
}
int main(){
    cin >> p1 >> p2 >> p3 >> s;
    res += s[0];
    for (int i = 1; i < s.length(); i++){
        char c = s[i], l = s[i-1], r = s[i+1];
        if (need(l,r) && c == '-') res += expand(l, r);
        else res += c;
    }
    cout << res;
}
```
一开始我不知道string.append的用法，写成了：

```cpp
string multiply(char c, int n){
    string out;
    for (int i = 1; i <= n; i++)
        out += c;
    return out;
}
out += multiply(c,p2);
```