Algorithm Notebook 2（2.1.2026~2.28.2026）

本文最后更新于 2026年3月16日凌晨

CF 266B - Queue at the School (800)

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

#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() 即为答案。

#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也可以：可以使用排序

#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 统计频次，遍历字符串时直接更新频次并记录最大值对应的子串。

#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

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

其中

for(auto &kv:cnt){
    if(kv.second>best){
        res=kv.first;
        best=kv.second;
    }
}

的部分是现代写法，等价于

1 2	`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() 即为答案。

#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 读整行，并在统计时过滤掉非小写字母。

1	`cin >> s;`

这种写法会默认以空格为分隔符，所以只能读到第一个单词，无法处理题目中包含空格的情况。

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

#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。

#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。根因是：

#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 都必须进入序列（只是值不同）。

1
2
3

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

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

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

遍历方法

在遍历网格（坐标系）的四周要使用多个 $\Delta$ 坐标，通常为8个方向：

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

对于每个格子 $(x,y)$ ，可以通过循环访问周围8个格子：

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

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

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

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

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

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

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

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

在 flatten() 里：

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

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

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

当运算符写成：

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

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

1	`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个操作，旋转矩阵中的子矩阵

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

#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判断每种情况（难点在于可能会忘记在表格的另一边取反）；
使用一个映射关系，构造一个二维数组或哈希表，直接查询结果。（矩阵形式）

#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] 垂直柱状图

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

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

#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 来找到最大值，和一些现代写法：

#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）。每个实体都有一个方向，按照规则移动或转向。

#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的位置和方向），如果出现重复状态，说明进入了循环，也可以判断永远不会相遇。

#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 字符串展开

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

遇到下面的情况需要做字符串的展开。在输入的字符串中，出现了减号 -，减号两侧同为小写字母或同为数字，且按照 ASCII 码的顺序，减号右边的字符严格大于左边的字符。
参数 $p_1$ ：展开方式。 $p_1=1$ 时，对于字母子串，填充小写字母； $p_1=2$ 时，对于字母子串，填充大写字母。这两种情况下数字子串的填充方式相同； $p_1=3$ 时，不论是字母子串还是数字字串，都用与要填充的字母个数相同的星号 * 来填充。
参数 $p_2$ ：填充字符的重复个数。 $p_2=k$ 表示同一个字符要连续填充 $k$ 个。例如，当 $p_2=3$ 时，子串d-h 应扩展为 deeefffgggh。减号两边的字符不变。
参数 $p_3$ ：是否改为逆序。 $p_3=1$ 表示维持原来顺序； $p_3=2$ 表示采用逆序输出。注意这时候仍然不包括减号两端的字符。例如，当 $p_1=1$ 、 $p_2=2$ 、 $p_3=2$ 时，子串 d-h 应扩展为 dggffeeh。
如果减号右边的字符恰好是左边字符的后继，只删除中间的减号。例如：d-e 应输出为 de，3-4 应输出为 34。如果减号右边的字符按照 ASCII 码的顺序小于或等于左边字符，输出时，要保留中间的减号。例如：d-d 应输出为 d-d，3-1 应输出为 3-1。

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

#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的用法，写成了：

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

algorithm

#algorithm notebook

Algorithm Notebook 2（2.1.2026~2.28.2026）

https://www.mirstar.net/2026/02/01/alogorithm-notebook-2/

作者

onlymatt

发布于

2026年2月1日

许可协议

Algorithm Notebook 3（3.1.2026~3.31.2026）上一篇

Algorithm Notebook 1（1.25.2026~1.31.2026）下一篇

Algorithm Notebook 2（2.1.2026~2.28.2026）

CF 266B - Queue at the School (800)

CF 228A - Is your horseshoe on the other hoof? (800)

CF 977B - Two-gram (800)

CF 443A - Anton and Letters (800)

CF 2197B - B.Arrary and Permutation

洛谷 P1042 - 乒乓球（WA 错误复盘）

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

遍历方法

边界处理

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

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

2) 进位传播也要用 +=

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

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

5) fac * i 合法的原因

最终体会

洛谷 P1007 - 魔法少女Scarlet

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

洛谷 P1598 [USACO03FEB] 垂直柱状图

洛谷 P1518 两只塔姆沃斯牛

洛谷 P1098 字符串展开

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

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

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

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

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

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