模板原型 - 基础篇
学习网站
一、进制转换
十进制数 n 转 q 进制
int n,a[1000],len=0;
cin>>n;
do{
a[len++] = n % q;
n /= q;
}while(n>0);
for(int i= len-1;i>=0;i--){
cout<<a[i];
}
p进制数 n 转 Q进制
int y = 0,product = 1; //product 不断乘以p
while( n != 0){
y += (n%10) * product;
n /= 10;
product *= p
}
二、二分查找
① 查找指定元素
// 查找指定元素
int findX(int a[],int l,int r,int x){
int mid;
while( l<= r){
//注意<= 号
mid = (l + r) / 2;
if(a[mid]==x){
return mid;
}else if(a[mid] < x){
l = mid + 1;
}else{
r = mid - 1;
}
}
return -1;
}
int main(){
cout<<findX(a,0,n-1,x); //n为数组长度
}
② 查找第一个大于等于 x 值的序列下标
// 查找第一个大于等于 x 值的序列下标
int findX(int a[],int l,int r,int x){
int mid;
while(l < r){
// 注意< 号
mid = (l+r)/2;
if(a[mid] >= x){
//
r = mid;
}else{
l = mid + 1;
}
}
return l; // 注意return l
}
③ 查找第一个大于 x 值的序列下标
int findX(int a[],int l,int r,int x){
int mid;
while(l<=r){
mid = (l+r)/2;
if(a[mid]<=x){
l = mid + 1;
}else{
r = mid - 1;
}
}
return l;
}
④ 单峰序列
单峰序列是指,在这个序列中存在一个位置,满足这个位置的左侧(含该位置)是严格递增的、右侧(含该位置)是严格递减的,这个位置被称作峰顶位置。现在给定一个单峰序列,求峰顶位置的下标。
int maxIn = 0;
int mx = 0;
void findX(int a[],int l,int r){
if(l>r)
return ;
int mid = (l+r)/2;
if(a[mid]>mx){
mx = a[mid];
maxIn = mid;
}
findX(a,mid+1,r);
findX(a,l,mid-1);
}
三、双指针
① 两数之和
给定一个严格递增序列A和一个正整数k,在序列A中寻找不同的下标i、j,使得Ai+Aj=k。问有多少对(i,j)同时i<j满足条件。
int i=0,j=n-1,cnt=0;
while(i<j){
if(a[i]+a[j]==k){
cnt++;
i++;
j--;
}else if(a[i]+a[j]<k){
i++;
}else{
j--;
}
}
② 序列合并
给定两个升序的正整数序列A和B,将它们合并成一个新的升序序列并输出。
int merge() {
int i = 0, j = 0, counter = 0;
while (i < n && j < m) {
if (a[i] < b[j]) {
mergedNums[counter++] = a[i++];
} else {
mergedNums[counter++] = b[j++];
}
}
while (i < n) {
mergedNums[counter++] = a[i++];
}
while (j < m) {
mergedNums[counter++] = b[j++];
}
return counter;
}
③ 集合求交
给定一个包含 n 个正整数的集合 S1,再给定一个包含 m 个正整数的集合 S2,求两个集合的交集。
void getIntersection() {
int i = 0, j = 0;
while (i < n && j < m) {
if (a[i] == b[j]) {
intersection.push_back(a[i]);
i++, j++;
} else if (a[i] < b[j]) {
i++;
} else {
j++;
}
}
}
④ 集合求并
给定一个包含 n 个正整数的集合S1,再给定一个包含 m 个正整数的集合S2,求两个集合的并集。
void getUnionSet() {
int i = 0, j = 0;
while (i < n && j < m) {
if (a[i] == b[j]) {
unionSet.push_back(a[i]);
i++, j++;
} else if (a[i] < b[j]) {
unionSet.push_back(a[i++]);
} else {
unionSet.push_back(b[j++]);
}
}
while (i < n) {
unionSet.push_back(a[i++]);
}
while (j < m) {
unionSet.push_back(b[j++]);
}
}
四、其他高效技巧与算法
① 区间和
给定由n个正整数组成的序列A,接下来给出k个查询,每个查询指定两个正整数l、r,计算序列从第l个整数至第r个整数之和,即Al+Al+1+…+Ar。
int main() {
int n;
cin >> n;
vector<int> A(n + 1);
vector<int> prefixSum(n + 1, 0);
// 读取原数组并构建前缀和数组
for (int i = 1; i <= n; ++i) {
cin >> A[i];
prefixSum[i] = prefixSum[i - 1] + A[i];
}
int k;
cin >> k;
for (int i = 0; i < k; ++i) {
int l, r;
cin >> l >> r;
// 计算区间和并输出结果
cout << prefixSum[r] - prefixSum[l - 1]