.天津网站建设,珠海网站建设哪家好,网站开发和前端是一样吗,静态页面网站怎么做文章目录#x1f4ac;前言#x1f332;day1最大和 (DP质因数分解)901. 滑雪 - 记忆化搜索#x1f332;day21227. 分巧克力 - 二分#x1f332;day31221. 四平方和 - 空间换时间1230. K倍区间#x1f332;day41076. 迷宫问题 - 路径2017-迷宫-填空#x1f332;day5848. 有…
文章目录前言day1最大和 (DP质因数分解)901. 滑雪 - 记忆化搜索day21227. 分巧克力 - 二分day31221. 四平方和 - 空间换时间1230. K倍区间day41076. 迷宫问题 - 路径2017-迷宫-填空day5848. 有向图的拓扑序列day6进制转换扫描线算法(二维区间合并面积和)day7蓝桥杯C/CB组历届真题-精选填空专项前言 重难点突破,重在场景应用以真题带练,涉及算法标签[⚽️DP,⚽️二分,⚽️图论,⚽️前缀和,⚽️进制转换,⚽️扫描线] 在理解DFSDP的基础上进一步巩固知识点结合题目变化运用加深记忆和理解 ⏳最后三个星期大家一起冲刺祝大家rp 如果对您有帮助的话还请动动小手 点赞收藏⭐️关注❤️ day1
最大和 (DP质因数分解)
问题描述 小蓝在玩一个寻宝游戏, 游戏在一条笔直的道路上进行, 道路被分成了 n 个方格, 依次编号 1 至 n, 每个方格上都有一个宝物, 宝物的分值是一个整数 (包括正数、负数和零), 当进入一个方格时即获得方格中宝物的分值。小蓝可 以获得的总分值是他从方格中获得的分值之和。
小蓝开始时站在方格 1 上并获得了方格 1 上宝物的分值, 他要经过若干步 到达方格n。
当小蓝站在方格 p 上时, 他可以选择跳到 p1 到 pD(n-p) 这些方格 中的一个, 其中 D(1)1, D(x)(x1)D(1)1定义为 x 的最小质因数。
给定每个方格中宝物的分值, 请问小蓝能获得的最大总分值是多少。
输入格式 输入的第一行包含一个正整数 n。
第二行包含 n 个整数, 依次表示每个方格中宝物的分值。
输出格式 输出一行包含一个整数, 表示答案。
样例输入
51 -2 -1 3 5样例输出
8样例输出 最优的跳跃方案为: 1→3→4→5。1 \rightarrow 3 \rightarrow 4 \rightarrow 5 。1→3→4→5。
评测用例规模与约定 对于 40 %40 的评测用例, 1≤n≤100。1 \leq n \leq 100 。1≤n≤100。
对于 80 %80 的评测用例, 1≤n≤1000。1 \leq n \leq 1000 。1≤n≤1000。
对于所有评测用例, 1≤n≤100001 \leq n \leq 100001≤n≤10000, 每个宝物的分值为绝对值不超过 10510^5105 的整数。
#include bits/stdc.h
using namespace std;
typedef long long LL;int n;
long long dp[10005];
long long w[10005];bool is_prime(int x)
{if(x 2) return false;for (int i 2; i x / i; i )if (x % i 0)return false;return true;
}int get(int x) //x的最小质因数
{for(int i 2; i x / i; i)if(x % i 0 is_prime(i)) return i;if(x 1) return x;
}int main()
{cin n;for (int i 1; i n; i)//输入结点权值{scanf(%lld, w[i]); dp[i] INT_MIN;}dp[1] w[1]; for (int i 1; i n; i) //选择任意起点{int len i get(n - i);for (int j i 1; j len; j) //[p1, p (n-p的最小质因数)]遍历所有下一步跳跃转移 - dp[]_max_value{dp[j] max(dp[j], dp[i] w[j]);}}cout dp[n];return 0;
}901. 滑雪 - 记忆化搜索
给定一个 R 行 C 列的矩阵表示一个矩形网格滑雪场。
矩阵中第 i 行第 j 列的点表示滑雪场的第 i 行第 j 列区域的高度。
一个人从滑雪场中的某个区域内出发每次可以向上下左右任意一个方向滑动一个单位距离。
当然一个人能够滑动到某相邻区域的前提是该区域的高度低于自己目前所在区域的高度。
下面给出一个矩阵作为例子 1 2 3 4 516 17 18 19 615 24 25 20 714 23 22 21 813 12 11 10 9在给定矩阵中一条可行的滑行轨迹为 24−17−2−1。
在给定矩阵中最长的滑行轨迹为 25−24−23−…−3−2−1沿途共经过 25 个区域。
现在给定你一个二维矩阵表示滑雪场各区域的高度请你找出在该滑雪场中能够完成的最长滑雪轨迹并输出其长度(可经过最大区域数)。
输入格式 第一行包含两个整数 R 和 C。 接下来 R 行每行包含 C 个整数表示完整的二维矩阵。
输出格式 输出一个整数表示可完成的最长滑雪长度。
数据范围 1≤R,C≤300, 0≤矩阵中整数≤10000 输入样例
5 5
1 2 3 4 5
16 17 18 19 6
15 24 25 20 7
14 23 22 21 8
13 12 11 10 9输出样例
25#include cstring
#include iostream
#include algorithmusing namespace std;const int N 310;int n, m;
int g[N][N];
int f[N][N];int dx[] {-1, 0 , 1, 0}, dy[] {0, 1, 0, -1};int dp(int x, int y)
{int v f[x][y];if(v ! -1) return v;v 1;for(int i 0; i 4; i){int a x dx[i], b y dy[i];if(a 1 a n b 1 b m g[a][b] g[x][y])v max(v, dp(a, b) 1); }return v;
}int main()
{scanf(%d%d, n, m);for (int i 1; i n; i ) for (int j 1; j m; j )scanf(%d, g[i][j]);memset(f, -1, sizeof f);int res 0;for(int i 1; i n; i)for(int j 1; j m; j)res max(res, dp(i, j));printf(%d\n, res);return 0;
}day2
1227. 分巧克力 - 二分
儿童节那天有 K 位小朋友到小明家做客。
小明拿出了珍藏的巧克力招待小朋友们。
小明一共有 N 块巧克力其中第 i 块是 Hi×Wi 的方格组成的长方形。
为了公平起见小明需要从这 N 块巧克力中切出 K 块巧克力分给小朋友们。
切出的巧克力需要满足 形状是正方形边长是整数大小相同 例如一块 6×5 的巧克力可以切出 6 块 2×2 的巧克力或者 2 块 3×3 的巧克力。
当然小朋友们都希望得到的巧克力尽可能大你能帮小明计算出最大的边长是多少么
输入格式 第一行包含两个整数 N 和 K
以下 N 行每行包含两个整数 Hi 和 Wi。
输入保证每位小朋友至少能获得一块 1×1 的巧克力。
输出格式 输出切出的正方形巧克力最大可能的边长。
数据范围 1≤N,K≤10510^5105 , 1≤Hi,Wi≤10510^5105 输入样例
2 10
6 5
5 6输出样例
2首先判断单调性【随着选取切除的边长越大切出的块数越少单调递减可以二分】 边长x, 切出的块数res(需满足res k) 边长为x最多切的块数为: ⌊wx⌋∗⌊hx⌋\lfloor \frac{w}{x} \rfloor * \lfloor \frac{h}{x} \rfloor⌊xw⌋∗⌊xh⌋ (向下取整) #include bits/stdc.husing namespace std;const int N 100010;int n, k;
int h[N], w[N];bool check(int mid) //判断边长mid能否切k块
{int res 0;//边长为mid时能切的块数resfor (int i 0; i n; i )//共n块巧克力来切{res (h[i] / mid) * (w[i] / mid);// (向下取整) (长 / 划分的边长mid) * (宽 / 划分的边长mid) [小学划分easy]if (res k) return true;//能切k块}return false;
}int main()
{scanf(%d%d, n, k);for (int i 0; i n; i ) scanf(%d%d, h[i], w[i]);int l 1, r 1e5;//边长至少1 * 1 ,左边界L从1开始, 且右边界R不超过W或H (长宽) while (l r){int mid l r 1 1;if (check(mid)) l mid;//边长为mid能切k块,往更大的尝试,找最大else r mid - 1;//mid不满足,则在试试[1,mid - 1] 找满足的}printf(%d\n, r);return 0;
}day3
1221. 四平方和 - 空间换时间
四平方和定理又称为拉格朗日定理
每个正整数都可以表示为至多 4 个正整数的平方和。
如果把 0 包括进去就正好可以表示为 4 个数的平方和。
比如
50202122250^20^21^22^2502021222
71212122271^21^21^22^2712121222
对于一个给定的正整数可能存在多种平方和的表示法。
要求你对 4 个数排序 0≤a≤b≤c≤d 并对所有的可能表示法按 a,b,c,d 为联合主键升序排列最后输出第一个表示法。
输入格式 输入一个正整数 N。
输出格式 输出4个非负整数按从小到大排序中间用空格分开。
数据范围 0N5×1060N5\times10^60N5×106 输入样例 5 输出样例 0 0 1 2 算法思想: 先枚举c2d2c^2 d^2c2d2的所有值存入数组, 令sum n - c2d2c^2 d^2c2d2, 枚举a2b2a^2 b^2a2b2过程中判断是否出现在标记数组中 【是否C[sum](或D[sum])被标记】, 输出ans{a, b, C[sum], D[sum]}; #include iostream
#include cstring
#include algorithmusing namespace std;const int N 5e6 10;int n;int C[N], D[N]; //存c与d的平方和为下标sum, c C[sum],d D[sum] int main()
{cin n;memset(C, -1, sizeof C); //初始标记for (int c 0; c * c n; c ) // 存一对for (int d c; c * c d * d n; d ){int sum c * c d * d;if (C[sum] -1) //存第一次出现的-满足最小C[sum] c, D[sum] d; //hash表sum,对应组成c , sum,对应组成d}for (int a 0; a * a n; a )for (int b a; a * a b * b n; b ){int sum n - a * a - b * b; //剩余差值if (C[sum] ! -1){ //查找存放值中是否存在剩余差值printf(%d %d %d %d\n, a, b, C[sum], D[sum]);return 0;}}return 0;
}#includebits/stdc.husing namespace std;const int N2500010;int n;int main()
{cin n;for(int a 0; a * a n; a){for(int b a; a * a b * b n; b){for(int c b; c * c b * b a * a n; c){int t n - a * a - b * b - c * c;int d sqrt(t);if(d * d t){printf(%d %d %d %d, a, b, c, d);return 0;}}}}
}1230. K倍区间
给定一个长度为 N 的数列A1,A2,…AN如果其中一段连续的子序列 Ai,Ai1,…Aj 之和是 K 的倍数我们就称这个区间 [i,j] 是 K 倍区间。
你能求出数列中总共有多少个 K 倍区间吗
输入格式 第一行包含两个整数 N 和 K。
以下 N 行每行包含一个整数 Ai。
输出格式 输出一个整数代表 K 倍区间的数目。
数据范围 1≤N,K≤100000, 1≤Ai≤100000 输入样例 5 2 1 2 3 4 5 输出样例 6 前缀和优化 区间差值k倍数(常用等效法) 余数组合: 题意以i为右端点的区间, (s[i] - s[i - 1] ~ s[i] - s[0] ) 有多少个区间值 % k 0 k倍区间转化成s[i] - s[j] % k 0 s[j] % k s[i] % k 余数是否相等【相等说明这一段的数的和是k的倍数】 #include cstdio
#include cstring
#include iostream
#include algorithmusing namespace std;typedef long long LL;const int N 100010;int n, k;//从n个数中找区间为k的倍数
LL s[N], cnt[N];//cnt[x]:动态统计余数为x的数量int main()
{scanf(%d%d, n, k);for (int i 1; i n; i )//构造前缀和{scanf(%lld, s[i]);s[i] s[i - 1];}LL res 0;cnt[0] 1;//一个都不选,则余数为0,初始有1个 for (int i 1; i n; i ){ res cnt[s[i] % k]; //当前余数 与之前[0,i-1]段中相同余数的可组合构成一段k倍数的区间cnt[s[i] % k] ;//当前余数的数量 }printf(%lld\n, res);return 0;
}先全部统计 - 相同余数的做左右端点可组合成k倍区间组合数Cn2C_n^2Cn2
#include iostream
#include cstring
#include algorithmusing namespace std;typedef long long LL;const int N 1e5 10;LL s[N], cnt[N];int n, k;int main()
{scanf(%d%d, n, k);for (int i 1; i n; i )//构造前缀和{scanf(%lld, s[i]);s[i] s[i - 1];}cnt[0] 1; //若不令cnt[0]1, 则统计完res cnt[0] 余数0可以仅选一个点构成s[i] - s[1]段k倍区间for (int i 1; i n; i ) cnt[s[i] % k] ; //统计余数LL res 0;for (int i 0; i k; i ) //枚举余数res (LL) cnt[i] * (cnt[i] - 1) / 2; //组合数printf(%lld\n, res);return 0;
}day4
1076. 迷宫问题 - 路径
2017-迷宫-填空
题目描述 本题为填空题只需要算出结果后在代码中使用输出语句将所填结果输出即可。
下图给出了一个迷宫的平面图其中标记为 11 的为障碍标记为 00 的为可以通行的地方。
010000
000100
001001
110000迷宫的入口为左上角出口为右下角在迷宫中只能从一个位置走到这 个它的上、下、左、右四个方向之一。
对于上面的迷宫从入口开始可以按 DRRURRDDDR 的顺序通过迷宫 一共 1010 步。其中 D、U、L、RD、U、L、R 分别表示向下、向上、向左、向右走。 对于下面这个更复杂的迷宫3030 行 5050 列请找出一种通过迷宫的方式其使用的步数最少在步数最少的前提下请找出字典序最小的一个作为答案。
请注意在字典序中 DLRUDLRU。
01010101001011001001010110010110100100001000101010
00001000100000101010010000100000001001100110100101
01111011010010001000001101001011100011000000010000
01000000001010100011010000101000001010101011001011
00011111000000101000010010100010100000101100000000
11001000110101000010101100011010011010101011110111
00011011010101001001001010000001000101001110000000
10100000101000100110101010111110011000010000111010
00111000001010100001100010000001000101001100001001
11000110100001110010001001010101010101010001101000
00010000100100000101001010101110100010101010000101
11100100101001001000010000010101010100100100010100
00000010000000101011001111010001100000101010100011
10101010011100001000011000010110011110110100001000
10101010100001101010100101000010100000111011101001
10000000101100010000101100101101001011100000000100
10101001000000010100100001000100000100011110101001
00101001010101101001010100011010101101110000110101
11001010000100001100000010100101000001000111000010
00001000110000110101101000000100101001001000011101
10100101000101000000001110110010110101101010100001
00101000010000110101010000100010001001000100010101
10100001000110010001000010101001010101011111010010
00000100101000000110010100101001000001000000000010
11010000001001110111001001000011101001011011101000
00000110100010001000100000001000011101000000110011
10101000101000100010001111100010101001010000001000
10000010100101001010110000000100101010001011101000
00111100001000010000000110111000000001000000001011
10000001100111010111010001000110111010101101111000#include iostream
#include cstring
#include algorithm
#include queue#define x first
#define y secondusing namespace std;typedef pairint, int PII;const int N 55;int dx[] {-1, 0, 1, 0}, dy[] {0, 1, 0, -1};int n 30, m 50;
char g[N][N];
int dist[N][N];
PII pre[N][N];
char c[N][N]; //存字符char get(int k) //转换成方向字符
{if (k 0)return D;if (k 1)return L;if (k 2)return R;return U;
}void bfs()
{queuePII q;q.push({0, 0});g[0][0] 1;while (q.size()){auto t q.front();q.pop();for (int i 0; i 4; i ){int tx t.x dx[i], ty t.y dy[i];if (tx 0 || ty 0 || tx n || ty m || g[tx][ty] 1) continue;dist[tx][ty] dist[t.x][t.y] 1;g[tx][ty] 1;pre[tx][ty] t; //存从[t.x][t.y]走到的下一步{a, b}的路径q.push({tx, ty});c[tx][ty] get(i); //}}
}int main()
{for (int i 0; i n; i )cin g[i];bfs();PII t {n - 1, m - 1};string res;while (t.x ! 0 || t.y ! 0) //逆回到起点{res c[t.x][t.y]; //从终点-起点t pre[t.x][t.y];}reverse(res.begin(), res.end()); //起点-终点cout res endl;return 0;
}答案
DDDDRRURRRRRRDRRRRDDDLDDRDDDDDDDDDDDDRDDRRRURRUURRDDDDRDRRRRRRDRRURRDDDRRRRUURUUUUUUULULLUUUURRRRUULLLUUUULLUUULUURRURRURURRRDDRRRRRDDRRDDLLLDDRRDDRDDLDDDLLDDLLLDLDDDLDDRRRRRRRRRDDDDDDRRday5
848. 有向图的拓扑序列
给定一个 n 个点 m 条边的有向图点的编号是 1 到 n图中可能存在重边和自环。
请输出任意一个该有向图的拓扑序列如果拓扑序列不存在则输出 −1。
若一个由图中所有点构成的序列 A 满足对于图中的每条边 (x,y)x 在 A 中都出现在 y 之前则称 A 是该图的一个拓扑序列。
输入格式 第一行包含两个整数 n 和 m。
接下来 m 行每行包含两个整数 x 和 y表示存在一条从点 x 到点 y 的有向边 (x,y)。
输出格式 共一行如果存在拓扑序列则输出任意一个合法的拓扑序列即可。
否则输出 −1。
数据范围 1≤n,m≤10510^5105 输入样例 3 3 1 2 2 3 1 3 输出样例 1 2 3
图中点之间的最短距离 - BFS 邻接表知识总结 具体含义理解 h[a] : 存点a邻接边(可能多个idx,头结点存放最后一次添加到a的边 ) e[idx] : 存第idx条边的终点(从h[a]遍历取的边即为 a - e[idx] ) ne[idx]: 此边的起点h[] (头插法中第idx条边 ne[idx] - e[idx]); idx : 边的编号 w[idx]: 存第idx条边的边权 add(a, b, c) : 头插法第idx条边a-b边权为c #includecstdio
#includecstringusing namespace std;const int N 1e5 10;int n, m;
int h[N], e[N], ne[N], idx; //【注意邻接表初始化h[]头结点数组 -1 表示null】
int q[N], d[N];void add(int a, int b) //a - b【h[a]头插入点b】
{e[idx] b, ne[idx] h[a], h[a] idx;
}int bfs()
{int hh 0, tt -1;q[ tt] 1; //从第1个结点出发[第一个结点入队]memset(d, -1, sizeof d);d[1] 0;while(hh tt) {auto t q[hh ]; //取队头 出队for(int i h[t]; i ! -1; i ne[i]) //h[t]开头的链表遍历 { int j e[i]; //【判断当前点下标i对应边的另一端点是否走过能否从i idx走到另一端点(下标e[i])】if(d[j] -1) //未访问过 (不能用~d[j] 【如d[j] 1但是取反! 0即访问过也会遍历-SF段错误】){d[j] d[t] 1;//统计步数q[ tt] j; //入队}}}return d[n]; //返回到第n个节点的步数
}int main()
{scanf(%d%d, n, m);memset(h, -1, sizeof h); //注意初始化头结点 -1 表示nullfor(int i 0; i m; i){int a, b;scanf(%d%d, a, b);add(a, b);}printf(%d\n, bfs());return 0;
}day6
进制转换扫描线算法(二维区间合并面积和)
day7
蓝桥杯C/CB组历届真题-精选填空专项
