Algorithm Notebook 1（1.25.2026~1.31.2026）

CF 14A - Letter

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

#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）在每一个路段的耗时，每一个路段的最大人数

#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且为偶数即可。

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

#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 名的分数为阈值，统计分数为正且不低于阈值的选手数。
思路：读入分数，使用自己的规律/直接模拟

自己的规律

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

但是这样太麻烦了，不如直接模拟

#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] 的次数即可。

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

---

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

B - Bikes and Barricades（几何，线段与 y 轴交点）

• 做法：判断线段是否跨过 y 轴（x1x2<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, AA-cc) 再开方；输出加换行。