第三周第一篇

本周学习了DFS枚举函数算法和快速幂算法以及动态规划的kadane算法第一题选数有N个整数x1,x2,x3,x4xn,以及一个整数K(kn),从n个整数中任选k个整数相加计算出和为素数共有多少种。解题要素1素数的判定2DFS枚举。#includebits/stdc.h using namepace std; int n,k; int x[25]; int ans0; booi sushu(int x){ if(x2) return false; for(int i2;i*ix;i){ if(x%i0) return false;} return true;} void DFS(int flag,int num,int sum){ if(num0){ ans: return;} if(n-flag1num) return ; for(int iflag;in;i){ DFS(i!,num-1,sumx[i]);} return ;} int main({ cinnk; for(int i1;in;i){ cinx[i]; } DFS(1,k,0); coutansendl; return 0;}首先本题用到了两个函数1一个是素数的判定有素数的定义可知一个大于1的自然数如果除以1和它本身以外没有其它正因数这个数就叫做素数。由此写出素数的判定函数如果是素数返回true否则返回false2DFS函数这个函数我还不是特别明白B站上讲的也没太明白我决定先背下来然后请教一下别人把素数判定的函数调用到DFS函数中判断和是否为素数。回到主函数将题目中所给的数据输入后调用DFS函数求出ans的值。第二题快速幂算法求a^b mod p;首先尝试暴力算法不可行会超出限制。long long ans1; for(long long i1;ib;i){ ans*a;} ans%c;优化#includestdio.h int main(){ long long a,b,p,a1,b1; scanf(%lld%lld%lld,a,b,p); a1a;b1b; long long s1; while(b0){ if(b%21){ s(s*a)%p; a(a*a)%p; bb/2;} else{ a(a*a)%p; bb/2;} printf(%lld^%lld mod %lld%lld,a1,b1,p,s); return 0;}本题核心规则是二进制处理通过将指数按二进制拆分把大幂次运算转化为多次平方和乘法减少计算次数。1初始化结果S1;2,循环处理指数当b是奇数将结果s乘以当前底数a,再模数p取模3底数平方取模将底数a进行平方运算后对模数p取模更新底数。本步表示用于生成快速幂所需的平方项同时防止数值溢出4指数折半将指数b除以2缩小指数规模。第三题最大段子和给出一个长度为n的序列a,选出其中连续且非空的一段使得这段的和最大#includebits/stdc.h using namespace std: int main(){ int n,i,a[n]; cinn; for(i0;in-1;i){ cina[i]; } int dangqian_suma[0]; int max_suma[0]; for(i1;in-1;i){ dangqian_summax(a[i],dangqian_suma[i]); max_summax(max_sum,dangqian_sum);} coutmax_sumendl; return 0;}本题主要在于公式当前最大值maxa[i],a[i]当前最大值全局最大值max(全局最大值当前最大值输出全局最大值即可。