工商局网站清算组备案怎么做,加强门户网站建设的方案,宁波建网站选哪家好一点,通辽网站开发0475seo别忘了请点个赞收藏关注支持一下博主喵#xff01;#xff01;#xff01;
关注博主#xff0c;更多蓝桥杯nice题目静待更新:)
思维与贪心
一、重复字符串
【问题描述】 如果一个字符串S恰好可以由某个字符串重复K次得到#xff0c;我们就称S是K次重复字 符串…
别忘了请点个赞收藏关注支持一下博主喵
关注博主更多蓝桥杯nice题目静待更新:)
思维与贪心
一、重复字符串
【问题描述】
· 如果一个字符串S恰好可以由某个字符串重复K次得到我们就称S是K次重复字 符串。例如abcabcabc可以看作是abc重复3次得到所以abcabcabc是3次重复字符串。 同理aaaaaa既是2次重复字符串又是3次重复字符串和6次重复字符串。 现在给定一个字符串S请你计算最少要修改其中几个字符可以使S变为一个K 次重复字符串?
【输入格式】 第一行包含一个整数K。 第二行包含一个只含小写字母的字符串S。 其中1⩽K⩽105,1⩽|S|⩽105。其中|S|表示S的长度。
【输出格式】 输出一个整数代表答案。如果S无法修改成K次重复字符串输出−1。
【样例输入】 【样例输出】 2
解析 先来分析什么情况下S无法修改成K次重复字符串? 1S 的长度小于K。K 次重复字符串的长度至少为K。因为我们只能修改字符串无 法添加字符串所以当S的长度小于K时S一定无法修改成K次重复字符串。 2S 的长度不是K 的倍数。若S 是K 次重复字符串则S是由某个字符串重复K 次构成所以S的长度一定是K的倍数。同样因为无法添加字符串所以当S的长度不为 K 的倍数时S一定无法修改成K次重复字符串。 第2种情况实际上是包含了第1种情况的。因此判断S能否修改为K次重复字符串只要 判断S的长度是否是K的倍数即可。 3对于其他情况S 一定可以修改为K 次重复字符串。 那么要如何修改才能保证修改的次数最少呢? 我们来分析一下。 假设我们以最少的修改次数将字符串S 修改成了K 次重复字符串记为S′。根据定 义S′ 可由某个字符串重复K 次得到。 由于K是已知的所以只要我们能求出某个字符串就可将S′还原。还原了S′后就可 以将其和S一一比对以求出需要修改的次数。于是问题就可以转换成如何求出某个字符串。 我们设某个字符串为TS′ 可由T 重复K 次得到|T| |S| 们设|T| 的值为n如下图所示。 根据K次重复字符串的性质如果我们将字符串T 展开为T1,T2,...,TnT1 表示T 的 第1个字符T2 表示T 的第2个字符...Tn 表示T 的第n个字符则满足以下条件。 例如S 的长度为6|S|6、K 3则n 2S′ 可由3个T 重复得到如下图所示。 观察上图可以发现如果将S′中与T1相同的部分组合在一起、与T2相同的部分组合在一 起······ 与Tn 相同的部分组合在一起就会得到一个n×K的矩阵n×K × K |S|如下表所示。 该矩阵为字符串S′ 对应的矩阵它满足每一行所有的元素值都相同。 S′ 是我们对S 进行了最少次数的修改后得到的K 次重复字符串。从已知条件推断它与S唯一的区别就在于它对应矩阵的每一行的所有元素值都相同。所以只要用最少的修改 次数将S对应矩阵的每一行元素都修改为相同的元素得到的就是S′而这最少的修改次数 就是我们想要的答案。 由于矩阵的行与行之间是互不关联的因此最少的修改次数就等价于每行的最少修改次数之和。那么针对矩阵的某一行如果我们要让所有元素的值都为x则需要修改的次数就 为矩阵的列数−该行中值为x的元素个数即为K−x出现的次数。 显然要使修改的次数最少就要将该行的所有元素都修改为出现次数最多的元素。于是我们可以得出贪心策略即将每一行的所有元素都修改为出现次数最多的元素。 由于修改某一行对其他行不会造成任何影响且每一行的修改次数都是最少的所以可 以保证使用该策略得到的修改次数一定最少而这最少的修改次数就是我们所要的答案。 总结我们在刚开始思考的时候将问题转换为了如何求解某个字符串T但最后并没 有实际地解决这个问题而是通过这个问题进一步去分析以得到最终的答案。其实很多时候 我们在面对一个问题时都不能很快有一条清晰的解题思路。这时与其马马虎虎猜结论、猜 做法不如脚踏实地一步步深入思考发掘解题的核心。
参考代码如下【时间复杂度为O(n×K)O |S| K×K O(|S|)】
#include bits/stdc.h
using namespace std;const int N 1e5 10;
int n, k, ma[N], cnt[30];
char s[N];signed main() {cin k (s 1); // 从s[1]开始存储字符串// 当S不是K的倍数时无论S如何修改也无法成为K次重复字符串if (strlen(s 1) % k) return cout -1 \n, 0;n strlen(s 1) / k;int ans 0;for (int i 1; i n; i) {// cnt[j]记录第i行第j个元素出现的次数。初始化cnt数组所有元素的值为0for (int j 0; j 25; j) cnt[j] 0;int ma 0; // ma统计第i行出现最多的元素for (int j 1; j k; j) {int x s[i (j - 1) * n]; // S对应矩阵的第i行的第j列个元素cnt[x - a]; // 该元素出现的次数1ma max(ma, cnt[x - a]); // 更新出现次数最多的元素}ans k - ma;}cout ans \n;return 0;
}
二、翻硬币
【问题描述】 小明正在玩一个“翻硬币”的游戏。 桌上放着排成一排的若干硬币。我们用∗表示正面用o表示反面是小写字母不是零。 比如可能情形是∗∗oo∗∗∗oooo; 如果同时翻转左边的两个硬币则变为oooo∗∗∗oooo。 现在小明的问题是如果已知了初始状态和要达到的目标状态每次只能同时翻转 相邻的两个硬币那么对特定的局面最少要翻动多少次呢? 我们约定把翻动相邻的两个硬币叫作一步操作。
【输入格式】 两行等长的字符串分别表示初始状态和要达到的目标状态。 每行的长度1000。
【输出格式】 一个整数表示最小操作步数。
【样例输入】 【样例输出】 5
解析 本题没有提到当无法将所有硬币的初始状态转换为目标状态时需要输出什么因此可笃定题目必有解。 依题意每次操作将同时翻转两枚硬币。为了方便表示我们可认为对第i枚硬币的操作会同时翻转第i枚硬币和第i1枚硬币。题目要求的是用最少的操作将硬币的初始状态 转换为目标状态。那么如何求这最少的操作次数呢?我们先从每次操作的意义入手。 已知对某枚硬币操作一次它与它相邻的硬币就会翻转一次。那么如果再对该硬币操作 一次呢?显然这两枚硬币就会回到初始状态相当于没有操作。从这里可以得出对于第i 枚硬币我们只会操作0次或者1次。 再来思考下一枚硬币最终的状态会受什么影响? 以第i枚硬币为例。只有当我们对第i枚硬币或第i−1枚硬币操作之后第i枚硬币的状态才会发生改变。这两种操作对第i枚硬币的影响实际上是相同的都是令其翻转。因此 第i枚硬币的最终状态不会受两种操作的先后顺序影响只会受两种操作的操作次数影响。 推广到所有硬币可得出结论操作的先后顺序对最终结果不会造成影响如下图所示。 通过上文的分析我们得到了以下两条重要的信息。 1对于第i枚硬币我们只会操作0次或者1次。 2操作的先后顺序对最终结果不会造成影响。 有了这两条重要的信息我们便可以开始模拟硬币的翻转。 显然当第i枚硬币的初始状态和目标状态不同时我们就要将其翻转。将其翻转的方 法可能有以下两种。 1对第i枚硬币进行操作。 2对第i−1枚硬币进行操作。 两种方法都能令第 i 枚硬币的状态转换为目标状态但不同的方法对其他硬币的影响可能 是不一样的我们并不好去预估这两种方法对其他硬币带来的影响。因此我们最好从第1枚 硬币开始入手。因为第1枚硬币前并没有其他硬币所以要想改变它的状态只能对其自身进 行操作。 根据信息1可得如果第1枚硬币的初始状态和目标状态相同我们就不进行操作反之 必须进行操作操作次数为1使其状态变为目标状态。 那么在我们处理完第 1 枚硬币状态变为目标状态后还会对第 1 枚硬币进行操 作吗? 答案是不会的。如果还对第1枚硬币进行操作则其状态将变得与目标状态不同状态 不同就又得再对第1枚硬币进行操作使其状态变为目标状态。这样这两次操作的作用就被 互相抵消了如下图所示。所以当第1枚硬币的状态变为目标状态后我们就不会再对第1 枚硬币进行操作了。 因为不会再对第1枚硬币进行操作所以我们就只要将注意力集中在剩余硬币上。 那剩余硬币要怎么处理呢?同样也是从这当中的第1枚硬币入手。 例如有5枚硬币它们的初始状态为∗∗∗∗∗终止状态为o∗o∗∗。如果使用上述方法 则硬币的状态变化将如下图所示。 可以发现我们每次的操作都会满足以下两个特性。 1必要性只有当被操作的硬币状态和目标状态不同时才进行操作。 2独立性不会影响已处理好达到目标状态的硬币。 显然满足了必要性和独立性的操作即最优操作。每次都使用最优操作那么总的操作 次数就会是最少的。
参考代码如下【时间复杂度为 O(n)】
#include bits/stdc.h
using namespace std;signed main() {int cnt 0;string s, t;cin s t; // s表示硬币的初始状态t表示硬币的目标状态for (int i 0; i s.size() - 1; i) {if (s[i] ! t[i]) { // 如果第i枚硬币的初始状态和目标状态不同则对第i枚硬币进行操作// 操作会改变第i枚硬币、第i1枚硬币的状态// 由于操作之后第i枚硬币的状态必然会是目标状态且之后不会再对第i枚硬币进行操作所以可以省去对第i硬币的实际修改if (s[i 1] *) s[i 1] o;else s[i 1] *;cnt;}}cout cnt \n;return 0;
} 本题也可以换一种角度思考。 由于我们已笃定题目一定有解所以根据操作的要求每次翻转两枚硬币可知初始状 态不为目标状态的硬币个数一定为偶数。 当第i枚硬币的初始状态和目标状态不同时就必须对其进行操作使其状态变为目标 状态。由于每次至少要翻转两枚硬币所以对第i枚硬币的操作会影响与它相邻的硬币第 i1枚硬币的状态且影响分以下两种情况。 1第i1枚硬币的初始状态不为目标状态→第i1枚硬币的状态变为目标状态。 2第i1枚硬币的初始状态为目标状态→第i1枚硬币的状态不再为目标状态。 对于第1种情况操作完成后第i枚硬币、第i1枚硬币的状态都达到了目标状态因此我们无法确定下一枚初始状态不为目标状态的硬币的位置就要继续寻找直到找到初始 状态不为目标状态的硬币。 对于第2种情况操作完成后第i枚硬币的状态会达到目标状态但第i1枚硬币的 状态不会所以我们可以确定下一次要对第i1枚硬币进行操作。当然如果对第i1枚硬 币的操作又造成了第2种情况则需要继续对第i2枚硬币进行操作。 显然只有在某次操作出现了第1种情况后连续的操作才会停止如下图所示。 由上可得我们的操作是由硬币的初始状态不为目标状态开始也是由硬币的初始状态 不为目标状态结束操作的次数为硬币编号。因此我们可以成对记录初始状态不为目标状 态的硬币编号而每一对硬币编号的差值的和就是答案。
参考代码如下 【时间复杂度为O(n)】
#include bits/stdc.h
using namespace std;signed main() {int cnt 0;string s, t;cin s t; // S表示硬币的初始状态T表示硬币的目标状态vectorint vec; // vec用来存储初始状态不等于目标状态的硬币的编号for (int i 0; i s.size(); i) {if (s[i] ! t[i]) vec.push_back(i);}for (int i 0; i vec.size() - 1; i 2) { // 成对枚举cnt vec[i 1] - vec[i]; // 操作次数 结束硬币的编号 - 开始硬币的编号}cout cnt \n;return 0;
} 三、乘积最大
【问题描述】 给定N个整数A1,A2,...,AN。 请你从中选出K个数使其乘积最大。 请你求出最大的乘积由于乘积可能超出整型范围你只需输出乘积除以1099的 余数。 注意如果X0我们定义X除以1099的余数是−X除以1099的余数即0−((0−x)%109 9)。
【输入格式】 第一行包含两个整数N,K。 以下N 行每行一个整数Ai。 其中1⩽K⩽N⩽105,−105 ⩽Ai ⩽105。
【输出格式】 输出一个整数表示答案。
【样例输入】 【样例输出】 999100009
解析
方式1满分做法 不妨设序列中有cnt1个非负数、cnt2 个负数cnt1 cnt2 N。 如果cnt1 N那么我们只要把最大的K 个数取出相乘即可几乎没有难度。但如果 cnt1 N题目的难度就提高了我们就需要讨论取负数的情况。 根据“负负得正”的性质为了让乘积的结果最大我们要尽量成对地取负数。 为什么说是尽量呢? 因为负数的个数可能是奇数。如果是奇数的话最终的负数可能只 剩下1个就无法成对地取负数。所以有了负数的情况是较为复杂的但存在一些特殊情况 如下图所示。 1K N。所有数都必须选取。 2cnt2 0。所有数都是非负数那么取K 个最大的数可令结果最大。 3cnt1 0。所有数都是负数那么分以下两种情况。 • 如果K为奇数则乘积必然为负数所以取绝对值最小的K个数可令结果最大。 • 如果K为偶数则乘积必然为正数所以取绝对值最大的K个数可令结果最大。 对于剩余的情况序列中一定会包含负数与非负数且K 一定小于N。 • K N cnt1 cnt2 → K ⩽ cnt1cnt2−1 • cnt1 0,cnt2 0 我们可以按照K,cnt1, cnt2 的奇、偶性将所有情况分解为以下8类。 1K 为奇数cnt1 为奇数cnt2 为奇数。 2K 为奇数cnt1 为奇数cnt2 为偶数。 3K 为奇数cnt1 为偶数cnt2 为奇数。 4K 为奇数cnt1 为偶数cnt2 为偶数。 5K 为偶数cnt1 为奇数cnt2 为奇数。 6K 为偶数cnt1 为奇数cnt2 为偶数。 7K 为偶数cnt1 为偶数cnt2 为奇数。 8K 为偶数cnt1 为偶数cnt2 为偶数。 为了保证结果尽可能大我们要尽量取偶数个负数和若干个非负数。 因为剩余情况满足K⩽cnt1cnt2−1所以无论如何我们都一定可以取偶数个负数、 若干个非负数使得总个数等于K即无论属于以上哪一类都可令乘积的结果大于等于0。
提示如下 可我们要如何取数才能保证结果在非负数的情况下乘积最大呢? 我们可以采用贪心策略即每次选择符号相同、乘积最大的两个数直到取完K 个数 如下图所示。 但这样可能会面临一个问题即当K为奇数时最后只能取一个数。而在此之前所有的 非负数都已经被取完(只剩下负数)我们就只能取负数导致最终的结果变为负数。 按照贪心策略若K5则取数的步骤如下。 如何解决这个问题呢? 方法很简单我们只要保证在取最后一个数的时候至少还剩有 一个非负数可取。 显然当K ⩽cnt1 时就不会产生上面的情况。但是当cnt1 K 时我们至少要取 K−cnt1 个负数。我们可以先成对地选取负数直到K ⩽cnt1后再用上述贪心策略。 假设cnt12, cnt26, K 5 则取数的步骤如下。 参考代码如下 【时间复杂度为 O(nlogn)】
#include bits/stdc.h
#define int long long
using namespace std;const int N 1e5 10, mod 1e9 9;
int n, k, cnt1 0, cnt2 0, res 1, a[N];signed main() {cin n k;for (int i 1; i n; i) {cin a[i];if (a[i] 0) cnt1; // 统计非负数的个数else cnt2; // 统计负数的个数}sort(a 1, a 1 n); // 排序// 对特殊情况进行处理if (n k) {for (int i 1; i n; i) {res * a[i];res % mod;}cout res \n;}// 对特殊情况进行处理else if (!cnt2) {for (int i n; i n - k 1; i--) {res * a[i];res % mod;}cout res \n;}// 对特殊情况进行处理else if (!cnt1) {if (k 1) {for (int i n; i n - k 1; i--) {res res * a[i] % mod;}} else {for (int i 1; i k; i) {res res * a[i] % mod;}}cout res \n;}else {// 当 cnt1 k 时成对取负数直到 k cnt1int p 1;while (k cnt1) {res * (a[p] * a[p 1]) % mod;res % mod;p 2;k - 2;}// 每次可以选择符号相同、乘积最大的两个数直到取完 K 个数int p1 p, p2 n;while (k 1) {if (a[p1] * a[p1 1] a[p2] * a[p2 - 1]) {res * (a[p1] * a[p1 1]) % mod;res % mod;p1 2;} else {res * (a[p2] * a[p2 - 1]) % mod;res % mod;p2 - 2;}k - 2;}// 如果 K 为奇数即最后只能取一个数那么要选择非负数才能保证乘积最大if (k) {res res * a[p2] % mod;}cout res \n;}return 0;
}
方式2能拿40%分数的做法 考虑动态规划。 题目让我们从N个数中选择K个使得乘积最大。 我们可以根据题目的要求定义dp[i][j] 其含义为从前i个数中选择j个的最大乘积。这样答案可以用dp[N][K]表示。 接着来推导dp[i][j]的转移方程。 我们从第i个数入手。第i个数有两种状态选和不选。如果选了则dp[i][j]的值等价 于从前i−1个数选j−1个数求最大乘积再乘以第i个数如果不选则dp[i][j]的含义等价于前i−1个数选了j个数求最大乘积。 由此便可得出dp[i][j]的转移方程。 不过这个转移方程并不包含所有可能。我们知道一个最大的乘积可能是由两个正数相乘 得到也可能是由两个负数相乘得到。因此我们还需要维护一个f[i][j]其含义为从前i个 数中选择j个数求最小乘积。 dp[i][j]也可能是由前i−1个数选择了j−1个数求最小乘积再乘以第i个数得到。所 以dp[i][j]的完整转移方程应为 f[i][j]的转移方程与dp[i][j]的类似就不赘述。 转移的时间复杂度为O(N2)。
提示如下代码就自己写吧qwq 方式3能拿60%分数的做法 在40% 分数的做法中我们同时维护了从前i个数中选j 个数的最大乘积、最小乘积 (dp[i][j]、f[i][j])还用上了字符串代替整型来模拟计算过程这是相当麻烦的。那么如何优化这些烦琐的步骤呢? 1优化既要记录最大乘积又要记录最小乘积。 回想一下我们为什么要记录最小乘积呢? 根据负负得正的性质最大乘积可能由若干个非负数以及偶数个负数相乘得到由若干个非负数以及奇数个负数构成的最小乘积再乘上一个负数得到。 那如果只乘上奇数个负数呢? 根据满分做法中的讨论只有当序列中不存在非负数时才有可能乘上奇数个负数。对于这种情况可以特别处理。但对于剩余的情况最大乘积不会包含奇数个负数。 既然如此为什么不将负数两两打包在一起视为一个整体呢?这样就能保证每次的乘 积结果都是非负数就不需要记录最小乘积如下图所示。 可是将两个数打包在一起后要怎么取数呢? 我们换个角度来思考。假设有一个容量为K的背包以及若干个物品。每个物品都有自 己的体积和价值其中一些物品的大小为2打包在一起的两个负数一些物品的大小为1 非负数那么如何选择物品可以使得背包能够恰好被装满且所装物品的总价值最大 这样题目就被转换为经典的01背包问题。于是dp[i][j]的定义就为装入前i个物品且 背包的物品体积总和为j可以使价值最大即乘积最大。其转移式为dp[i][j]max(dp[i− 1][j], dp[i − 1][j − w] × v)w, v 分别表示物品的体积和价值。 最后的答案为dp[n][k]。 2优化使用字符串来代替整型。 回想一下我们为什么要使用字符串来代替整型进行计算呢? 因为乘积可能超出整型范围从而导致我们无法进行大小的比较。 但是题目中是让我们通过取模来避免超出整型范围那为什么不按照题目的提示来呢? 因为题目只要求对最后的乘积结果取模。如果在求解过程中取模就可能导致大小关系 出现变化如下页图所示。 那有没有什么办法既能使大小关系不出现变化又能保证乘积结果不超过整型范围呢? 有的。这里介绍一个小技巧——用对数如log2表示正数的大小关系。 •如果XY则log2Xlog2Y。 •如果a×bc×d则log2(a×b)log2alog2blog2(c×d)log2clog2d。 将乘法替换为对数的加法可以保证数值不超过整型。 dp[i][j]max(dp[i−1][j],dp[i−1][j−w]log2v)w,v分别表示物品的体积和价值。 不过这样记录的结果是对数值并不能作为实际的答案。所以我们还得再定义一个 ans[i][j]其含义为装入前i个物品且物品的体积总和为j所能获得的最大价值即最大乘 积。当dp[i][j]被更新时同步更新ans[i][j]即可参考代码如下。
if (dp[i - 1][j] dp[i][j]) {dp[i][j] dp[i - 1][j];ans[i][j] ans[i - 1][j];
}// ...if (dp[i - 1][j - w] log2(v) dp[i][j]) {dp[i][j] dp[i - 1][j - w] log2(v);ans[i][j] ans[i - 1][j - w] * v % mod;
} 能拿60%分数的做法对应的完整代码如下。
#include bits/stdc.h
using namespace std;
#define int long long
const int N 1e3 10, mod 1e9 9;
int a[N], ans[N][N];
double dp[N][N];signed main() {int n, k, cnt1 0, cnt2 0, res 1;cin n k;for (int i 1; i n; i) cin a[i];sort(a 1, a 1 n); // 将数组排序for (int i 1; i n; i) {if (a[i] 0) cnt2;else cnt1;}// 对特殊情况进行处理if (k n) {for (int i 1; i n; i) res res * a[i] % mod;return cout res \n, 0;}// 对特殊情况进行处理if (cnt2 n) {if (k 1) {for (int i n; i n - k 1; i--) res res * a[i] % mod;} else {for (int i 1; i k; i) res res * a[i] % mod;}return cout res \n, 0;}vectorpairint, int vec;vec.push_back(make_pair(0, 0));for (int i 1; i n; i) {// 将负数两两打包在一起视为一个物品if (a[i] 0 a[i 1] 0) {vec.push_back(make_pair(a[i] * a[i 1], 2));i;}// 将正数单独作为一个物品else if (a[i] 0) vec.push_back(make_pair(a[i], 1));}memset(dp, -0x3f, sizeof(dp));dp[0][0] 0;ans[0][0] 1; // 初始化for (int i 1; i vec.size(); i) {int v vec[i].first, w vec[i].second;for (int j 0; j k; j) {// 状态转移dp[i][j] dp[i - 1][j];ans[i][j] ans[i - 1][j];if (j - w 0) {if (dp[i][j] dp[i - 1][j - w] log2(v)) {dp[i][j] dp[i - 1][j - w] log2(v);ans[i][j] ans[i - 1][j - w] * v % mod;}}}}cout ans[vec.size() - 1][k] \n;return 0;
}
四、皮亚诺曲线距离【难】
【问题描述】 皮亚诺曲线是一条平面内的曲线。 下图给出了皮亚诺曲线的1阶情形它是从左下角出发经过一个3×3的方格中 的每一个格子最终到达右上角的一条曲线。 下图给出了皮亚诺曲线的2阶情形它是经过一个32×32 的方格中的每一个格子 的一条曲线。它是将1阶曲线的每个方格由1阶曲线替换而成的。 下图给出了皮亚诺曲线的3阶情形它是经过一个33×33 的方格中的每一个格子 的一条曲线。它是将2阶曲线的每个方格由1阶曲线替换而成的。 皮亚诺曲线总是从左下角开始出发最终到达右上角。 我们将这些格子放到坐标系中对于k阶皮亚诺曲线左下角的坐标是(0,0)右 角坐标是(3k−1,3k−1)右下角坐标是(3k−1,0)左上角坐标是(0,3k−1)。 给定k阶皮亚诺曲线上的两个点的坐标请问这两个点之间如果沿着皮亚诺曲线走距离是多少?
【输入格式】 输入的第一行包含一个正整数k皮亚诺曲线的阶数。 第二行包含两个整数x1,y1表示第一个点的坐标。 第三行包含两个整数x2,y2表示第二个点的坐标。 其中有0⩽k⩽100,0⩽x1,y1,x2,y23k,x1,y1,x2,y2⩽1018次方。数据保证答案不 超过1018次方。
【输出格式】 输出一个整数表示给定的两个点之间的距离。
【样例输入】 【样例输出】 8
解析 本题是一道“思维”大题它极其考验选手的观察力、分析力及判断力难度颇高。 显然想要根据观察规律直接求出皮亚诺曲线上任意两个点的坐标几乎不可能。因此我 们需要对问题进行优化。 对于皮亚诺曲线上两个不同的点(x1,y1)、(x2,y2)它们的位置关系有以下两种。 •从起点(0,0)出发先走到(x1,y1)再走到(x2,y2)那么从(0,0)走到(x2,y2)就可以分解为 (0,0)→(x1,y1)→(x2,y2)。 •从起点(0,0)出发先走到(x2,y2)再走到(x1,y1)那么从(0,0)走到(x1,y1)就可以分解为 (0,0)→(x2,y2)→(x1,y1)。 假设(x1,y1)、(x2,y2)到点(0,0)的距离分别为a,b则它们之间的距离必然为|b−a| 如下图所示。 于是求解 (x1,y1) 到 (x2,y2) 的问题就可简化为求点 (x1,y1)、(x2,y2) 到点 (0,0) 的 距离。 如何求解一个点到起点(0,0)的距离呢? 我们接着优化。 根据定义可得一个n阶的皮亚诺曲线一定可以由9个n−1阶的皮亚诺曲线拼凑构成 方程如下。 若按照先后顺序将n阶的皮亚诺曲线划分为9个块九宫格则每个块都将会是一个 n−1 阶的皮亚诺曲线。因此我们可以通过缩放将点映射到块上来简化问题。 对于点(x,y)其缩放后坐标会变为比如在3阶皮亚诺曲线中坐标为(22, 13) 的点缩放后的坐标就为即 (2,1)。 3 阶皮亚诺曲线在对点缩放后会有以下几种情况。 对于一个块我们可以为其添加两个新的概念。 1块的出口表示一个块内距离起点(0,0)最近的点。 2块的大小表示从进入块到离开块所要走的步数一个 n−1 阶的块的大小等于 3n−1 ×3n−1。 设(x,y) 位于九宫格的第i 个块则它到起点的距离可以分解为以下两部分。 1(x,y) 到第 i 个块的出口的距离。 2第i个块的出口到第1个块的出口的距离。 通过观察可以得知第i个块的出口到第1个块的出口的距离等于i−1个块的大小即 (i −1)×3n−1 ×3n−1。接下来我们只要能求出 (x,y) 到第 i 个块的出口的距离就可求出 (x, y) 到起点的距离。 我们知道第i个块的结构相当于一个n−1阶的皮亚诺曲线。根据已有的分析可知当 n−1 很大时我们是很难求出(x,y)到n−1阶皮亚诺曲线的出口的距离的。不过如果n−1 很小比如n−11时我们就可以通过暴力、模拟甚至肉眼的观察轻松求出(x,y)到 n−1 阶皮亚诺曲线的出口的距离。那么有没有办法将n−1以大化小呢? 如果我们将第i个块看作是一个全新的n−1阶的皮亚诺曲线则求(x,y)到第i个块 的出口的距离就等价于求(x,y)到全新的n−1阶皮亚诺曲线的出口的距离。 如果我们将这个全新的n−1阶皮亚诺曲线划分为新的九宫格并设(x,y)位于新的九 宫格中的第i′ 个块那么此时(x,y)距离新的九宫格起点的出口又可以分为两部分。 1(x,y) 到新九宫格第 i′ 个块的出口的距离。 2新九宫格第i′ 个块的出口到新九宫格第1个块的距离。 从新九宫格第i′ 个块的出口到新九宫格第1个块的出口的距离距离为(i′−1)×3n−2× 3n−2而求 (x,y) 到第 i′ 个块的出口的距离可以重复上述步骤将其转换为新的问题如下图所示。 需要注意的是n−1阶的九宫格和n阶九宫格的块的顺序结构不一定相同。
提示如下 整个求解通过层层转换的方式将问题逐渐简化为一个与原问题相似但规模较小的问题 来求解与递归的性质极其吻合因此我们可以用递归的方式来完成求解。 首先声明一个递归函数calc(n,x,y,??)用于计算位于n阶皮亚诺曲线中的点(x,y) 距离第1个块的出口的距离?? 用来表示这个n阶皮亚诺曲线的结构同阶的皮亚诺曲线的结构不一定相同比如第1个块与第2个块。 根据前文可以分析出以下两种情况。 那么要怎么表示n阶皮亚诺曲线的结构又要如何解决结构的变化呢? 我们可以定义一个3×3的二维数组mp[][]并用mp[0][0]、mp[0][1]、mp[0][2]、mp[1][0]、 mp[1][1]、mp[1][2]、mp[2][0]、mp[2][1]、mp[2][2]分别表示对应位置的块的编号再根据上图 中3阶九宫格每个块变化的规律对mp进行修改即可。 至此本题的解题分析完成具体代码如下
参考代码如下【时间复杂度为O(9×log31018次方)】
#include bits/stdc.h
#define ll long long
using namespace std;ll p[40];
mappairint, int, int mp;ll calc(int n, ll x, ll y, mappairint, int, int mp) {ll x_ x / p[n - 1], y_ y / p[n - 1]; // 将 (x, y) 缩放得到 (x_, y_)if (n 1) return mp[make_pair(x_, y_)] - 1; // 如果 n 1返回所在块的编号 - 1ll ans (mp[make_pair(x_, y_)] - 1) * p[n - 1] * p[n - 1];mappairint, int, int mp1; // mp1 记录 n-1 阶皮亚诺曲线的变化if ((x_ 0 y_ 1) || (x_ 2 y_ 1)) {for (int i 0; i 2; i) {for (int j 0; j 2; j) {mp1[make_pair(2 - i, j)] mp[make_pair(i, j)];}}} else if ((x_ 1 y_ 2) || (x_ 1 y_ 0)) {for (int i 0; i 2; i) {for (int j 0; j 2; j) {mp1[make_pair(i, 2 - j)] mp[make_pair(i, j)];}}} else if (x_ 1 y_ 1) {for (int i 0; i 2; i) {for (int j 0; j 2; j) {mp1[make_pair(2 - i, 2 - j)] mp[make_pair(i, j)];}}} else {mp1 mp;}return ans calc(n - 1, x % p[n - 1], y % p[n - 1], mp1);
}signed main() {p[0] 1;for (int i 1; i 40; i) p[i] p[i - 1] * 3;mp[make_pair(0, 0)] 1;mp[make_pair(0, 1)] 2;mp[make_pair(0, 2)] 3;mp[make_pair(1, 2)] 4;mp[make_pair(1, 1)] 5;mp[make_pair(1, 0)] 6;mp[make_pair(2, 0)] 7;mp[make_pair(2, 1)] 8;mp[make_pair(2, 2)] 9;ll k, x1, y1, x2, y2;cin k x1 y1 x2 y2;// 由于 3^39 10^18所以 39 阶皮亚诺曲线已包含了横、纵坐标在 1~10^18 范围内的所有点// 所以从 39 阶皮亚诺曲线开始递归即可ll a calc(39, x1, y1, mp);ll b calc(39, x2, y2, mp);cout abs(a - b) \n;return 0;
}
别忘了请点个赞收藏关注支持一下博主喵
关注博主更多蓝桥杯nice题目静待更新:)
