- 博客(81)
- 收藏
- 关注
RSS订阅原创 谷粒商城-个人学习（1）
对于应届生来说，秋招的时候是否有合适的实习、项目、竞赛经验真的很重要。希望这篇学习总结笔记对他人会有帮助吧。对拥有相同经历的被导师卡着不能出去实习的专硕表示同情，并共勉。加油吧。谷粒商城-个人学习笔记谷粒学院的微服务分布式电商系统，免费的，B站资源一抓一大把。作为分布式和商城系统的入门项目。感谢博主的细致总结https://blog.csdn.net/hancoder/article/details/106922139分布式系统在一个分布式系统中，一组独立的计算机展现给用户的是一个统一的整
2020-11-13 22:18:08
1172
原创 牛客网——正则表达式匹配
给出匹配串，给出模式串。给出两种正则运算，一个是.（点）表示占位代表任意一个字符，一个是字符*（例如a*）代表此处可以有任意个*前面的字符。一开始想着是正着慢慢模拟，但是显然不可行，正着做显然是直接使用了前面的字符，而每次特殊判断字符后是不是*号过于复杂。第二个想着是倒着匹配，碰到*号了往新串中添加字符，然后观察时候可以构造出一个与原串相同的字符，但是也失败了，因为无法控制个数，例如abaaaa，...
2018-03-07 13:00:36
950
原创 牛客网——丑数
题目描述很简单，给一个函数，返回第n个丑数。丑数：质因数只包含2,3,5的数字，第一个丑数是1。例如2,4,6,10就是丑数，7,14就不是丑数。一开始以为是直接暴力判断就可以过，但是后来发现，越到数字越大的数就会越容易产生非丑数，因此到后面的时候丑数与丑数之间可能存在很大的间隔，因此暴力数个数方法不可取。第二反应是搜索，从第一个数1开始每次放入2,3,5的倍数慢慢扩充，但是发现扩充过程数字大小并...
2018-03-04 19:59:47
441
原创 牛客网——栈的压入、弹出序列
题目大意，给出两个序列一个代表压入序列，一个代表弹出序列，判断这是否是一个合理的弹出序列。一开始看到这个问题的时候直接想到了二叉树的先序中序，构造后续（我也不知道我的思路为什么这么清奇）。后来发现自己的思路歪了，然后简单的认为只需要判断弹出序列中，在判断某个数是否合理时，只需要判断在他之前弹出的数是否在压入序列中排在他的后面。但是后来想想又不对，顿时陷入僵局。后来查看了讨论中的代码。直接使用vec...
2018-03-02 19:01:21
316
原创 Python爬虫初步个人学习及心得
自从毕设开始搞了Python之后就觉得这个东西值得研究。但是毕设的东西非常的浅显，个人觉得最值得训练的还是Python的爬虫，谨以此开篇，作为学习和练习Python的起步。——————————学习分割线————————————第一次学习的是Python爬取图片信息。网上有很多很多关于这一类东西的教程，我也仅仅是可以实现，并且停留在一知半解的程度，在代码过程中添加了很多对Python的新的理解，对编...
2018-02-28 19:49:44
56316
2
原创 数据结构复习——二叉排序树
最近复习到二叉排序树，让自己对树的概念理解的更加清晰了。贴上自己的代码供大家参考学习用。最关键的是二叉排序树的删除操作。#includeusing namespace std;typedef struct node * tree_point;struct node{ int data; tree_point lchild, rchild;};int n, a[105]
2017-07-18 18:28:47
394
原创 树形dp回顾Anniversary party
这道题真的是已经被用烂了。一个是最大人数是多少，一个是最大的happy值是多少，都是大同小异的。从树根开始dfs做dp如果这个人是来的那么dp[root][1]先初始化，继续向下做dp。然后最后的状态方程式dp[root][0]+=max(dp[child][0],dp[child][1]);dp[root][1]+=dp[child][0];#includ
2017-04-01 18:18:56
334
原创 推箱子 HDU1254
题目大意是在说给一张图，给定人的起点和终点，以及箱子的起始位置，问最少箱子推多少格可以到达终点。感觉自己的做法稍微有点麻烦了。先是使用五维的数组pushdir[a][b][c][d][i]表示人在（a,b）位置，箱子在（c,d）位置是否能往上下左右四个方向推动。例如人在(0,0)，箱子在(3,5)可以往上下左右四个方向推那么pushdir[0][0][3][5][0]=pushdir[0]
2017-04-01 12:53:44
384
原创 页面置OPT算法
已经第二次出现这种OPT模拟的题目了，时间被卡到怀疑人生第一次出现时统计置换次数第二次出现是添加部分条件：同时存在最大值时按页面大的删除，最后输出操作结束后的结果，按照最原始的顺序输出。贴上代码。#includeusing namespace std;#define inf 0x3f3f3fstruct node{ int pos, x; node(){};
2017-03-22 10:08:40
1104
原创 Kattis-spiral
题目大意:给定蛇形矩阵,然后矩阵中的素数是不能到达的.现在给定两个数,求从一个数为起点到另一个数的最短距离是多少.(上下左右移动)其实就是简单的素数筛,加简单bfs,只需要一开始吧矩阵构建出来就行.自己荒废了一个寒假,手生了很多.徒手撸的时候耽误了很多时间直接导致崩盘.引以为戒,而且自己以前也学习过一篇专门描写螺旋矩阵的题目的文章.写完就去回顾http://blog.csdn.net/tinygu...
2017-03-01 18:43:50
345
原创 codeforces368B - Sereja and Suffixes
题目大意:给出n个数字m个 查询,然后查询的从第x个位置到最后一个位置,去重之后剩下几个数字.一开始真的挺难想的.数据范围都是1e5,觉得应该是nlog的复杂度,联想到树状数组等.但是还是无果,看了题解之后顿时觉得自己好蠢正应了先前的那句话碰到题目难解的时候一定要反过来考虑.反过来考虑的话就简单多了.从最后一个数开始,出现一个数,标记一个数.如果当前的数出现过了,那么ans[i
2017-02-17 14:57:55
398
原创 codeforces520B-Two Buttons
题目已经写过很多次了,但是还是写错.记下来引以为戒.题目大意,给定两个数a,b,通过两种操作将a变成b一种是将a乘以2,一种是将a减1这里可以用贪心的思路做,强行bfs搜也是可以,但是数据一大就容易T首先如果a>b那么必然是直接减,因为变小的操作只有减如果a如果是偶数,那么必然最后一步是乘以2也可以还原,把b变成b/2直到操作到b思考的方式其实是倒着做,并不是用a去
2017-02-17 12:34:37
764
原创 codeforces455A-Boredom
一开始没想到是dp题.想到之后其实发现还是挺简单的.记录的是每个数字出现的次数,然后如果这个数要取那么对答案的贡献是c[i]*i,因为有c[i]个i,然后如果这个数不能取,那么必然是前一个数取过了.因此,状态转移方程是dp[i]=max(dp[i-1],dp[i-2]+c[i]*i),需要注意的是会出现溢出问题#includeusing namespace std;#define inf
2017-02-15 15:16:00
591
原创 Kattis-torn to pieces
题目大意:第一行给出n代表有n张地图碎片,接下来n行给出碎片上的信息,第一个单词代表这个碎片上的节点,后边所有的节点都与第一个节点相连接.最后一行给出查询,问从A到B是否存在一条路径可以通过给定的拼图的一部分拼凑而成,可行的话输出路径,否则输出no route find可能是比赛当时受了先前题目的影响,看到这题之后第一时间想到的就是最短路,题目保证了最多只有一条路.因此,只需要把每个节点名
2017-01-14 08:52:21
759
原创 Kattis - oceancurrents优先队列+bfs
题目大意是,给定整个图中各个点的流向,在这个点上顺着流向前进是不需要消耗体力的,但是往其他方向走是需要消耗体力的.给定终点起点,求从起点到终点,最小消耗的体力是多少当时看到这个问题之后第一反应是搜索,但是1000*1000个各自显然是要爆炸的.赛后发现其实可以用优先队列搜索,或者是A*搜索
2017-01-14 08:45:00
323
原创 阶乘位数问题
这次碰上的问题更加奇葩.需要求N次阶乘之后一共有多少位.方法一,取log10既是N次阶乘的位数又给定是阶乘,所以可以分解成log的加法运算.代码如下#includeusing namespace std;#define inf 0x3f3f3f3f3fdouble x;int t,n;int s[1000005];int main(){ //freopen
2017-01-13 11:06:11
453
原创 hdu3172Virtual Friends涨姿势并查集
题目描述大致如下:给定n个关系,每次给出关系的时候,求出这个集合的中人的总数,每次合并这两个人所在的集合因为每次给出关系的时候都需要求出总数,所以每次去合并的时候去重新更新根节点,再去统计是不现实的.一开始因为这个TLE好几次.之后发现其实每个子节点的个数也是可以合并到根节点去的,就类似p数组,可以定义sum数组,每次合并的时候,把子节点中的个数加入到父节点中,每次输出父节点的sum即
2017-01-13 10:59:38
312
原创 hihocoder1138涨姿势的最短路
题目的大致意思是说,给定n个点的坐标,让我们求起点到终点的最短距离.点点之间的距离是min(abs(x1-x2),abs(y1-y2))一开始根本不会写.直到看到了博主:http://blog.csdn.net/octopusflying/article/details/51125562的代码思路大体是,从点1到点n的最短路必然经过这个点的前驱和后继.相对的,有x方向的前驱后继,y方向
2017-01-13 10:44:12
563
原创 manachar模板
需要注意的点是开数组的时候需要开出2倍。否则会访问越界。因为一开始涉及到字符的扩充#includeusing namespace std;const int MAX=1100000+10;char s[2*MAX];int p[2*MAX];int t;int main(){ scanf("%d",&t); while(t--){ scanf("%s
2016-10-05 12:29:40
470
原创 KMP模板学习
KMP真是个神奇的东西#include using namespace std;char mo[10005],str[1000005];int nextpos[10005];int t;int main(){ //freopen("1.txt", "r", stdin); scanf("%d",&t); while(t--){ scanf("
2016-10-03 19:34:00
282
原创 Trie树模板
最近在扩充知识量，疯狂学习模板贴一个trie树模板，里边26可改动，这里仅针对小写字母#include using namespace std;typedef struct Trie{ int v; Trie *next[26];} Trie;Trie root;void createTrie(char *str){ int len = strlen(
2016-10-03 14:32:30
253
原创 两个序列中公共子序列的个数
原题HDU5791代码如下#includeusing namespace std;#define inf 0x3f3f3f3f3f#define mod 1000000007int n,m,x;int a1[1005],a2[1005];long long dp[1005][1005];int main(){ while(cin>>n>>m) {
2016-09-14 18:39:51
1168
原创 Function（HDU5875）
大连网络赛。当时挺混乱的，其实根本都没看这道题。后来看了题解觉得用的方法很巧妙。值得学习。同时回忆起一道以前的题目。用的都是类似的思想。#includeusing namespace std;#define inf 0x3f3f3f3fint t,n,q,l,r,ans,modpos;int a[100005];int rightpos[100005];int main
2016-09-11 18:49:21
381
原创 列车调度（PAT）
当时想了很久，总是超时。最后参考了别人的代码才完全A了。PAT题目总是这样，用一些很巧妙的容器跟函数。然后大大简化代码量。#includeusing namespace std;sets;int n,x;int main(){ cin>>n; s.insert(0); for(int i=0;i<n;i++){ cin>>x;
2016-09-10 19:15:50
1394
1
原创 红色警报(PAT)
一个并查集的问题。先把边全部存起来，然后记录节点是否被攻占。然后用这些边，去掉被攻占的节点。重复建图。不断比较。#includeusing namespace std;struct node{ int w,v;};node link[5005];int n,m,k,last,now;int pa[505],live[505];int findpa(int x){
2016-09-10 19:11:51
657
原创 树状数组模板学习
树状数组的代码模板int a[maxn];int lowbit(int x){ return x&(-x);}void add(int x,int y){ while(x<=n) { a[x]+=y; x+=lowbit(x); }}int sum(int x){ int s=0; while(
2016-08-28 00:58:02
220
原创 数据结构复习——堆
说真的浙大的老师讲的挺好的。其中建堆的时候引用了哨兵概念少了很多判断，然后用堆的插入删除操作做起来简直飞快。void createH(){ Hsize=0; H[0]=-99999;}void heap_insert(int x){ int i; for(i=++Hsize; H[i/2]>x; i/=2) H[i]=H[i/2];
2016-08-28 00:54:12
320
原创 中序后序，中序先序求二叉树
用中序，后序求二叉树int build(int la,int ra,int lb,int rb){ if(la>ra) return 0; int root=a[ra]; int i; for(i=lb;i<=rb&&b[i]!=root;i++){} if(i<=rb){ L[root]=build(la,ra-rb+i
2016-08-26 03:22:07
532
原创 UVALive 7427 Elementary Math
题目大意：给定一些数对，用+-*三个运算符号去操作数对，使得每个数对操作之后的结果都不相同。如果存在满足情况的解，则按照原顺序输出，否则输出impossible一个设计的非常巧妙地二分图！！数对是一边，匹配的是所有的运算结果，如果存在这样的结果，就把点对和结果连边，得出最大匹配。特别需要注意的是，结果存储的时候需要三倍空间。小错误真的可以让人WA到怀疑人生#includeus
2016-08-05 16:41:57
693
原创 Gym 100818F Irrational Roots
暑假集训题目。真的是涨姿势了。如果高阶方程的最高系数是1。那么他的根必然是整数根。题目要求求无理根的个数，则n减去有理跟的个数，其中注意判断重根。重根判断：已知某个满足条件的根对于原方程成立，求导之后，如果仍然满足方程，则必然是一次重根，继续操作就是二次，三次。#includeusing namespace std;int a[10];int n;int cnt;int
2016-08-05 16:23:28
439
原创 数据结构复习——二叉树的几个基本操作
包括了几个很基本的操作，树的创建删除遍历等等#includeusing namespace std;typedef struct node* tree_pointer;struct node{ char ch; tree_pointer left_child,right_child;};tree_pointer create(tree_pointer T){
2016-07-03 10:03:20
425
原创 中缀表达式转成后缀表达式
正常表达式是中缀表达式，转化成后缀表达式之后方便计算值。需要注意的几点是。1.栈空直接将运算符号入栈。2.有元素，且栈顶元素优先级小于现有元素优先级，则放入，因为后边可能比改元素优先级还要高。3.栈顶元素优先级大于或等于当前元素，那么，必然是前面的先算，因此可以循环控制，将前面的优先级大于或等于当前元素优先级的符号都输出。4.控制左括号时，左括号进栈优先级降为最低。右括号进栈时
2016-07-02 15:24:07
384
原创 螺旋矩阵
螺旋矩阵解释起来有点烦，但是看上去之后让人一目了然。其实一开始对这个还是很反感的，因为特别难控制。但是参考了http://www.cnblogs.com/eshizhan/archive/2010/06/01/1749013.html之后，其实发现也就这么回事儿。#includeusing namespace std;int ar[105][105];int n;void Sp
2016-07-02 09:52:14
451
原创 数据结构复习——线性表的链式存储实现（双向链表）
其实与单向链表大同小异，只是多了一个前驱指针。操作起来多了几个小步骤而已。#includeusing namespace std;typedef struct Node * Nodeptr;typedef struct Node{ int data; //数据 struct Node *pre,*next; //指针} NODE;
2016-06-30 15:27:29
498
原创 数据结构复习——线性表的链式存储实现（单向链表）
上一篇讲了顺序存储，现在是实现另一种形式：链式存储。顺便还多做了除了做了单向链表，还实现了双向链表，十字链表。
2016-06-30 10:25:07
439
原创 数据结构复习——线性表的顺序存储实现
线性表有两种方法实现，一种是顺序存储实现，另一种是链表存储实现。顺序存储说白了就是用数组去存储。简单的实现了增，删，查。#includeusing namespace std;#define MAXSIZE 105typedef struct{ int data[MAXSIZE]; int Len;} List;void printList(List *pt
2016-06-29 14:26:39
540
原创 肿瘤诊断(PAT)
题目链接：https://www.patest.cn/contests/gplt/L3-004一道很裸的bfs，一开始以为会超时，抱着试一试的心态交了一发竟然过了#include#include#include#include#includeusing namespace std;int m,n,l,t;int a[100][1300][130],vis[100][1300]
2016-05-26 21:02:06
1803
原创 集合相似度（PAT）
题目链接：https://www.patest.cn/contests/gplt/L2-005一开始用map超时了，总是有一组数据超时。当时觉得很纳闷。后来学到了，其实set也是可以开数组的，map也是。#includeusing namespace std;set s[55];int N,n;int main(){ cin>>N; for(int k=1;k
2016-05-26 20:58:32
2245
原创 RSA的简单模拟实现
对称加密都非常好理解，而且十分容易实现。其实小的时候就早早知道了非对称加密的概念。但是就算在现实中找到海枯石烂也找到不到一个实例去实现。然后上课老师举了一个很形象的例子：非对称加密就像一个邮箱。邮箱的外壳就是加密秘钥，而邮箱的钥匙是解密秘钥。大家都可以使用这个加密秘钥把自己的信息发送出去而其他人也是同样的手法加密信息。但是过程是不可逆的，只有拥有解密秘钥的人，也就是拥有邮箱钥匙的人才能
2016-05-12 20:19:41
925
原创 最长公共子序列LCS（The longest common subsequence）
最长公共子序列，英文缩写为LCS（Longest Common Subsequence）。其定义是，一个序列 S ，如果分别是两个或多个已知序列的子序列，且是所有符合此条件序列中最长的，则 S 称为已知序列的最长公共子序列。而最长公共子串(要求连续)和最长公共子序列是不同的.最长公共子序列是一个十分实用的问题，它可以描述两段文字之间的“相似度”，即它们的雷同程度，从而能够用来辨别抄袭。对一段文
2016-05-07 19:31:47
788
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人