黄冈网站推广优化找哪家,休闲会所网站建设,wordpress 搬家 sae,网站开发学些什么文章目录 一.快速幂二.倍增三.构造 一.快速幂
快速幂算法是一种高效计算幂ab的方法#xff0c;特别是当b非常大时。它基于幂运算的性质#xff0c;将幂运算分解成一系列的平方操作#xff0c;以此减少乘法的次数。算法的核心在于将指数b表示为二进制形式#xff0c;并利用… 文章目录 一.快速幂二.倍增三.构造 一.快速幂
快速幂算法是一种高效计算幂ab的方法特别是当b非常大时。它基于幂运算的性质将幂运算分解成一系列的平方操作以此减少乘法的次数。算法的核心在于将指数b表示为二进制形式并利用二进制位来决定何时将当前的底数的幂乘入结果中。
普通的快速幂算法
#include iostream
#include algorithm
using namespace std;
long long fastPower(long long base, long long power) {long long result 1;while (power 0) {if (power % 2 1) {result * base;}base * base;power / 2;}return result;
}
int main() {long long base, power;cin base power;cout fastPower(base, power);
}为了适用于大数运算提高效率引入了位运算和模运算 位运算比乘除法和模运算更快。 模运算在每次乘法后进行避免了大整数的处理和溢出的问题。
#include iostream
#include algorithm
using namespace std;
#define mod 998244353 //固定数
long long fastPower(long long base, long long power) {long long result 1;while (power 0) {if (power1) { //power % 2 1result * base% mod;}base * base% mod;power 1;//右移一位相当于÷2即power / 2;}return result;
}
int main() {long long base, power;cin base power;cout fastPower(base, power);
}[例] 快速幂 评测系统
#include iostream
#include algorithm
using namespace std;
long long fastPower(long long base, long long power, long long k) {long long result 1;while (power 0) {if (power 1) {result result * base % k;}base base * base % k;power 1;}return result;
}
int main() {long long b, p, k;cin b p k;long long s fastPower(b, p, k);cout s;
}二.倍增
倍增算法是一种用于解决各种问题的通用技术例如在计算斐波那契数列、找到图中节点的祖先或者处理区间查询问题如最小值或最大值时。其基本思想是通过重复倍增一个数或者序列的长度从而以对数时间解决问题。例如在求解LCA最近公共祖先问题时倍增算法可以在预处理阶段通过倍增跳跃来快速移动到任意节点的不同层级的祖先节点。
[例1] 最近公共祖先LCA查询 评测系统
分析 1预处理 ①使用DFS从根节点开始变量计算每个结点的所有祖先 ②使用数组parent[node][i]存储结点node的第2i个祖先parent[node][0]就是结点node的父节点parent[node][1]就是node的第2个祖先 ③递推式parent[node][i]parent[parent[node][i-1]][i-1] //两个i-1就是i 2查询 为了找到两个结点u和v的最低公共祖先若u的深度≥v我们将u的深度提升至与v相同若提升后的u与v是同一结点则该结点就是他们的最低公共祖先否则同时提升二者的深度直到他们有相同的第2i个祖先为止
例如查找第1248个祖先1248二进制表示为10011100000 即1248210272625 即从node向上跳210步再跳27再跳26再跳25 即任意一个数都可以通过向上跳2i来表示
#include iostream
#include algorithm
#include vector
using namespace std;
const int MAXN 1e5 5;//节点数量的上限
const int MAXLOG 20;//最大深度,2^201e5
vectorint tree[MAXN];//tree[i]存储了所有直接连接到节点i的子节点的列表即树的邻接表表示
int parent[MAXN][MAXLOG];
int depth[MAXN];//每个节点在树中的深度
void dfs(int node, int prev) { //遍历树并填充 parent 和 depth 数组for (int i 1; i MAXLOG; i) {parent[node][i] parent[parent[node][i - 1]][i - 1];}for (int child : tree[node]) { //递归处理子节点if (child ! prev) {depth[child] depth[node] 1;parent[child][0] node;dfs(child, node);}}
}
int lca(int u, int v) {if (depth[u] depth[v]) swap(u, v);//确保u更深for (int i MAXLOG - 1; i 0; i--) { //向上提升uif (depth[u] - (1 i) depth[v]) { //1i相当于2的i次幂u parent[u][i];}}if (u v)return u;for (int i MAXLOG - 1; i 0; i--) {if (parent[u][i] ! parent[v][i]) {u parent[u][i];v parent[v][i];}}return parent[u][0];
}
int main() {int N;cin N;for (int i 1; i N; i) {int u, v;cin u v;tree[u].push_back(v);tree[v].push_back(u);}dfs(1, -1);int Q;cin Q;while (Q--) {int a, b;cin a b;cout lca(a, b) endl;}return 0;
}[例2] 如今仍是遥远的理想之城1 对于小数据
#include iostream
#include algorithm
using namespace std;
const int N 2e5 5;
int main() {int n, k;cin n k;long long a[N];for (int i 1; i n; i) {cin a[i];}long long position 1;while(k--) {position a[position];}cout position;
}对于大数据 需要移除重复的循环 例如 第 1 次传送从 1 到 2 第 2 次传送从 2 到 3 第 3 次传送从 3 到 4 第 4 次传送从 4 到 2 在第 4 次传送时我们回到了传送阵 2这里形成了一个循环2 - 3 - 4 - 2,这个循环会一直重复,循环长度为3 可以看出当k足够大时,若pre1说明一定没有节点能跳转到当前结点。若pre2当k足够大时一定有能跳转过来的也就一定能出现循环
#include iostream
#include algorithm
using namespace std;
const int N 2e5 5;
int main() {long long n, k;cin n k;long long a[N], pre[N] { 0 };//pre[position]表示访问到position时总的传送次数【这里必须初始化为0】for (int i 1; i n; i) {cin a[i];}long long position 1;long long num 1;//num表示总传送次数while (k--) {position a[position];if (pre[position])k k % (num - pre[position]);//num-1-pre[position]表示这个循环的长度pre[position] num;}cout position;
}注局部变量不会自动初始化为零全局变量会初始化为0。在main函数内long long a[N], pre[N]时必须初始化为0或者直接在全局定义。
[例3] 数的变换
分析F[i][j]表示A初始为i时经过2j次变换的值其中201次变换表示进行一次变化即输出A/BC212表示两次变换即将A/BC作为新的A放入A/BC中输出结果
例如 A 10, B 2, C 1, D 5 F[i][0]表示Ai时即i/bc的值通过遍历i的所有可能以此作为第0列的值即初始化过程。由于A不断变为A/BC所以A的最大取值为max(1e5,A/BC的大小)max(1e5,2e5)2e5即F的最大行数 以下是第0列的初始化过程
for (int i 0; i 200000; i) { //初始化F[i][0] i / b c;
}然后我们按列更新 更新F[0][1]时表示A0经过212次变换的结果具体的变化过程为A0→A1一次变换→A1两次变换
更新F[3][1]同样 即对第一列所有的更新我们都是把F[i][0]作为新的行找到第0列对应的值即一次变换
for (int i 0; i 200000; i) {F[i][1] F[F[i][0]],0];
}更新F[18][2]时从A18起经过了4次变换得到了3 显然我们从F[18][2]的左侧F[18][1]6开始进行两次变换标号3和4更快得到了答案 更显然的A6进行两次变化可以直接从表格中的F[6][1]得到注意1是21 我们据此更新第二列以当前行前一列的值6作为行直接找到该行6这一行前一列第1列的值3即为结果
for (int i 0; i 200000; i) {F[i][2] F[F[i][1]],1];
}对于第j列的更新按照同样的逻辑我们有
for (int i 0; i 200000; i) {F[i][j] F[F[i][j-1]],j-1];
}再遍历所有的j我们有
for (int j 1; j 30; j) {for (int i 0; i 200000; i) {F[i][j] F[F[i][j - 1]][j - 1];}
}j表示进行2j次变换2301e9maxQ查询次数的最大值
以上过程是倍增的重要思想
当A3时1左移3位就是1000视为二进制对应的十进制是8即23可视为F[i][j]的j3 当A8时1左移8位就是100000000视为二进制对应的十进制是256即28可视为F[i][j]的j8 可以看出A的值1左移位数j的值 而j的范围很小是从0到30我们遍历j就相当于遍历了A 1左移j位得到的这个二进制数中只会有一个1我们将查询次数Q也写为二进制二者相与若结果为1说明两个二进制数一定完全相同即此时Q的二进制中也只有一个1而这个1所在的位置可以通过1j表示 因此通过遍历j当相与为1时我们可以直接在F数组中找到F[A][j]
for (int j 0; j 30; j) {if ((1 j) q) {answer F[A][j];break;}
}因此本题的求解代码为
#include iostream
#include algorithm
using namespace std;
const int N 2e5 5, M 30 5;
int main() {long long a, b, c, q;long long F[N][M];cin a b c q;if (b 1) { //特殊情况cout a q * c;return 0;}for (int i 0; i 200000; i) {F[i][0] i / b c;}for (int j 1; j 30; j) {for (int i 0; i 200000; i) {F[i][j] F[F[i][j - 1]][j - 1];}}for (int j 0; j 30; j) {if ((1 j) q) {a F[a][j];break;}}cout a;
}三.构造
通过观察问题的结构和规律找到一种通用的方法或模式使得在问题规模增大时依然能够高效地得到答案。
1.小浩的ABC 评测系统
分析 A*BC2若X2无解 若X1061则BC1,AX-1。此时字典序一定是最小的 若X1061为了让B更小应该A尽可能大即A106 若A、C都是106那么X一定是106的整数倍即有X%1060 若X不是106的整数倍说明C一定不是106设X1e72 A1e6B9C1e6不满足 A1e6B10C2满足显然BX/ACX%A
#include iostream
#include algorithm
using namespace std;
int main() {long long T, A, B, C;cin T;while (T--) {long long X;cin X;if (X 2) {cout -1 endl;}else {if (X 1e6 1) {B 1, C 1, A X - 1;}else {A 1e6;if (X % 1000000 0) {C 1e6, B (X - C) / A;}else {B X / 1000000;C X % 1000000;}}cout A B C endl;}}
}2.小新的质数序列挑战 评测系统
分析质数2、3、5、7、11 A和B任一个小于2都失败 每一个偶数都能由多个2组成每一个奇数都能由1个3和多个2组成 因此输出只能为0或1 若AB都是偶数输出一定为0 若AB相等输出一定为0 其他情况需要具体分析 如一奇一偶 27和24由9个3和8个3组成输出为0 3和5由3和2 3组成输出为1 所以可以查看AB大于1的公因数若有则输出为0否则为1 此方法也涵盖了都是偶数和两数相等的情况
#include iostream
#include algorithm
using namespace std;
long long f(long long a, long long b) { //求最大公因数while (b) {long long temp b;b a % b;a temp;}return a;
}
int main() {int T;cin T;long long A, B;while (T--) {cin A B;if (A 2 || B 2) {cout -1 endl;}else {if (f(A, B) 1) {cout 0 endl;}elsecout 1 endl;}}
}3.小蓝找答案 评测系统
【本题分析与注释仅供参考】
分析 ①假设3个字符串的长度分别为123 s1:a s2长度为2aa满足 s3长度为3aaa满足 因此长度|si|长度|si1|显然没有产生进位那么si就是si1的前缀。所以si1是由si向后补字符集中最小的字母直到长度等于si1
②假设3个字符串的长度分别为321 s1:aaa s2长度为2将s1的长度变为2即截尾得到aa显然不满足最后一位1得到ab满足 s3长度为1将s2的长度变为1截尾得到a显然不满足最后一位1得到b满足 因此长度|si|≥长度|si1|一定产生了进位具体来说是si截尾后的最后一位加1得到的。
③假设3个字符串的长度分别为322这里k2 s1:aaa s2长度为2将s1的长度变为2即截尾得到aa显然不满足最后一位1得到ab满足 s3长度为2将s2的长度变为2不变得到ab显然不满足最后一位1得到了ac这时c字符集中最小的字母1需要再次进位即进位到前一位ac变为ba
④假设s2为abc这里k3 s3长度为3将s2的长度变为3不变得到abc显然不满足最后一位1得到abd此时d字符集中最小的字母2需要再次进位即进位到前一位abd变为aca 因此当某一位字符集中最小的字母k-1时就产生了进位 或者更通用的当某一位1后字符集中最小的字母k时就产生了进位
⑤假设4个字符串的长度分别为3122 s1:aaa s2长度为1将s1的长度变为1截尾得到a显然不满足最后一位1得到b满足 s3长度为2将s2作为前缀后面补字符集中最小的字母至与s3等长得到bb满足 s4长度为2将s2的长度变为2不变得到bb显然不满足最后一位1得到了bc这时c字符集中最小的字母1需要再次进位即进位到前一位bc变为ca这时c字符集中最小的字母1需要再次进位即进位到前一位ca变为aaa超出长度。即第一位产生进位就是不合法。
我们假设字符集的大小为k使用二分去找最小的合法字符集的大小并验证二分出来的k是否合法
最终代码
#include iostream
#include algorithm
using namespace std;
const int N 2e5 5;
int s[N];
int n;
struct node {int pos;//字符串长度int num;//长度为pos的字符串产生的进位次数
}stk[N];//栈
int top;//栈顶指针
void insert(int v, int mid) {//处理进位while (top 1 stk[top].pos v)//截尾。或者说当前长度的进位信息我们当前不需要考虑,可以移除top--;if (stk[top].pos v)//如果二者长度相等stk[top].num;//直接复制过来,最后一位1。即产生进位次数1else//如果长度不相等,新信息压入栈stk[top] { v,1 };//进位次数初始化为1if (top 1 stk[top].num mid)//若某个长度的字符串的进位次数≥mid,需要向前进位。如aa/ab两次进位mid2,此时需要向前进位变成bainsert(v - 1, mid);
}
int check(int mid) {//验证给定的字符集大小mid是否足够用来构造出满足条件的字符串序列top 1;stk[top] { 0,0 };for (int i 1; i n; i) {if (s[i 1] s[i]) //一定有进位insert(s[i 1], mid);}return stk[1].num;//返回第一个位置上的进位,为0表示没有进位,即合法
}
int main() {cin n;for (int i 1; i n; i) {cin s[i];}int num 0;for (int i 1; i n; i) {if (s[i 1] s[i])num;}if (num n - 1) { //如果从第二个起每一个都能通过补齐实现则字符集中只有acout 1;return 0;}//补不了,使用二分找kint left 2, right 2e5 5;int ans 0;while (left 1 ! right) {int mid (left right) / 2;if (check(mid) 0)right mid;elseleft mid;}if (check(left) 0)cout left;elsecout right;
}一些具体的分析 ①假设我们有一个字符串长度序列 [4, 3, 2, 1]并且我们正在按序处理这些字符串的长度。我们将关注栈中的变化特别是在 top-- 过程中栈的状态。
while (top 1 stk[top].pos v)//当前长度更小top--;处理长度4: 假设栈初始为 [{0, 0}]。 长度4是序列中的第一个元素因此不需要进位操作。栈状态不变。
处理长度3: 当我们开始处理长度3的字符串时由于它小于4我们需要在长度3上进行一次进位操作。 栈变为 [{0, 0}, {3, 1}]。
处理长度2: 现在我们处理长度2的字符串。在这里长度为3的进位记录即 {3, 1}不再相关因为我们现在关注的是长度2。 执行 top–栈中长度为3的记录被移除栈变回 [{0, 0}]。 然后我们在长度2上进行进位操作栈变为 [{0, 0}, {2, 1}]。
处理长度1: 接下来是长度1的字符串。同样长度为2的记录即 {2, 1}现在不再相关。 执行 top–移除长度为2的记录栈变回 [{0, 0}]。 在长度1上进行 进位操作栈变为 [{0, 0}, {1, 1}]。
在 top-- 的过程中栈中存储的是之前处理的不同长度字符串的进位记录。每当我们转向处理一个更短的字符串时所有比这个新长度长的字符串的进位记录都变得不再相关因此需要被移除。这些进位记录反映了在之前长度上的字符集使用情况和进位情况。
②假设有一个字符串长度序列 [3, 2, 2, 1]我们考虑如何处理这些长度并记录进位信息
if (stk[top].pos v)//如果二者长度相等stk[top].num;处理长度3: 不需要进位假设栈状态是 [{0, 0}]。 处理长度2: 第一次出现长度2进行一次进位操作。栈状态变为 [{0, 0}, {2, 1}]。 再次处理长度2: 当再次遇到长度2时栈顶元素已经是 {2, 1}。这时这行代码 stk[top].num 会执行表示在长度2上又发生了一次进位。栈状态更新为[{0, 0}, {2, 2}]意味着在长度为2的字符串上发生了两次进位操作。
③当字符串长度再次变为之前处理过的长度时确保 num 是累加的 示例分析 考虑序列 [3, 2, 2, 1, 2, 2] 处理长度 3不涉及进位操作。 处理第一个长度 2进行一次进位操作栈变为 [{2, 1}]。 处理第二个长度 2再次进位栈更新为 [{2, 2}]。 处理长度 1由于这比 2 小栈清除长度 2 的记录变回 [{0, 0}]然后为 1 添加进位记录变为 [{1, 1}]。 再次处理长度 2由于栈中没有长度 2 的记录会添加一个新的进位记录栈变为 [{1, 1}, {2, 1}]。 处理另一个长度 2找到栈中的 {2, 1}记录然后将其num增加栈更新为[{1, 1}, {2, 2}]。 虽然top–的过程删除了部分数据但num的更新过程是基于当前字符串长度更新的也能实现累加的效果。
4.小蓝的无限集
分析 若第一次计算1*a得到的通式为naxby 其中xy为任意满足要求的整数 若第一次计算xb得到的通式为n(1b)* axbyb*(axy)ax 我们可以令x0若b%(n-1)0则n一定在无限集中 上述条件不满足且a1则n一定不在无限集中 此外根据通式有 n-axby n-axb*(axy) 我们可以遍历x计算n-ax若b能够将其整除则n一定在无限集中
#include iostream
#include algorithm
using namespace std;
int main() {int t;cin t;int a, b, n;while (t--) {cin a b n;if ((n - 1) % b 0) {cout Yes endl;continue;}else if (a 1) {cout No endl;continue;}long long res 1;bool flag 0;while (res n) {res * a;if (res n)break;else if (res n) {cout Yes endl;flag 1;break;}else if ((n - res) % b 0) {cout Yes endl;flag 1;break;}}if (flag 1)continue;cout No endl;}
}
文章转载自： http://www.morning.dybth.cn.gov.cn.dybth.cn http://www.morning.gstmn.cn.gov.cn.gstmn.cn http://www.morning.drqrl.cn.gov.cn.drqrl.cn http://www.morning.pqqhl.cn.gov.cn.pqqhl.cn http://www.morning.fphbz.cn.gov.cn.fphbz.cn http://www.morning.yubkwd.cn.gov.cn.yubkwd.cn http://www.morning.qgghj.cn.gov.cn.qgghj.cn http://www.morning.xfmwk.cn.gov.cn.xfmwk.cn http://www.morning.lmjtp.cn.gov.cn.lmjtp.cn http://www.morning.tbzcl.cn.gov.cn.tbzcl.cn http://www.morning.bgygx.cn.gov.cn.bgygx.cn http://www.morning.rnnts.cn.gov.cn.rnnts.cn http://www.morning.jjrsk.cn.gov.cn.jjrsk.cn http://www.morning.jtmql.cn.gov.cn.jtmql.cn http://www.morning.xfhms.cn.gov.cn.xfhms.cn http://www.morning.nkhdt.cn.gov.cn.nkhdt.cn http://www.morning.dnbkz.cn.gov.cn.dnbkz.cn http://www.morning.zbkdm.cn.gov.cn.zbkdm.cn http://www.morning.enjoinfo.cn.gov.cn.enjoinfo.cn http://www.morning.ljyqn.cn.gov.cn.ljyqn.cn http://www.morning.gfznl.cn.gov.cn.gfznl.cn http://www.morning.nkpml.cn.gov.cn.nkpml.cn http://www.morning.dqzcf.cn.gov.cn.dqzcf.cn http://www.morning.frqtc.cn.gov.cn.frqtc.cn http://www.morning.tbstj.cn.gov.cn.tbstj.cn http://www.morning.bfjtp.cn.gov.cn.bfjtp.cn http://www.morning.rdpps.cn.gov.cn.rdpps.cn http://www.morning.pgkpt.cn.gov.cn.pgkpt.cn http://www.morning.rdtp.cn.gov.cn.rdtp.cn http://www.morning.skscy.cn.gov.cn.skscy.cn http://www.morning.dwxqf.cn.gov.cn.dwxqf.cn http://www.morning.cpfbg.cn.gov.cn.cpfbg.cn http://www.morning.lwgrf.cn.gov.cn.lwgrf.cn http://www.morning.yrdt.cn.gov.cn.yrdt.cn http://www.morning.qljxm.cn.gov.cn.qljxm.cn http://www.morning.nbqwr.cn.gov.cn.nbqwr.cn http://www.morning.rqfkh.cn.gov.cn.rqfkh.cn http://www.morning.mytmx.cn.gov.cn.mytmx.cn http://www.morning.ydryk.cn.gov.cn.ydryk.cn http://www.morning.wgtnz.cn.gov.cn.wgtnz.cn http://www.morning.zlxrg.cn.gov.cn.zlxrg.cn http://www.morning.yktwr.cn.gov.cn.yktwr.cn http://www.morning.jfcbs.cn.gov.cn.jfcbs.cn http://www.morning.lfcfn.cn.gov.cn.lfcfn.cn http://www.morning.lkrmp.cn.gov.cn.lkrmp.cn http://www.morning.fpqsd.cn.gov.cn.fpqsd.cn http://www.morning.kzcfr.cn.gov.cn.kzcfr.cn http://www.morning.gsksm.cn.gov.cn.gsksm.cn http://www.morning.rqqmd.cn.gov.cn.rqqmd.cn http://www.morning.nafdmx.cn.gov.cn.nafdmx.cn http://www.morning.mmhyx.cn.gov.cn.mmhyx.cn http://www.morning.dphmj.cn.gov.cn.dphmj.cn http://www.morning.lktjj.cn.gov.cn.lktjj.cn http://www.morning.hkshy.cn.gov.cn.hkshy.cn http://www.morning.rhfh.cn.gov.cn.rhfh.cn http://www.morning.frcxx.cn.gov.cn.frcxx.cn http://www.morning.xcjwm.cn.gov.cn.xcjwm.cn http://www.morning.pdtjj.cn.gov.cn.pdtjj.cn http://www.morning.qnklx.cn.gov.cn.qnklx.cn http://www.morning.kjksn.cn.gov.cn.kjksn.cn http://www.morning.kqxwm.cn.gov.cn.kqxwm.cn http://www.morning.qglqb.cn.gov.cn.qglqb.cn http://www.morning.fnhxp.cn.gov.cn.fnhxp.cn http://www.morning.pxwjp.cn.gov.cn.pxwjp.cn http://www.morning.jyzqn.cn.gov.cn.jyzqn.cn http://www.morning.zyrp.cn.gov.cn.zyrp.cn http://www.morning.pybqq.cn.gov.cn.pybqq.cn http://www.morning.fkgct.cn.gov.cn.fkgct.cn http://www.morning.ydzly.cn.gov.cn.ydzly.cn http://www.morning.yrdt.cn.gov.cn.yrdt.cn http://www.morning.jfsbs.cn.gov.cn.jfsbs.cn http://www.morning.tnjz.cn.gov.cn.tnjz.cn http://www.morning.mwmxs.cn.gov.cn.mwmxs.cn http://www.morning.qtrlh.cn.gov.cn.qtrlh.cn http://www.morning.bxdlrcz.cn.gov.cn.bxdlrcz.cn http://www.morning.fylsz.cn.gov.cn.fylsz.cn http://www.morning.dpbdq.cn.gov.cn.dpbdq.cn http://www.morning.rrxmm.cn.gov.cn.rrxmm.cn http://www.morning.iuibhkd.cn.gov.cn.iuibhkd.cn http://www.morning.gkpgj.cn.gov.cn.gkpgj.cn
