小毅儿 - 个人主页动态 - 牛客网

发布(153) 评论刷题收藏

2019-12-03 21:10

已编辑

山东师范大学游戏前端

埃拉托斯特尼筛法，简称埃氏筛或爱氏筛，是一种由希腊数学家埃拉托斯特尼所提出的一种简单检定素数的算法。要得到自然数n以内的全部素数，必须把不大于根号n的所有素数的倍数剔除，剩下的就是素数。 详细列出算法如下：  列出2以后的所有序列：  2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 标出序列中的第一个素数，也就是2，序列变成：  2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 将剩下序列中，划掉2的倍数，序列变成： 2 3 5 7 9 ...

0 点赞评论收藏

分享

2019-11-28 19:19

山东师范大学游戏前端

D - Patrol Robot

BFS做法：用队列。注意事项：1.设的结构体只有一个。2.标记函数在此题中是三维，第三维代表着走过了多少个1. #include <cstdio> #include <iostream> #include <queue> #include <string> #include <cstring> using namespace std; int m,n,k,ans; int a[30][30]; int b[30][30][30]; struct sss { int shu; int heng; int step; int jishu;...

0 点赞评论收藏

分享

2020-05-22 10:45

已编辑

山东师范大学游戏前端

棋盘问题（POJ - 1321）

例题链接：https://vjudge.net/contest/339651#problem/B #include <cstdio> #include <iostream> using namespace std; char a[10][10]; int biaoji[10]; int sum,num; int m,n; void DFS(int x) { if(num==n) { sum++; return ; //sum满足条件，记得返回 } if(x>m) return; for (int i=1;i<=m;i++) { if(biaoji[i]==0...

0 点赞评论收藏

分享

2019-11-25 21:02

山东师范大学游戏前端

畅通工程（并查集）

注意事项：1.用到结构体进行比较，在比较过程中for循环是以输入的道路条数为界限。2.使用并查集的时候，一定要注意m,n的使用，该用m就用m,该用n就用n。 #include <cstdio> #include <iostream> #include <cstring> #include <string> #include <algorithm> using namespace std; int m,n; int pre[105]; struct sss { int l; int r; int j; }a[10005]; bool c...

0 点赞评论收藏

分享

2020-10-02 18:58

已编辑

山东师范大学游戏前端

最短路（Floyd）

例题链接（这道题也可以用Dijkstra做）：https://vjudge.net/contest/341090#problem/A Floyd的优点：1.代码短2.可以带负值3.最后mp[i][j]存的是从i到j的最短路,并不是单源最短路 缺点：三层for循环，时间复杂度是O（n^3)，比Dijkstra的事件复杂度大挺多的。 #include <cstdio> #include <iostream> #include <cstring> #include <string> using namespace std; #define MAX 0x...

0 点赞评论收藏

分享

2019-11-25 19:03

山东师范大学游戏前端

Dijkstra算法、Floyd算法的区别与联系

首先，Dijkstra算法与Floyd算法都是广度优先搜索的算法。 都可以用来求单源点到其他所有点的最短路径。（即从一个点到任意一个点的最短距离） 1.Dijkstra是不能计算负权图的。  Dijkstra算法本质上是贪心算法，下一条路径都是由当前更短的路径派生出来的更长的路径。不存在回溯的过程。 如果权值存在负数，那么被派生出来的可能是更短的路径，这就需要过程可以回溯，之前的路径需要被更短的路径替换掉，而Dijkstra算法是不能回溯的。它每一步都是以当前最优选择为前提的。 2.Floyd算法实际上是一个动态规划算法。  所以一定能用贪心算法解的问题肯定可以由动态规划解。但是可以用动态规划...

0 点赞评论收藏

分享

2021-05-04 11:54

已编辑

山东师范大学游戏前端

Dijkstra基础用法

例题链接：https://vjudge.net/contest/341090#problem/A Dijkstra算法：缺点：图中不存在负权边 记录一下大体思路，便于复习：1.按照题目输入变量，进行初始化（标记点第一个点是false，第一个点到其它点的距离。。。）2.Dijkstra几个注意事项：（1）初始化时，范围是105。（2）找距离初始点距离最近的未标记点的时候，是dis数组与minx比较，而不是mp数组与minx进行比较。 dis[j]<minx那里（3）更换dis数组的值时，判断条件是dis[j]>dis[weizhi]+mp[weizhi][j];（4）在找到weizh...

0 点赞评论收藏

分享

2020-05-22 10:45

已编辑

山东师范大学游戏前端

POJ 1979 Red and Black

题目链接：https://vjudge.net/contest/339651#problem/A 典型的DFS题，在这里记录一下自己的习惯，复习起来会好些。 1.典型要遍历所有满足条件的点2.输入的m,n的含义一定要清楚，谁是列，谁是行（谁是shu,谁是heng)3.在习惯上一般有一个biaoji函数，用作标记走过的点（vis)4.在DFS上一般写成竖和横的形式，所以在输入时就要按照这个形式进行输入（即两者要统一）5.初始化一定要有 #include <cstdio> #include <iostream> using namespace std; int xx[10]...

0 点赞评论收藏

分享

2019-11-22 19:39

山东师范大学游戏前端

Nim游戏是博弈论中最经典的模型（之一），它又有着十分简单的规则和无比优美的结论 ，Nim游戏 是 组合游戏(Combinatorial Games)的一种，准确来说，属于“Impartial Combinatorial Games”（以下简称ICG）。 （1）条件： 满足以下条件的游戏是ICG（可能不太严谨）： 1、有两名选手； 2、两名选手交替对游戏进行移动(move)，每次一步，选手可以在（一般而言）有限的合法移动集合中任选一种进行移动； 3、对于游戏的任何一种可能的局面，合法的移动集合只取决于这个局面本身，不取决于轮到哪名选手操作、以前的任何操作、骰子的点数或者其它什么因素；  4、如...

0 点赞评论收藏

分享

2020-10-21 20:01

已编辑

山东师范大学游戏前端

vector的基本用法

使用vector索引： (1)什么是vector：向量（vector）是一个封装了动态大小数组的顺序容器（Sequence Container）。跟任意其他类型容器各种类型的对象。可以简单的认为，向量是一个能够存放任意类型的动态数组。 (2)头文件：#include <vector> (3)vector的基本用法 #include <vector> vector <int> a,b; 1.添加元素 a.assign(b.begin(),b.begin()+3) //将b的第0到2个元素添加到a a.assign(4,2) //a含有4个值为2的元素(不管原来...

0 点赞评论收藏

分享

2019-11-20 20:47

已编辑

山东师范大学游戏前端

田忌赛马（贪心法）

题目分析： 策略是充分利用每一匹马的战斗力，若己方的最好马优于对方的最好马，则使己方的最好马战胜对方的最好马；若己方的最好马劣于对方的最好马，则必定要输一次，用己方最劣的一匹马消耗对方的最好马，从而使己方的最好马可以对战对方下一个等级的马，增大赢的概率。当双方的最好马实力相当时，为了尽可能多赢，检查双方最劣马的实力，若己方最劣马强于对方，则先用己方最劣马战胜对方最劣马，保证赢一局，若己方最劣马弱于对方，则该匹马注定要输，用其消耗对方最高战斗力。若双方最劣马实力相当，仍用己方最劣马消耗对方最好马，当只看最优和最劣两组数据时，这样最坏的结果是平局，然而可以增大中间数据赢的概率（因为己方的最优马得以...

0 点赞评论收藏

分享

2020-05-22 10:45

已编辑

山东师范大学游戏前端

DFS中关于字符串的应用（SDNU 1022.成语接龙）

题目链接：http://www.acmicpc.sdnu.edu.cn/problem/show/1022 #include <cstdio> #include <iostream> #include <string> #include <cstring> #include <cmath> using namespace std; int panduan[25]; int sum; int n; string a[25]; void DFS(string b,int maxn) { sum=max(maxn,sum); for (in...

0 点赞评论收藏

分享

2019-11-19 11:32

山东师范大学游戏前端

并查集的简单应用（矩形合并）

题目链接：http://www.acmicpc.sdnu.edu.cn/problem/show/1016 #include<iostream> #include<cstdio> #include<cstring> #include<cmath> #include<algorithm> using namespace std; int pre[100]; struct sss { int lx,ly,rx,ry; }l[105]; int find (int x) { if(pre[x]==x)return x; else retur...

0 点赞评论收藏

分享

2019-11-19 11:13

已编辑

山东师范大学游戏前端

转的一个超级有意思，好懂的并查集解释， 膜拜大神~~  先写自己的总结：1.根据题目要求，初始化所需的变量。 2.设pre数组，代表自己的祖先是谁（一开始祖先都是自己）。 3.查找：设一个find函数（建议大家学习递归的用法，很好理解，并且代码很短） int find (int x) { if(pre[x]==x)return x; else return find(pre[x]); }4.路径压缩（最好也是学习递归的用法，非递归的用法实在是有点长）（在写的时候直接把第三步空过去行了，直接写第四步，当然很多题目是不需要路径压缩de） int find (int x) { if(pre[x]==...

0 点赞评论收藏

分享

2019-11-19 08:22

山东师范大学游戏前端

用结构体排序的应用

例题：https://ac.nowcoder.com/acm/contest/1838/I #include <cstdio> #include <iostream> #include <string> #include <cstring> #include <map> #include <algorithm> #include <stack> #include <queue> #include <cmath> using namespace std; struct sss { stri...

0 点赞评论收藏

分享

创作者周榜

更多

关注他的用户也关注了：

牛客网
牛客网在线编程
牛客网题解
牛客企业服务