Doraemon's Blog

暑假学习了KMP，奈何掌握不深，现在又来复习，结果又是从零开始 什么是KMP？现在有一个原字符串，再给你一段模式串，问你在原字符串中是否存在一段子串等于模式串，或者模式串在原串中出现几次？ BF算法，也就是人人都会的指针回朔暴力算法，略过 原串： ABABABAABA （i） 模式串： ABAA （j） 当匹配时第一个失配的位置是3(下标从0开始)，然后朴素做法是把i和j指针都回朔，但其实可以利用之前已经匹配的信息的，可以找到当前失配字符之前的最大公共前后缀长度，假设长度为k，则s[i-k]…s[i-1]==t[j-k]…t[j-1]，而t[0]…t[k-1]==t[j-k]…t[j-1]，所以s[i-k]..s[i-1]==t[0]…t[k-1]，所以只需要把j移到k位置就可以了，i指针不回朔，这样一来就只要j指针回朔，而且大概率没有回朔到0，省去大量时间，那么问题就来了，怎么找到模式串中每一个位置的k呢？ 前面已经说了，k是每一个位置之前字符串(不包括k位置)的最长公共前后缀长度，而公共前后缀与原串无关，只是在模式串中求即可 求解NEXT用next[i]表示i位置之前字符串的 ...

2020年10月18日，这一天是我第一次打比赛的日子，非常有纪念意义，但是时至今日我才补了这篇文章 2020年注定是不平凡的一年，突如其来的疫情改变很多人的生活轨迹，原本该在这一年大展拳脚的学长们无奈只能在家里打着练习赛，然而对我们而言，有好也有坏吧，好的是我们有更多时间去提升自己(当然全靠自觉)，坏的是少了许多阅历，不管怎样，终于在2020年8月29日我们开学了，开学后经过一个星期的过渡，又回到了算法的训练中去，在下面也打了许多训练赛，每次都紧紧抱着大佬的大腿，每次成绩也都还不错(不错指的是会的都比较快的做出来了)，然而只要是dp只要是新算法我们就止步于此了 又过了一个月，我们迎来的这一年的CCPC邀请赛，首先是出线问题，最终学长们也都打进去了，我们19级的因为时间还多，机会就都留给学长们了，不过一星期后，老师跟我们说可以办外卡，也可以参赛拿奖，高兴了我一天，当时我以为是线下赛，想着终于可以出去涨涨见识了，然而第二天就丧了，因为疫情，这一年几乎所有比赛都是线上举行的！一下子感觉气氛都不对了，不过毕竟是比赛，比赛前我还是有去多刷题的，然而因为好多新算法都没学，有很多题目都是干瞪眼 ...

LCA 公共祖先什么是最小公共祖先，顾名思义就是俩点最近的公共祖先 如图所示： 2和5的最小公共祖先就是4 2和1的最小公共祖先就是4 3和5的最小公共祖先是1 那么怎么求呢？ 先介绍两种朴素的做法，也就是超时的做法🐷 第一种： 向上标记法 想求两个点的最小公共祖先可以先从其中一个点往上找父亲结点，直到根节点，把路径标记一下，然后从另一个点开始做同样的操作，当遇到已经标记过的点的时候就停下来，这个点一定是最小公共祖先（ 每次查询时间复杂度：O(n) ） CODE12345678910111213141516171819202122232425262728293031323334353637383940414243#include <bits/stdc++.h>using namespace std;const int MAXN=500100;vector<int> vt[MAXN];int fa[MAXN];bool vis[MAXN];void dfs(int u){ int len=vt[u].size(); for(int i=0;i&l ...

注意注意注意： 异或运算符优先级比等于还要低！！！！二进制的运算符尽量都加上括号 必胜状态后继节点一定有必败 必败状态后继都是必胜 巴什博弈 数上博弈俩人轮流取数，一次可以取走1到m个数，假如有m+1个数，则第一个人怎么取第二个人都可以一次取走，第二个人就赢了，现在有x个数，这x个数可能是m+1的倍数，也可能不是，假设不是，那么那么第一个人就可以第一次取s个数，把m+1这个必败状态给对方，假如是，则自己就是必败了x=n*(m+1)+s Brave game (HDU1846)1234567891011121314#include <bits/stdc++.h>using namespace std;int main(){ int t; cin>>t; while(t--){ int a,b; cin>>a>>b; int mod=a%(b+1); if(mod>=1) cout<<"first"< ...

计蒜客之前比赛的一道题目，记录一下 G Millionaire Madness A close friend of yours, a duck with financial problems, has requested your help with a matter that will help him pay off his debts. He is the nephew of an extremely wealthy duck, who has a large vault, filled with mountains of coins. This wealthy duck has a certain coin in his possession which has a lot of sentimental value to him. Usually, it is kept under a protective glass dome on a velvet cushion.However, during a recent relocating of the coins in t ...

写这个代码花了一个小时，因为刚学了一点点OS模块，还不是很熟悉，写完后功能也都有，但是！！！导出为exe文件时不小心误删了py文件，气死我了！又重新写了一遍。 新加了GUI界面的整理页面小程序，效果如下图所示 GitHub项目地址 Here 效果图： {height=”400”,width=”400”} CODE1（不含有重命名）12345678910111213141516171819202122232425262728293031323334353637383940414243444546import osfrom shutil import copyfiledef create(): print('------创建文件夹------') for i in var_list: Path_now = os.path.join(Path, i).replace('\\', '/') if(not os.path.exists(Path_now)): os.m ...

前言 趁着还没忘记录一下吧🐷 哈希能干些啥？学一个新算法首先一定要知道学这个能干些啥对吧，我们是为了用某个东西而去学这个东西而不是盲目目的的学，现在假如给你两段字符串让你去比较他们是否相同，如果暴力做法就是从头到尾扫一遍，都相同则相同，复杂度为O(N)，假如数据量非常大，而且字符串长度很大，现在题目就变成了给你n个字符串，现在又给你t个字符串问你每一个字符串是否在这n个字符串中，平常做法时间复杂度O(tt个字符串每一个字符串长度\n)，若用哈希预处理时间复杂度降到O(t*字符串长度+n)，也就是把那n个字符串预先处理一下，使得接下来比较每一个字符串时时间复杂度变成O(1)，让我们来看一下具体怎么操作吧 思想其实哈希和二进制思想是类似的，如果让你比较两个二进制串是否相同，你肯定会想到把二进制转成十进制比较起来会更方便，因为复杂度降低到了O(1)，不用你去逐位比较了，那字符串也是可以像二进制那样转换成为一个数字的，例如：abcd这个字符串可以转换成为ap^3^+b\p^2^+c*p^1^+d*p^0^，这里的p值是多少先不说，每一个字符都是有acall值的，我们可以直接利用这一点把每 ...

最友好的一次积分赛2333应该也是最后一个个人积分赛了，不知道最后一次会不会是团队赛，再说吧，已经八月十五了，自从集训以来每天都有训练，虽然晚上一般都是有些时间去记录一些题解的，但是懒癌晚期的我真的不想去写，终于今天下定决心，趁着这两天我要补一下题解，把最近有意义的题目记录一下，也算是一个复习吧🎉 D 何不好的晨练描述 何不好是一名晨练爱好者，每天他都要一大早出门进行晨跑锻炼，何不好生活的城市很大， 同时也比较繁荣，路边高楼耸立，道路上车辆往来，川流不息。 晨练的同时还可以欣赏路边的风景，于是，何不好打算每天选择 M 条路段，其中包括 N 个路口。 但何不好想要从起点开始不重复的跑完所有路段，并且跑回起点，苦于是学渣的他不知道 能不能完成这个条件，于是他向你寻求帮助。 输入数据 第一行给定两个整数 N , M 。 接下来 M 行，每行有两个整数 U，V 代表路段相连的两个路口。 1 ≤ N ≤ 100,000. 0 ≤ M ≤ 100,000. 毎对儿 U, V 互不相同，且 U, V 不同。 输出数据 若能完成这个条件则输出Yes，否则输出No。 样例输入 4 4 1 2 2 ...

题目面板 提取码：k2fu A. 胡图图的数学难题这道题很有意思让你求斐波那契数列的平方和，一篇易懂的题解 得到公式以后直接一个矩阵快速幂就解决了 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051#include <bits/stdc++.h>#define ios ios::sync_with_stdio(0); cin.tie(0); cout.tie(0)using namespace std;typedef long long ll;const ll MOD=1e9+7;struct node{ ll mat[2][2]; void set(){ memset(mat,0,sizeof mat); for(int i=0;i<2;i++) mat[i][i]=1; } node operator * (const node &o){ node ans; for(int ...

dfs标记的位置太重要了，放在不同位置产生的效果都有巨大的差别，记录今天的一些dfs记忆化搜索题目 A- Function Run Fun题目链接 12345678910111213141516171819202122232425#include<stdio.h>#include<string>#include<string.h>#include<algorithm>#include<iostream>typedef long long ll;using namespace std;ll used[50][50][50];ll w(int x,int y,int z){ if(x<=0||y<=0||z<=0) return 1; if(x>20||y>20||z>20) return w(20,20,20); if(used[x][y][z]) return used[x][y][z]; if(x<y&&y<z) return used[x][y] ...