2026年码蹄杯题集
目前为止做的都是青铜与白银难度的题目，然后就只是将自己思考的比较深的题目放在这里做一个记录了，其他非常非常简单的题目没有记录在这里，黄金及以上会在后面慢慢去挑战！
MC0505厨房里练手艺
专诸为了完成刺杀任务，天天在厨房练习藏剑于鱼肚的技巧，反复模拟刺杀动作。经过几个月的训练，他手法越来越熟练。他记录了一个长度为nn的整数序列a1∼an，表示这一系列动作的初始熟练度。在接下来的q次训练调整中，每次操作可能是以下三种之一：
·1 l r x：将al∼ar都加上x。
·2 l r x：对于al∼ar每个数，若它大于x，则将其变成x，否则不变。
·3 l r：问你等于多少？
请处理所有操作，并输出每次操作类型3的询问结果。
格式
输入格式：
第一行两个整数n,q(1≤n,q≤104)n。
第二行nn个整数a1∼an(1≤ai≤10)。
接下来q行，每行三个整数或者四个整数，表示询问或者操作，其中满足1≤l≤r≤n,1≤x≤10。
输出格式：
对于每个询问，输出一行一个整数，表示答案。
样例 1
输入：
6 3 3 3 1 2 6 6 2 5 6 3 1 1 5 1 3 2 6
输出：
16
样例 2
输入：
5 2 1 2 3 4 5 3 1 3 3 3 4
输出：
6 7
本题相关知识点： 语言基础：数组 语言基础：循环结构
思考
这个题主要考察的是数组，题目本身不难，直接遍历就能解决，代码如下
#include<bits/stdc++.h> #define N 10004 using namespace std; int a[N]; int main( ) { int n, q; cin >> n >> q; for(int i = 0; i < n; i++) cin >> a[i]; while(q--) { int num, l, r, x; cin >> num >> l >> r; if(num == 3) { int ans3 = 0; for(int i = l-1; i < r; i++) ans3 += a[i]; cout << ans3 << '\n'; } if(num == 1) { cin >> x; for(int i = l-1; i < r; i++) a[i] += x; } if(num == 2) { cin >> x; for(int i = l-1; i < r; i++) { if(a[i] > x) a[i] = x; } } } return 0; }MC0506摆酒席设圈套
公子光设宴邀请吴王僚，吴王虽心存疑虑但仍前来赴宴。公子光早已布置武士埋伏在四周，并让专诸将短剑藏于烤鱼之中，准备在宴席上发动刺杀。为了评估动手的最佳时机，公子光记录了宴会上每道菜的美味度，形成一个长度为nn的整数序列a1∼an。现在，他想知道有多少个四元组(q,w,e,r)(q,w,e,r)满足1≤q<w<e<r≤n且aq<aw=ae>ar？
这种模式表示在两道美味度相同且较高的菜品出现时，吴王僚的注意力被吸引，是动手的良机。请输出满足条件的四元组数量对10007取模的结果。
格式
输入格式：
第一行一个整数n(1≤n≤3000)。
第二行nn个整数a1∼an(1≤ai≤109)，整数之间用一个空格隔开。
输出格式：
一行一个整数，表示答案。
样例 1
输入：
4 1 3 3 2
输出：
1
本题相关知识点： 语言基础：数组
思考
这个题一开始看到，本人就有些许害怕了，哈哈哈哈，因为也就只会纯暴力去遍历然后计数，想着想着就忘记思考题目了，然后就只剩下恐惧！！！就被aq<aw=ae>ar所吸引，尤其是中间两个元素还是相等的，然后！！！我就因为粗心然后被误导了，一度以为中间两个元素是相邻的，所以去提交了好几个WA，不中了orz
ok，回到正题，这里我们知道aw=ae，然后w<e，我们可以遍历整个数组，找到两个相等的元素，然后再依次去统计左边小于aw的元素个数l以及右边小于ae的元素个数r，然后根据排列组合得到这个aw=ae四元组的个数为l×r（左边有l个选择，右边有r个选择，所以一共计算l×r组），遍历完整个数组后就能得到所有四元组的个数。但是！！！提交之后，超时了orz，直接暴力超时版本，代码如下：
// 21个示例只通过了20个示例 #include<bits/stdc++.h> #define N 3003 #define M 10007 using namespace std; long long a[N]; int main( ) { int n; cin >> n; for(int i = 0; i < n; i++) cin >> a[i]; long long cont = 0; for(int i = 1; i < n-1; i++) { for(int k = i+1; k < n-1; k++) { if(a[i] == a[k]) { long long l = 0, r = 0; for(int j = 0; j < i; j++) { if(a[j] < a[i]) l++; } for(int j = k+1; j < n; j++) { if(a[j] < a[k]) r++; } cont += l*r; } } } cout << cont%M; return 0; }然后我痛定思痛，还去问了小豆包，最后反应过来，似乎我现在的代码是，每找到一组aw=ae，我都会去重复计算满足条件的元素个数，emmmm，这就是超时的主要原因了，所以，假设我们现在找到了第w个元素和第e个元素相等，如果我们能提前算出前w个有多少是小于aw与后n-e-1个是有多少小于ae的，后面再去遍历找相等时，直接取元素个数值出来相乘计算的话就能解决刚刚的问题了。
所以，在新的代码里面我就在一开始就去计数，将每一个元素a[i]所对应的左边小于其的个数和右边小于其的个数分别存入了l[i]和r[i]，后面在寻找相等的a[w]==a[e]（也就是代码里面的a[i]==a[k]）元素时，就直接将l[w]×r[e]（也就是代码里面的l[i]*r[k]），就能得到当前可以组合的四元组个数了，AC代码如下
#include<bits/stdc++.h> #define N 3003 #define M 10007 using namespace std; long long a[N], l[N], r[N]; int main( ) { int n; cin >> n; for(int i = 0; i < n; i++) cin >> a[i]; long long cont = 0; // 预处理左边小于a[i]的元素个数，后面查表直接用，用空间换时间 for(int i = 0; i < n; i++) { for(int j = 0; j < i; j++) { if(a[j] < a[i]) cont++; } l[i] = cont; cont = 0; } // 预处理右边 for(int i = 0; i < n; i++) { for(int j = i+1; j < n; j++) { if(a[j] < a[i]) cont++; } r[i] = cont; cont = 0; } for(int i = 1; i < n-1; i++) { for(int k = i+1; k < n-1; k++) { if(a[i] == a[k]) { cont += l[i]*r[k]; } } } cout << cont%M; return 0; }最后这个题一定不要忘记了还要对10007取模，并且数组的范围是1e9的所以用long long。
还想说一句话，这个我问过豆包后才知道，原来处理这里超时的方法实则是借鉴了动态规划的用空间换时间的思想，所以也算是接触到了看似难的算法，只不过这道题没有那么那么难，主要是这里预处理的思想我真的觉得太妙了，所以忍不住又多了几句话，希望自己后面多看看。
MC0513水淹晋城险象生
智伯下令引汾水灌城，晋阳城墙被水浸泡，眼看就要倒塌。城中百姓架起木筏逃生，粮仓被淹，情况十分危急。赵襄子站在城头，望着滔滔洪水，心中对城里剩余的粮食数量万分焦急。
现给定整数n，粮仓初始存粮为n!石，守军每日固定消耗2026石粮食。当存粮不足2026石时，停止消耗。请计算最终粮仓剩余的粮食数量，即n! mod 2026的值。
其中x mod y表示x对y取模的结果。
格式
输入格式：
一行一个整数n(1≤n≤106)。
输出格式：
一行一个整数，表示答案。
样例 1
输入：
1000
输出：
596
本题相关知识点： 语言基础：循环结构
思考
这个题是阶乘最后取模，如果就直接进行乘，n过大时就算使用的是long long类型的变量，仍然会溢出，所以我们就可以考虑边乘边取模，这里的原理也是我向豆包学习后才知道的
(a*b) mod M=[(a mod M)*(b mod M)] mod M
具体代码如下
#include<bits/stdc++.h> using namespace std; int main( ) { int n; cin >> n; long long sum = 1; for(int i = 2; i <= n; i++) { sum = sum * i % 2026; // 边乘边取模防止溢出，原理是(a*b)mod M=[(a mod M)*(b mod M)] mod M } cout << sum % 2026; return 0; }MC0517义释壮士显胸襟
赵襄子发现豫让后质问豫让，豫让直言欲为智伯报仇。左右欲诛杀之，襄子叹道：”彼义士也，吾谨避之耳。”遂下令释放豫让。赵襄子释放豫让后，为防其再度行刺，在宫中布置了n个重点防守的哨点，第ii个哨点坐标为(xi,yi)。襄子下令进行m次全面巡查，每次巡查有三个参数x,y,r，表示以(x,y)为中心，r为半径的圆形区域。现在需要统计在所有巡查结束后，每个哨点总共被重点检查了多少次，以便调整后续的布防策略。
格式
输入格式：
第一行两个整数n,m(1≤n,m≤104)。
第2∼n+1行，第i+1行包含两个整数xi,yi(1≤xi,yi≤104)，整数之间用一个空格隔开，表示第ii个哨点的坐标。
接下来m行，每行三个整数x,y,r(1≤x,y,r≤104)，表示一次巡查的中心坐标和半径。
输出格式：
输出一共n行，每行一个整数，其中第ii行代表第ii个哨点被巡察的次数。
样例 1
输入：
5 3 3 1 1 1 2 2 3 3 4 4 1 1 1 2 1 3 3 1 2
输出：
2 3 2 2 0
本题相关知识点： 语言基础：公式与计算
思考
这个题我一开始又想歪了，看到坐标就会不自觉想到二维坐标系，但是既然提到了圆的半径，所以我们直接计算每一个坐标点与圆心的距离，再将其与半径比较就能知道被搜索了多少次（MC0516题的话就是能得到是否被搜索过），然后再记录下来即可
然后这里存坐标的话，我是直接用的二维数组，m行2列，然后遍历行去与圆心做距离的计算。
注意：此题与MC0516的思路是一样的，就只是最后存储输出的不一样而已。
代码如下
#include<bits/stdc++.h> using namespace std; int a[10004][2], c[10004]; int main( ) { int n, m; cin >> n >> m; for(int i = 0; i < n; i++) { cin >> a[i][0] >> a[i][1]; } while(m--) { int x, y, r; cin >> x >> y >> r; for(int i = 0; i < n; i++) { // 直接算距离，若是小于搜索半径的就能被找到，因此cont++ double len = sqrt((x-a[i][0])*(x-a[i][0])+(y-a[i][1])*(y-a[i][1])); if(len <= r) c[i]++; } } for(int i = 0; i < n; i++) cout << c[i] << '\n'; return 0; }MC0549专诸市井被荐
吴国市井之中，专诸正与众人搏斗，场面激烈。伍子胥路过，见专诸勇猛，心生赏识，想引荐给公子光。为考验专诸的应变之能，伍子胥设计了一道题目：
假设市井中的摊位排布在一条直线上，共有n个摊位，其中第i个摊位的坐标为xi，这n个点的位置互不相同且构成一个连续的整数集合。每个摊位初始的分数值都为0。
接下来有m次事件发生，每次事件给出一对整数l,r，对于∀i∈[1,n]，若l≤xi≤r，则本次操作该点分数值不变，否则该点分数值加1。
现在需要专诸计算，在m次事件之后，所有摊位的分数总和是多少？由于结果可能很大，请输出其对10007取模后的结果。
连续的整数集合：把这个集合中的数字从小到大排序后，满足后一个数值等于前一个数值+1。
格式
输入格式：
第一行两个整数n,m(1≤n,m≤3×1e5)。
第二行n个整数x1∼xn(1≤xi≤1e9)。
接下来m行，每行两个整数l,r(1≤l≤r≤1e9)，表示一次操作。
输出格式：
一行一个整数，表示操作结束后所有点的分数值之和对10007取模的结果。
样例 1
输入：
5 2 3 5 4 7 6 4 100 1 3
输出：
5
本题相关知识点： 语言基础：选择结构语言基础：循环结构
思考
整个题的思路其实非常之简单，就是找到数组元素里面不在l和r范围内的元素个数，然后每一次操作的个数都加起来最后取模就是答案了。但是！！！如果就这样直接暴力遍历整个数组的话，其实是会超时的，我们可以来看看时间复杂度，如果直接暴力的话就是O(m*n)，已经是10的10次方了，所以超时是必然的，所以就得想想其他办法了。
再观察观察题目，我发现，其实数组x里面存的值其实是不会改变的，然后我们要找的也是l和r范围外的元素个数，所以这里就可以将数组x进行一个排序（这里是直接使用了sort(x, x+n)），如果是直接和个数挂钩的话，实则在排完序后直接分别记录第一个小于l的元素的位置L以及最后一个大于r的元素的位置R，最后在l和r范围外的元素个数就是n-(R-L+1)了，然后每操作一次就加上（这里为了防止加上过大溢出，我仍然是使用的边加边取模）。
再仔细想想，我要降低时间复杂度，然后找数组位置，不禁就能联想到二分查找，进行时间复杂度的验证，二分后时间复杂度将会为O(log(m*n))，可以发现的确是会降低，所以就尝试着写二分查找了。
二分查找的函数，我个人浅浅尝试写了一下，如下
int find_left(int val) { int l = 0, r = n-1, mid; while(l <= r) { mid = (l+r)/2; if(val < x[mid]) r = mid - 1; else l = mid + 1; } return l; // 这里浅浅尝试写的是找的从左往右第一个大于val(也就是输入的l)的元素位置 } int find_right(int val) { int l = 0, r = n-1, mid; while(l <= r) { mid = (l+r)/2; if(val > x[mid]) l = mid + 1; else r = mid - 1; } return r; // 这里浅浅尝试写的是找的从左往右最后一个小于val(也就是输入的r)的元素位置 }整道题的代码如下
#include<bits/stdc++.h> using namespace std; long long x[300005]; int n, m; int find_left(long long val) { int l = 0, r = n-1, mid; while(l <= r) { mid = (l+r)/2; if(val <= x[mid]) r = mid-1; else l = mid+1; } return l; } int find_right(long long val) { int l = 0, r = n-1, mid; while(l <= r) { mid = (l+r)/2; if(val >= x[mid]) l = mid+1; else r = mid-1; } return r; } int main( ) { cin >> n >> m; for(int i = 0; i < n; i++) cin >> x[i]; sort(x, x+n); long long l, r, cont = 0; while(m--) { cin >> l >> r; long long L = find_left(l); long long R = find_right(r); long long in = R-L+1; long long out = n-in; cont = (cont+out)%10007; } cout << cont%10007; return 0; }碎碎念：五一假期可以小小的休息，但是还有正事要做，等这些都完事了可以放一个大大的假，加油加油，冲冲冲！！！
