第十届蓝桥杯B组决赛"/>
2020年第十届蓝桥杯B组决赛
一.美丽的 2
题目描述
本题为填空题，只需要算出结果后，在代码中使用输出语句将所填结果输出即可。
小蓝特别喜欢 2，今年是公元 2020 年，他特别高兴。 他很好奇，在公元 1 年到公元 2020 年（包含）中，有多少个年份的数位中包含数字 2？
运行限制
- 最大运行时间：1s
- 最大运行内存: 128M
思路：水题，枚举数字，判断一下是否满足条件，统计结果即可。
#include <iostream>
using namespace std;bool hasTwo(int num)
{while(num){if(num % 10 ==2){return true;}num /= 10;}return false;
}int main()
{int year, ans = 0;for(year = 1; year <= 2020; ++ year){if(hasTwo(year)){++ ans;}}cout << ans;return 0;
}二.题目描述
本题为填空题，只需要算出结果后，在代码中使用输出语句将所填结果输出即可。
小蓝在一张无限大的特殊画布上作画。
这张画布可以看成一个方格图，每个格子可以用一个二维的整数坐标表示。
小蓝在画布上首先点了一下几个点：(0, 0), (2020, 11), (11, 14), (2000, 2000)。
只有这几个格子上有黑色，其它位置都是白色的。
每过一分钟，黑色就会扩散一点。具体的，如果一个格子里面是黑色，它就会扩散到上、下、左、右四个相邻的格子中，使得这四个格子也变成黑色（如果原来就是黑色，则还是黑色）。
请问，经过 2020 分钟后，画布上有多少个格子是黑色的。
运行限制
- 最大运行时间：1s
- 最大运行内存: 128M
思路：
1.可以选择用数学计算机几何的知识，实际上每一个点扩散后形成的图形为菱形（边上的所有点到中心点的曼哈顿距离相等），然后实际上就是问四个菱形的并集中含有多少个方格。
2.本题最直观的解法是使用BFS，值得注意的是本题的坑，我们需要将所有的点 x方向 + 2020，y方向 + 2020，防止在BFS的过程中点的坐标变为负，进而导致越界问题。
#include <iostream>
#include <queue>
using namespace std;
struct Point{int x, y, step;
};int dir[4][2] = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};bool used[6200][6200];int BFS(queue<Point>& pointQue)
{int pointNum = 4, x, y, step, i, n_x, n_y;Point p;while(!pointQue.empty()){p = pointQue.front();pointQue.pop();x = p.x;y = p.y;step = p.step;if(step == 2020){break;}for(i = 0; i < 4; ++ i){n_x = x + dir[i][0];n_y = y + dir[i][1];if(!used[n_x][n_y]){++ pointNum;used[n_x][n_y] = true;pointQue.push(Point{n_x, n_y, step + 1});}}}return pointNum;
}int main()
{// 请在此输入您的代码queue<Point> pointQue;const int offset = 2020;pointQue.push(Point{0 + offset, 0 + offset, 0});pointQue.push(Point{2020 + offset, 11 + offset, 0});pointQue.push(Point{11 + offset, 14 + offset, 0});pointQue.push(Point{2000 + offset, 2000 + offset, 0});used[0][0] = used[2020][11] = used[11][14] = used[2000][2000] = true;cout << BFS(pointQue);return 0;
}三.阶乘约数
题目描述
本题为填空题，只需要算出结果后，在代码中使用输出语句将所填结果输出即可。
定义阶乘 n! = 1 × 2 × 3 × · · · × n。
请问 100! （100 的阶乘）有多少个正约数。
运行限制
- 最大运行时间：1s
- 最大运行内存: 128M
思路：使用素数分解定理，对于任意一个正整数x，我们都可以将其分解为：
于是，当我们对一个合数进行素数分解后，他的约数数量为：
相当于我们从一堆素数中随机挑选几个乘出数字得到约数，由于所有的数都是素数，因此两次挑出的素数不是完全一致的就一定不会得到相同的约数。对于每一个素数，它可以被选择出现~次共种情况，因此答案为上述公式。
值得注意的是，本题我们不可以先算出100!再分解，因为这个结果太大了，如果用大整数存下再分解，又是没必要的。我们只需要对2*3*..*100的每一个数分解后累加素因子即可。
#include <iostream>
#include <unordered_map>
using namespace std;
int main()
{unordered_map<int, int> hash_count;int temp, factor, i;long long c;for(factor = 2; factor <= 100; ++ factor){temp = factor;for(i = 2; temp != 1; ++ i){c = 0;while(temp % i == 0){temp /= i;++ c;}hash_count[i] += c;}}c = 1;for(unordered_map<int, int>::iterator iter = hash_count.begin(); iter != hash_count.end(); ++ iter){c = c * (iter -> second + 1);}cout << c;return 0;
}四.本质上升序列
题目描述
本题为填空题，只需要算出结果后，在代码中使用输出语句将所填结果输出即可。
小蓝特别喜欢单调递增的事物。
在一个字符串中，如果取出若干个字符，将这些字符按照在字符串中的顺序排列后是单调递增的，则成为这个字符串中的一个单调递增子序列。
例如，在字符串 lanqiao 中，如果取出字符 n 和 q，则 nq 组成一个单调递增子序列。类似的单调递增子序列还有 lnq、i、ano 等等。 小蓝发现，有些子序列虽然位置不同，但是字符序列是一样的，例如取第二个字符和最后一个字符可以取到 ao，取最后两个字符也可以取到 ao。小蓝认为他们并没有本质不同。
对于一个字符串，小蓝想知道，本质不同的递增子序列有多少个？ 例如，对于字符串 lanqiao，本质不同的递增子序列有 21 个。它们分别是 l、a、n、q、i、o、ln、an、lq、aq、nq、ai、lo、ao、no、io、lnq、anq、lno、ano、aio。
请问对于以下字符串（共 200 个小写英文字母，分四行显示）：
tocyjkdzcieoiodfpbgcncsrjbhmugdnojjddhllnofawllbhf
iadgdcdjstemphmnjihecoapdjjrprrqnhgccevdarufmliqij
gihhfgdcmxvicfauachlifhafpdccfseflcdgjncadfclvfmad
vrnaaahahndsikzssoywakgnfjjaihtniptwoulxbaeqkqhfwl
本质不同的递增子序列有多少个？
运行限制
- 最大运行时间：1s
- 最大运行内存: 128M
分析：题意为从一个字符串中取出一些字符，按照在字符串中的位置摆放好，如果形成的串是按照字典序递增的，就是我们需要找的串。只考虑串的内容不考虑形成串的字符所在位置是否有不同，这样的串成为本质不同的串。也就是说，对于串:acab，存在两个ab，但是他们算作同一个串。
思路：首先我们需要明确，假定我们确定串的开始字符进行枚举，那么这个字符一定要在第一次出现的位置，比如：
acab，我们要考虑以a为开始的串，我们只需要考虑第一个a所能形成的串集合，而不需要考虑第二个a，这是因为第二个a后面可以考虑接的字符的范围一定是在第一个a的可考虑范围内的，也就是说第一个a的答案是包含了第二个的。
a***a****，若第二个a可以得到串a**，那么第一个a必然可以得到串a**。
我们现在可以确定开始字符，但这也很麻烦，因为生成的串不在同一处结束。那么我们可以逆向考虑，从整个串的尾到头，由于我们可以确定生成串的串头，因此逆向考虑就变成了串在同一处结束。
那么既然我们可以逆向考虑，不如我们在一开始就考虑的是串在何时结束。我们用dp[i]表示以str[i]为结束的串的个数，那么算法如下：
1.初始化，所有的dp[i]=1（因为字符自己本身可以形成一个串）
2.对于dp[i]，枚举j<i，如果str[j]∈['a',str[i])，那么在以str[j]结尾的串后面可以连接上str[i]，但需要注意的是，若str[j1]=str[j2]，且j1<j2，那么应该对dp[i]累加上dp[j2]而不是dp[j1]，因为我们要避免重复（本质相同的串只计算一次），而dp[j2]上的答案一定会包括dp[j1]的，因此我们累加dp[j2]。
#include <iostream>
#include <cstring>
using namespace std;
int main()
{// 正向解：对于每一个字符，只需要计算从他第一次出现开始，可以产生的递增序列数量即可。a*****a****，显然第一个a产生的序列一定包含第二个a产生的序列// 反向解：对于每一个字符，计算以他结束的递增序列数量，只计算最靠近开头的字符// 请在此输入您的代码// 转化 最后出现的 以其为结尾的字符串数量// 去重 al***lk，第一个l贡献的答案一定被包含在第二个l里string str = "tocyjkdzcieoiodfpbgcncsrjbhmugdnojjddhllnofawllbhfiadgdcdjstemphmnjihecoapdjjrprrqnhgccevdarufmliqijgihhfgdcmxvicfauachlifhafpdccfseflcdgjncadfclvfmadvrnaaahahndsikzssoywakgnfjjaihtniptwoulxbaeqkqhfwl";int dp[205], last[30];int i, j, ans = 0;bool vis[30];memset(vis, 0, sizeof(vis));memset(dp, 0, sizeof(dp));memset(last, -1, sizeof(last));dp[0] = 1;last[str[0] - 'a'] = 0;for(i = 1;i < str.length(); ++ i){dp[i] = 1;last[str[i] - 'a'] = i;for(j = 0; j < str[i] - 'a'; ++ j){if(last[j] != -1){dp[i] += dp[last[j]];}}}for(i = str.length() - 1; i >=0; -- i){if(!vis[str[i] - 'a']){vis[str[i] - 'a'] = true;ans += dp[i];}}cout << ans;return 0;
}五.玩具蛇
题目描述
本题为填空题，只需要算出结果后，在代码中使用输出语句将所填结果输出即可。
小蓝有一条玩具蛇，一共有 16 节，上面标着数字 1 至 16。每一节都是一个正方形的形状。相邻的两节可以成直线或者成 9090 度角。
小蓝还有一个 4 × 4 的方格盒子，用于存放玩具蛇，盒子的方格上依次标着字母 A 到 P 共 16 个字母。
小蓝可以折叠自己的玩具蛇放到盒子里面。他发现，有很多种方案可以将玩具蛇放进去。
下图给出了两种方案：
请帮小蓝计算一下，总共有多少种不同的方案。如果两个方案中，存在玩具蛇的某一节放在了盒子的不同格子里，则认为是不同的方案。
运行限制
- 最大运行时间：1s
- 最大运行内存: 128M
思路：直接枚举起点，然后DFS统计一下合法数量即可。
#include <iostream>
using namespace std;bool used[5][5];
int dir[4][2] = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};bool check(int x, int y)
{return x >= 1 && x <= 4 && y >= 1 && y <= 4 && !used[x][y];
}void DFS(int x, int y, int step, int& ans)
{if(step == 16){++ ans;return;}int n_x, n_y;for(int i = 0; i < 4; ++ i){n_x = dir[i][0] + x;n_y = dir[i][1] + y;if(check(n_x, n_y)){used[n_x][n_y] = true;DFS(n_x, n_y, step + 1, ans);used[n_x][n_y] = false;}}return;
}int main()
{// 请在此输入您的代码int ans = 0, i, j;for(i = 1; i <= 4; ++ i){for(j = 1; j <= 4; ++ j){used[i][j] = true;DFS(i, j, 1, ans);used[i][j] = false;}}cout << ans;return 0;
}六.皮亚诺曲线距离(前方高能)
题目描述
皮亚诺曲线是一条平面内的曲线。
下图给出了皮亚诺曲线的 1 阶情形，它是从左下角出发，经过一个 3×3 的方格中的每一个格子，最终到达右上角的一条曲线。
下图给出了皮亚诺曲线的 2 阶情形，它是经过一个 3^2 × 3^2 的方格中的每一个格子的一条曲线。它是将 1 阶曲线的每个方格由 1 阶曲线替换而成。
下图给出了皮亚诺曲线的 3 阶情形，它是经过一个 3^3 × 3^3 的方格中的每一个格子的一条曲线。它是将 2 阶曲线的每个方格由 1 阶曲线替换而成。
皮亚诺曲线总是从左下角开始出发，最终到达右上角。
我们将这些格子放到坐标系中，对于 kk 阶皮亚诺曲线，左下角的坐标是(0, 0)(0,0)，右上角坐标是 (3^k − 1, 3^k − 1)，右下角坐标是 (3^k − 1, 0)，左上角坐标是(0, 3^k − 1)。
给定 kk 阶皮亚诺曲线上的两个点的坐标，请问这两个点之间，如果沿着皮亚诺曲线走，距离是到少？
输入描述
输入的第一行包含一个正整数 kk，皮亚诺曲线的阶数。
第二行包含两个整数 x_1, y_1，表示第一个点的坐标。
第三行包含两个整数 x_2, y_2，表示第二个点的坐标。
其中有 ，0 ≤ k ≤ 100, 0 ≤ x_1, y_1, x_2, y_2 < 3^k, x_1, y_1, x_2, y_2 ≤ 10^{18}。数据保证答案不超过 10^{18}。
输出描述
输出一个整数，表示给定的两个点之间的距离。
输入输出样例
示例
输入
1
0 0
2 2
输出
8
运行限制
- 最大运行时间：1s
- 最大运行内存: 128M
思路：本题需要用到递归分解的思想。
1.通过模拟的方式得到两点的皮亚诺距离，但是方格可能很大，不切实际。
2.我们可以解出两个点与(1,1)之间的皮亚诺距离，再做差即可。
首先我们知道，皮亚诺曲线阶数上升1，则行*3，列*3。并且对于1阶皮亚诺曲线，他的起点到终点的距离为8，每升一阶，则是低阶重复了9次，并且还有9个重复块(包含旋转)之间的8条连接线。也就是说，对于一个满k阶的皮亚诺曲线，我们可以知道他的路径长度为：
我们拿3阶曲线做一个示范，他是由9个2阶曲线按照皮亚诺曲线的生成顺序堆叠而成，因此我们可以看成如下这种方式：
注：棕色矩形框就是低阶曲线之间的连接线。
假设我们要求图中红色圆圈的节点到起点(1,1)的路径距离，我们从图上很容易知道，这是处于第8个二阶曲线图内部的点，因此答案可以类加上7个1阶曲线加7条连接线的路径长度，即
然后我们递归进入第8个二阶曲线图进行求解：
这时候我们又发现他是9个1阶皮亚诺曲线组合而成，目标点处于第2个1阶皮亚诺曲线图内，前面有1个完整的1阶皮亚诺曲线，答案可以累计上1个1阶曲线加1条连接线的路径长度，即
再次递归分解，于是剩余的部分为：
再累加上2就是最终答案了，为567+9+2=578。
我们可以看出不论怎么旋转或堆叠，1阶皮亚诺曲线只有两种。同理推广到k阶，依旧是只有两种，即正序和逆序。
注：本题需要注意的是坐标转换，数组的索引是从左上到右下，本题的坐标系为从左下到右上
过了但没完全过，汗*************
#include <iostream>
#include <cmath>
using namespace std;
typedef long long LL;
const int maxn = 110;
LL p_len[maxn], side_len[maxn];int positiveCoord[3][3] =
{{0,5,6},{1,4,7},{2,3,8},
},
negativeCoord[3][3] =
{{8,3,2},{7,4,1},{6,5,0},
};//求解 (x,y) 在 k阶图 上 距离(0,0)的距离
LL get_len(LL x, LL y, int k, int isPositive)
{if(k == 1) {cout << (isPositive ? "顺序":"逆序") << " y:" << y << " x:" << x << endl; return isPositive ? positiveCoord[y][x] : negativeCoord[y][x];}int col = x / side_len[k - 1];int row = y / side_len[k - 1];//求出前面有多少块int block = isPositive ? positiveCoord[row][col] : negativeCoord[row][col];cout << "有" << block << "个" << k - 1 << "阶块,贡献量为:" << p_len[k - 1] * block + block << endl; return p_len[k - 1] * block + block + get_len(x % side_len[k - 1], y % side_len[k - 1], k - 1, (block & 1) ^ isPositive);
}int main()
{int k, i;LL dis_one, dis_two, x, y;cin >> k;p_len[0] = 1;p_len[1] = 8;side_len[0] = 1;side_len[1] = 3;//生成1~k-1阶的皮亚诺曲线的总长度for(i = 2; i < k; ++ i){side_len[i] = side_len[i - 1] * 3;p_len[i] = p_len[i - 1] * 9 + 8; // p_len[i] = side_len[i] * side_len[i] - 1;}cin >> x >> y;dis_one = get_len(x, y, k, 1);cout << "dis_one:" << dis_one << endl;cin >> x >> y;dis_two = get_len(x, y, k, 1);cout << "dis_two:" << dis_two << endl;cout << abs(dis_one - dis_two);return 0;
}问题探索：上面递归分解的思想是没有问题的，但是在做坐标系转化的时候忽视了一共有四种情况(两种形状*两个方向)。
情况一(从左下角开始)：
情况二(从右下角开始)：
情况三(从左上角开始)：
情况四(从右上角开始)：
捏嘛毒瘤题，我已经晕了(划掉)
我们将这四种基本形状进行标号后可以发现，在第k阶图中，k-1阶的子图排列的顺序也是(不考虑递归分解，只看图形本身)：
1 3 1
2 4 2
1 3 1
那么我们在递归分解的过程中可以知道出发点是在四个角落中的哪一个位置，依次来确定当前位置是第几块。
举个例子：
A.开始分解时，从左下角出发，发现当前位置处于第8个大块，累计上前面7块的贡献，并且可以知道当我们分解第8块的时候是从右下角开始。
B.从右下角开始，发现目标位置处于第2个子大块，累计上前面1块的贡献，现在知道继续分解从左下开始。
C.继续处理，直到阶数降为0
#include <iostream>
#include <cstdio>
#include <cmath>
using namespace std;
typedef long long LL;
const int maxn = 110;
LL p_len[maxn], side_len[maxn];int dir_one_loc[3][3] =
{{0, 1, 2},{5, 4, 3},{6, 7, 8},
}, dir_two_loc[3][3] =
{{6, 7, 8},{5, 4, 3},{0, 1, 2},
}, dir_three_loc[3][3] =
{{2, 1, 0},{3, 4, 5},{8, 7, 6},
}, dir_four_loc[3][3] =
{{8, 7, 6},{3, 4, 5},{2, 1, 0},
},
dir_one[9] = {1, 2, 1, 3, 4, 3, 1, 2, 1},//左下
dir_two[9] = {2, 1, 2, 4, 3, 4, 2, 1, 2},//右下
dir_three[9] = {3, 4, 3, 1, 2, 1, 3, 4, 3},//左上
dir_four[9] = {4, 3, 4, 2, 1, 2, 4, 3, 4}//右上
;//求解 (x,y) 在 k阶图 上 距离(0,0)的距离
LL get_len(LL x, LL y, int k, int preDir)
{if(k == 0) return 0;int col = x / side_len[k - 1];int row = y / side_len[k - 1];//printf("阶:%d col:%lld row:%lld x:%lld y:%lld\n", k, col, row, x, y);int block, nextDir;//求出前面有多少块switch(preDir){case 1:block = dir_one_loc[col][row];nextDir = dir_one[block];break;case 2:block = dir_two_loc[col][row];nextDir = dir_two[block];break;case 3:block = dir_three_loc[col][row];nextDir = dir_three[block];break;case 4:block = dir_four_loc[col][row];nextDir = dir_four[block];break;}//cout << "有" << block << "块," << "下一个方向为:" << nextDir << ",当前阶数:" << k << ",块大小:" << p_len[k - 1] << endl;return p_len[k - 1] * block + (k > 1 ? block : 0) + get_len(x % side_len[k - 1], y % side_len[k - 1], k - 1, nextDir);
}int main()
{int k, i;LL dis_one, dis_two, x, y;cin >> k;p_len[0] = 1;p_len[1] = 8;side_len[0] = 1;side_len[1] = 3;//生成1~k-1阶的皮亚诺曲线的总长度for(i = 2; i < k; ++ i){side_len[i] = side_len[i - 1] * 3;p_len[i] = p_len[i - 1] * 9 + 8; // p_len[i] = side_len[i] * side_len[i] - 1;}cin >> x >> y;dis_one = get_len(x, y, k, 1);//cout << "dis_one:" << dis_one << endl;cin >> x >> y;dis_two = get_len(x, y, k, 1);//cout << "dis_two:" << dis_two << endl;cout << abs(dis_one - dis_two);return 0;
}然而！上面的代码还是不能全过，实际上本题需要用到BigInt，哎，差点给我人送走了，好吧，就当是个花絮吧
#pragma comment(linker, "/STACK:10240000,10240000")
#include <iostream>
#include <string>
#include <cstring>
#include <cstdio>
#include <algorithm>
using namespace std;const int maxn = 1000;struct bign{int d[maxn], len;void clean() { while(len > 1 && !d[len-1]) len--; }bign() { memset(d, 0, sizeof(d)); len = 1; }bign(int num) { *this = num; } bign(char* num) { *this = num; }bign operator = (const char* num){memset(d, 0, sizeof(d)); len = strlen(num);for(int i = 0; i < len; i++) d[i] = num[len-1-i] - '0';clean();return *this;}bign operator = (int num){char s[1000] = { 0 }; sprintf_s(s, "%d", num);*this = s;return *this;}bign operator + (const bign& b){bign c = *this; int i;for (i = 0; i < b.len; i++){c.d[i] += b.d[i];if (c.d[i] > 9) c.d[i]%=10, c.d[i+1]++;}while (c.d[i] > 9) c.d[i++]%=10, c.d[i]++;c.len = max(len, b.len);if (c.d[i] && c.len <= i) c.len = i+1;return c;}bign operator - (const bign& b){bign c = *this; int i;for (i = 0; i < b.len; i++){c.d[i] -= b.d[i];if (c.d[i] < 0) c.d[i]+=10, c.d[i+1]--;}while (c.d[i] < 0) c.d[i++]+=10, c.d[i]--;c.clean();return c;}bign operator * (const bign& b)const{int i, j; bign c; c.len = len + b.len; for(j = 0; j < b.len; j++) for(i = 0; i < len; i++) c.d[i+j] += d[i] * b.d[j];for(i = 0; i < c.len-1; i++)c.d[i+1] += c.d[i]/10, c.d[i] %= 10;c.clean();return c;}bign operator / (const bign& b){int i, j;bign c = *this, a = 0;for (i = len - 1; i >= 0; i--){a = a*10 + d[i];for (j = 0; j < 10; j++) if (a < b*(j+1)) break;c.d[i] = j;a = a - b*j;}c.clean();return c;}bign operator % (const bign& b){int i, j;bign a = 0;for (i = len - 1; i >= 0; i--){a = a*10 + d[i];for (j = 0; j < 10; j++) if (a < b*(j+1)) break;a = a - b*j;}return a;}bign operator += (const bign& b){*this = *this + b;return *this;}bool operator <(const bign& b) const{if(len != b.len) return len < b.len;for(int i = len-1; i >= 0; i--)if(d[i] != b.d[i]) return d[i] < b.d[i];return false;}bool operator >(const bign& b) const{return b < *this;}bool operator<=(const bign& b) const{return !(b < *this);}bool operator>=(const bign& b) const{return !(*this < b);}bool operator!=(const bign& b) const{return b < *this || *this < b;}bool operator==(const bign& b) const{return !(b < *this) && !(b > *this);}string str() const{char s[maxn]={};for(int i = 0; i < len; i++) s[len-1-i] = d[i]+'0';return s;}int toInt() const{int num = 0;for(int i = 0; i < len; i++) num = num * 10 + d[i];return num;}
};istream& operator >> (istream& in, bign& x)
{string s;in >> s;x = s.c_str();return in;
}ostream& operator << (ostream& out, const bign& x)
{out << x.str();return out;
}typedef long long LL;
const int maxLen = 110;
bign p_len[maxLen], side_len[maxLen];int dir_one_loc[3][3] =
{{0, 1, 2},{5, 4, 3},{6, 7, 8},
}, dir_two_loc[3][3] =
{{6, 7, 8},{5, 4, 3},{0, 1, 2},
}, dir_three_loc[3][3] =
{{2, 1, 0},{3, 4, 5},{8, 7, 6},
}, dir_four_loc[3][3] =
{{8, 7, 6},{3, 4, 5},{2, 1, 0},
},
dir_one[9] = {1, 2, 1, 3, 4, 3, 1, 2, 1},//左下
dir_two[9] = {2, 1, 2, 4, 3, 4, 2, 1, 2},//右下
dir_three[9] = {3, 4, 3, 1, 2, 1, 3, 4, 3},//左上
dir_four[9] = {4, 3, 4, 2, 1, 2, 4, 3, 4}//右上
;//求解 (x,y) 在 k阶图 上 距离(0,0)的距离
bign get_len(bign x, bign y, int k, int preDir)
{if(k == 0) return 0;int col = (x / side_len[k - 1]).toInt();int row = (y / side_len[k - 1]).toInt();//printf("阶:%d col:%d row:%d\n", k, col, row);int block, nextDir;//求出前面有多少块switch(preDir){case 1:block = dir_one_loc[col][row];nextDir = dir_one[block];break;case 2:block = dir_two_loc[col][row];nextDir = dir_two[block];break;case 3:block = dir_three_loc[col][row];nextDir = dir_three[block];break;case 4:block = dir_four_loc[col][row];nextDir = dir_four[block];break;}//cout << "有" << block << "块," << "下一个方向为:" << nextDir << ",当前阶数:" << k << ",块大小:" << p_len[k - 1] << endl;return p_len[k - 1] * block + (k > 1 ? block : 0) + get_len(x % side_len[k - 1], y % side_len[k - 1], k - 1, nextDir);
}int main()
{int k, i;bign dis_one, dis_two, x, y;cin >> k;p_len[0] = 1;p_len[1] = 8;side_len[0] = 1;side_len[1] = 3;//生成1~k-1阶的皮亚诺曲线的总长度for(i = 2; i < k; ++ i){side_len[i] = side_len[i - 1] * 3;p_len[i] = p_len[i - 1] * 9 + 8; // p_len[i] = side_len[i] * side_len[i] - 1;//cout << "阶:" << i << " " << side_len[i] << " " << p_len[i] << endl;}cin >> x >> y;dis_one = get_len(x, y, k, 1);//cout << "dis_one:" << dis_one << endl;cin >> x >> y;dis_two = get_len(x, y, k, 1);//cout << "dis_two:" << dis_two << endl;cout << (dis_one > dis_two ? dis_one - dis_two : dis_two - dis_one);return 0;
}过了过了别骂了，偷了个大整数的板子，过了过了，汗=-=
八.答疑
题目描述
有 n 位同学同时找老师答疑。每位同学都预先估计了自己答疑的时间。
老师可以安排答疑的顺序，同学们要依次进入老师办公室答疑。 一位同学答疑的过程如下：
- 首先进入办公室，编号为 i 的同学需要 s_i 毫秒的时间。
- 然后同学问问题老师解答，编号为 i 的同学需要 a_i 毫秒的时间。
- 答疑完成后，同学很高兴，会在课程群里面发一条消息，需要的时间可以忽略。
- 最后同学收拾东西离开办公室，需要 e_i 毫秒的时间。一般需要 10 秒、20 秒或 30 秒，即 e_i 取值为 10000，20000 或 30000。
一位同学离开办公室后，紧接着下一位同学就可以进入办公室了。
答疑从 0 时刻开始。老师想合理的安排答疑的顺序，使得同学们在课程群 里面发消息的时刻之和最小。
输入描述
输入第一行包含一个整数 n，表示同学的数量。
接下来 nn 行，描述每位同学的时间。其中第 i 行包含三个整数 s_i, a_i, e_i，意义如上所述。
其中有 ，1 ≤ n ≤ 1000，1 ≤ s_i ≤ 60000，1 ≤ a_i ≤ 10^6， e_i ∈ {10000, 20000, 30000}，即 e_i 一定是 10000、20000、30000 之一。
输出描述
输出一个整数，表示同学们在课程群里面发消息的时刻之和最小是多少。
输入输出样例
示例
输入
3
10000 10000 10000
20000 50000 20000
30000 20000 30000
输出
280000
运行限制
- 最大运行时间：3s
- 最大运行内存: 128M
思路：我们先来看看需要计算的时刻到底是个什么玩意儿，对于i号学生来说，他发消息的时刻为：
现在我们要求的是：
对于这种题目，我们一般会有两种思路：
1.将累加式展开，看实际影响的项
2.一般来说这种题目都是按照某种序列对原数据进行排序，因此我们可以随机找出两组数据，试着交换他们，对比他们交换前后产生的影响
现在我们尝试交换一下i与j，这种交换实际上是会对区间(i,j)内部的元素产生影响的，我们只会比较交换前后受影响的部分：
| i | (i,j) | j | |
| 交换前 | |||
| 交换后 |
我们可以消去交换前后相同的部分，可以得到：
| 受影响的值 | |
| 交换前 | |
| 交换后 |
那么显而易见，把更小的放在前面就是最优方案：
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;struct Stu{long long s, a, e;bool operator < (const Stu stu) const {int pre = s + a + s + a + e + stu.s + stu.a;int p = stu.s + stu.a + stu.s + stu.a + stu.e + s + a;return pre < p;}
};int main()
{// 但是对其他人没有任何影响// Si进入教室 Ai问问题 Ei离开// 想要 ∑ Si + Ai 最小 但是 Ei-1 显然会影响到Si + Ai的大小// 请在此输入您的代码// 推公式Stu stus[1010];memset(stus, 0, sizeof(stus));long long n, i, timeSum = 0, timeStart = 0;cin >> n;for(i = 1; i <= n; ++ i){cin >> stus[i].s >> stus[i].a >> stus[i].e;}sort(stus + 1, stus + 1 + n );for(i = 1; i <= n; ++ i){timeStart += stus[i].s + stus[i].a;timeSum += timeStart;timeStart += stus[i].e;}cout << timeSum;return 0;
}更多推荐
2020年第十届蓝桥杯B组决赛
发布评论