XP04-day01
2026-08-12 20:35:42
发布于：广东
131阅读
0回复
0点赞
小明的数字
#include<bits/stdc++.h>
using namespace std;
int a[1000010];
int st[1000010];//表示i被凑出的次数
vector<int> b;//存储原序列
void dfs(int u,int sum){//表示遍历到第u个数，讨论第u个数选还是不选
if(u==b.size()-1){
st[sum]++;
return;
}
dfs(u+1,sum+b[u]);
dfs(u+1,sum);
}
int main(){
int n;
cin>>n;
for(int i=1;i<(1<<n);i++){
cin>>a[i];
}
sort(a+1,a+(1<<n));
for(int i=1;i<(1<<n);i++){
//如果a[i]被求出过 跳过
if(st[a[i]]){
st[a[i]]--;
continue;
}
b.push_back(a[i]);
dfs(0,a[i]);
st[a[i]]--;
}
if(b.size()==n){
for(int i=0;i<n;i++){
cout<<b[i]<<' ';
}
}else{
cout<<-1;
}
return 0;
}
活动安排
扑克牌
#include <bits/stdc++.h>
using namespace std;
int n;
set<string>s;
int main(){
cin>>n;
for(int i=1;i<=n;i++){
string x;
cin>>x;
s.insert(x);
}
cout<<52-s.size();
return 0;
}
A-B数对
数值统计 【模版题】
快速拆步
#include<bits/stdc++.h>
using namespace std;
int main(){
int t;
cin>>t;
while(t--){
vector<long long> ans;
long long x;
cin>>x;
for(int i=63;i>=0;i--){
if(x>>i&1){
ans.push_back(1LL<<i);
}
}
cout<<ans.size()<<" ";
for(long long x:ans)cout<<x<<" ";
cout<<endl;
}
return 0;
}
ST表
#include<bits/stdc++.h>
using namespace std;
const int N = 500010;
int st[N][20];
int n,m,a[N],lg2[N];
void init(){
//st[i][j] 含义是从 i 点 往后跳 1<<j 区间[i,i+(1<<j)-1]的信息
// for(int len=2;len<=n;len++)
for(int j=1;(1<<j)<=n;j++){
for(int i=1;i+(1<<j)-1<=n;i++){
st[i][j] = min(st[i][j-1],st[i+(1<<(j-1))][j-1]);
}
}
}
int find(int l,int r){
int k = log2(r - l + 1);
int ans = min(st[l][k],st[r-(1<<k)+1][k]);
return ans;
}
int main(){
cin>>n>>m;
for(int i=1;i<=n;i++)cin>>st[i][0];
init();
while(m--){
int l,r;
cin>>l>>r;
cout<<find(l,r)<<" ";
}
return 0;
}
二维前缀和
#include<bits/stdc++.h>
using namespace std;
const int N = 3010;
int n,m,c;
int a[N][N];
int main(){
cin>>n>>m>>c;
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
cin>>a[i][j];
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
a[i][j]+=a[i][j-1];
for(int j=1;j<=m;j++)
for(int i=1;i<=n;i++)
a[i][j]+=a[i-1][j];
int ans = 0,x = 0,y = 0;
for(int i=1;i<=n-c+1;i++){
for(int j=1;j<=m-c+1;j++){
int sum = a[i+c-1][j+c-1]- a[i-1][j+c-1]- a[i+c-1][j-1]+ a[i-1][j-1];
if(sum>ans){
ans=sum;
x=i;
y=j;
}
}
}
cout<<x<<" "<<y;
return 0;
}
邻接表
set
离散化
#include<bits/stdc++.h>
using namespace std;
const int N = 1e6+10;
int a[N],b[N];
int main(){
int n;
cin>>n;
for(int i=1;i<=n;i++){
cin>>a[i];
b[i] = a[i];
}
sort(b+1,b+n+1);
int m = 1;
for(int i=2;i<=n;i++){
if(b[i]!=b[m])b[++m]=b[i];
}
for(int i=1;i<=n;i++){
cout<<lower_bound(b+1,b+m+1,a[i])-b<<" ";
}
return 0;
}
随机化哈希
#include<bits/stdc++.h>
using namespace std;
using ull = unsigned long long;
const int M = 7800007;
ull a[M];
int cnt[M];
bool vis[M];
ull seed =chrono::steady_clock::now().time_since_epoch().count();
ull splitmix64(ull x){
x += 0x9e3779b97f4a7c15ULL;
x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9ULL;
x = (x ^ (x >> 27)) * 0x94d049bb133111ebULL;
return x ^ (x >> 31);
}
int Hash(ull x){
return splitmix64(x + seed) % M;
}
int get(ull x){
int h = Hash(x);
while(vis[h] && a[h] != x){
h++;
if(h == M){
h = 0;
}
}
return h;
}
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
int q;
cin >> q;
ull last = 0;
while(q--){
int op;
ull y;
cin >> op >> y;
ull x = y ^ last;
int h = get(x);
if(op == 1){
if(!vis[h]){
vis[h] = true;
a[h] = x;
}
cnt[h]++;
}else{
int ans = 0;
if(vis[h]){
ans = cnt[h];
}
cout << ans << '\n';
last = ans;
}
}
return 0;
}
C++ 计数、哈希与集合类容器
一、计数数组
1. 作用
当数据的值域较小时，可以直接把“数值”当作数组下标，用数组记录出现次数。
例如：
int cnt[100005];
for(int i = 1; i <= n; i++){
int x;
cin >> x;
cnt[x]++;
}
若输入：
2 5 2 7 5 2
则：
cnt[2] = 3
cnt[5] = 2
cnt[7] = 1
2. 常见用途
| 用途 | 写法 |
|---|---|
| 统计 出现次数 | cnt[x]++ |
| 判断 是否出现 | cnt[x] > 0 |
| 删除一个 | cnt[x]-- |
| 枚举所有出现过的数 | for(int i=0;i<=V;i++) if(cnt[i]) ... |
| 求不同数字数量 | 第一次出现时令答案加 |
3. 特点
- 查询、修改复杂度：
- 速度非常快
- 需要值域不能太大
- 数组空间取决于“值域大小”，而不是实际出现多少种数字
例如 时，通常不能直接开：
int cnt[1000000001];
此时可以考虑 map、unordered_map 或离散化。
二、map
1. 作用
map 用来维护：
Key -> Value
例如统计数字出现次数：
map<long long,int> mp;
mp[x]++;
可以理解为：
数字 -> 出现次数
2. 特点
- Key 不需要连续
- Key 自动按照从小到大排列
- Key 不能重复
- 底层通常使用红黑树
- 插入、删除、查询复杂度均为
3. 常用函数
| 写法 | 作用 |
|---|---|
mp[x] |
访问 Key 为 x 的 Value；若不存在会自动创建 |
mp[x]++ |
统计 x 的出现次数 |
mp.insert({x,y}) |
插入 x -> y |
mp.find(x) |
查找 Key x |
mp.count(x) |
判断 Key x 是否存在 |
mp.erase(x) |
删除 Key x |
mp.size() |
Key 的数量 |
mp.empty() |
判断是否为空 |
mp.clear() |
清空 |
mp.lower_bound(x) |
第一个 Key 的位置 |
mp.upper_bound(x) |
第一个 Key 的位置 |
4. 遍历
for(auto [x,y] : mp){
cout << x << " " << y << '\n';
}
遍历顺序按照 Key 从小到大。
5. 查找
auto it = mp.find(x);
if(it != mp.end()){
cout << it->second;
}
三、unordered_map
1. 作用
unordered_map 同样维护：
Key -> Value
常见写法：
unordered_map<long long,int> mp;
mp[x]++;
2. 特点
- 底层为哈希表
- 不维护 Key 的大小顺序
- 平均插入、查询、删除为
- 最坏情况下可能退化到
- 适合值域很大，只需要快速查询、计数，不需要有序性的情况
3. 常用函数
| 写法 | 作用 |
|---|---|
mp[x] |
访问 Key 为 x 的 Value |
mp[x]++ |
统计次数 |
mp.insert({x,y}) |
插入 |
mp.find(x) |
查找 |
mp.count(x) |
判断是否存在 |
mp.erase(x) |
删除 |
mp.size() |
元素数量 |
mp.empty() |
判断是否为空 |
mp.clear() |
清空 |
unordered_map 没有：
lower_bound()
upper_bound()
因为它本身没有维护大小顺序。
四、map 与 unordered_map 对比
| 对比 | map |
unordered_map |
|---|---|---|
| 底层 | 红黑树 | 哈希表 |
| 是否有序 | 是 | 否 |
| 查找 | 平均 | |
| 插入 | 平均 | |
| 删除 | 平均 | |
| 最坏复杂度 | ||
lower_bound |
支持 | 不支持 |
upper_bound |
支持 | 不支持 |
| 前驱 / 后继 | 支持 | 不支持 |
| 适合场景 | 需要有序、稳定复杂度 | 只要求快速查找、计数 |
五、手写哈希：线性探测
1. 核心思想
先通过哈希函数计算初始位置：
h = x % M;
如果该位置已经被其他数字占用，就继续向后寻找：
h
h+1
h+2
h+3
...
直到：
- 找到
x - 或找到空位置
2. 基础模板
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const int M = 200003;
ll a[M];
int cnt[M];
bool vis[M];
int get(ll x){
int h = (x % M + M) % M;
while(vis[h] && a[h] != x){
h++;
if(h == M) h = 0;
}
return h;
}
int main(){
int n;
cin >> n;
for(int i = 1; i <= n; i++){
ll x;
cin >> x;
int h = get(x);
if(!vis[h]){
vis[h] = true;
a[h] = x;
}
cnt[h]++;
}
return 0;
}
3. 主要问题
固定哈希：
h = x % M;
如果大量数据的哈希值集中在相邻位置，线性探测容易形成连续聚集：
■■■■■■■■■■■■■■■■■■■■□□□□□□
此时一次查询可能需要连续检查很多位置，复杂度可能明显退化。
六、随机哈希
1. 作用
普通固定哈希容易被特殊数据针对：
h = x % M;
随机哈希先将 x 打乱，再映射到哈希表：
x
↓
随机化哈希
↓
新的 hash 值
↓
桶位置
注意：
随机种子只在程序开始时产生一次，同一次程序运行过程中保持不变。
因此同一个 x 每次计算得到的哈希结果仍然相同。
2. splitmix64
using ull = unsigned long long;
ull splitmix64(ull x){
x += 0x9e3779b97f4a7c15ULL;
x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9ULL;
x = (x ^ (x >> 27)) * 0x94d049bb133111ebULL;
return x ^ (x >> 31);
}
随机种子
ull seed =
chrono::steady_clock::now()
.time_since_epoch()
.count();
随机哈希
int Hash(ull x){
return splitmix64(x + seed) % M;
}
3. 随机哈希 + 线性探测模板
#include<bits/stdc++.h>
using namespace std;
using ull = unsigned long long;
const int M = 200003;
ull a[M];
int cnt[M];
bool vis[M];
ull seed =
chrono::steady_clock::now()
.time_since_epoch()
.count();
ull splitmix64(ull x){
x += 0x9e3779b97f4a7c15ULL;
x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9ULL;
x = (x ^ (x >> 27)) * 0x94d049bb133111ebULL;
return x ^ (x >> 31);
}
int Hash(ull x){
return splitmix64(x + seed) % M;
}
int get(ull x){
int h = Hash(x);
while(vis[h] && a[h] != x){
h++;
if(h == M) h = 0;
}
return h;
}
4. 普通哈希与随机哈希
| 做法 | 特点 |
|---|---|
x % M |
简单，但规律容易被特殊数据利用 |
splitmix64(x + seed) |
先打乱 Key，较难构造集中冲突 |
map |
不依赖哈希，复杂度稳定为 |
七、set
1. 作用
set 用来维护一个：
有序、不重复的集合。
set<int> s;
例如：
s.insert(5);
s.insert(2);
s.insert(8);
s.insert(5);
集合中实际为：
2 5 8
2. 特点
- 自动从小到大排序
- 不允许重复元素
- 底层通常为红黑树
- 插入、删除、查询复杂度均为
3. 常用函数
| 写法 | 作用 |
|---|---|
s.insert(x) |
插入 x |
s.erase(x) |
删除 x |
s.find(x) |
查找 x |
s.count(x) |
判断 x 是否存在 |
s.lower_bound(x) |
第一个 的元素 |
s.upper_bound(x) |
第一个 的元素 |
s.begin() |
最小元素的位置 |
s.rbegin() |
最大元素的位置 |
s.size() |
元素数量 |
s.empty() |
判断是否为空 |
s.clear() |
清空 |
最小值与最大值
cout << *s.begin() << '\n';
cout << *s.rbegin() << '\n';
前驱与后继
auto it = s.lower_bound(x);
ll r = *it;
--it;
ll l = *it;
八、unordered_set
1. 作用
unordered_set 用来维护：
无序、不重复的集合。
unordered_set<int> s;
主要适合快速判断：
某个元素是否出现过
2. 特点
- 不允许重复
- 不保证遍历顺序
- 底层为哈希表
- 查询、插入、删除平均
- 最坏可能退化到
3. 常用函数
| 写法 | 作用 |
|---|---|
s.insert(x) |
插入 |
s.erase(x) |
删除 |
s.find(x) |
查找 |
s.count(x) |
判断是否存在 |
s.size() |
元素数量 |
s.empty() |
是否为空 |
s.clear() |
清空 |
判断元素是否存在
if(s.count(x)){
cout << "YES";
}else{
cout << "NO";
}
unordered_set 不支持：
lower_bound()
upper_bound()
九、multiset
1. 作用
multiset 是：
有序、允许重复的集合。
multiset<int> s;
例如：
s.insert(5);
s.insert(5);
s.insert(2);
s.insert(8);
集合中为：
2 5 5 8
2. 特点
- 自动排序
- 允许重复
- 插入、删除、查询复杂度通常为
- 适合需要维护重复元素、最小值、最大值、前驱后继的问题
3. 常用函数
| 写法 | 作用 |
|---|---|
s.insert(x) |
插入一个 x |
s.count(x) |
x 出现次数 |
s.find(x) |
找到某一个 x |
s.lower_bound(x) |
第一个 |
s.upper_bound(x) |
第一个 |
s.begin() |
最小值 |
s.rbegin() |
最大值 |
s.size() |
元素总数 |
4. 删除一个与删除全部
删除所有值为 x 的元素
s.erase(x);
如果集合为：
2 5 5 5 8
执行：
s.erase(5);
变为：
2 8
只删除一个 x
auto it = s.find(x);
if(it != s.end()){
s.erase(it);
}
如果集合为：
2 5 5 5 8
只删除一个 5 后：
2 5 5 8
十、set、unordered_set、multiset 对比
| 容器 | 是否有序 | 是否允许重复 | 查询复杂度 | lower_bound |
|---|---|---|---|---|
set |
是 | 否 | 支持 | |
unordered_set |
否 | 否 | 平均 | 不支持 |
multiset |
是 | 是 | 支持 |
常见选择：
只判断是否出现 -> unordered_set
需要有序、前驱、后继 -> set
需要有序并且允许重复 -> multiset
有帮助，赞一个