记录45
#include<bits/stdc++.h> using namespace std; int main(){ int a[1010]={},b[1010]={},cnt[1010]={},n,m,f,x,y; cin>>n>>m; for(int i=1;i<=n;i++) cin>>a[i]; while(m--){ memset(b+1,0,sizeof(b)); memset(cnt+1,0,sizeof(cnt)); cin>>f>>x>>y; if(f==1) a[x]=y; int e=1; if(f==0){ for(int i=x;i<=y;i++){ bool check=1; for(int j=1;j<e;j++){ if(b[j]==a[i]){ check=0; cnt[j]++; } } if(check){ b[e]=a[i]; cnt[e++]++; } } int max_=0,t=0; for(int i=1;i<e;i++){ if(cnt[i]>max_){ max_=cnt[i]; t=b[i]; } if(cnt[i]==max_){ if(b[i]<t) t=b[i]; } } cout<<t<<endl; } } return 0; }题目传送门https://www.luogu.com.cn/problem/P2681
突破点
现在她需要 Bob 支持询问一个区间内的众数,
👉区间内出现最多的数
还要支持修改一个位置的 ai。
👉修改指定位置的数字
区间内的众数，如果有多个输出较小的。
👉输出出现最多数字中最小的那一个
思路
- 数据不大，直接暴力模拟
- 输入数字序列
- 判断是输出众数还是修改数字👉修改数字直接改
- 一个存放区间内出现数字的数组👉统计出现的数字
- 一个存放数字出现个数的数组👉统计数字出现的情况
- 比较后输出最小的众数
代码简析
#include<bits/stdc++.h> using namespace std; int main(){ int a[1010]={},b[1010]={},cnt[1010]={},n,m,f,x,y; cin>>n>>m; for(int i=1;i<=n;i++) cin>>a[i]; while(m--){ memset(b+1,0,sizeof(b)); memset(cnt+1,0,sizeof(cnt)); cin>>f>>x>>y; if(f==1) a[x]=y; int e=1; if(f==0){ ... } return 0; }a[1010]={},👉存储序列
b[1010]={},👉存储出现的数字
cnt[1010]={},👉存储出现的数字个数（跟b数组的下标对应）
n,m,f,x,y;👉n个数，m个操作，f判断操作，x开始下标，y结束下标
memset()函数👉初始化数组
注意：关于memset()函数，我会放到补充部分详细介绍
if(f==1) a[x]=y;👉直接修改数字
int e=1;👉用来记录b数组的最后一位数的下标，e永远指向下一位，因为要空一位存数
if(f==0){..}👉输出最小众数
#include<bits/stdc++.h> using namespace std; int main(){ int a[1010]={},b[1010]={},cnt[1010]={},n,m,f,x,y; cin>>n>>m; for(int i=1;i<=n;i++) cin>>a[i]; while(m--){ memset(b+1,0,sizeof(b)); memset(cnt+1,0,sizeof(cnt)); cin>>f>>x>>y; if(f==1) a[x]=y; int e=1; if(f==0){ for(int i=x;i<=y;i++){ bool check=1; for(int j=1;j<e;j++){ if(b[j]==a[i]){ check=0; cnt[j]++; } } if(check){ b[e]=a[i]; cnt[e++]++; } } ... } return 0; }for(int i=x;i<=y;i++){...}👉遍历区间内的数字
bool check=1;👉是不是往b数组放不重复的数字（默认放）
for(int j=1;j<e;j++){...}👉跟b数组依次比较
if(b[j]==a[i]){}👉b数组内找到相同的数
check=0;👉不往b数组内放数
cnt[j]++;👉统计数组计数
if(check){...}👉需要往b数组内放数
b[e]=a[i];👉数字存进b数组
#include<bits/stdc++.h> using namespace std; int main(){ int a[1010]={},b[1010]={},cnt[1010]={},n,m,f,x,y; cin>>n>>m; for(int i=1;i<=n;i++) cin>>a[i]; while(m--){ memset(b+1,0,sizeof(b)); memset(cnt+1,0,sizeof(cnt)); cin>>f>>x>>y; if(f==1) a[x]=y; int e=1; if(f==0){ for(int i=x;i<=y;i++){ bool check=1; for(int j=1;j<e;j++){ if(b[j]==a[i]){ check=0; cnt[j]++; } } if(check){ b[e]=a[i]; cnt[e++]++; } } int max_=0,t=0; for(int i=1;i<e;i++){ if(cnt[i]>max_){ max_=cnt[i]; t=b[i]; } if(cnt[i]==max_){ if(b[i]<t) t=b[i]; } } cout<<t<<endl; } } return 0; }int max_=0,t=0;👉max_存最多的次数，t为具体数字
for(int i=1;i<e;i++){}👉从头到尾遍历
if(cnt[i]>max_){}👉找到最大的数（即出现次数最多的）
if(cnt[i]==max_){}👉找到同样出现次数最多的数
if(b[i]<t) t=b[i];👉取同样数字最小的
补充
memset()函数竞赛完全指南1. 函数原型与头文件
#include <cstring> // C++ 推荐 // 或 #include <string.h> // C风格 void *memset(void *s, int c, size_t n);参数说明：
s：指向要填充的内存块的起始地址
c：要填充的值（0~255，但实际以int类型传递）
n：要填充的字节数2. 最常用场景：清零操作
int a[100]; memset(a, 0, sizeof(a)); // 将整个数组每个元素置0 // 等价于 for (int i = 0; i < 100; i++) a[i] = 0;优势：代码简洁，执行速度极快（通常由硬件指令优化）。
3. 典型应用场景
场景 代码示例 说明 静态数组清零 int arr[1000]; memset(arr, 0, sizeof(arr));将数组所有元素设为0 动态数组清零 int* p = new int[100]; memset(p, 0, 100 * sizeof(int));注意：sizeof(p)仅指针大小 结构体清零 Student s; memset(&s, 0, sizeof(s));快速初始化所有成员为0/NULL 二维数组清零 int g[100][100]; memset(g, 0, sizeof(g));sizeof(g)自动计算总字节数 4. 按字节填充原理与陷阱
memset按字节填充，这是其强大与危险的根源：
清零（0）：任何类型都适用，因为全0字节对数值类型就是0，对指针就是NULL
置-1：
memset(arr, -1, sizeof(arr));也普遍适用，因为-1的补码是0xFF陷阱：不能填充非0xFF的值到多字节类型
int arr[10]; memset(arr, 1, sizeof(arr)); // 危险！ // 每个int元素实际是 0x01010101 = 16843009，不是1！5. 不同类型数据的处理
数值类型：
// ✅ 正确：清零或置-1 memset(arr, 0, sizeof(arr)); memset(arr, -1, sizeof(arr)); // ❌ 错误：意图赋其他值 memset(arr, 1, sizeof(arr)); // 实际得到16843009字符数组：
char str[100]; memset(str, 'A', sizeof(str)); // ✅ 正确：所有字符为'A' // 或填充空字符串 memset(str, 0, sizeof(str)); // 全'\0'，等价于空字符串布尔数组：
bool flag[100]; memset(flag, 0, sizeof(flag)); // ✅ 全false memset(flag, 1, sizeof(flag)); // ✅ 全true（所有字节为1）6. 动态内存的特殊处理
// ❌ 错误示范 int* p = new int[100]; memset(p, 0, sizeof(p)); // 只清零了指针本身（4/8字节） // ✅ 正确写法 memset(p, 0, 100 * sizeof(int)); // 计算总字节数 // 或 int n = 100; int* p = new int[n]; memset(p, 0, n * sizeof(int));7. 与初始化/赋值的区别
方式 时机 效率 适用场景 int a[100] = {0};编译时 最快 静态数组，只能初始化为0 memset(a, 0, sizeof(a));运行时 极快 任意时刻，可重复清零 fill(a, a+100, 0);运行时 较快 可赋任意值，需头文件 <algorithm>for循环赋值运行时 较慢 灵活，但代码冗余 8. 常见错误
struct Node { int val; vector<int> adj; // ⚠️ 非POD类型 }; Node nodes[100]; memset(nodes, 0, sizeof(nodes)); // ❌ 危险！ // 仅将val清零，vector内部状态被破坏，程序可能崩溃致命问题：
memset对包含非POD类型（如string,vector）的结构体是未定义行为，会导致程序崩溃。正确做法：
for (int i = 0; i < 100; i++) { nodes[i].val = 0; nodes[i].adj.clear(); }9. 性能与适用性
性能：在-O2优化下，
memset通常比手动循环快数倍适用性：仅适用于POD类型（Plain Old Data），如基本类型、数组、不含复杂成员的struct
不推荐：含
string,vector,map等STL成员的结构体10. 竞赛最佳实践
#include <bits/stdc++.h> using namespace std; const int MAXN = 1e5 + 5; int arr[MAXN]; bool vis[MAXN]; long long dp[MAXN][2]; int main() { // ✅ 标准清零模板 memset(arr, 0, sizeof(arr)); memset(vis, 0, sizeof(vis)); memset(dp, 0, sizeof(dp)); // 对long long同样有效 // ✅ 多组数据测试时的重置 int T; cin >> T; while (T--) { int n; cin >> n; memset(arr, 0, sizeof(int) * (n + 1)); // 只清零前n+1个 // ... 处理逻辑 } // ✅ 结构体初始化（仅含POD成员） struct Edge { int u, v, w; }; Edge edges[MAXN]; memset(edges, 0, sizeof(edges)); return 0; }核心要点总结
万能公式：
memset(arr, 0, sizeof(arr));永远安全仅限-1：
memset(arr, -1, sizeof(arr));对整数数组有效动态数组：必须手动计算字节数
n * sizeof(type)结构体：仅当所有成员都是POD类型时才可用
速度：竞赛中清零操作应优先使用
memset，比循环快且代码简洁陷阱：绝不用memset赋1或其他非0xFF值，结果不符合预期
掌握以上用法，可确保在CSP竞赛中安全、高效地使用
memset。
