# Algorithm Notebook 1（1.25.2026~1.31.2026）

Canonical: https://www.mirstar.net/2026/01/25/alogorithm-notebook-1/
Author: onlymatt
Published: 2026-01-25T10:54:49.000Z
Updated: 2026-10-21T11:21:55.737Z
Categories: Programming, Algorithms
Tags: Algorithm Notes

## CF 14A - Letter

题意：给定一个$n*m$矩阵，找到一个矩形，包含所有的'$*$'，并且这个矩形的面积最小。
思路：遍历矩阵，找到最左、最右、最上、最下的'*'的位置，然后计算面积。

```cpp
#include<iostream>
using namespace std;
const int MAXN=50+2,MAXM=50+2;
int main(){
    int n,m;
    bool a[MAXN][MAXM];
    cin >> n >> m;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++){
            char c;
            cin >> c;
            a[i][j] = c == '*';
        }
    
    //Finding the four key point
    
    int max_row=-1,max_col=-1,min_row=55,min_col=55;
    int counter = 0;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            if(a[i][j]){
                min_row = min(i,min_row);
                min_col = min(j,min_col);
                max_row = max(i,max_row);
                max_col = max(j,max_col);   
            }    
        }
    }
    for(int i = min_row;i<=max_row;i++){
        for(int j = min_col;j<=max_col;j++){
            if(a[i][j])
                cout << '*';
            else
                cout << '.';
        }
        cout << endl;
    }
    return 0;
}
```

总结：这道题目比较简单，主要考察对矩阵的遍历和边界的确定。通过找到最左、最右、最上、最下的'*'位置，可以很容易地确定包含所有'*'的最小矩形区域。
- 1. 这个是归约算法，把“一堆数据”用一个（或少数几个）聚合结果概括掉，并且你可以用同一种规则把结果不断更新，直到看完整个数据集。
- 2. 同类题：6A-Triangle, 34A-Reconnaissance 2，LuoguP1046

## HNU 2026寒假集训 contest1(1.25) - A. Bottle

题意：在比赛中有m个路段，给出每一个选手（共n）在每一个路段的耗时，每一个路段的最大人数

```cpp
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
struct Event{
    int time,type;
    bool operator<(const Event& other) const{
        if(time!=other.time)
            return time<other.time;
        return type < other.type;
    }
};
int main(){
    int n,m;
    cin >> n >> m;
    vector<vector<int>> runner(n,vector<int>(m));
    vector<int> result;
    for(int i=0;i<n;i++)
        for(int j=0;j<m;j++)
            cin >> runner[i][j];
    for(int k=0;k<m;k++){//对于每一个路段进行遍历
        vector<Event> events;//创建该路段事件
        for(int i=0;i<n;i++){//对于每一个人进行遍历
            int start = 0;
            for(int j=0;j<k;j++){//从第一个路段到第k-1个路段的总用时即为第k路段的开始时间
                start += runner[i][j];//计算累计时间
            }
            int end = start+runner[i][k];
            events.push_back({start,1});//加入第i个选手进入第k个路段的事件
            events.push_back({end,-1});
        }
        sort(events.begin(),events.end());//对于按照事件进行排序（之前已经进行了运算符重载）
        //遍历事件，寻找最大值
        int max_=0,current=0;
        for(int i=0;i<events.size();i++){
            current+=events[i].type;//type -1离开 1进入
            max_=max(current,max_);
        }
        result.push_back(max_);//按照路段的顺序压入事件
    }
    cout << result[0];
    for(int i=1;i<result.size();i++){
        cout << ' ' << result[i];
    }
    return 0;
}
```
总结：这道题目考察了事件排序和扫描线算法的应用。通过将每个选手在每个路段的进入和离开时间作为事件进行处理，可以有效地计算出每个路段的最大同时在线人数。
- 1. 事件排序+扫描线算法
- 2. 同类题：CF-1163C, CF-835C

- 扫描线算法：
  - 将区间或几何对象的“事件点”（进入/离开、开始/结束）排序后依次扫描。
  - 维护一个动态的数据结构（如计数器、优先队列、平衡树）来记录当前活跃对象集合。
  - 在处理事件时更新结构并同步更新答案（如最大覆盖数、可见性、交点数等）。
  - 典型复杂度：排序 $O(N \log N)$ + 扫描 $O(N \log N)$ 或 $O(N)$（视维护结构而定）。

## CF 4A - Watermelon (800)
题意：判断一个整数是否可以被分成两个偶数部分。
思路：只要大于2且为偶数即可。

```cpp
#include <bits/stdc++.h>
using namespace std;
int main(){
    int w; cin >> w;
    cout << (w > 2 && w % 2 == 0 ? "YES" : "NO") << "\n";
    return 0;
}
```

坑点&测试：w=2 → NO；w=4 → YES；w=7 → NO。

---

## CF 71A - Way Too Long Words (800)
题意：|s|>10 时缩写为 首字母 + (len-2) + 尾字母，否则原串。
坑点：短词不缩写；长度用 len-2。
**不要忘了len-2！**

```cpp
#include <bits/stdc++.h>
using namespace std;
int main(){
    int n; cin >> n;
    while(n--){
        string s; cin >> s;
        if(s.size() > 10) cout << s.front() << s.size() - 2 << s.back() << "\n";
        else cout << s << "\n";
    }
    return 0;
}
```

自测："word"→word；len=10 仍原样；"localization"→l10n。

---

## CF 158A - Next Round (800)
题意：第 k 名的分数为阈值，统计分数为正且不低于阈值的选手数。
思路：读入分数，使用自己的规律/直接模拟

自己的规律
```cpp
#include<iostream>
using namespace std;
const int MAXN = 50 + 2;
int main(){
    int n,k,counter=0,a[MAXN];
    cin >> n >> k;
    for(int i=1;i<=n;i++){
        cin >> a[i];
    }
    int res=0;
    for(int i=1;i<=n;i++){
        if(a[i]>0&&i<=k)
            res++;
        else if(i>k&&a[k]==a[i]&&a[k]>0)
            res++;
    }
    cout << res << endl;
    return 0;
}
```

但是这样太麻烦了，不如直接模拟
```cpp
#include<iostream>
using namespace std;
int main(){
    int n, k;
    cin >> n >> k;
    int a[55];
    for(int i = 0; i < n; i++) cin >> a[i];

    int threshold = a[k - 1];              // 第k名的分数
    int res = 0;
    for(int i = 0; i < n; i++) {
        if(a[i] > 0 && a[i] >= threshold)   // 分数为正且不低于第k名
            res++;
    }

    cout << res << endl;
    return 0;
}
```

自测：阈值为 0 时仍不能计入 0 分；典型输入 8 5 | 10 9 8 7 7 7 5 5 → 6。

---

## CF 266A - Stones on the Table (800)
题意：给定长为 $n$ 的串，删除最少字符使相邻字符不相同，输出删除数。
思路：从左到右统计 `s[i] == s[i-1]` 的次数即可。

```cpp
#include <bits/stdc++.h>
using namespace std;
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, ans = 0; string s;
    if (!(cin >> n >> s)) return 0;
    for(int i = 1; i < n; i++) if(s[i] == s[i-1]) ans++;
    cout << ans << '\n';
    return 0;
}
```

要点：直接比较相邻字符，无需多余数组；复杂度 $O(n)$。

---

### C++ 小技巧
- `string(k, ch)` 可直接构造包含 k 个字符 ch 的字符串，适合在居中/填充类题目里生成左右的点或空格。例如居中放置单词时，用 `string(left, '.') + word + string(right, '.')` 快速输出。

---

## 集训赛复盘（2026-01-27）

### B - Bikes and Barricades（几何，线段与 y 轴交点）
- 做法：判断线段是否跨过 y 轴（x1*x2<0），求交点 y= y1 + (-x1)*(y2-y1)/(x2-x1)，取最小非负值。
- 细节：忽略端点在 y 轴的情况；初值用大数，若未更新输出 -1.0。

### C - Call for Problems（计数）
- 题意：统计难度为奇数的题数（被淘汰的）。
- 修正：我之前误统计偶数，正确是 `if (d % 2 == 1) ++ans;`。

### E - Dishonest Lottery（频次统计）
- 题意：10·n 行开奖，每行 5 个不同数字，出现次数 > 2·n 的数字列出，否则 -1。
- 做法：数组计数 1..50，遍历输出排序（自然有序），无则 -1。

### F - Ellipse Eclipse（几何，椭圆外接轴对齐矩形）
- 公式：已知两焦点、长轴 2A=a_input，焦距 2c=d。半短轴 B=√(A²-c²)。中心 (x0,y0)=(f1+f2)/2。
- 半径投影：
    - 在 x 方向：$x\_{radius} = \sqrt{\left(\frac{A\,dx}{d}\right)^2 + \left(\frac{B\,(y1-y2)}{d}\right)^2}$
    - 在 y 方向：$y\_{radius} = \sqrt{\left(\frac{A\,dy}{d}\right)^2 + \left(\frac{B\,dx}{d}\right)^2}$
    - 结果：$[x0 \pm x\_{radius}],\; [y0 \pm y\_{radius}]$
- 细节：$B^2$ 可能因精度略负，取 max(0, A*A-c*c) 再开方；输出加换行。

## 集训赛复盘（2026-01-29）

### A - Welcome Sign（字符串/模拟）
- 逐行居中：`blank = c - len`，若为奇数，按“出现的奇数空行编号”交替分配左右（第 1/3/5 个奇数空行左少右多，第 2/4/6 个左多右少）；偶数空直接对半。
- 输出 `string(left, '.') + word + string(right, '.')`。

### B - Triangles of a Square（几何结论）
- 只看已画线段两端：非顶点端点数量就是最少再画的线段数，答案 ∈ {0,1,2}。
- 理由：每个新端点增加一个顶点，同时已有约束边抵消一条需要的补边。

### D - Duel of Cards（贪心/双指针）
- Bob 的牌是 1..2n 去掉 Alice 的补集。排序后双指针：
    - Alice 最大得分：`alice[i] > bob[j]` 赢，i++, j++，否则 i++。
    - Bob 最大得分同理 `bob[j] > alice[i]`，则 Alice 最小得分 = n - bobMax。

### H - Herb Mixing（贪心）
- 优先用 1G1R=10（配对 min(g,r)），剩余绿 3G=10，最后 2G=3, 1G=1。
- 红剩余无用，直接丢弃。

# CF 112A - Petya and Strings (800)
题意：比较两个字符串的字典序，输出 `-1`、`1` 或 `0`。
思路：将两个字符串转换为小写后逐字符比较。
```cpp
#include<iostream>
#include<string>
using namespace std;
int main(){
    string s1,s2;
    int res = 0; // 默认相等，只有发现差异才修改
    cin >> s1 >> s2;
    for(int i=0;i<s1.length();i++){
        char c1 = tolower(s1[i]);
        char c2 = tolower(s2[i]);
        if(c1<c2){res=-1;break;}
        if(c1>c2){res=1;break;}
    }
    cout << res;
    return 0;
}
```
**注意**: 不要忘记初始化变量

---

## CF 110A - Nearly Lucky Number (800)
题意：统计数字串中 4 或 7 出现的个数 $k$；若 $k$ 本身只由 4/7 组成则输出 YES，否则 NO。
思路：边读边统计，转整数后再逐位检查。

```cpp
#include<iostream>
#include<string>
using namespace std;
int main(){
    string s;
    cin >> s;
    int res = 0;
    for(int i = 0; i < s.length(); ++i){
        if(s[i] == '4' || s[i] == '7') res++;
    }
    string s_ = std::to_string(res);
    bool is_lucky = true;
    for(int i = 0; i < s_.length(); ++i){
        if(s_[i] != '4' && s_[i] != '7'){
            is_lucky = false;
            break;
        }
    }
    cout << (is_lucky ? "YES" : "NO");
    return 0;
}
```

坑点：字符比较用 `'4'` 不是 `4`；`res==0` 也是 NO（0 不由 4/7 组成）。

---

## CF 69A - Young Physicist (800)
题意：$n$ 个三维向量，求其和是否为零向量；若是输出 YES，否则 NO。
思路：逐个向量累加三个分量，最后判和。

```cpp
#include<iostream>
using namespace std;
int main(){
    int n;
    cin >> n;
    int x = 0, y = 0, z = 0;
    for(int i = 0; i < n; ++i){
        int a, b, c;
        cin >> a >> b >> c;
        x += a;
        y += b;
        z += c;
    }
    cout << (x == 0 && y == 0 && z == 0 ? "YES" : "NO");
    return 0;
}
```

简洁且直接，复杂度 $O(n)$。

---