青少年编程知识记录

2021年02月06日

1.幂幂（power）是指乘方运算的结果。n^m指该式意义为m个n相乘。把n^m看作乘方的结果，叫做n的m次幂，也叫n的m次方。2.幂的数学表示和规则2^3 * 2^4 = 2^73^4 * 3^4 = 3^83.分治法求快速幂在平常中我们如果遇到求 a^b的时候，可能是一个一个挨个乘起来，也就是将a乘b次，如果b的值非常大时，在算法竞赛中又有时间限制，累次乘几乎是不行的。（不要说这个时候用pow()

2021年01月28日

【二分】----基础用法

0.二分法简介二分法是一种查找算法要求：数据必须是有序序列核心思想：掐头去尾取中间1. 引入对于一个有序数组，如{1，3，6，8，23，56，78，99}，如果我们要查找其中的一个数78的下标位置，按照以前的写法，可能会这么写123456789101112131415161718#include<cstdio>#include<iostream>using namespace std;int main(){ int a[]={

2021年01月28日

【贪心】----排队打水

一、基础版排队打水【题目描述】学校里有一个水房，水房里一共装有m 个龙头可供同学们打开水，每个龙头每秒钟的供水量相等，均为1。现在有n 名同学准备接水，他们的初始接水顺序已经确定。将这些同学按接水顺序从1到n 编号，i号同学的接水量为wi。接水开始时，1到m 号同学各占一个水龙头，并同时打开水龙头接水。当其中某名同学j完成其接水量要求wj后，下一名排队等候接水的同学k马上接替j 同学的位置开始接水。这个换人的过程是瞬间完成的，且没有任何水的浪费。

2021年01月28日

【贪心】----最优装载、背包、乘船问题

1.最优装载题目描述：有n个物体，第i个物体的重量为wi（wi为正整数）。选择尽量多的物体，使得总重量不超过C。【分析】由于只关心选择的物品的最大数量（而不是最大重量，最大重量需要考虑DP），所以装重的物体没有装轻的物体划算。这里只需对n个物体按重量递增排序，依次选择每个物体直到装不下为止。这是一种典型的贪心算法，它只顾眼前，却能得到最优解。例1：【题目描述】有n个物体，第i个物体的重量为wi（wi为正整数）。选择尽量多的物体，使得总重量不超过C。【输入描述】n和C以及n个整数表示的wi。【输出

2021年01月28日

【贪心】----找零钱问题

一、找零钱问题例题1：有 1 元，5元，10元，20元，100元，200元的钞票无穷多张。现在使用这些钞票支付X元，最少需要多少张钞票。X = 628最佳支付方法：3张200块的，1张20块的，1张5块的，3张1块的共需3+1+1+3 = 8张直觉告诉我们:尽可能多的使用面值较大的钞票!贪心法: 遵循某种规律，不断贪心的选取当前最优策略的算法设计方法。分析：面额为1元、5元、10元、20元、100元、200元，任意面额是比自己小的面额的倍数关系。所以当使用一张较大面额钞票时，若用较小面额钞票替

2021年01月28日

【贪心】----基本概念

一、基本概念所谓贪心算法是指，在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，它所做出的仅仅是在某种意义上的局部最优解。贪心算法没有固定的算法框架，算法设计的关键是贪心策略的选择。必须注意的是，贪心算法不是对所有问题都能得到整体最优解，选择的贪心策略必须具备无后效性（即某个状态以后的过程不会影响以前的状态，只与当前状态有关。）所以，对所采用的贪心策略一定要仔细分析其是否满足无后效性。二、基本思路(1)建立数学模型来描述问题(2)把求解的问题分成若干个子问题(3)

2021年01月28日

【DFS】搜索回溯基础

0.前言搜索与回溯是计算机解题中常用的算法，很多问题无法根据某种确定的计算法则来求解，可以利用搜索与回溯的技术求解。回溯是搜索算法中的一种控制策略。它的基本思想是：为了求得问题的解，先选择某一种可能情况向前探索，在探索过程中，一旦发现原来的选择是错误的，就退回一步重新选择，继续向前探索，如此反复进行，直至得到解或证明无解。如迷宫问题：进入迷宫后，先随意选择一个前进方向，一步步向前试探前进,如果碰到死胡同，说明前进