自己做的网站如何兼容ie11,深圳网络推广大师,怎么让WORDPRESS首页显示菜单,网站城市切换如何做时间优化 一、调试方法1. 输出调试2. 构造样例 二、时间优化1. 前缀和1.1 概念1.2 例题Ⅰ 区间最多数码Ⅱ 双字母字符串Ⅲ Wandering...Ⅳ 数对数目 2. 排序例题选择排序过程 一、调试方法
1. 输出调试
cout 是一个强大的调试工具#xff0c;可以帮助我们查看程序的状态和变… 时间优化 一、调试方法1. 输出调试2. 构造样例 二、时间优化1. 前缀和1.1 概念1.2 例题Ⅰ 区间最多数码Ⅱ 双字母字符串Ⅲ Wandering...Ⅳ 数对数目 2. 排序例题选择排序过程 一、调试方法
1. 输出调试
cout 是一个强大的调试工具可以帮助我们查看程序的状态和变量的值。在调试过程中可以使用 cout 来输出变量的值以验证程序的正确性。虽然是第一节课学的
2. 构造样例
构造的样例包括下面的两种
边界信息特殊样例
这两种应该说是蹭分 debug 的一个工具尤其注意分辨 continue、break、return 0;。特殊样例一定要考虑极端情况。好吧实在不行就打表
二、时间优化
1. 前缀和
1.1 概念
仅有两个元素的容斥关系如下 ∣ A ∪ B ∣ ∣ A ∣ ∣ B ∣ − ∣ A ∩ B ∣ |A \cup B| |A| |B| - |A \cap B| ∣A∪B∣∣A∣∣B∣−∣A∩B∣ 根据这一公式我们可以求出二维前缀和的公式 s i , j s i − 1 , j s i , j − 1 − s i − 1 , j − 1 a i , j s_{i,j}s_{i-1,j}s_{i,j-1}-s_{i-1,j-1}a_{i,j} si,jsi−1,jsi,j−1−si−1,j−1ai,j 从而逆推出二维区间和公式 s x 1 , y 1 ∼ 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 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} sx1,y1∼x2,y2sx2,y2−sx1−1,y2−sx2,y1−1sx1−1,y1−1
1.2 例题
Ⅰ 区间最多数码
给定一个长度为 n n n 的数列 a 1 , a 2 , ⋯ , a n a_1,a_2,\cdots,a_n a1,a2,⋯,an。小猴会对你进行 q q q 次询问每次询问要求你计算出在区间 [ l , l 1 , … , r ] [l,l1,…,r] [l,l1,…,r] 中出现次数最多的十进制数码是谁 0 × 9 0\times 9 0×9 中的一个以及该十进制数码出现了多少次如果有多个数码出现次数相同则选择数值最小的数码。
首先我们考虑暴力方法大致代码如下
memset(sum,0,sizeof(sum));
for(int il;ir;i){int numa[i];do{sum[num%10];num/10;}while(num);
}
int ans,cnt0;
for(int i0;i9;i)if(sum[i]cnt){cntsum[i];ansi;}
coutans cntendl;这里新增加一个知识点 do-while结构也就是先执行然后进行 while 循环条件的判断。这主要是因为 num 是 0 0 0 的时候也是需要统计 0 0 0 这个数码的。
所以前缀和桶 就这样登场了。
参考答案
#includebits/stdc.h
using namespace std;
int n,q,l,r,num;
int a[200010][10],s[200010][10];
int main(){cinnq;for(int i1;in;i){cinnum;do{a[i][num%10];num/10;}while(num);}for(int i1;in;i)for(int j0;j10;j)s[i][j]s[i-1][j]a[i][j];while(q--){cinlr;int ans,cnt0;for(int i0;i10;i)if(s[r][i]-s[l-1][i]cnt){cnts[r][i]-s[l-1][i];ansi;}coutans cntendl;}return 0;
}Ⅱ 双字母字符串
小猴正在挑战一个关于字符串的简单题给定 n n n 个只包含大小写字母的字符串所有字符串的长度均为 2 2 2。要求在这 n n n 个字符串中找出任意两个字符串 s , t s,t s,t使得 s , t s,t s,t 在不区分大小写的情况下有且只有一个位置上的字母相同请问这样成对的字符串一共有多少对。
首先还是先上暴力
#includebits/stdc.h
using namespace std;
int t,n;
string a[100010];
int main(){cint;while(t--){cinn;for(int i1;in;i)cina[i];int cnt0;for(int i1;in;i)for(int ji1;jn;j){int match0;for(int k0;k2;k)if(tolower(a[i][k])tolower(a[j][k]))match;if(match1)cnt;}coutcntendl;}return 0;
}接下来上技巧
考虑两个数组来统计第一个字母和第二个字母的出现次数以及一个 tot 数组统计每个字符串出现的个数。
#includebits/stdc.h
using namespace std;
const int BYTE256;
int t,n;
int fst[BYTE],scd[BYTE],tot[BYTE][BYTE];
int main(){ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);cint;while(t--){cinn;memset(fst,0,sizeof(fst));memset(scd,0,sizeof(scd));memset(tot,0,sizeof(tot));long long ans0;for(int i1;in;i){string s;cins;s[0]tolower(s[0]),s[1]tolower(s[1]);ansfst[s[0]]scd[s[1]]-tot[s[0]][s[1]]*2;fst[s[0]],scd[s[1]],tot[s[0]][s[1]];}coutansendl;}return 0;
}Ⅲ Wandering…
给出一个整数数列 a 1 , a 2 , ⋯ , a n a_1,a_2,\cdots,a_n a1,a2,⋯,an这个数列可能包含负数。一个机器人初始在数轴的坐标 0 0 0 点按照以下流程移动 向正方向移动 a 1 a_1 a1 单位长度。 向正方向移动 a 1 a_1 a1 单位长度再向正方向移动 a 2 a_2 a2 单位长度。 ⋯ \cdots ⋯ 向正方向移动 a 1 a_1 a1 单位长度再向正方向移动 a 2 a_2 a2 单位长度。 ⋯ \cdots ⋯ 最后向正方向移动 a n a_n an 单位长度。 你需要求出机器人在整个移动过程中坐标的最大值。
参考代码就这么短……
#includebits/stdc.h
using namespace std;
long long n,pos,ans;
long long a[200010],res[200010],maxOff[200010];
int main(){cinn;for(int i1;in;i){cina[i];res[i]res[i-1]a[i];maxOff[i]max(maxOff[i-1],res[i]);ansmax(ans,posmaxOff[i]);posres[i];}coutans;return 0;
}Ⅳ 数对数目
给出一个序列求出其中满足 a i i a j j a_iia_jj aiiajj 的个数 1 ≤ i , j ≤ n 1\le i,j \le n 1≤i,j≤n。
先暴力
#includebits/stdc.h
using namespace std;
long long n,cnt,a[2000010];
int main(){cinn;for(int i1;in;i)cina[i];for(int l1;ln;l)for(int rl1;rn;r)if(a[l]lla[r]a[r]r)cnt;coutcnt;return 0;
}前缀信息优化单调性为 a[i]i
#includebits/stdc.h
using namespace std;
long long n,ans;
long long a[2000010],s[2000010];
int main(){cinn;for(int i1;in;i){cina[i];s[i]s[i-1](a[i]i);if(a[i]i)anss[a[i]-1];}coutans;return 0;
}2. 排序
例题
选择排序过程
还记得我们之前打的暴力
#include iostream
#include vector
using namespace std;void selectionSort(vectorint 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;vectorint 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;
}现在来优化。
#includebits/stdc.h
using namespace std;
int n,m,iter,lmt;
int num[100010],num2idx[100010];
int main(){cinnm;for(int i1;in;i){cinnum[i];num2idx[num[i]]i;}while(m--){cinlmt;while(iterlmt){//iter永远是numiter;int idxnum2idx[iter];swap(num[idx],num[iter]);num2idx[iter]iter;num2idx[num[idx]]idx;}for(int i1;in;i)coutnum[i] ;coutendl;}return 0;
}
