wweiyiのblog

Dijkstra（迪杰斯特拉）算法 晚上是个好时间去刷题，我今天就看了Dijkstra算法，名字倒挺不好读的，所以我进行了深入思考，终于把一个看起来很难的算法，实际上不太简单的算法弄懂了，先来介绍一下Dijkstra 迪杰斯特拉算法(Dijkstra)是由荷兰计算机科学家狄克斯特拉于1959 年提出的，因此又叫狄克斯特拉算法。是从一个顶点到其余各顶点的最短路径算法，解决的是有权图中最短路径问题。迪杰斯特拉算法主要特点是以起始点为中心向外层层扩展，直到扩展到终点为止。 ——来自《百度百科》 这个荷兰科学家还是比较厉害的。 我们就开始看Dijkstra了。 Dijkstra是一个基于贪心的最短路算法，不能处理权值为负的情况，是单源的最短路算法的一种 这个算法的主要过程如下： 1.建一个数组d[n]，表示从第n个节点到第1个节点的最短距离，然后初始化d[1]=1，其他的为正无穷。 2.遍历找到一个没有被覆盖的d[x]的最小的节点x，然后标记x 3.尝试x的每个出边(x,y,z)，如果d[y]>d[x]+z,就赋值d[y]=d[x]+z;（z为x到y的距离）； 4.最后重复以...

简单素数筛 今天，我看了一些数学知识，而数论是比较主要的，而素数筛是其中重要的一个，现在来介绍一下简单素数筛 首先来，普及一下素数的概念 若一个正整数无法被除了1和它本身之外的任何自然数整除，则称该数为素数，也称质数（或素数），否则称该正整数为合数。 通过介绍质数（下文统称质数）的概念，我们知道了一种判断质数的方法 通过枚举：这种方法的速度太慢了，因此我们需要更快的方法 ps：即使从1枚举到根号n也是很慢的 所以我们要引进一种好方法 就是大于二的所有数的倍数都是合数，那就好办了，我们可以从2开始（先初始化一个v[]数组的所有元素为零）2的倍数都是合数，标记v[i*j]为一,3的倍数都是合数，标记为1…… 以此类推，我们就可以得出答案了 下面有一道例题 题目描述 给定一个范围N，你需要处理M个某数字是否为质数的询问（每个数字均在范围1-N内） 输入格式 第一行包含两个正整数N、M，分别表示查询的范围和查询的个数。 接下来M行每行包含一个不小于1且不大于N的整数，即询问该数是否为质数。 输出格式 输出包含M行，每行为Yes或No，即依次为每一个询问的结果。 输入输出样例 输入 ...

【解题报告】 POJ1958 奇怪的汉诺塔 在这样热浪滚滚的暑假，外面晴空高照，在家里刷刷题不妨是最好的选择 ——来自wweiyi语录 题目链接（翻译过的）： https://www.acwing.com/problem/content/98/ 题意简述：输出四个塔的汉诺塔分别从1个盘子到12个盘子的最少步数 我们看了题之后，可以知道这道题跟三个塔的汉诺塔一样，用递归，但是我们设先移走i个盘子到第二个塔或第三个塔，然后就转化成三个塔的问题了。 但是问题在于不知道i等于多少，而且直接输出12个值要用递归也会有些慢，所以我们做一下优化，记忆化一下，我们就可以很快的输出了 设三个塔n个盘子的步数为d[n],设四个塔n个盘子的步数为f[n] 动态转移方程如下 fn=min(fn,2fi+dn−i)f_n=min(f_n,2f_i+d_{n-i}) fn​=min(fn​,2fi​+dn−i​) 其中 1≤n,i≤121\leq n,i \leq 12 1≤n,i≤12 所以我们就解决了这道题目 代码如下 123456789101112131415161718192021222324...

【解题报告】 POJ1958 奇怪的汉诺塔 在这样热浪滚滚的暑假，外面晴空高照，在家里刷刷题不妨是最好的选择 ——来自wweiyi语录 题目链接（翻译过的）： https://www.acwing.com/problem/content/98/ 题意简述：输出四个塔的汉诺塔分别从1个盘子到12个盘子的最少步数 我们看了题之后，可以知道这道题跟三个塔的汉诺塔一样，用递归，但是我们设先移走i个盘子到第二个塔或第三个塔，然后就转化成三个塔的问题了。 但是问题在于不知道i等于多少，而且直接输出12个值要用递归也会有些慢，所以我们做一下优化，记忆化一下，我们就可以很快的输出了 设三个塔n个盘子的步数为d[n],设四个塔n个盘子的步数为f[n] 动态转移方程如下 fn=min(fn,2fi+dn−i) f_n=min(f_n,2f_i+d_{n-i}) fn​=min(fn​,2fi​+dn−i​) 其中 1≤n,i≤12 1\leq n,i \leq 12 1≤n,i≤12 所以我们就解决了这道题目 代码如下 1234567891011121314151617181920212223...

【基础题目】A%B Problem 题目描述 C–语言是一种C的简化版，它仅有的三种运算符为++，–和==（没有=，+，-，*，/，%，<,>等任何其他运算符），也没有循环及goto语句，除此之外与C相同。使用C–编写一个函数int mod(int a,int b)，计算a除以b的余数。 ——来自wweiyi暑假集训 题意简述：只用++,–,==运算符和C++的其他功能来完成a%b的功能 提示：允许调用其他函数 这是一道神奇的题目，我想了大半天才想出来，甚至引来了老师的批评，接下来我说一说我的思路 这道题我们需要只用++,–,==和C++的其他功能来实现模运算，这个看起开似乎无法实现，因为不能够使用循环，因此，这道题的阴影加深了。 递归！循环的后裔！ 这里我们不能用循环，也就是我们需要使用类似循环的一个过程，递归来解决问题，递归是一种很常用的解决问题的方法，将一个大问题转换成一个子问题也许模运算就可以这样解决了。 ++，–，==三运算符！三符成虎！ 我们要解决模运算首先要解决减法运算的问题，因为a%b，就是a一直减b，减到a小于b为止，因此，我们可以先解决减法运算...

【基础题目】A%B Problem 题目描述 C–语言是一种C的简化版，它仅有的三种运算符为++，–和==（没有=，+，-，*，/，%，<,>等任何其他运算符），也没有循环及goto语句，除此之外与C相同。使用C–编写一个函数int mod(int a,int b)，计算a除以b的余数。 ——来自wweiyi暑假集训 题意简述：只用++,–,==运算符和C++的其他功能来完成a%b的功能 提示：允许调用其他函数 这是一道神奇的题目，我想了大半天才想出来，甚至引来了老师的批评，接下来我说一说我的思路 这道题我们需要只用++,–,==和C++的其他功能来实现模运算，这个看起开似乎无法实现，因为不能够使用循环，因此，这道题的阴影加深了。 递归！循环的后裔！ 这里我们不能用循环，也就是我们需要使用类似循环的一个过程，递归来解决问题，递归是一种很常用的解决问题的方法，将一个大问题转换成一个子问题也许模运算就可以这样解决了。 ++，–，==三运算符！三符成虎！ 我们要解决模运算首先要解决减法运算的问题，因为a%b，就是a一直减b，减到a小于b为止，因此，我们可以先解决减法运算...

最大公约数的故事 最大公因数，也称最大公约数、最大公因子，指两个或多个整数共有约数中最大的一个。a，b的最大公约数记为（a，b），同样的，a，b，c的最大公约数记为（a，b，c），多个整数的最大公约数也有同样的记号。——来自《百度百科》 [^]: 两个数的最大公约数a，b一般用gcd（a，b）来表示，因此，我后文也会用gcd（ ， ）来表示两个数的最大公约数 最大公约数在计算机中也很常用，而对于这种数了解最深的非欧几里得莫属了！ 欧几里得 欧几里得（英文：Euclid；希腊文：Ευκλειδης，约公元前330年—公元前275年），古希腊人，数学家，被称为“几何之父”。他最著名的著作《几何原本》是欧洲数学的基础，提出五大公设，欧几里得几何，被广泛的认为是历史上最成功的教科书。欧几里得也写了一些关于透视、圆锥曲线、球面几何学及数论的作品。——来自《百度百科》 特别是数论方面有很深的造诣，因此我们今天计算机中关于数论的东西有很可观的一部分来自欧几里得，所以我们在这里看一下最大公约数。 如何算最大公约数？ 质因数分解法 这是一个好问题，最简单的方法是用质因数分解法 例如：gcd...

汉诺塔问题（Hanoi Tower Problem） 汉诺塔问题家喻户晓，它源于一个印度的神话，内容如下： 在世界中心贝拿勒斯（在印度北部）的圣庙里，一块黄铜板上插着三根宝石针。印度教的主神梵天在创造世界的时候，在其中一根针上从下到上地穿好了由大到小的64片金片，这就是所谓的汉诺塔。不论白天黑夜，总有一个僧侣在按照下面的法则移动这些金片：一次只移动一片，不管在哪根针上，小片必须在大片上面。僧侣们预言，当所有的金片都从梵天穿好的那根针上移到另外一根针上时，世界就将在一声霹雳中消灭，而梵塔、庙宇和众生也都将同归于尽。 这个问题看起来十分可怕，实际上很简单。接下来就解决一个问题来体会这个小小问题中的大大的递归思想！ 有三根柱子，第一根柱子上有n个从下向上越来越小的圆盘。 目标：使第一根柱子上的n个圆盘按原样摆放在另一个柱子上。 注：一次移动一个圆盘，不可以出现大的盘子在小的盘子上面的情况。 解： 首先我们先玩一下这个游戏。 接着我们找出一个规律，要彻底地把这个塔移开，我们必须要移开上方的n-1个盘子，使最下面的盘子可以移动到另一个柱子上，然后在把上方的n-1个盘子移动到最下...

大家好 ##大家好 ###大家好 重要的事情说三遍，这是我的新博客，因此，我准备开始我的OIer新生涯（虽然稀里糊涂地学了两年了） 但是我感觉我还没学会，所以在这上面发布解题报告和一些简单的数学逻辑分析，好吧，我觉得我要开始了。 #你好，世界 1234567#include <iostream>using namespace std;int main(){ cout<<"Hello ,world!"<<endl; return 0;} 以此来表达我对这门信息学的热爱！ 我认为我以后会有更多的文章和高端的题解的！ Thanks all！