当前位置：首页 > news >正文

位掩码、哈希表、异或运算、杨辉三角、素数查找、前缀和

news 来源：原创 2025/9/15 20:49:21

1、位掩码

对二进制数操作的方法，（mask=1<<n）,将数mask的第n位置为1，其它位置为0，即1000...=2^n，当n较小时，可以用于解决类似于0/1背包的问题，要么是0，要么是1，以及排列组合类的问题，当数量较小的情况下可以枚举出所有组合。

1、mask | (1<<i) ，将mask的二进制数的第i位置为1

2、mask&(1<<i)，判断mask的二进制数的第i位是否为1

例题

题目描述

房间里放着 n 块奶酪。一只小老鼠要把它们都吃掉，问至少要跑多少距离？老鼠一开始在 (0,0) 点处。

输入格式

第一行有一个整数，表示奶酪的数量 n。

第 2 到第 (n+1) 行，每行两个实数，第 (i+1) 行的实数分别表示第 i 块奶酪的横纵坐标 xi,yi。

输出格式

输出一行一个实数，表示要跑的最少距离，保留 2 位小数。

输入输出样例

输入 #1复制

输出 #1复制

7.41

说明/提示

数据规模与约定

对于全部的测试点，保证 1≤n≤15，∣xi∣,∣yi∣≤200，小数点后最多有 3 位数字。

提示

对于两个点 (x1,y1)，(x2,y2)，两点之间的距离公式为 (x1−x2)2+(y1−y2)2。

2022.7.13：新增加一组 Hack 数据。

#include<bits/stdc++.h>
using namespace std;
const double INF=1e18;
int main(){int n;cin>>n;vector<pair<double,double>> points(n);//所有奶酪点的坐标 for(int i=0;i<n;i++)cin>>points[i].first>>points[i].second;//各点之间的距离 vector<vector<double>> dist(n,vector<double>(n));for(int i=0;i<n;i++){for(int j=0;j<n;j++){double dx=points[i].first-points[j].first;double dy=points[i].second-points[j].second;dist[i][j]=sqrt(dx*dx+dy*dy);}}//各点到原点的距离 vector<double> origin_dist(n);for(int i=0;i<n;i++){double dx=points[i].first;double dy=points[i].second;origin_dist[i]=sqrt(dx*dx+dy*dy);}//状态dp数组，dp[mask][i]表示mask状态下，最后到达点i的最短距离 vector<vector<double>> dp(1<<n,vector<double>(n,INF));for(int i=0;i<n;i++){dp[1<<i][i]=origin_dist[i];}//状态转移 for(int mask=1;mask<(1<<n);mask++){for(int i=0;i<n;i++){if(!mask&(1<<i))  continue;for(int j=0;j<n;j++){if(mask&(1<<j)) continue;int new_mask=mask | (1<<j);dp[new_mask][j]=min(dp[new_mask][j],dp[mask][i]+dist[i][j]);}}}double ans=INF;int full_mask=(1<<n)-1;for(int i=0;i<n;i++){ans=min(ans,dp[full_mask][i]);}cout<<setprecision(2)<<fixed<<ans<<endl;return 0;
}

2、哈希表map

map<key,value>:有序，存储键值对的一种数据结构

unordered_map<key,value>:无序，同样是存储键值对的一种哈希表

例题

题目描述

超市里有 n(1≤n≤105) 个寄包柜。每个寄包柜格子数量不一，第 i 个寄包柜有 ai(1≤ai≤105) 个格子，不过我们并不知道各个 ai 的值。对于每个寄包柜，格子编号从 1 开始，一直到 ai。现在有 q(1≤q≤105) 次操作：

1 i j k：在第 i 个柜子的第 j 个格子存入物品 k(0≤k≤109)。当 k=0 时说明清空该格子。
2 i j：查询第 i 个柜子的第 j 个格子中的物品是什么，保证查询的柜子有存过东西。

已知超市里共计不会超过 107 个寄包格子，ai 是确定然而未知的，但是保证一定不小于该柜子存物品请求的格子编号的最大值。当然也有可能某些寄包柜中一个格子都没有。

输入格式

第一行 2 个整数 n 和 q，寄包柜个数和询问次数。

接下来 q 个行，每行有若干个整数，表示一次操作。

输出格式

对于查询操作时，输出答案，以换行隔开。

输入输出样例

输入 #1复制

5 4
1 3 10000 118014
1 1 1 1
2 3 10000
2 1 1

输出 #1复制

118014
1

说明/提示

upd 2022.7.26：新增加一组 Hack 数据。

#include<bits/stdc++.h>
using namespace std;
int main(){ios::sync_with_stdio(false);cin.tie(0);int n,q;cin>>n>>q;//相当于一个二维数组，数组中的每个元素是一个哈希表，map中的键和值表示某个柜子的格数和存储的物品 vector<unordered_map<int,int>> lockers(n+1);for(int x=0;x<q;x++){int num,i,j,k;cin>>num>>i>>j;if(num==1){cin>>k;lockers[i][j]=k;}else if(num==2){cout<<lockers[i][j]<<endl;}}return 0;
}

3、异或运算

异或运算是指将两个数转为二进制数，然后对位进行异或运算，相同取0，不同取1,如3^2等价于11^10=01=1.

规律：a^a=0,a^0=a,a^a^a=a;

例题

题目描述

经过一段时间的紧张筹备，电脑小组的“RP 餐厅”终于开业了，这天，经理 LXC 接到了一个定餐大单，可把大家乐坏了！员工们齐心协力按要求准备好了套餐正准备派送时，突然碰到一个棘手的问题：筷子！

CX 小朋友找出了餐厅中所有的筷子，但遗憾的是这些筷子长短不一，而我们都知道筷子需要长度一样的才能组成一双，更麻烦的是 CX 找出来的这些筷子数量为奇数，但是巧合的是，这些筷子中只有一只筷子是落单的，其余都成双，善良的你，可以帮 CX 找出这只落单的筷子的长度吗？

输入格式

第一行是一个整数，表示筷子的数量 n。

第二行有 n 个整数，第 i 个整数表示第 i 根筷子的长度 ai。

输出格式

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

输入输出样例

输入 #1复制

9
2 2 1 3 3 3 2 3 1

输出 #1复制

说明/提示

数据规模与约定

对于 30% 的数据，保证 n≤105。
对于 100% 的数据，保证 1≤n≤107+1，1≤ai≤109。

提示

请注意数据读入对程序效率造成的影响。
请注意本题的空间限制为 4 Mb。

#include<bits/stdc++.h>
using namespace std;
int main(){ios::sync_with_stdio(false);cin.tie(0);int n,ans=0;cin>>n;for(int i=0;i<n;i++){int a;cin>>a;ans^=a;}cout<<ans; 
}

4、组合数问题杨辉三角+前缀和

杨辉三角公式：c[i][j]=c[i-1][j-1]+c[i-1][j]

c[i][j]表示从i种物品中选取j种的组合方案数，即为选第i个(c[i-1][j-1])和不选第i个物品(c[i-1][j])的组合数之和。

前缀和：即依次累加前面的值

例题

题目描述

组合数 (mn) 表示的是从 n 个物品中选出 m 个物品的方案数。举个例子，从 (1,2,3) 三个物品中选择两个物品可以有 (1,2),(1,3),(2,3) 这三种选择方法。根据组合数的定义，我们可以给出计算组合数 (mn) 的一般公式：

(mn)=m!(n−m)!n!

其中 n!=1×2×⋯×n；特别地，定义 0!=1。

小葱想知道如果给定 n,m 和 k，对于所有的 0≤i≤n,0≤j≤min(i,m) 有多少对 (i,j) 满足 k∣(ji)。

输入格式

第一行有两个整数 t,k，其中 t 代表该测试点总共有多少组测试数据，k 的意义见问题描述。

接下来 t 行每行两个整数 n,m，其中 n,m 的意义见问题描述。

输出格式

共 t 行，每行一个整数代表所有的 0≤i≤n,0≤j≤min(i,m) 中有多少对 (i,j) 满足 k∣(ji)。

输入输出样例

输入 #1复制

1 2
3 3

输出 #1复制

输入 #2复制

2 5
4 5
6 7

输出 #2复制

0
7

说明/提示

【样例1说明】

在所有可能的情况中，只有 (12)=2 一种情况是 2 的倍数。

#include<bits/stdc++.h>
using namespace std;
int main(){int t,k;cin>>t>>k;const int max_n=2000;//c[i][j]表示从i种物品中选取j种，有多少种组合方式 模k vector<vector<int>> c(max_n+1,vector<int>(max_n+1,0));//valid[i][j]表示当前组合方式的数量是否为k的倍数 vector<vector<int>> valid(max_n+1,vector<int>(max_n+1,0));//row_sum[i][j]表示 当前情况所有的有效标记和 vector<vector<int>> row_sum(max_n+1,vector<int>(max_n+1,0));//标记处理 for(int i=1;i<=max_n;i++){c[i][0]=1%k;if(i>=1) c[i][i]=1%k; //初始化for(int j=1;j<i;j++){c[i][j]=(c[i-1][j-1]+c[i-1][j])%k; //杨辉三角 c[i][j]=c[i-1][j-1]+c[i-1][j]}for(int j=0;j<=i;j++){valid[i][j]=(c[i][j]==0)?1:0;}row_sum[i][0]=valid[i][0]; //初始化for(int j=1;j<=i;j++){row_sum[i][j]=row_sum[i][j-1]+valid[i][j]; //选择1~j-1个和选择j个的有效标记之和}}while(t--){int n,m;cin>>n>>m;int ans=0;for(int i=0;i<=n;i++){int j_upper=min(m,i);ans+=row_sum[i][j_upper]; }cout<<ans<<endl;} return 0;
}

5、素数查找

大致分为两种，第一种试除法：直接判断当前数是否为素数；第二种查表法（欧拉线性筛，埃拉托斯特尼筛法）。

例题

题目描述

如题，给定一个范围 n，有 q 个询问，每次输出第 k 小的素数。

输入格式

第一行包含两个正整数 n,q，分别表示查询的范围和查询的个数。

接下来 q 行每行一个正整数 k，表示查询第 k 小的素数。

输出格式

输出 q 行，每行一个正整数表示答案。

输入输出样例

输入 #1复制

输出 #1复制

/*
//试除法 
bool isPrime(int n){if(n<=1) return false;for(int i=2;i*i<=n;i++){if(n%i==0) return false;}return true;
} 
//埃拉托斯特尼筛法 
void sieveOfEratosthenes(int n){vector<bool> prime(n+1,true);prime[0]=false,prime[1]=false;for(int i=2;i<=n;i++){if(prime[i]){//筛除所有的i的倍数，从i*i开始 for(int j=i*i;j<=n;j+i){prime[j]=false;}}}
} 
*/
#include<bits/stdc++.h>
using namespace std;
int main(){ios::sync_with_stdio(false);cin.tie(0);int n,q;cin>>n>>q;//欧拉筛法 vector<bool> isPrime(n+1,true);vector<int> primes;for(int i=2;i<=n;i++){if(isPrime[i]){primes.push_back(i);}for(int j=0;j<primes.size()&&i*primes[j]<=n;j++){isPrime[i*primes[j]]=false;if(i%primes[j]==0) break;//确保每个和数只被筛一次 }}while(q--){  //先判断q的值再进行q--运算！ int k;cin>>k;cout<<primes[k-1]<<"\n";}return 0;
}

6、最小公约数

题目描述

输入两个正整数 x0,y0，求出满足下列条件的 P,Q 的个数：

P,Q 是正整数。
要求 P,Q 以 x0 为最大公约数，以 y0 为最小公倍数。

试求：满足条件的所有可能的 P,Q 的个数。

输入格式

一行两个正整数 x0,y0。

输出格式

一行一个数，表示求出满足条件的 P,Q 的个数。

输入输出样例

输入 #1复制

3 60

输出 #1复制

说明/提示

P,Q 有 4 种：

3,60。
15,12。
12,15。
60,3。

对于 100% 的数据，2≤x0,y0≤105。7

#include<bits/stdc++.h>
using namespace std;
int gcd(int a,int b){while(b){int temp=b;b=a%b;a=temp;}return a;
}
int main(){int x,y,ans=0;cin>>x>>y;if(y%x!=0){cout<<0<<endl;return 0;}//x*y=p*q  int k=y/x;for(int a=1;a*a<=k;a++){if(k%a==0){int b=k/a;if(gcd(a,b)==1){ans+=(a==b)?1:2;}}} cout<<ans<<endl;return 0;
}

7、前缀和+kadane算法（求最大连续子集）

前缀和：即累加的意思，依次保留每次累加的结果。

kadane算法：求数组中的最大连续子集。

int kadane(const vector<int>&arr){int current_max=arr[0];int global_max=arr[0];for(int i=1;i<arr.size();i++){current_max=max(a[i],current_max+a[i]);global_max=max(global_max,current_max);}return global_max;
}

例题

题目描述

为了更好的备战 NOIP2013，电脑组的几个女孩子 LYQ,ZSC,ZHQ 认为，我们不光需要机房，我们还需要运动，于是就决定找校长申请一块电脑组的课余运动场地，听说她们都是电脑组的高手，校长没有马上答应他们，而是先给她们出了一道数学题，并且告诉她们：你们能获得的运动场地的面积就是你们能找到的这个最大的数字。

校长先给他们一个 n×n 矩阵。要求矩阵中最大加权矩形，即矩阵的每一个元素都有一权值，权值定义在整数集上。从中找一矩形，矩形大小无限制，是其中包含的所有元素的和最大。矩阵的每个元素属于 [−127,127] ,例如

 0 –2 –7  0 9  2 –6  2
-4  1 –4  1 
-1  8  0 –2

在左下角：

9  2
-4  1
-1  8

和为 15。

几个女孩子有点犯难了，于是就找到了电脑组精打细算的 HZH，TZY 小朋友帮忙计算，但是遗憾的是他们的答案都不一样，涉及土地的事情我们可不能含糊，你能帮忙计算出校长所给的矩形中加权和最大的矩形吗？

输入格式

第一行：n，接下来是 n 行 n 列的矩阵。

输出格式

最大矩形（子矩阵）的和。

输入输出样例

输入 #1复制

4
0 -2 -7 09 2 -6 2
-4 1 -4  1 
-1 8  0 -2

输出 #1复制

说明/提示

1≤n≤120

#include<bits/stdc++.h>
using namespace std;
//求集合中最大子集（连续的） 
int Kadane(const vector<int>& arr){int current_max=arr[0];int global_max=arr[0];for(int i=1;i<arr.size();i++){current_max=max(arr[i],current_max+arr[i]);  //局部最大 ，当前值和之前最大加上当前值  global_max=max(global_max,current_max);      //全局最大   之前最大和当前最大 }return global_max;
}
int main(){int n;cin>>n;vector<vector<int>> matrix(n,vector<int>(n));for(int i=0;i<n;i++){for(int j=0;j<n;j++){cin>>matrix[i][j];}}//每一行的前缀和 vector<vector<int>> prefix(n,vector<int>(n+1,0));for(int i=0;i<n;i++){for(int j=1;j<=n;j++){prefix[i][j]=prefix[i][j-1]+matrix[i][j-1];}}int max_sum=INT_MIN;//遍历所有的列区间 for(int l=0;l<n;l++){for(int r=l;r<n;r++){vector<int> temp(n);for(int i=0;i<n;i++){temp[i]=prefix[i][r+1]-prefix[i][l];}int current_max=Kadane(temp);max_sum=max(current_max,max_sum);}}cout<<max_sum<<endl;return 0;
}

1、位掩码

题目描述

输入格式

输出格式

输入输出样例

说明/提示

数据规模与约定

提示

2、哈希表map

题目描述

输入格式

输出格式

输入输出样例

说明/提示

3、异或运算

题目描述

输入格式

输出格式

输入输出样例

说明/提示

数据规模与约定

提示

4、组合数问题杨辉三角+前缀和

题目描述

输入格式

输出格式

输入输出样例

说明/提示

5、素数查找

题目描述

输入格式

输出格式

输入输出样例

6、最小公约数

题目描述

输入格式

输出格式

输入输出样例

说明/提示

7、前缀和+kadane算法（求最大连续子集）

题目描述

输入格式

输出格式

输入输出样例

说明/提示

相关文章：