网站建设世纪明珠,厦门网站建设及维护,嵌入式转行到网站开发,网络公司 网站建设 小程序1.台阶问题#xff1a; 这道题目一看其实很容易想到可以用dp的板子去做#xff0c;并且只需要用一维dp即可#xff0c;其中dp的下标表示到达当前阶梯总共有多少种方法#xff0c;由于结果有可能会很大所以一定要记得边记录边模#xff0c;代码实现如下#xff1a;
#incl…1.台阶问题 这道题目一看其实很容易想到可以用dp的板子去做并且只需要用一维dp即可其中dp的下标表示到达当前阶梯总共有多少种方法由于结果有可能会很大所以一定要记得边记录边模代码实现如下
#includebits/stdc.h
using namespace std;
const int mod 100003;
int n,k;
int dp[100010];
int main(){ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);cinnk;dp[0]dp[1]1;for(int i2;in;i){for(int j1;jk;j){if(ij){dp[i](dp[i]dp[i-j]) % mod;} }}coutdp[n]%mod;return 0;
}
2.递增三元组 这一道题目的意思是比较好理解的我们需要考虑的是由于给的N的极限值是1e5所以暴力的方式时间复杂度n的三方肯定会爆于是我们就要考虑如何对时间复杂度进行优化。
我们可以这样进行考虑由于数组b是中间数组我们不妨先对三个数组进行排序然后我们对b进行枚举对于每一次枚举我们在a数组中找到所有小于当前枚举对应的b数组下标元素的个数然后再找到c数组中所有大于当前b数组下标所对应的元素个数再把当前符合条件的总个数加到ans上面即可。
再继续思考我们对于每次枚举然后在ac数组中查找符合要求的都可以通过二分进行查找从而降低时间复杂度。所以代码如下
#include iostream
#include cstdio
#include algorithm
using namespace std;typedef long long LL;
const int N 1e510;
int num[3][N];int main() {int n;scanf(%d, n);for(int i 0; i 3; i) for(int j 1; j n; j) scanf(%d, num[i][j]);for(int i 0; i 3; i)sort(num[i]1, num[i]n1);LL ans 0;//枚举B寻找A满足的个数以及C满足的个数相乘for(int i 1; i n; i) {int key num[1][i];//A中二分查找第一个不小于key的数的下标int pos1 lower_bound(num[0]1, num[0]n1, key)-num[0]-1;//C中二分查找第一个大于key的数的下标int pos2 upper_bound(num[2]1, num[2]n1, key)-num[2];if(pos1 1 pos2 n) {ans (LL)pos1*(n-pos21);}}coutansendl;return 0;
}这段代码有需要解释的地方
num[0]1这是指向num数组的第一个元素的下一个位置的指针。换句话说它指向num数组中的第二个元素。num[0]n1这是指向num数组的最后一个元素的下一个位置的指针。换句话说它指向num数组之后的第一个位置。lower_bound(num[0]1, num[0]n1, key)这是在num数组的第二个元素和最后一个元素之间不包括最后一个元素查找第一个不小于key的元素的迭代器。lower_bound(...)-num[0]-1这将返回的迭代器与num数组的第一个元素的指针相减然后减去1。这样我们得到的是找到的元素在num数组中的索引。
所以pos1存储的是key在num数组中的位置如果key不在num数组中则pos1将是key应该插入的位置以保持num数组的有序性。
简而言之这段代码在num数组中查找key的位置并返回其索引。如果key不在数组中则返回应该插入key的位置。
在C中指针的算术运算实际上是对指针所指向的内存地址进行算术运算。当两个指针指向同一个数组或同一个对象的成员时它们之间的差值表示两个元素之间的偏移量这个偏移量是以元素为单位而不是以字节为单位。
对于数组numnum[0]是一个指向数组第一个元素的指针。当我们执行lower_bound函数时得到的是一个迭代器它指向数组中第一个不小于key的元素。这个迭代器也是一个指针指向数组中的某个元素。
当从lower_bound返回的迭代器中减去num[0]时得到的是两个指针之间的偏移量这个偏移量表示从数组的第一个元素到找到的元素之间有多少个元素。因为lower_bound返回的迭代器指向的是数组中的元素而不是元素之间的空隙所以这个偏移量实际上就是找到的元素在数组中的下标从0开始计数。
最后减去1是因为我们希望得到的是下标而不是偏移量。在C中数组的下标是从0开始的而指针的偏移量是从1开始的即指向第一个元素的指针偏移量为0指向第二个元素的指针偏移量为1依此类推。因此减去1将偏移量转换为正确的下标。
所以lower_bound(...)-num[0]-1的结果就是找到的元素在数组中的下标。
第二种方法双指针优化
#include iostream
#include cstdio
#include algorithm
using namespace std;typedef long long LL;
const int N 1e510;
int num[3][N];int main() {int n;scanf(%d, n);for(int i 0; i 3; i) for(int j 1; j n; j) scanf(%d, num[i][j]);for(int i 0; i 3; i)sort(num[i]1, num[i]n1);LL ans 0;//枚举B寻找A满足的个数以及C满足的个数相乘int a 1, c 1;for(int i 1; i n; i) {int key num[1][i];while(an num[0][a] key) a;while(cn num[2][c] key) c;ans (LL)(a-1)*(n-c1);}coutansendl;return 0;
}
其实也就是将二分中的部分更改了一下。
之前的双指针算法时间复杂度的瓶颈为排序O(nlog2n) 考虑是否可以不排序在O(n)的时间内解决此问题呢
既然要排序实现快速的查找A中小于B[i]的数的个数可以将数组A中所有元素出现的次数存入一个哈希表中因为数组中元素的范围只有n5, 可以开一个大的数组cnta 作为哈希表。
在枚举B中元素时我们需要快速查找找小于B[i]的所有元素的总数只需要在枚举之前先将求出表中各数的前缀和即可。
查找C与查找A同理可得。
代码如下
//前缀和
#include iostream
#include cstdiousing namespace std;typedef long long LL;
const int N 1e510;
int A[N], B[N], C[N];
int cnta[N], cntc[N], sa[N], sc[N];int main() {int n;scanf(%d, n);//获取数i在A中有cntc[i]个并对cnt求前缀和safor(int i 1; i n; i) {scanf(%d, A[i]);cnta[A[i]];}sa[0] cnta[0];for(int i 1; i N; i) sa[i] sa[i-1]cnta[i];//B只读取即可for(int i 1; i n; i) scanf(%d, B[i]), B[i];//获取数i在C中有cntc[i]个并对cnt求前缀和scfor(int i 1; i n; i) {scanf(%d, C[i]);cntc[C[i]];}sc[0] cntc[0];for(int i 1; i N; i) sc[i] sc[i-1]cntc[i]; //遍历B求解LL ans 0;for(int i 1; i n; i) {int b B[i];ans (LL)sa[b-1] * (sc[N-1] - sc[b]);}coutansendl;return 0;
}
感谢您的观看。
