@[TOC]
Contest100000585 - 《算法笔记》4.7小节——算法初步->其他高效技巧与算法
4.7 其他高效技巧与算法
4.7.1 打表
4.7.2 活用递推
例题：PAT B1040/A10993 有几个PAT
https://pintia.cn/problem-sets/994805260223102976/problems/994805282389999616
/*
思想：找到A，则PAT的个数=A左边P的个数 * A右边T的个数；
为了统计P、T的个数，设置变量leftNumP[]数组与rightNumT（不用数组应为记录T时候可以直接计算出PAT个数最终结果），实时更新即可
*/
//4.7.2 活用递推PAT B1040有几个PAT
/*
思想：找到A，则PAT的个数=A左边P的个数 * A右边T的个数；
为了统计P、T的个数，设置变量leftNumP[]数组
与rightNumT（不用数组应为记录T时候可以直接计算出PAT个数最终结果），实时更新即可
注意乘积的取模
// gets(str);PAT不支持gets
换成 cin.getline(str,MAXN);//读入字符串
*/
#include <iostream>
#include <cstring>
#include <cstdio>
using namespace std;
const int MAXN = 100010;
const int MOD = 1000000007;
char str[MAXN];//字符串
int leftNumP[MAXN] = {0};//每一位左边（含）P的个数
int main()
{
// gets(str);PAT不支持gets
cin.getline(str,MAXN);//读入字符串
int len = strlen(str);//字符串长度
for(int i=0;i<len;i++)//从左到右遍历字符串
{
if(i>0)//如果不是0号位
{
leftNumP[i] = leftNumP[i-1];//继承上一位的结果
}
if(str[i] == 'P')//当前位是P
{
leftNumP[i]++;//令leftNumP[i]加1
}
}
int ans = 0,rightNumT = 0;//ans为答案，rightNumT记录右边T的个数
for(int i=len-1;i>=0;i--)//从右向左遍历字符串
{
if(str[i] == 'T')//当前位是T
{
rightNumT++;//右边T的个数加1
}
else if(str[i] == 'A')//当前位是A
{
ans = (ans+leftNumP[i] * rightNumT)%MOD;//累积乘积
}
}
printf("%d\n",ans);
return 0;
}
4.7.3 随机选择算法
随机选择算法
//4.7.3 随机选择算法
//从A[left,right]中返回第K大的数
int randSelect(int A[],int left,int right,int K)
{
if(left == right) return A[left];//边界
int p = randPartition(A,left,right);//划分后主元的位置为p
int M = p - left + 1;//A[p]是A[left,right]中的第M大
if(K == M) return A[p];//找到第K大的数
if(K < M)
{//第K大的数在主元左侧
return randSelect(A,left,p - 1,K);//往主元左侧找第K大
}
else
{//第K大的数在主元右侧
return randSelect(A,p + 1,right,K - M);//往主元右侧找第K-M大的数
}
}
随机选择算法应用
//4.7.3 随机选择算法应用
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <ctime>
#include <cmath>//用于round
#include <cstring>
#include <algorithm>
using namespace std;
const int maxn = 100010;
int A[maxn],n;//A存放所有整数，n为其个数
//随机选取主元，对区间[left,right]进行划分
int randPartition(int A[],int left,int right)
{
//生成[left,right]内的随机数
int p = (round(1.0*rand()/RAND_MAX*(right-left)+left));
swap(A[p],A[left]);//交换A[p]和A[left]
//以下为原先Partition函数划分过程，不需要改变任何东西
int temp = A[left];//将A[left]存放至临时变量temp
while(left < right)
{//此处与temp相比是否需要带等号，
//<=与>=结果差别不大，此处向下取整，所以用<=
while(left < right && A[right] > temp) right--;//反复左移right
A[left] = A[right];//将后面比基准值小的数与基准值互换
while(left < right && A[left] <= temp) left++;//反复右移left
A[right] = A[left];//将前面比基准值大的数与基准值互换
}
A[left] = temp;//把temp放到left与right相遇的地方
return left;//返回相遇的下标
}
//随机选择算法，从A[left,right]中返回第K大的数，并进行切分
void randSelect(int A[],int left,int right,int K)
{
if(left == right) return;//边界
int p = randPartition(A,left,right);//划分后主元的位置为p
int M = p - left + 1;//A[p]是A[left,right]中的第M大
if(K == M) return;//找到第K大的数
if(K < M)
{//第K大的数在主元左侧
randSelect(A,left,p - 1,K);//往主元左侧找第K大
}
else
{//第K大的数在主元右侧
randSelect(A,p + 1,right,K - M);//往主元右侧找第K-M大的数
}
}
int main()
{
srand((unsigned)time(NULL));//初始化随机数种子
//sum和sum1记录所有整数之和与切分后前n/2个元素之和
int sum = 0,sum1 = 0;
scanf("%d",&n);//整数个数
for(int i = 0;i<n;i++)
{
scanf("%d",&A[i]);//输入整数
sum += A[i];//累计所有整数之和
}
randSelect(A,0,n-1,n/2);//寻找第n/2大的数，并进行切分
for(int i=0;i<n/2;i++)
{
sum1+=A[i];//累计较小的子集合中元素之和
}
printf("%d\n",(sum - sum1) - sum1);//求两个子集合的元素和之差
return 0;
}
Codeup习题
http://codeup.cn/contest.php?cid=100000587
5067 Problem A 求第k大数
http://codeup.cn/problem.php?cid=100000587&pid=0
//5067 Problem A 求第k大数
//4.7.3 随机选择算法应用
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <ctime>
#include <cmath>//用于round
#include <cstring>
#include <algorithm>
using namespace std;
const int maxn = 100010;
int A[maxn],n;//A存放所有整数，n为其个数
//随机选取主元，对区间[left,right]进行划分
int randPartition(int A[],int left,int right)
{
//生成[left,right]内的随机数
int p = (round(1.0*rand()/RAND_MAX*(right-left)+left));
swap(A[p],A[left]);//交换A[p]和A[left]
//以下为原先Partition函数划分过程，不需要改变任何东西
int temp = A[left];//将A[left]存放至临时变量temp
while(left < right)
{//此处与temp相比是否需要带等号，
//<=与>=结果差别不大，此处向下取整，所以用<=
while(left < right && A[right] > temp) right--;//反复左移right
A[left] = A[right];//将后面比基准值小的数与基准值互换
while(left < right && A[left] <= temp) left++;//反复右移left
A[right] = A[left];//将前面比基准值大的数与基准值互换
}
A[left] = temp;//把temp放到left与right相遇的地方
return left;//返回相遇的下标
}
int randSelect(int A[],int left,int right,int K)
{
if(left == right) return A[left];//边界
int p = randPartition(A,left,right);//划分后主元的位置为p
int M = p - left + 1;//A[p]是A[left,right]中的第M大
if(K == M) return A[p];//找到第K大的数
if(K < M)
{//第K大的数在主元左侧
return randSelect(A,left,p - 1,K);//往主元左侧找第K大
}
else
{//第K大的数在主元右侧
return randSelect(A,p + 1,right,K - M);//往主元右侧找第K-M大的数
}
}
int main()
{
int n,k;
while(cin>>n>>k)
{
for(int i=0;i<n;i++)
cin>>A[i];
//注意此处调用函数时候，K取值，K不为k，题目要求，表示很迷QWQ：
//（关于第k大的数：例如序列{1,2,3,4,5,6}中第3大的数是4。）
cout<<randSelect(A,0,n-1,n-k+1)<<endl;
}
return 0;
}
总结下：
打表暴力算数组；巧用递推看规律；随机选择算法类似快排
三种方法各有特色
