- 博客(51)
- 问答 (2)
- 收藏
- 关注
RSS订阅原创 三星研究院（南京）机试练习（二）搜索经典题---解数独
2676 -- Sudoku题意：给定一个九行九列矩阵，让你填充矩阵里面的元素，要求：1.每一行，每一列，每个小九宫格（图片画粗的地方就是）不能包含相同元素2.每一行，每一列，每个小九宫格均会完整出现1-9的数字思路：DFS回溯填充数字，一行一行填充，当填到第十行说明填充成功，唯一难点就是判断九宫格横坐标/3*3就能获得小九宫格左上角横坐标，纵坐标/3*3就能获得小九宫格左上角纵坐标#include<iostream>#include<queue>usi
2022-05-09 01:40:00
2042
原创 三星研究院（南京）机试练习（搜索入门）
搜索小贴士：1.DFS、BFS其实是图的一种遍历方式，两种算法均可以遍历所有情况，是非常暴力的算法，但其应用场景却不太一样，由于他们两种的算法特性导致的，如下：2.问最短、最少之类的问题，一般要想到BFS，BFS搜索是逐层搜索，换个角度来说，每一层是一种状态，达到本次状态所花费的value值是一样的，由于BFS借助队列实现，而队列有先进先出的特性，所以当找到结果时，是由上一层状态继承下来的，一定是当前问题的最少花费。3.DFS一般会伴随着回溯，只需要记得DFS是一条路走到黑，走不通时返回到最近.
2022-04-30 16:29:28
3844
原创 一道题练三种算法（并查集/BFS/DFS）
1971. 寻找图中是否存在路径1.并查集将给定双向图中的连通分量看成一个集合，把所有相连节点合并为一个集合，最后直接查找start和end节点的祖宗节点，若在同一集合内则说明存在从顶点start到end的路径class Solution {public: static const int maxn=1e5; int *fa=new int[maxn*2+10]; int find(int x){ if(fa[x]==x)return x;
2022-03-23 02:16:15
290
原创 一些对刷题有用的技巧集锦（自用，持续更新中...）
String1.replace用str替换指定字符串从idx位置开始长度为len的字符replace(idx,len,str);class Solution {public: string replaceSpace(string s) { for(int i=0;i<s.length();++i){ if(s[i]==' '){ s.replace(i,1,"%20");
2022-03-15 00:48:58
1453
原创 C++：new用法入门篇
用法1： int *a=new int; *a=1; cout<<"方法一:"; cout<<*a<<endl; delete a; 加*是取指针指向的内存地址存储的元素，不加*是取指针指向的内存地址cout<<a<<" "<<(&a)<<endl; 输出：0x32de0 0x6cfeec，为什么地址不同？因为这两个指向的不是同一个地址，a是指针指向的地址，&a
2021-02-21 16:17:45
1126
原创 剑指 Offer 06. 从尾到头打印链表
剑指 Offer 06. 从尾到头打印链表1.用栈实现（基础解法）遍历单链表，将每个链表元素压入栈底，最后再依次弹出push进入vector即可/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode(int x) : val(x), next(NULL) {} * }; */class Solution {
2021-02-11 01:42:33
114
原创 剑指 Offer 54. 二叉搜索树的第k大节点
剑指 Offer 54. 二叉搜索树的第k大节点1.先序遍历+数组存储所有节点i.定义一个vector，用来存储二叉树的所有节点ii.先序遍历将所有节点值push进去（下标从0开始）iii.从大到小排列一下(调用sort，注意sort默认从小到大，如果要从大到小，必须加上greater<int>())/** * Definition for a binary tree node. * struct TreeNode { * int val; *
2021-02-08 20:20:42
71
原创 剑指 Offer 17. 打印从1到最大的n位数
剑指 Offer 17. 打印从1到最大的n位数1.pow版（傻瓜暴力版）class Solution {public: vector<int> printNumbers(int n) { vector<int>ans; for(int i=1;i<=pow(10,n)-1;++i)ans.push_back(i); return ans; }};执行用时：8 ms, 在所有 C++ 提交中击败了8
2021-02-06 02:31:59
122
原创 剑指 Offer 22. 链表中倒数第k个节点
剑指 Offer 22. 链表中倒数第k个节点1.基础解法（1）若当前链表是空链表或者只有头节点（只有一个元素），那么就直接返回（2）遍历整个链表记录链表长度（3）计算一下倒数第k个节点从左往右数是第几个（4）再遍历一遍原链表，遍历我们在第三步计算出的值就是答案举个例子：10->20->30->40->50, 和 k = 2.返回链表40->50链表内有5个元素，5-2=3，遍历一次，head=20,两次,head=30,三次，head=40/** * De
2021-02-06 02:26:07
118
原创 剑指 Offer 05. 替换空格
剑指 Offer 05. 替换空格1.利用string的insert和erase，用法在注释中已标明class Solution {public: string replaceSpace(string s) { //int len=s.length();这里有坑点 for(int i=0;i<s.length();++i){ if(s[i]==' '){ s.erase(i,1);//s.erase
2021-02-06 02:12:35
79
原创 剑指 Offer 27. 二叉树的镜像
剑指 Offer 27. 二叉树的镜像1.递归--DFS（后序遍历）思路：后序遍历，不断递归交换当前节点的左右孩子位置即可，从后往前换/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NUL
2021-02-05 01:15:04
71
原创 剑指 Offer 58 - II左旋转字符串 && 剑指 Offer 55 - I二叉树的深度
力扣剑指offer刷题博客第一篇，后续会更完所有题目，题库链接https://leetcode-cn.com/problemset/lcof/每道题力求多种解法！！！左旋转字符串1.暴力做法class Solution {public: string reverseLeftWords(string s, int n) { int len=s.length(); string ans=""; for(int i=n;i<.
2021-02-04 22:54:00
211
2
原创 字典树&&AC自动机---看完应该会...了...吧
目录字典树AC自动机字典树又称单词查找树，Trie树，是一种树形结构，是一种哈希树的变种。典型应用是用于统计，排序和保存大量的字符串（但不仅限于字符串），所以经常被搜索引擎系统用于文本词频统计。它的优点是：利用字符串的公共前缀来减少查询时间，最大限度地减少无谓的字符串比较，查询效率比哈希树高。其基本操作有：查找、插入和删除,当然删除操作比较少见。----百度词条一个插入字符...
2020-04-19 13:09:27
1158
1
原创 UVA437 巴比伦塔
题目链接：https://www.luogu.com.cn/problem/UVA437题目：有n（n≤30）种立方体，每种都有无穷多个。要求选一些立方体摞成一根尽量高的柱子（可以自行选择哪一条边作为高），使得每个立方体的底面长宽分别严格小于它下方立方体的底面长宽。intput：110 20 3026 8 105 5 571 1 12 2 23 3 34 4 45 ...
2019-12-02 17:37:52
217
原创 树状数组模板
Color the ballHDU - 1556N个气球排成一排，从左到右依次编号为1,2,3....N.每次给定2个整数a b(a <= b),lele便为骑上他的“小飞鸽"牌电动车从气球a开始到气球b依次给每个气球涂一次颜色。但是N次以后lele已经忘记了第I个气球已经涂过几次颜色了，你能帮他算出每个气球被涂过几次颜色吗？Input每个测试实例第一行为一个整数N,(N...
2019-11-22 22:03:03
129
原创 逆拓扑排序 Reward HDU - 2647
RewardHDU - 2647题意：每个人的起始金额是888，有些人觉得自己做的比另一个人好所以应该多得一些钱，问最少需要花多少钱，如果不能满足所有员工的要求，输出 -1样例1：2 11 2 输出17771认为自己的报酬应该比2多，所以2为888，1为889是最小的情况样例2：5 41 2 2 5 2 4 4 3 输出4446相当于给定一张图，n个节点...
2019-11-21 11:22:19
385
原创 校内训练 day_1 递归&&分治
题目https://vjudge.net/contest/343889A - BadgeCodeForces - 1020B题意：有n个学生，老师要抓学生，每抓到一个学生就标记这个学生1次，然后这个学生会指证另一个学生，老师就会去寻找另一个学生，直到老师找下一个学生的时候，该学生已经被标记过了为止，输出这个学生的编号。从1开始找，输出被重复标记的学生，然后从2开始找......直到...
2019-11-20 16:06:46
141
原创 Educational Codeforces Round 76 (Rated for Div. 2) 题解
http://codeforces.com/contest/1257B：给定两个数a，b通过两个操作(1)若a是偶数，则可以将它乘上3/2(1)若a大于1，则可以将a-1两个操作可进行任意次数，问a是否可以通过一系列操作转换为b思路：找规律，特判两个数字即可。。。。暴力解法：当他是偶数时才可以乘上3/2，否则只能减1，不然最终结果就不可能为整数（1）若在进行操作时会...
2019-11-14 23:31:21
127
原创 图论基础知识
连通图：任意两点之间都有路径连接的图若无向图不是连通图，但图中存储某个子图符合连通图的性质，则称该子图为连通分量。若有向图本身不是强连通图，但其包含的最大连通子图具有强连通图的性质，则称该子图为强连通分量。ps：如果无向图是连通图，则其无法分解出多个最大连通子图，因为图中所有的顶点之间都是连通的树：无环的连通图，一棵树的边数恰好是顶点数-1森林：无环的非连通图（是树的集合）...
2019-11-14 18:20:41
444
原创 C语言局部数组大小与内存的栈的关系
为什么不能在函数体内开局部整型二维数组[1000][1000]？但是在数组前面加上一个static就可以了？windows下栈的大小（不是数据结构里面的栈）是2MB，换算成字节大概是2*10^6个字节整型变量占用4个字节，那么一个1000*1000的int数组就占用4*10^6个字节，栈的空间不够大，所以这样定义数组是错误的那么为什么把它定义为静态变量就可以了呢？因为全局变量保存在内存的全局存储区中，占用静态的存储单元，所以加上static就相当于全局变量了快速计算数组所占用内存字节数：
2019-11-11 20:34:43
720
原创 Ants POJ - 1852 弹性碰撞+模拟
题目https://vjudge.net/problem/POJ-1852题意：在一个固定长度的木条上面有n只蚂蚁，每个蚂蚁的速度一样，方向任意（可由自己决定初始方向），每只蚂蚁碰头后会朝相反反向前进，问所有蚂蚁都从木条上掉下去（走到左右端点处）的最短和最长时间是多少？这篇博客讲的挺好https://www.cnblogs.com/zhenghao2/p/6446065.html思...
2019-11-09 11:57:37
184
1
原创 Codeforces Round #595 (Div. 3)
http://codeforces.com/contest/1249B：题意：数组下标表示第i天，每天都有一本书，通过数组元素所代表的下标传送，问传回当天需要多长时间例如：[2,3,1]第一个数组元素是2，表示从第一个位置传递到第二个位置，第二个数组元素是3，表示从第二个位置传递到第三个位置，第三个数组元素是1，表示从第三个位置传递到第一个位置第一本书初始在第一个位置，也就是说...
2019-10-28 16:50:03
98
原创 (DP)Ivan the Fool and the Probability Theory---------- Codeforces Round #594 (Div. 2)
https://codeforces.com/contest/1248/problem/C题意：给定一个N×M大小的方格图，现在要求将每个格子染成黑白两种颜色，要求每个格子至多和四个方向（上下左右）上的一个格子同色，问有多少种方案。感谢几位大佬的博客https://blog.csdn.net/weixin_42856843/article/details/102655689#comm...
2019-10-22 21:36:20
142
原创 POJ 1308 Is It A Tree?
A - Is It A Tree?POJ - 1308题意：输入一组有向边，判断是否能形成一棵树考察点：连通图和树的定义森林：多个树的集合本题要点： （1）判环，若已存在两点在同一个集合中，此时连接两点会形成环 （2）判联通 很坑！！！ 如果有多个集合说明不联通 特判：空树也是树（即没有...
2019-10-13 00:01:02
99
原创 带权并查集
普通并查集https://blog.csdn.net/weixin_42488861/article/details/97620959总结一下我理解的带权并查集与普通并查集的区别：普通的并查集仅仅记录的是集合的关系，这个关系无非是同属一个集合或者是不在一个集合，而带权并查集是记录集合内元素的关系，而这个关系被带上了一个权值表示集合内元素之间关系的区别，例如食物链这道题，权值为0表示和根节...
2019-10-10 22:13:29
129
原创 拓扑排序入门详解&&Educational Codeforces Round 72 (Rated for Div. 2)-----D
https://codeforces.com/contest/1217D：给定一个有向图，给图染色，使图中的环不只由一种颜色构成，输出每一条边的颜色不成环的边全部用1染色ps:最后输出需要注意，一个环上的序号必然是非全递增的，若有环且有一条边u->v,u的序号<v则输出1否则输出2(反过来也可以)可以用dfs染色或者用拓扑排序做顺便复习一下拓扑排序：...
2019-10-05 19:23:11
153
原创 CF收获到的知识点
差分数组https://blog.csdn.net/weixin_42488861/article/details/96969141set容器用法https://blog.csdn.net/weixin_42488861/article/details/102150096floyd最小环https://blog.csdn.net/weixin_42488861/article/de...
2019-10-05 15:41:28
125
原创 Codeforces Round #590 (Div. 3)
https://codeforces.com/contest/1234D：给定一个字符串操作1更改该位置上的字符，2输出区间内有几个不同的字符正常写法应该是线段树和树状数组，不过我忘了怎么写。。。用set可以做，以数字代替字母，'a'-0，'b'-1这样表示，在该字母表示的set容器插入出现该字母的所有位置set用insert插入例如：set<int>vis[30...
2019-10-05 15:40:12
108
原创 Shortest Cycle&&floyd最小环进阶
Shortest CycleCodeForces - 1206D题目大意:给定一个无向图，两点的权值做与操作为1则表示连接，找最小环1.权值为0的点直接删除，因为与任何值相与都为02.二进制每一位上至少3个点说明即可成环，权值最大为1e18,小于2^60，60个位上，120个点平均分配给每一个位，那么只要再加一个任意权值的点肯定能成环，所以当不为0的点大于120个时直接输出3,否则进...
2019-08-25 01:09:27
146
原创 floyd最小环&&模板
floyd的核心代码：for(int k=1;k<=n;k++){ for(int i=1;i<=n;i++){ for(int j=1;j<=n;j++){ dis[i][j]=min(dis[i][j],dis[i][k]+dis[k][j]); } } }通过中间节点k去松弛i到j的距离，这是floyd算...
2019-08-25 00:47:04
127
原创 并查集模板&&畅通工程
畅通工程HDU - 1232某省调查城镇交通状况，得到现有城镇道路统计表，表中列出了每条道路直接连通的城镇。省政府“畅通工程”的目标是使全省任何两个城镇间都可以实现交通（但不一定有直接的道路相连，只要互相间接通过道路可达即可）。问最少还需要建设多少条道路？Input测试输入包含若干测试用例。每个测试用例的第1行给出两个正整数，分别是城镇数目N ( < 1000 )和道路数目M...
2019-08-23 10:01:10
81
原创 二分图匹配&&最大团&&最大独立集&&完全图运用
看了大佬的博客才理解https://blog.csdn.net/flushhip/article/details/52012887https://blog.csdn.net/qq_41730082/article/details/81456611https://blog.csdn.net/weixin_43843835/article/details/88603462 -------...
2019-08-19 17:14:31
411
原创 二分图匹配&&最小顶点覆盖
上大佬博客https://blog.csdn.net/acdreamers/article/details/8621130https://blog.csdn.net/qq_41730082/article/details/81456611https://blog.csdn.net/qq_34921856/article/details/79535004https://blog.c...
2019-08-19 16:21:54
694
原创 二分图匹配&&二分图的一些基本概念
上一些大佬博客https://www.cnblogs.com/czsharecode/p/9777533.html二分图指的是可以用两个不相交的集合表示该图的节点，然后该图的每一条边的端点分别位于这两个集合中。设G=(V,E)是一个无向图，如果顶点V可分割为两个互不相交的子集(A,B)，并且图中的每条边（i，j）所关联的两个顶点i和j分别属于这两个不同的顶点集(i in A,j i...
2019-08-19 14:51:36
171
原创 记录一下每天的学习状况
学习总是一开始雄心壮志，后面发现计划总是比想象中推迟好几天，总是把时间浪费在一些没有必要的事情上面，从今天开始，立贴于此，直到进入区域赛~~~。8.17，糜烂与各种自我否定的生活结束，也是按原轨道进行的开始。8.18，学习了二分图匹配基本模板以及最小顶点覆盖的几道题目，晚上又是被cf折磨的夜晚，怎么练了一个暑假还是这么菜，枯了8.19，A了一道最大独立集问题,一堆性质记不来啊，下午写了...
2019-08-17 16:46:41
372
原创 线段树入门2---区间更新模板&&懒惰标记&&color the ball
题目链接 https://cn.vjudge.net/problem/HDU-1556对区间更新不理解的可以去看大佬的博客 https://www.cnblogs.com/TenosDoIt/p/3453089.html#g#include<iostream>#include<cstring>#include<math.h>#include<st...
2019-08-11 12:55:53
139
原创 线段树入门1---单点修改模板&&敌兵布阵
https://cn.vjudge.net/problem/HDU-1166 敌兵布阵https://www.cnblogs.com/TenosDoIt/p/3453089.html#g 线段树入门一开始对查询函数上面的一行代码感到疑惑，即为什么只要当前区间被所求区间覆盖之后就可以直接返回这个区间的值，返回的不是只有所求区间和的一部分吗。后来发现还是自己太菜了。来看个例子☟随便找了张图...
2019-08-11 11:20:17
97
原创 差分数组&&定义&&使用方法&&与线段树的区别
参考了大佬的博客 https://www.cnblogs.com/COLIN-LIGHTNING/p/8436624.htmlhttps://www.cnblogs.com/robin1998/p/6863402.html1.定义对于一个有n个元素的数组a[n]，我们令a[i]-a[i-1]=d[i],且d[1]=a[1]-0=a[1];那么我们将d[i]称为差分数组—即记录数组a每项与前一...
2019-08-11 10:38:29
652
2
原创 最小生成树----Save your cats+kruskal
https://vjudge.net/problem/Aizu-2224题意:很多猫被女巫用篱笆围了起来，给出连接每一个栅栏的两个点，问如何破坏栅栏使消耗最小(即边最小)并且解救出所有被围起来的猫直接看样例三，如箭头所示，我们只要解开这两条栅栏，就可以解放所有的猫，因为是被围起来的嘛，所以只需要开一个缺口，被围的猫不就可以被放出来了吗。那么又如何找到这些最短的边呢，我们可以通过最大生成树来...
2019-08-05 21:58:50
290
原创 Apple Catching
Apple Catching - POJ 2385 - Virtual Judge https://vjudge.net/problem/POJ-2385题意:有两棵树，每分钟树上会掉下一颗苹果，问在T分钟内，最多移动次数为W，能获得的最多苹果数量是多少，最开始在树1下面这道题目并不是来回移动得越多拿到的苹果就越多，因为移动次数是有限制的，所以需要在获利最多的情况下才能移动，而不是无脑移动代...
2019-08-04 00:44:08
214
空空如也
请问为什么BFS求迷宫最短路径的时候可以得到最优解呢？
2022-04-29
请问一下unordered_set内部是怎么排序的
2022-03-21
TA创建的收藏夹 TA关注的收藏夹
TA关注的人