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

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&#4
3;1) 行，每行两个实数，第 (i&#4
3;1) 行的实数分别表现第 i 块奶酪的横纵坐标 xi​,yi​。
[size=4
]输特别式

输出一行一个实数，表现要跑的最少间隔，保留 2 位小数。
[size=4
]输入输出样例

输入 #1复制

1. 4
3. 1 1
4. 1 -1
5. -1 1
6. -1 -1

复制代码

输出 #1复制

1. 7.4
2. 1

复制代码

[size=4
]分析/提示

数据规模与约定

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

对于两个点 (x1​,y1​)，(x2​,y2​)，两点之间的间隔公式为 (x1​−x2​)2&#4
3;(y1​−y2​)2​。

---

2022.7.13：新增加一组 Hack 数据。

1. #include<bits/stdc&#4
2. 3;&#4
3. 3;.h>
4. using namespace std;
5. const double INF=1e18;
6. int main(){
7.         int n;
8.         cin>>n;
9.         vector<pair<double,double>> points(n);
10.         //所有奶酪点的坐标
11.         for(int i=0;i<n;i&#4
12. 3;&#4
13. 3;)
14.         cin>>points[i].first>>points[i].second;
15.         //各点之间的距离
16.         vector<vector<double>> dist(n,vector<double>(n));
17.         for(int i=0;i<n;i&#4
18. 3;&#4
19. 3;){
20.                 for(int j=0;j<n;j&#4
21. 3;&#4
22. 3;){
23.                         double dx=points[i].first-points[j].first;
24.                         double dy=points[i].second-points[j].second;
25.                         dist[i][j]=sqrt(dx*dx&#4
26. 3;dy*dy);
27.                 }
28.         }
29.         //各点到原点的距离
30.         vector<double> origin_dist(n);
31.         for(int i=0;i<n;i&#4
32. 3;&#4
33. 3;){
34.                 double dx=points[i].first;
35.                 double dy=points[i].second;
36.                 origin_dist[i]=sqrt(dx*dx&#4
37. 3;dy*dy);
38.         }
39.         //状态dp数组，dp[mask][i]表示mask状态下，最后到达点i的最短距离
40.         vector<vector<double>> dp(1<<n,vector<double>(n,INF));
41.         for(int i=0;i<n;i&#4
42. 3;&#4
43. 3;){
44.                 dp[1<<i][i]=origin_dist[i];
45.         }
46.         //状态转移
47.         for(int mask=1;mask<(1<<n);mask&#4
48. 3;&#4
49. 3;){
50.                 for(int i=0;i<n;i&#4
51. 3;&#4
52. 3;){
53.                         if(!mask&(1<<i))  continue;
54.                         for(int j=0;j<n;j&#4
55. 3;&#4
56. 3;){
57.                                 if(mask&(1<<j)) continue;
58.                                 int new_mask=mask | (1<<j);
59.                                 dp[new_mask][j]=min(dp[new_mask][j],dp[mask][i]&#4
60. 3;dist[i][j]);
61.                         }
62.                 }
63.         }
64.         double ans=INF;
65.         int full_mask=(1<<n)-1;
66.         for(int i=0;i<n;i&#4
67. 3;&#4
68. 3;){
69.                 ans=min(ans,dp[full_mask][i]);
70.         }
71.         cout<<setprecision(2)<<fixed<<ans<<endl;
72.         return 0;
73. }

复制代码

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复制

1. 5 4
3. 1 3 10000 118014
5. 1 1 1 1
6. 2 3 10000
7. 2 1 1

复制代码

输出 #1复制

1. 118014
3. 1

复制代码

[size=4
]分析/提示

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

1. #include<bits/stdc&#4
2. 3;&#4
3. 3;.h>
4. using namespace std;
5. int main(){
6.         ios::sync_with_stdio(false);
7.         cin.tie(0);
8.         int n,q;
9.         cin>>n>>q;
10.         //相当于一个二维数组，数组中的每个元素是一个哈希表，map中的键和值表示某个柜子的格数和存储的物品
11.         vector<unordered_map<int,int>> lockers(n&#4
12. 3;1);
13.         for(int x=0;x<q;x&#4
14. 3;&#4
15. 3;){
16.                 int num,i,j,k;
17.                 cin>>num>>i>>j;
18.                 if(num==1){
19.                         cin>>k;
20.             lockers[i][j]=k;
21.                 }else if(num==2){
22.                         cout<<lockers[i][j]<<endl;
23.                 }
24.         }
25.         return 0;
26. }

复制代码

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复制

1. 9
2. 2 2 1 3 3 3 2 3 1

复制代码

输出 #1复制

1. 2

复制代码

[size=4
]分析/提示

数据规模与约定

• 对于 30% 的数据，保证 n≤105。
  
• 对于 100% 的数据，保证 1≤n≤10
  7
  &#4
  3;1，1≤ai​≤109。
  

提示

• 请留意数据读入对程序服从造成的影响。
  
• 请留意本题的空间限制为 4
   Mb。
  

1. #include<bits/stdc&#4
2. 3;&#4
3. 3;.h>
4. using namespace std;
5. int main(){
6.         ios::sync_with_stdio(false);
7.         cin.tie(0);
8.        
9.         int n,ans=0;
10.         cin>>n;
11.     for(int i=0;i<n;i&#4
12. 3;&#4
13. 3;){
14.             int a;
15.             cin>>a;
16.             ans^=a;
17.         }
18.         cout<<ans;
19. }

复制代码

4
、组合数题目杨辉三角&#4
3;前缀和

杨辉三角公式：c[j]=c[i-1][j-1]&#4
3;c[i-1][j] 
c[j]表现从i种物品中选取j种的组合方案数，即为选第i个(c[i-1][j-1])和不选第i个物品(c[i-1][j])的组合数之和。
前缀和：即依次累加前面的值
例题
[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. 1 2
2. 3 3

复制代码

输出 #1复制

1. 1

复制代码

输入 #2复制

1. 2 5
2. 4
3. 5
4. 6 7

复制代码

输出 #2复制

1. 0
2. 7

复制代码

[size=4
]分析/提示

【样例1分析】
在所有大概的情况中，只有 (12​)=2 一种情况是 2 的倍数。

1. #include<bits/stdc&#4
2. 3;&#4
3. 3;.h>
4. using namespace std;
5. int main(){
6.         int t,k;
7.         cin>>t>>k;
8.         const int max_n=2000;
9.         //c[i][j]表示从i种物品中选取j种，有多少种组合方式 模k
10.         vector<vector<int>> c(max_n&#4
11. 3;1,vector<int>(max_n&#4
12. 3;1,0));
13.         //valid[i][j]表示当前组合方式的数量是否为k的倍数
14.         vector<vector<int>> valid(max_n&#4
15. 3;1,vector<int>(max_n&#4
16. 3;1,0));
17.         //row_sum[i][j]表示 当前情况所有的有效标记和
18.         vector<vector<int>> row_sum(max_n&#4
19. 3;1,vector<int>(max_n&#4
20. 3;1,0));
21.         //标记处理
22.         for(int i=1;i<=max_n;i&#4
23. 3;&#4
24. 3;){
25.                 c[i][0]=1%k;
26.                 if(i>=1) c[i][i]=1%k; //初始化
27.                 for(int j=1;j<i;j&#4
28. 3;&#4
29. 3;){
30.                         c[i][j]=(c[i-1][j-1]&#4
31. 3;c[i-1][j])%k; //杨辉三角 c[i][j]=c[i-1][j-1]&#4
32. 3;c[i-1][j]
33.                 }
34.                 for(int j=0;j<=i;j&#4
35. 3;&#4
36. 3;){
37.                         valid[i][j]=(c[i][j]==0)?1:0;
38.                 }
39.                 row_sum[i][0]=valid[i][0]; //初始化
40.                 for(int j=1;j<=i;j&#4
41. 3;&#4
42. 3;){
43.                         row_sum[i][j]=row_sum[i][j-1]&#4
44. 3;valid[i][j]; //选择1~j-1个和选择j个的有效标记之和
45.                 }
46.         }
47.         while(t--){
48.                 int n,m;
49.                 cin>>n>>m;
50.                 int ans=0;
51.                 for(int i=0;i<=n;i&#4
52. 3;&#4
53. 3;){
54.                         int j_upper=min(m,i);
55.                         ans&#4
56. 3;=row_sum[i][j_upper];
57.                 }
58.                 cout<<ans<<endl;
59.         }
60.         return 0;
61. }

复制代码

5、素数查找

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

如题，给定一个范围 n，有 q 个询问，每次输出第 k 小的素数。
[size=4
]输入格式

第一行包含两个正整数 n,q，分别表现查询的范围和查询的个数。
接下来 q 行每行一个正整数 k，表现查询第 k 小的素数。
[size=4
]输特别式

输出 q 行，每行一个正整数表现答案。
[size=4
]输入输出样例

输入 #1复制

1. 100 5
2. 1
3. 2
4. 3
5. 4
7. 5

复制代码

输出 #1复制

1. 2
2. 3
3. 5
4. 7
5. 11

复制代码

1. /*
2. //试除法
3. bool isPrime(int n){
4.         if(n<=1) return false;
5.         for(int i=2;i*i<=n;i&#4
6. 3;&#4
7. 3;){
8.                 if(n%i==0) return false;
9.         }
10.         return true;
11. }
12. //埃拉托斯特尼筛法
13. void sieveOfEratosthenes(int n){
14.         vector<bool> prime(n&#4
15. 3;1,true);
16.         prime[0]=false,prime[1]=false;
17.         for(int i=2;i<=n;i&#4
18. 3;&#4
19. 3;){
20.                 if(prime[i]){
21.                         //筛除所有的i的倍数，从i*i开始
22.                         for(int j=i*i;j<=n;j&#4
23. 3;i){
24.                                 prime[j]=false;
25.                         }
26.                 }
27.         }
28. }
29. */
30. #include<bits/stdc&#4
31. 3;&#4
32. 3;.h>
33. using namespace std;
34. int main(){
35.         ios::sync_with_stdio(false);
36.         cin.tie(0);
37.        
38.         int n,q;
39.         cin>>n>>q;
40.         //欧拉筛法
41.         vector<bool> isPrime(n&#4
42. 3;1,true);
43.         vector<int> primes;
44.         for(int i=2;i<=n;i&#4
45. 3;&#4
46. 3;){
47.                 if(isPrime[i]){
48.                         primes.push_back(i);
49.                 }
50.                 for(int j=0;j<primes.size()&&i*primes[j]<=n;j&#4
51. 3;&#4
52. 3;){
53.                         isPrime[i*primes[j]]=false;
54.                         if(i%primes[j]==0) break;//确保每个和数只被筛一次
55.                 }
56.         }
57.         while(q--){  //先判断q的值再进行q--运算！
58.                 int k;
59.                 cin>>k;
60.                 cout<<primes[k-1]<<&#34
61. ;\n&#34
62. ;;
63.         }
64.         return 0;
65. }

复制代码

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复制

1. 3 60

复制代码

输出 #1复制

1. 4

复制代码

[size=4
]分析/提示

P,Q 有 4
 种：

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

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

1. #include<bits/stdc&#4
2. 3;&#4
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&#4
4. 3;&#4
5. 3;){                if(k%a==0){                        int b=k/a;                        if(gcd(a,b)==1){                                ans&#4
6. 3;=(a==b)?1:2;                        }                }        }         cout<<ans<<endl;        return 0;}

复制代码

7、前缀和&#4
3;kadane算法（求最大连续子集）

前缀和：即累加的意思，依次保留每次累加的结果。
kadane算法：求数组中的最大连续子集。

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

复制代码

例题
[size=4
]标题形貌

为了更好的备战 NOIP2013，电脑组的几个女孩子 LYQ,ZSC,ZHQ 以为，我们不但需要机房，我们还需要活动，于是就决定找校长申请一块电脑组的课余活动场地，听说她们都是电脑组的高手，校长没有立刻答应他们，而是先给她们出了一道数学题，并且告诉她们：你们能获得的活动场地的面积就是你们能找到的这个最大的数字。
校长先给他们一个 n×n 矩阵。要求矩阵中最大加权矩形，即矩阵的每一个元素都有一权值，权值界说在整数集上。从中找一矩形，矩形大小无限制，是此中包含的所有元素的和最大 。矩阵的每个元素属于 [−127,127] ,例如

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

复制代码

在左下角：

1. 9  2-4
2.   1-1  8

复制代码

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

第一行：n，接下来是 n 行 n 列的矩阵。
[size=4
]输特别式

最大矩形（子矩阵）的和。
[size=4
]输入输出样例

输入 #1复制

1. 4
2. 0 -2 -7 0 9 2 -6 2-4
3. 1 -4
4.   1 -1 8  0 -2

复制代码

输出 #1复制

1. 15

复制代码

[size=4
]分析/提示

1≤n≤120

1. #include<bits/stdc&#4
2. 3;&#4
3. 3;.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&#4
4. 3;&#4
5. 3;){                current_max=max(arr[i],current_max&#4
6. 3;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&#4
7. 3;&#4
8. 3;){                for(int j=0;j<n;j&#4
9. 3;&#4
10. 3;){                        cin>>matrix[i][j];                }        }        //每一行的前缀和         vector<vector<int>> prefix(n,vector<int>(n&#4
11. 3;1,0));        for(int i=0;i<n;i&#4
12. 3;&#4
13. 3;){                for(int j=1;j<=n;j&#4
14. 3;&#4
15. 3;){                        prefix[i][j]=prefix[i][j-1]&#4
16. 3;matrix[i][j-1];                }        }        int max_sum=INT_MIN;        //遍历所有的列区间         for(int l=0;l<n;l&#4
17. 3;&#4
18. 3;){                for(int r=l;r<n;r&#4
19. 3;&#4
20. 3;){                        vector<int> temp(n);                        for(int i=0;i<n;i&#4
21. 3;&#4
22. 3;){                                temp[i]=prefix[i][r&#4
23. 3;1]-prefix[i][l];                        }                        int current_max=Kadane(temp);                        max_sum=max(current_max,max_sum);                }        }        cout<<max_sum<<endl;        return 0;}

复制代码

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。