C++知识点总结(55)：时间优化

一、调试方法

1. 输出调试

cout 是一个强大的调试工具，可以帮助我们查看程序的状态和变量的值。在调试过程中，可以使用 cout 来输出变量的值，以验证程序的正确性。（虽然是第一节课学的）

2. 构造样例

构造的样例包括下面的两种：

• 边界信息
• 特殊样例

这两种应该说是蹭分 debug 的一个工具，尤其注意分辨 continue、break、return 0;。特殊样例一定要考虑极端情况。好吧，实在不行就打表

二、时间优化

1. 前缀和

1.1 概念

仅有两个元素的容斥关系如下：
$$|A\cup B|=|A|+|B|-|A\cap B|$$
根据这一公式，我们可以求出二维前缀和的公式：
$$s_{i,j}=s_{i-1,j}+s_{i,j-1}-s_{i-1,j-1}+a_{i,j}$$
从而逆推出二维区间和公式：
$$s_{x_1,y_1\sim x_2,y_2}=s_{x_2,y_2}-s_{x_1-1,y_2}-s_{x_2,y_1-1}+s_{x_1-1,y_1-1}$$

1.2 例题

Ⅰ 区间最多数码

给定一个长度为 $n$ 的数列 $a_1,a_2,\cdots ,a_n$。小猴会对你进行 $q$ 次询问，每次询问要求你计算出在区间 $[l,l+1,\dots ,r]$ 中出现次数最多的十进制数码是谁（$0\times 9$ 中的一个）以及该十进制数码出现了多少次，如果有多个数码出现次数相同，则选择数值最小的数码。

首先我们考虑暴力方法，大致代码如下：

memset(sum,0,sizeof(sum));
for(int i=l;i<=r;i++){int num=a[i];do{sum[num%10]++;num/=10;}while(num);
}
int ans,cnt=0;
for(int i=0;i<=9;i++)if(sum[i]>cnt){cnt=sum[i];ans=i;}
cout<<ans<<" "<<cnt<<endl;

这里新增加一个知识点 do-while结构，也就是先执行然后进行 while 循环条件的判断。这主要是因为 num 是 $0$ 的时候也是需要统计 $0$ 这个数码的。

所以，前缀和&桶 就这样登场了。

参考答案：

#include<bits/stdc++.h>
using namespace std;
int n,q,l,r,num;
int a[200010][10],s[200010][10];
int main(){cin>>n>>q;for(int i=1;i<=n;i++){cin>>num;do{a[i][num%10]++;num/=10;}while(num);}for(int i=1;i<=n;i++)for(int j=0;j<10;j++)s[i][j]=s[i-1][j]+a[i][j];while(q--){cin>>l>>r;int ans,cnt=0;for(int i=0;i<10;i++)if(s[r][i]-s[l-1][i]>cnt){cnt=s[r][i]-s[l-1][i];ans=i;}cout<<ans<<" "<<cnt<<endl;}return 0;
}

Ⅱ 双字母字符串

小猴正在挑战一个关于字符串的"简单题"：给定 $n$ 个只包含大小写字母的字符串，所有字符串的长度均为 $2$。要求在这 $n$ 个字符串中找出任意两个字符串 $s,t$，使得 $s,t$ 在不区分大小写的情况下有且只有一个位置上的字母相同，请问这样成对的字符串一共有多少对。

首先还是先上暴力：

#include<bits/stdc++.h>
using namespace std;
int t,n;
string a[100010];
int main(){cin>>t;while(t--){cin>>n;for(int i=1;i<=n;i++)cin>>a[i];int cnt=0;for(int i=1;i<=n;i++)for(int j=i+1;j<=n;j++){int match=0;for(int k=0;k<2;k++)if(tolower(a[i][k])==tolower(a[j][k]))match++;if(match==1)cnt++;}cout<<cnt<<endl;}return 0;
}

接下来，上！技！巧！！

考虑两个数组来统计第一个字母和第二个字母的出现次数，以及一个 tot 数组统计每个字符串出现的个数。

#include<bits/stdc++.h>
using namespace std;
const int BYTE=256;
int t,n;
int fst[BYTE],scd[BYTE],tot[BYTE][BYTE];
int main(){ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);cin>>t;while(t--){cin>>n;memset(fst,0,sizeof(fst));memset(scd,0,sizeof(scd));memset(tot,0,sizeof(tot));long long ans=0;for(int i=1;i<=n;i++){string s;cin>>s;s[0]=tolower(s[0]),s[1]=tolower(s[1]);ans+=fst[s[0]]+scd[s[1]]-tot[s[0]][s[1]]*2;fst[s[0]]++,scd[s[1]]++,tot[s[0]][s[1]]++;}cout<<ans<<endl;}return 0;
}

Ⅲ Wandering…

给出一个整数数列 $a{}_1,a_2,\cdots ,a_n$，这个数列可能包含负数。一个机器人初始在数轴的坐标 $0$ 点，按照以下流程移动：

向正方向移动 $a_1$ 单位长度。
向正方向移动 $a_1$ 单位长度，再向正方向移动 $a_2$ 单位长度。
$\cdots$
向正方向移动 $a_1$ 单位长度，再向正方向移动 $a_2$ 单位长度。
$\cdots$
最后向正方向移动 $a_n$ 单位长度。

你需要求出机器人在整个移动过程中，坐标的最大值。

参考代码（就这么短……）

#include<bits/stdc++.h>
using namespace std;
long long n,pos,ans;
long long a[200010],res[200010],maxOff[200010];
int main(){cin>>n;for(int i=1;i<=n;i++){cin>>a[i];res[i]=res[i-1]+a[i];maxOff[i]=max(maxOff[i-1],res[i]);ans=max(ans,pos+maxOff[i]);pos+=res[i];}cout<<ans;return 0;
}

Ⅳ 数对数目

给出一个序列，求出其中满足 $a_i<i<a_j<j$ 的个数（$1\le i,j\le n$）。

先暴力：

#include<bits/stdc++.h>
using namespace std;
long long n,cnt,a[2000010];
int main(){cin>>n;for(int i=1;i<=n;i++)cin>>a[i];for(int l=1;l<n;l++)for(int r=l+1;r<=n;r++)if(a[l]<l&&l<a[r]&&a[r]<r)cnt++;cout<<cnt;return 0;
}

前缀信息优化：单调性为 a[i]<i

#include<bits/stdc++.h>
using namespace std;
long long n,ans;
long long a[2000010],s[2000010];
int main(){cin>>n;for(int i=1;i<=n;i++){cin>>a[i];s[i]=s[i-1]+(a[i]<i);if(a[i]<i)ans+=s[a[i]-1];}cout<<ans;return 0;
}

2. 排序

例题

选择排序过程

还记得我们之前打的暴力：

#include <iostream>
#include <vector>
using namespace std;void selectionSort(vector<int>& A, int q) {int n = A.size();for (int i = 0; i < q; i++) {int minIndex = i;for (int j = i + 1; j < n; j++) {if (A[j] < A[minIndex]) {minIndex = j;}}swap(A[i], A[minIndex]);}
}int main() {int n, m;cin >> n >> m;vector<int> A(n);for (int i = 0; i < n; i++) {cin >> A[i];}for (int i = 0; i < m; i++) {int q;cin >> q;selectionSort(A, q);for (int j = 0; j < n; j++) {cout << A[j] << " ";}cout << endl;}return 0;
}

现在来优化。

#include<bits/stdc++.h>
using namespace std;
int n,m,iter,lmt;
int num[100010],num2idx[100010];
int main(){cin>>n>>m;for(int i=1;i<=n;i++){cin>>num[i];num2idx[num[i]]=i;}while(m--){cin>>lmt;while(iter<lmt){//iter永远是numiter++;int idx=num2idx[iter];swap(num[idx],num[iter]);num2idx[iter]=iter;num2idx[num[idx]]=idx;}for(int i=1;i<=n;i++)cout<<num[i]<<" ";cout<<endl;}return 0;
}