做视频投稿赚钱的网站,设计电子商务网站主页,34线城市做网站推广,怎么用dw做网站报名明年4月蓝桥杯软件赛的同学们#xff0c;如果你是大一零基础#xff0c;目前懵懂中#xff0c;不知该怎么办#xff0c;可以看看本博客系列#xff1a;备赛20周合集 20周的完整安排请点击#xff1a;20周计划 每周发1个博客#xff0c;共20周#xff08;读者可以按…报名明年4月蓝桥杯软件赛的同学们如果你是大一零基础目前懵懂中不知该怎么办可以看看本博客系列备赛20周合集 20周的完整安排请点击20周计划 每周发1个博客共20周读者可以按自己的进度选“正常”和“快进”两种计划。 每周3次集中答疑周三、周五、周日晚上在QQ群上答疑 文章目录 0. 上周答疑1. 精讲题1.1 修剪灌木1.2 英文数字计数1.3 矩形拼接1.4 最少砝码 1.5 蜂巢1.6 立方体表面距离 2. 刷题 第 4周: 杂题-2
0. 上周答疑 伪代码怎么转化Java语言 C/C、Java、Python代码怎么互转 回答用大数据模型转例如文心一言3.5是免费的。 在转换代码这件事上大数据模型做得很好。
1. 精讲题 本周还是杂题 大家是不是感到太慢了什么时候才学数据结构、算法呢我想立刻现在马上学二分、排序、二叉树、DFS、… 不要着急杂题做得越多后面的学习越高效越快 一是提高编码能力争取做到一次写20行代码不用调试一次过 二是算法能力杂题虽然没用到经典算法但它们的解题步骤其实也是算法有时难度不亚于经典算法。 下面给出6个精讲题有模拟、构造、思维、数学等各种杂题难度从简单到难。大家自己先做然后再看题解。
1.1 修剪灌木
难度 ** 2022年第十三届省赛链接1-蓝桥OJ 、链接2-NewOj 【题解】这是一道思维题。由于每棵灌木都会在2N天内被剪为0所以不会无限长高。其中的第i棵它左边有i-1棵右边有n-i棵。爱丽丝分别从左右绕回来各需要2i和2(n-i-1)天取最大值就是高度。i从0开始。 1C/C代码
#includebits/stdc.h
using namespace std;
int main() {int n; cin n;for (int i 0; i n; i) cout max(i, n - i - 1) * 2 endl;return 0;
}2python代码
n int(input())
for i in range (n): print(max(i,n-i-1)*2)3java代码
import java.util.*;public class Main {public static void main(String[] args) {Scanner scanner new Scanner(System.in);int n scanner.nextInt();for (int i 0; i n; i) {System.out.println(Math.max(i, n - i - 1) * 2);}}
}1.2 英文数字计数
见博客英文数字计数 难度 ***
1.3 矩形拼接
2022年第十三届省赛: 链接-NewOJ 难度 *** 准确地说难度有3.5颗星 【题解】本题是一道纯粹的构造题思维简单但是代码比较繁琐细致目的是考核编码能力。 3个矩形摆在一起可能有几个边读者可以在纸上手画观察如果3个矩形完全不能匹配是8边形如果能完全匹配成一个新矩形是4边形其他情况是6边形。 本题只有3个矩形并不复杂。3个矩形做任意组合每个矩形有横竖两种摆法共48种情况。T 1000组测试总计算量是1000×48计算量很小不会超时所以简单地用暴力法组合出所有情况取最小值即可。 1C/C代码 下面的C代码第10 ~ 14行对3个矩形进行组合。第15 ~ 17行每个矩形有横和竖两种摆法。 第18行如果一个矩形的边长等于另外两个矩形边长之和那么至少是6个边。然后第20行如果这两个矩形边长相等那么就是4个边。后面几行请自己分析。
#includebits/stdc.h
using namespace std;
int a[3][2];
int main(){int T; cin T;while(T--) {for(int i 0; i 3; i)cin a[i][0] a[i][1];int ans 8;for(int i 0; i 3; i) //第1个矩形for(int j 0; j 3; j)if(i ! j) //第2个矩形for(int k 0; k 3; k)if(k ! i k ! j) //第3个矩形for(int ii 0; ii 1; ii){ //第1个有横竖两种摆法for(int jj 0; jj 1; jj){ //第2个横竖摆for(int kk 0; kk 1; kk){ //第3个横竖摆if(a[i][ii] a[j][jj] a[k][kk]){ ans min(ans, 6);if(a[j][1-jj] a[k][1-kk])ans min(ans, 4);}if(a[i][ii] a[j][jj] || a[j][jj] a[k][kk])ans min(ans, 6);if(a[i][ii] a[j][jj] a[j][jj] a[k][kk])ans min(ans, 4);}}}coutansendl;}return 0;
}2python代码
def check1(x1,x2,x3):if x1x2 and x1x3:if x1x2x3 and a[2]a[3]-x2a[4]a[5]-x3: return Trueif x2x1 and x2x3:if x2x1x3 and a[0]a[1]-x1a[4]a[5]-x3: return Trueif x3x1 and x3x2:if x3x1x2 and a[0]a[1]-x1a[2]a[3]-x2: return Truereturn False
def check2(x1,x2,x3):if x1x2 and x1x3:if x1x2x3: return Trueif x2x1 and x2x3:if x2x1x3: return Trueif x3x1 and x3x2:if x3x1x2: return Truereturn FalseT int(input())
for t in range(T):alist(map(int,input().split()))ans8for i in range(0,2): #第1个矩形for j in range(2,4): #第2个矩形for k in range(4,6): #第3个矩形x1,x2,x3 a[i],a[j],a[k]if x1x2 and x2x3: ans min(ans,4)if check1(x1,x2,x3): ans min(ans,4)if x1x2 or x1x3 or x2x3: ans min(ans,6)if check2(x1,x2,x3): ans min(ans,6)print(ans)3java代码
import java.util.*;
import java.io.*;
public class Main { public static void main(String[] args) {Scanner in new Scanner(System.in);int T in.nextInt();for(int _t 1; _t T; _t){int[][] a new int[3][2];int ans 8;for(int i 0; i 3; i) {a[i][0] in.nextInt();a[i][1] in.nextInt();}//枚举第一个矩形下标为i第二个矩形下标为j第三个矩形下标为kfor(int i 0; i 3; i)for(int j 0; j 3; j)if(i ! j)for(int k 0; k 3; k)if(i ! k j ! k)//枚举三个矩形的两条边for(int ii 0; ii 1; ii)for(int jj 0; jj 1; jj)for(int kk 0; kk 1; kk) {if(a[i][ii] a[j][jj])//6条边的情况1ans Math.min(ans, 6);if(a[i][ii] a[j][jj] a[i][ii] a[k][kk])//4条边的情况1ans Math.min(ans, 4);//枚举仅考虑a[i][ii] 与 a[j][jj] a[k][kk]的关系if(a[i][ii] a[j][jj] a[k][kk]) {ans Math.min(ans, 6); //6条边的情况2if(a[j][1 - jj] a[k][1 - kk]) //4条边的情况2ans Math.min(ans, 4);}}System.out.println(ans);}}
}1.4 最少砝码
2021年第十二届蓝桥杯省赛: 链接1-蓝桥OJ 难度 *** 【题解】这是一道找规律题。 题目要求给出最少数量的几个整数砝码通过加减组合得到1 ~ N的整数。熟悉二进制的都知道用1、2、4、8、16、…这些2的倍数可以组合后相加得到任意整数。不过本题的砝码不仅可以相加还可以放在天平的两边通过减法得到新的称重。例如N 3时砝码可以是{1, 2}也可以是{1, 3}、{2, 3}。 本题的思维有一点难度读者如果自己提前做了此题思维过程可能比较繁琐。下面给出一种简洁的推理方法。 设当前砝码称重范围是1 ~ R。加一个砝码w并且要求不重复加w前已经能得到的称重那么w将是一个很大的砝码。新的称重范围是 {1, 2, …, R, w-R, w-R1,…, w, w1, w2, …, wR} 因为从R到w-R是连续的所以有w-R R1即w 2R1。也就是说如果当前称重范围是1 ~ R那么加一个w 2R1的砝码可以扩展到新的称重范围R’ wR 3R1。 下面列表计算每一行的“原砝码原称重范围”是上一行的“新砝码新称重范围”。 这个表格给出了一种最少砝码的实现方式虽然可能有其他实现方式但这种实现方式最大程度扩展了新的R’是一种最优方案。 根据这个表格可以得到计算方法1砝码按3的倍数增长2每加一个砝码称重范围增长到R’ 3R1。 R按3倍增长这比二进制的倍增还快当N 1 0 9 10^9 109时计算量 l o g 3 N log_3N log3N l o g 2 N log_2N log2N 30。
1C/C代码
#include stdio.h
int main() {int N;scanf(%d, N);int R 1;int cnt 1;while (R N) {R R * 3 1;cnt;}printf(%d, cnt);return 0;
}2python代码
N int(input())
R 1
cnt 1
while R N:R R*3 1cnt 1
print(cnt)3java代码
import java.util.*;
public class Main {public static void main(String[] args) {Scanner scanner new Scanner(System.in);int N scanner.nextInt();int R 1;int cnt 1;while (R N) {R R * 3 1;cnt;}System.out.println(cnt);}
}1.5 蜂巢
2022年第十三届省赛: [链接1-蓝桥OJ] 难度 **** 【题解】本题是一道构造题考点有两个坐标转换、距离计算。 蜂巢有6个方向看起来比较复杂但实际上走步非常简单例如样例中从B走到CC在B的右下方B只要一直向右向下走且不超过C的行和列不管怎么走一定能以最小步数走到C。 本题的难点是对坐标的处理。如果是简单的直角坐标系很容易计算。本题是六角形的蜂巢每个蜂巢的中心点是否能转为直角坐标把蜂巢的关系用下面的直角坐标表示 中心点O对应的6个蜂巢的坐标分别为(-2, 0)、(-1, 1)、(1, 1)、(2, 0)、(1, -1)、(-1, -1)下面代码中用xdir[]、ydir[]表示。 先计算得到起点坐标(x1, y1)、终点坐标(x2, y2)。如何计算起点到终点的步数由于蜂巢的坐标比较奇怪不能直接用“曼哈顿距离[ 曼哈顿距离又称为出租车距离两点的距离等于x方向上的距离加上y方向上的距离即|x1-x2| |y1-y2|。]”计算。读者如果已经做了这一题可能是用各种复杂的判断来计算的。下面给出一个简单巧妙的方法。 坐标之差的绝对值dx |x1-x2|dy |y1-y2|有以下结论 1、若dx ≥ dy那么最少步数是(dxdy)/2即先横着走再斜着走 2、若dx dy一直斜着走就行最少步数是dy。
1C/C代码 代码中有一个地方需要注意即坐标值应该用long long如果用int会溢出。
#includebits/stdc.h
using namespace std;
typedef long long ll;
ll xdir[] {-2,-1,1,2, 1,-1}; //横向
ll ydir[] { 0, 1,1,0,-1,-1}; //纵向
void walk(ll d, ll q, ll x, ll y){x xdir[d] * q;y ydir[d] * q; //引用传参返回坐标值(x,y)
}
int main(){ll d1,p1,q1,d2,p2,q2;cind1p1q1d2p2q2;ll x1 0, y1 0; //计算起点坐标(x1, y1)walk(d1,p1,x1,y1); //先走第1个方向walk((d1 2) % 6,q1,x1,y1); //再走第2个方向ll x2 0, y2 0; //计算终点坐标(x2, y2)walk(d2,p2,x2,y2);walk((d2 2) % 6,q2,x2,y2);ll dx abs(x1 - x2), dy abs(y1 - y2);if (dx dy) cout (dxdy)/2; //先横走再斜着走else cout dy; //一直斜着走就行了
}2python代码
xdir [-2,-1,1,2, 1,-1]
ydir [ 0, 1,1,0,-1,-1]
def walk(d, q,x,y): x xdir[d]*qy ydir[d]*qreturn x,y
d1,p1,q1,d2,p2,q2 map(int,input().split())
x1, y1 walk(d1,p1,0,0)
x1, y1 walk((d1 2) % 6, q1,x1,y1)
x2, y2 walk(d2,p2,0,0)
x2, y2 walk((d2 2) % 6, q2,x2,y2)
dx,dy abs(x1 - x2), abs(y1 - y2);
if (dx dy): print((dxdy)//2) #先横走再斜着走
else: print(dy) #一直斜着走 3java代码
import java.util.*;
public class Main {static long[] xdir {-2, -1, 1, 2, 1, -1}; //横向static long[] ydir {0, 1, 1, 0, -1, -1}; //纵向static void walk(int d, long q, long[] pos) {pos[0] xdir[d] * q;pos[1] ydir[d] * q;}public static void main(String[] args) {Scanner scanner new Scanner(System.in);int d1 scanner.nextInt();long p1 scanner.nextLong();long q1 scanner.nextLong();int d2 scanner.nextInt();long p2 scanner.nextLong();long q2 scanner.nextLong();long[] pos1 {0, 0};walk(d1, p1, pos1);walk((d1 2) % 6, q1, pos1);long[] pos2 {0, 0};walk(d2, p2, pos2);walk((d2 2) % 6, q2, pos2);long dx Math.abs(pos1[0] - pos2[0]);long dy Math.abs(pos1[1] - pos2[1]);if (dx dy) System.out.println((dx dy) / 2);else System.out.println(dy); }
}1.6 立方体表面距离
见博客立方体表面距离 难度 *****
2. 刷题 还是继续刷题吧。上周的题目链接大家接着做 蓝桥题库的模拟题-简单 蓝桥题库的模拟题-中等 蓝桥题库的模拟题-困难 蓝桥题库的枚举题-简单 蓝桥题库的枚举题-中等 蓝桥题库的枚举题-困难 蓝桥题库的递归题
