2026马蹄杯省赛第三场总结（前四道题+第十道题）

第一题：

题干：MC0567侠累擅权韩

难度：青铜 时间限制：1秒 占用内存：256 M

致各位参赛者：

本套题目灵感来源于《史记·刺客列传》中的经典篇章。然而，我们意图呈现的，并非历史上的刀光剑影，而是这些故事背后跨越千年的精神内核：忠诚、信义、智慧与担当。

在各位选手的赛场上，你们无需仗剑而行，但需要具备同样的精神：
面对复杂难题，需要“专诸”般的极致专注与“鱼藏剑”式的巧妙构造；
遭遇多次失败，需要“豫让”般的不屈不挠与“漆身吞炭”式的持久韧性；
抉择算法策略，需要“聂政”般的纯粹信念与“一往无前”的果断执行；
挑战压轴题目，需要“荆轲”般的沉着胆识与“风萧易寒”的临危不乱。

我们旨在将古老的智慧，转化为激励诸位在算法世界里披荆斩棘的动力。希望诸位在解题过程中，不仅能感受编程的乐趣，更能体会到中华文化中关于承诺、勇气与智慧的深刻哲理。现在，请开始你们的‘智取’而非‘刺杀’——用代码和逻辑，攻克眼前的每一个堡垒！”

本套题背景故事概况：聂政 - 独行刺韩报恩

战国时，韩国大臣严仲子与国相侠累结仇，寻得勇士聂政相助。聂政为报知遇之恩，单枪匹马闯入相府，刺杀侠累后自毁容貌、剖腹自杀，以绝连累。其姐聂嫈认尸后亦自杀殉义。

正篇：

韩国权臣侠累专断朝政，门客成群，朝中许多人依附他行事。他性情强横，言语间常以权势压人，国中风气因而紧张，敢直言者渐少。

侠累府中有个管账的小吏，为了不在账目上留下把柄，把每天收来的“十进制整数”钱串号都按一种规矩记成暗号：把这个整数从右往左倒着写，得到的新数记作f(x)f(x)。比如原号是 123，倒着写就是321，于是f(123)=321。

如今已知府里记下的钱串号x一定是个有效的三位数，且个位数字不是0。你要做的事很简单：输出它的f(x)。

格式

输入格式：

一个三位数整数x(101≤x≤999)，且个位数字不是0。

输出格式：

输出一个整数，表示答案。

样例 1

输入：

123

输出：

321

分析：

本体就是一个简单的字符串反转问题，只需要简单的对个位数取余，输出后将原始数值进行整除即可

代码：

#include<bits/stdc++.h> 
using namespace std;
int main( )
{
    int n;cin>>n;
    while(n){
        cout<<n%10;
        n/=10;
    }
    cout<<"\n";
    return 0;
}

第二题：

题干：MC0568仲子受辱恨

难度：白银 时间限制：1秒 占用内存：256 M

士人严仲子与侠累不合，竟被侠累当众轻慢羞辱。仲子自知若以官场手段难讨公道，只得强压怒气，暗中筹谋：要寻敢死之人，以非常之举雪此大辱。

为免走漏风声，仲子先秘密整理出一份可能敢为他出头的名册，共有n人。第i人的名字为si​，均由小写英文字母组成。

接着，仲子会进行m次“试探”。每次试探给出一段暗记字符串t：对所有i∈[1,n]，若t是名字si​的前缀，则说明此人“对得上暗记”，仲子便在心中给此人记一笔（该人计数+1）。

问：当m次试探都结束后，名册上每个人分别被记了多少笔？

格式

输入格式：

第一行两个整数n,m(1≤n,m≤1000)。
第二行n个字符串s1​∼sn​(1≤∣si​∣≤10)。
接下来m行，每行一个长度不超过10的仅包含小写英文字母的字符串t(1≤∣t∣≤10)，表示一次操作。

输出格式：

一行n个整数，整数之间用一个空格隔开，其中第i个整数表示第i个人的得分。

样例 1

输入：

5 5
abc abe ddf ccd ce
ab
cc
c
ddfg
abef

输出：

1 1 0 2 1

分析：

这题就是一个简单的字符串匹配问题，也就是所说的，下方出现的查询字符串是不是上方的每一个字符串的前缀（是不是子串，以及出现的位次是不是第一个位次）仅需模拟位次即可。

代码：

#include<bits/stdc++.h> 

using namespace std;

int main( )
{
    int n,m;cin>>n>>m;
    vector<string>s(n);for(auto &i:s)cin>>i;
    vector<int>ans(n,0);
    while(m--){
        string a;cin>>a;
        for(int i=0;i<n;i++){
            size_t pos=s[i].find(a);
            if(pos!=string::npos&&pos==0){
                ans[i]++;
            }
        }
    }
    for(auto &i:ans)cout<<i<<" ";
    cout<<"\n";
    return 0;
}

第三题：

题干：MC0569重金求死士

难度：白银

时间限制：1秒

占用内存：256 M

严仲子四处访求侠客死士，许以厚礼重金。可众人一听要对付权臣，便纷纷退缩，唯恐祸及家门。仲子辗转打听，才得知市井屠肆有聂政，胆气过人。只是要请动这样的人，前后疏通、上下打点，处处都要花费，必须算得清清楚楚。

仲子手中有一份“打点开销表”，记作一个n行m列的整数矩阵gi,j​：矩阵中每个格子的整数，表示在那一处联络、疏通所需的花费数额。

为便于分段核算，他要把整张表按规矩切成t1​n​×t2​m​份小账页，每份恰好是t1​行t2​列，并保证n能被t1​整除，m能被t2​整除。

对每一份小账页，仲子将该小账页中矩阵内所有整数做按位异或和，定义为该小账页的“权值”。

现在请你计算：所有小账页的权值之和是多少？（注意这里是普通加法的“和”，不是异或和）

备注：按位异或和，简称异或和，是对一组数依次执行按位异或操作，最终得到的那个唯一值，就是这组数的异或和。特定的，对于两个整数x与y的按位异或和的规则为：将整数x与整数y转换成二进制数，然后再逐位对齐做0和1的异或运算，得到的结果即为整数x与整数y的按位异或和的结果。

格式

输入格式：

第一行四个整数n,m,t1​,t2​(1≤n,m≤1000,1≤t1​≤n,1≤t2​≤m,满足n是t1​的倍数，m是t2​的倍数)。
接下来n行，每行m个整数，其中第i行第j个数表示gi,j​(0≤gi,j​≤1000)的值。

输出格式：

一行一个整数，表示答案。

样例 1

输入：

6 4 3 2
1 1 2 2
3 3 4 2
6 6 5 1
3 3 7 8
5 5 6 6
6 6 5 3

输出：

11

备注

对于该样例，被分成这些矩阵：
注意最左边是行号。

分析：

这是一道非常典型的模拟与二维映射题目。正如题目所标定的“白银”难度，这道题不需要用到复杂的动态规划（DP）或者单调栈，考察的核心就是如何把一个大矩阵正确地映射划分到各个小矩阵中去。

在赛场上，遇到这种题千万不要想得太复杂。我们甚至不需要把整个$n \times m$ 的矩阵都存进内存，可以采用边读入边处理（On-the-fly）的方式，不仅代码精简，还能极大地节省内存和时间。

核心解题思路

1. 坐标映射：

   对于原矩阵中第$i$ 行第$j$ 列的元素（坐标从 0 开始算），它所属的小账页（Block）的行号为 i / t1，列号为 j / t2。

   （举例：如果$t_1 = 3$，那么原矩阵的第 0, 1, 2 行除以 3 都会得到 0，刚好对应第 0 个小账页）。

2. 异或和累加：

   建立一个二维数组（或二维 Vector）block_xor，专门用来存储每个小账页的异或和。

   每读入一个数字 val，计算出它属于哪个小账页后，直接执行 block_xor[i / t1][j / t2] ^= val 即可。

3. 计算总和：

   处理完所有输入后，遍历 block_xor 数组，将所有的异或和用普通的加法累加起来。

   注意数据范围防溢出： 尽管每个数字最大为 1000，异或后不会变得特别大，但小账页的数量最多可能有$10^6$ 个，极端情况下加法总和可能接近$10^9$。虽然在 32 位有符号整数的范围内，但为了算法竞赛中的绝对安全，累加总和推荐使用 long long 类型。

代码：

#include <iostream>
#include <vector>

using namespace std;

int main() {
    // 算法竞赛起手式：解除 cin/cout 与 stdio 的同步，加速 I/O 操作
    // 本题最多有 1000 * 1000 = 10^6 次读入，快读非常必要
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n, m, t1, t2;
    if (!(cin >> n >> m >> t1 >> t2)) return 0;

    // 计算被切割后，小矩阵的行数和列数
    int num_block_rows = n / t1;
    int num_block_cols = m / t2;

    // 创建一个二维 vector 来存储每个小矩阵的异或和，初始值全为 0
    // vector 维度：num_block_rows 行，num_block_cols 列
    vector<vector<int>> block_xor(num_block_rows, vector<int>(num_block_cols, 0));

    // 边读入边处理，不需要存储庞大的原矩阵
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) {
            int val;
            cin >> val;
            
            // 核心逻辑：计算当前元素属于哪个小矩阵
            int block_r = i / t1;
            int block_c = j / t2;
            
            // 将当前元素与对应小矩阵的现有异或和 进行异或运算
            block_xor[block_r][block_c] ^= val;
        }
    }

    // 计算所有小矩阵异或和的 普通加法总和
    // 使用 long long 防止极限数据下的整数溢出
    long long total_sum = 0;
    for (int r = 0; r < num_block_rows; ++r) {
        for (int c = 0; c < num_block_cols; ++c) {
            total_sum += block_xor[r][c];
        }
    }

    // 输出最终答案
    cout << total_sum << "\n";

    return 0;
}

第四题：

题干：MC0570屠肆会聂政

难度：黄金 时间限制：1秒 占用内存：256 M

严仲子亲到屠肆见聂政，直说自己受辱于侠累之横，求其出手。聂政先问清缘由与后果，却以“母亲尚在、无人奉养”为由坚决谢绝，不轻许命。

严仲子不敢再逼，只得把话掰开揉碎：他把诸般缘由记成一列长度为n的整数序列a1​∼an​，又一段一段指给聂政看，反复问——“此处到彼处（l,r）之间，可曾有三层递进、步步抬高的势头？”也就是在问al​∼ar​中的最长严格上升子序列长度是否大于等于3？如果是，输出Yes，否则输出No。

注：最长严格上升子序列，是指在一个数值序列中：

• 选取一部分元素组成子序列（元素保持原序列的相对顺序，但不需要连续）；

• 这部分元素满足严格上升的规则——每个后续元素都严格大于前一个元素（不能相等）；

• 这个子序列的长度是所有符合上述条件的子序列中最长的。

格式

输入格式：

第一行两个整数n,q(1≤n,q≤104)。
第二行n个整数a1​∼an​(1≤ai​≤109)。
接下来q行，每行两个整数l,r(1≤l≤r≤n)，表示一组询问。

输出格式：

输出q行，每行输出Yes或者No，表示每组询问的答案。

样例 1

输入：

10 5
3 1 3 1 3 9 10 8 2 4
1 3
1 4
1 5
2 6
2 9

复制

输出：

No
No
No
Yes
Yes

分析：

这道题实际上可以使用双单调栈的方法，来实现，分别记录每一个元素左侧第一个比他小的元素位置，和右边第一个比他大的元素位置，这样的话，在后续一个区间内如果这个元素处于一个长度为3的递增序列中，那么其左侧第一个比他小的，和右侧第一个比他大的元素也一定在区间内。

假设在一个给定的查询区间内，真的存在一个长度为 3 的递增子序列，我们设它的三个元素为A、B、C（位置先后顺序为$A \rightarrow B \rightarrow C$）。

• 对于左侧（找更小的数）： 既然存在一个比$B$ 小的元素$A$ 在区间内，那么$B$ 左侧第一个比它小的元素（我们称之为$A'$），其位置必然夹在$A$ 和$B$ 之间。既然$A$ 都没有超出区间的左边界，那么离$B$ 更近的$A'$ 必然也乖乖待在区间内！

• 对于右侧（找更大的数）： 同理，既然存在一个比$B$ 大的元素$C$ 在区间内，那么$B$ 右侧第一个比它大的元素（我们称之为$C'$），其位置必然夹在$B$ 和$C$ 之间。既然最远的$C$ 都没有越过右边界，离$B$ 更近的$C'$ 自然更不可能越界！

所以，根本不需要去遍历寻找那个“确切”的$A$ 和$C$，而是直接考察距离$B$ 最近的候选人$A'$ 和$C'$ 有没有出界。只要它们没出界，这个长度为 3 的递增序列就一定成立。

代码

#include<bits/stdc++.h> 
using namespace std;

int main()
{
    // 1. 加上快速 I/O
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    // 2. 防止隐藏测试点数据过大导致整型溢出
    long long n, q;
    if (!(cin >> n >> q)) return 0;
    
    vector<long long> a(n);
    for(long long &i : a) cin >> i;
    
    vector<long long> ans2(n, -1);
    // 3. 用 2e9 (20亿)确保绝对比任何可能的下标大
    vector<long long> ans1(n, 2e9); 
    
    stack<long long> st;
    stack<long long> st1;
    
    // 计算右侧最近的更大元素 (Next Greater Element)
    for(long long i = 0; i < n; i++){
        while(!st.empty() && a[i] > a[st.top()]){
            long long top_index = st.top();
            ans1[top_index] = i;
            st.pop();
        }
        st.push(i);
    }

    // 计算左侧最近的更小元素 (Previous Smaller Element)
    for(long long i = n - 1; i >= 0; i--){
        while(!st1.empty() && a[i] < a[st1.top()]){
            long long top_index = st1.top();
            ans2[top_index] = i;
            st1.pop();
        }
        st1.push(i);
    }
    
    while(q--){
        long long l, r, tag = 0;
        cin >> l >> r;
        
        // 只需判断中间元素两侧最近的符合条件的元素是否在区间内
        for(long long i = l - 1; i < r; i++){
            if(ans1[i] < r && ans2[i] >= l - 1){
                tag = 1;
                break;
            }
        }
        
        if(tag) cout << "Yes\n";
        else cout << "No\n";
    }
    
    return 0;
}

第十题：

题干：MC0576义名传后世

难度：白银 时间限制：1秒 占用内存：256 M

聂政行刺侠累的事后来写进史书，被后世视作战国刺客里极有代表性的一例：他先尽孝道，母在则不轻赴死；母亡之后才决然出手；事成之后又自毁面目、自刎而死，只为不牵连恩人和家人。后人谈起刺客，常称他刚决果断、重义守信、行事干净利落。

可史官写史，不只写几句评语。他走访了许多人：有人敬重聂政的孝，有人佩服他的决断，也有人觉得他太过激烈。于是史官给每位受访者记下一个“敬佩程度”，第i个人的评价记作ai​。为了找出“大家普遍的敬佩水平”，史官把所有人的评价相加，除以人数n，再向下取整，定义为敬佩阈值：

⌊n∑i=1n​ai​​⌋

现在要你统计：在这n个人里，有多少人的评价ai​严格大于这个阈值？

注：⌊x⌋表示不超过x的最大整数。

后记（与题无关）

本套赛题以“聂政”的故事为蓝本，但我们所聚焦的，并非市井的暴力，而是其目标的纯粹与执行的果决。

我们想向每一位选手传达：高效的算法，源于对问题本质的纯粹洞察与毫无冗余的执行路径。聂政为报知遇之恩便心无杂念、直取核心，这是一种“极简主义”的解题哲学；他仗剑独行、冲破阻碍，是算法在运行时追求最优复杂度的体现。这正提醒我们，最优解往往属于那些能摒除干扰、直指要害的人。

愿诸位在抉择策略时，能拥有聂政般的纯粹与决断，找到那条最直接、最有效的通关路径。这，即是我们希望传递的“聂政精神”：信念至纯，则行动至锐；目标至简，则执行至刚。

格式

输入格式：

第一行一个整数n(1≤n≤105)。
第二行n个整数a1​∼an​(1≤ai​≤104)，整数之间用一个空格隔开。

输出格式：

一行一个整数，表示答案。

样例 1

输入：

10
3 3 3 1 1 1 2 2 2 10

输出：

4

分析：

这题就比较简单了单纯的累加整除即可

代码：

#include<bits/stdc++.h> 

using namespace std;

int main( )
{
    int n,sum=0,re=0;cin>>n;
    vector<int>a(n);for(auto &i:a)cin>>i,sum+=i;
    sum/=n;
    for(int &i:a){
        if(i>sum){
            re++;
        }
    }
    cout<<re<<"\n";
    return 0;
}