位掩码、哈希表、异或运算、杨辉三角、素数查找、前缀和
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
例题
[size=4
]标题形貌
房间里放着 n 块奶酪。一只小老鼠要把它们都吃掉，问至少要跑多少间隔？老鼠一开始在 (0,0) 点处。
[size=4
]输入格式
第一行有一个整数，表现奶酪的数目 n。
第 2 到第 (n
3;1) 行，每行两个实数，第 (i
3;1) 行的实数分别表现第 i 块奶酪的横纵坐标 xi,yi。
[size=4
]输特别式
输出一行一个实数，表现要跑的最少间隔，保留 2 位小数。
[size=4
]输入输出样例
输入 #1复制
4
1 1
1 -1
-1 1
-1 -1 输出 #1复制
7.4
1 [size=4
]分析/提示
数据规模与约定
对于全部的测试点，保证 1≤n≤15，∣xi∣,∣yi∣≤200，小数点后最多有 3 位数字。
提示
对于两个点 (x1,y1)，(x2,y2)，两点之间的间隔公式为 (x1−x2)2
3;(y1−y2)2。
2022.7.13：新增加一组 Hack 数据。
#include<bits/stdc
3;
3;.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
3;
3;)
cin>>points.first>>points.second;
//各点之间的距离
vector<vector<double>> dist(n,vector<double>(n));
for(int i=0;i<n;i
3;
3;){
for(int j=0;j<n;j
3;
3;){
double dx=points.first-points.first;
double dy=points.second-points.second;
dist=sqrt(dx*dx
3;dy*dy);
}
}
//各点到原点的距离
vector<double> origin_dist(n);
for(int i=0;i<n;i
3;
3;){
double dx=points.first;
double dy=points.second;
origin_dist=sqrt(dx*dx
3;dy*dy);
}
//状态dp数组，dp表示mask状态下，最后到达点i的最短距离
vector<vector<double>> dp(1<<n,vector<double>(n,INF));
for(int i=0;i<n;i
3;
3;){
dp=origin_dist;
}
//状态转移
for(int mask=1;mask<(1<<n);mask
3;
3;){
for(int i=0;i<n;i
3;
3;){
if(!mask&(1<<i))continue;
for(int j=0;j<n;j
3;
3;){
if(mask&(1<<j)) continue;
int new_mask=mask | (1<<j);
dp=min(dp,dp
3;dist);
}
}
}
double ans=INF;
int full_mask=(1<<n)-1;
for(int i=0;i<n;i
3;
3;){
ans=min(ans,dp);
}
cout<<setprecision(2)<<fixed<<ans<<endl;
return 0;
} 2、哈希表map
map<key,value>:有序，存储键值对的一种数据结构
unordered_map<key,value>:无序，同样是存储键值对的一种哈希表
例题
[size=4
]标题形貌
超市里有 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 个格子中的物品是什么，保证查询的柜子有存过东西。
已知超市里共计不会超过 10
7
个寄包格子，ai 是确定然而未知的，但是保证一定不小于该柜子存物品请求的格子编号的最大值。当然也有大概某些寄包柜中一个格子都没有。
[size=4
]输入格式
第一行 2 个整数 n 和 q，寄包柜个数和询问次数。
接下来 q 个行，每行有多少个整数，表现一次操纵。
[size=4
]输特别式
对于查询操纵时，输出答案，以换行隔开。
[size=4
]输入输出样例
输入 #1复制
5 4
1 3 10000 118014
1 1 1 1
2 3 10000
2 1 1 输出 #1复制
118014
1 [size=4
]分析/提示
upd 2022.7.26：新增加一组 Hack 数据。
#include<bits/stdc
3;
3;.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
3;1);
for(int x=0;x<q;x
3;
3;){
int num,i,j,k;
cin>>num>>i>>j;
if(num==1){
cin>>k;
lockers=k;
}else if(num==2){
cout<<lockers<<endl;
}
}
return 0;
} 3、异或运算
异或运算是指将两个数转为二进制数，然后对位进行异或运算，雷同取0，不同取1,如3^2等价于11^10=01=1.
规律：a^a=0,a^0=a,a^a^a=a;
例题
[size=4
]标题形貌
颠末一段时间的告急筹备，电脑小组的“RP 餐厅”终于开业了，这天，司理 LXC 接到了一个定餐大单，可把大家乐坏了！员工们齐心协力按要求准备好了套餐正准备派送时，突然碰到一个棘手的题目：筷子！
CX 小朋侪找出了餐厅中所有的筷子，但遗憾的是这些筷子长短不一，而我们都知道筷子需要长度一样的才能组成一双，更麻烦的是 CX 找出来的这些筷子数目为奇数，但是偶合的是，这些筷子中只有一只筷子是落单的，其余都成双，善良的你，可以帮 CX 找出这只落单的筷子的长度吗？
[size=4
]输入格式
第一行是一个整数，表现筷子的数目 n。
第二行有 n 个整数，第 i 个整数表现第 i 根筷子的长度 ai。
[size=4
]输特别式
输出一行一个整数表现答案。
[size=4
]输入输出样例
输入 #1复制
9
2 2 1 3 3 3 2 3 1
输出 #1复制
2 [size=4
]分析/提示
数据规模与约定
[*]对于 30% 的数据，保证 n≤105。
[*]对于 100% 的数据，保证 1≤n≤10
7

3;1，1≤ai≤109。
提示
[*]请留意数据读入对程序服从造成的影响。
[*]请留意本题的空间限制为 4
Mb。
#include<bits/stdc
3;
3;.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
3;
3;){
int a;
cin>>a;
ans^=a;
}
cout<<ans;
}
4
、组合数题目杨辉三角
3;前缀和
杨辉三角公式：c=c
3;c
c表现从i种物品中选取j种的组合方案数，即为选第i个(c)和不选第i个物品(c)的组合数之和。
前缀和：即依次累加前面的值
例题
[size=4
]标题形貌
组合数 (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)。
[size=4
]输入格式
第一行有两个整数 t,k，此中 t 代表该测试点总共有多少组测试数据，k 的意义见题目形貌。
接下来 t 行每行两个整数 n,m，此中 n,m 的意义见题目形貌。
[size=4
]输特别式
共 t 行，每行一个整数代表所有的 0≤i≤n,0≤j≤min(i,m) 中有多少对 (i,j) 满意 k∣(ji)。
[size=4
]输入输出样例
输入 #1复制
1 2
3 3 输出 #1复制
1 输入 #2复制
2 5
4
5
6 7 输出 #2复制
0
7
[size=4
]分析/提示
【样例1分析】
在所有大概的情况中，只有 (12)=2 一种情况是 2 的倍数。
#include<bits/stdc
3;
3;.h>
using namespace std;
int main(){
int t,k;
cin>>t>>k;
const int max_n=2000;
//c表示从i种物品中选取j种，有多少种组合方式 模k
vector<vector<int>> c(max_n
3;1,vector<int>(max_n
3;1,0));
//valid表示当前组合方式的数量是否为k的倍数
vector<vector<int>> valid(max_n
3;1,vector<int>(max_n
3;1,0));
//row_sum表示 当前情况所有的有效标记和
vector<vector<int>> row_sum(max_n
3;1,vector<int>(max_n
3;1,0));
//标记处理
for(int i=1;i<=max_n;i
3;
3;){
c=1%k;
if(i>=1) c=1%k; //初始化
for(int j=1;j<i;j
3;
3;){
c=(c
3;c)%k; //杨辉三角 c=c
3;c
}
for(int j=0;j<=i;j
3;
3;){
valid=(c==0)?1:0;
}
row_sum=valid; //初始化
for(int j=1;j<=i;j
3;
3;){
row_sum=row_sum
3;valid; //选择1~j-1个和选择j个的有效标记之和
}
}
while(t--){
int n,m;
cin>>n>>m;
int ans=0;
for(int i=0;i<=n;i
3;
3;){
int j_upper=min(m,i);
ans
3;=row_sum;
}
cout<<ans<<endl;
}
return 0;
} 5、素数查找
大致分为两种，第一种试除法：直接判断当前数是否为素数；第二种查表法（欧拉线性筛，埃拉托斯特尼筛法）。
例题
[size=4
]标题形貌
如题，给定一个范围 n，有 q 个询问，每次输出第 k 小的素数。
[size=4
]输入格式
第一行包含两个正整数 n,q，分别表现查询的范围和查询的个数。
接下来 q 行每行一个正整数 k，表现查询第 k 小的素数。
[size=4
]输特别式
输出 q 行，每行一个正整数表现答案。
[size=4
]输入输出样例
输入 #1复制
100 5
1
2
3
4
5 输出 #1复制
2
3
5
7
11 /*
//试除法
bool isPrime(int n){
if(n<=1) return false;
for(int i=2;i*i<=n;i
3;
3;){
if(n%i==0) return false;
}
return true;
}
//埃拉托斯特尼筛法
void sieveOfEratosthenes(int n){
vector<bool> prime(n
3;1,true);
prime=false,prime=false;
for(int i=2;i<=n;i
3;
3;){
if(prime){
//筛除所有的i的倍数，从i*i开始
for(int j=i*i;j<=n;j
3;i){
prime=false;
}
}
}
}
*/
#include<bits/stdc
3;
3;.h>
using namespace std;
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
int n,q;
cin>>n>>q;
//欧拉筛法
vector<bool> isPrime(n
3;1,true);
vector<int> primes;
for(int i=2;i<=n;i
3;
3;){
if(isPrime){
primes.push_back(i);
}
for(int j=0;j<primes.size()&&i*primes<=n;j
3;
3;){
isPrime]=false;
if(i%primes==0) break;//确保每个和数只被筛一次
}
}
while(q--){//先判断q的值再进行q--运算！
int k;
cin>>k;
cout<<primes<<"
;\n"
;;
}
return 0;
} 6、最小公约数
[size=4
]标题形貌
输入两个正整数 x0,y0，求出满意下列条件的 P,Q 的个数：
[*] P,Q 是正整数。
[*] 要求 P,Q 以 x0 为最大公约数，以 y0 为最小公倍数。
试求：满意条件的所有大概的 P,Q 的个数。
[size=4
]输入格式
一行两个正整数 x0,y0。
[size=4
]输特别式
一行一个数，表现求出满意条件的 P,Q 的个数。
[size=4
]输入输出样例
输入 #1复制
3 60
输出 #1复制
4
[size=4
]分析/提示
P,Q 有 4
种：
[*]3,60。
[*]15,12。
[*]12,15。
[*]60,3。
对于 100% 的数据，2≤x0,y0≤105。7
#include<bits/stdc
3;
3;.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
3;
3;){ if(k%a==0){ int b=k/a; if(gcd(a,b)==1){ ans
3;=(a==b)?1:2; } } } cout<<ans<<endl; return 0;} 7、前缀和
3;kadane算法（求最大连续子集）
前缀和：即累加的意思，依次保留每次累加的结果。
kadane算法：求数组中的最大连续子集。
int kadane(const vector<int>&arr){ int current_max=arr; int global_max=arr; for(int i=1;i<arr.size();i
3;
3;){ current_max=max(a,current_max
3;a); global_max=max(global_max,current_max); } return global_max;} 例题
[size=4
]标题形貌
为了更好的备战 NOIP2013，电脑组的几个女孩子 LYQ,ZSC,ZHQ 以为，我们不但需要机房，我们还需要活动，于是就决定找校长申请一块电脑组的课余活动场地，听说她们都是电脑组的高手，校长没有立刻答应他们，而是先给她们出了一道数学题，并且告诉她们：你们能获得的活动场地的面积就是你们能找到的这个最大的数字。
校长先给他们一个 n×n 矩阵。要求矩阵中最大加权矩形，即矩阵的每一个元素都有一权值，权值界说在整数集上。从中找一矩形，矩形大小无限制，是此中包含的所有元素的和最大 。矩阵的每个元素属于 [−127,127] ,例如
0 –2 –7092 –62-4
1 –4
1 -180 –2 在左下角：
92-4
1-18 和为 15。
几个女孩子有点犯难了，于是就找到了电脑组精打细算的 HZH，TZY 小朋侪帮忙计算，但是遗憾的是他们的答案都不一样，涉及地皮的事情我们可不能含糊，你能帮忙计算出校长所给的矩形中加权和最大的矩形吗？
[size=4
]输入格式
第一行：n，接下来是 n 行 n 列的矩阵。
[size=4
]输特别式
最大矩形（子矩阵）的和。
[size=4
]输入输出样例
输入 #1复制
4
0 -2 -7 0 9 2 -6 2-4
1 -4
1 -1 80 -2 输出 #1复制
15 [size=4
]分析/提示
1≤n≤120
#include<bits/stdc
3;
3;.h>using namespace std;//求集合中最大子集（连续的） int Kadane(const vector<int>& arr){ int current_max=arr; int global_max=arr; for(int i=1;i<arr.size();i
3;
3;){ current_max=max(arr,current_max
3;arr);//局部最大 ，当前值和之前最大加上当前值 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
3;
3;){ for(int j=0;j<n;j
3;
3;){ cin>>matrix; } } //每一行的前缀和 vector<vector<int>> prefix(n,vector<int>(n
3;1,0)); for(int i=0;i<n;i
3;
3;){ for(int j=1;j<=n;j
3;
3;){ prefix=prefix
3;matrix; } } int max_sum=INT_MIN; //遍历所有的列区间 for(int l=0;l<n;l
3;
3;){ for(int r=l;r<n;r
3;
3;){ vector<int> temp(n); for(int i=0;i<n;i
3;
3;){ temp=prefix[r
3;1]-prefix; } int current_max=Kadane(temp); max_sum=max(current_max,max_sum); } } cout<<max_sum<<endl; return 0;}
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。
页:
[1]