BzhH

第一遍读完这道题，这不就是个裸的KMP板子吗，然后迅速打出了KMP，发现并过不了样例2，于是又仔细读了一下题，发现读漏了一个条件，即需要在中间也出现过，因为我们知道,KMP中的next数组存的是相同的前缀和后缀的长度,那么只需要找在中间出现过前缀长度,并标记一下就行了,最后在匹配的时候多判断一下。 详见代码 #include<iostream>#include<cstdio>using namespace std;const int N = 1e6 + 5;string s;int net[N], num[N];bool is[N];int main(){ cin >> s; for (int i = 1, j = 0; s[i]; i++) { while (j && s[i] != s[j]) j = net[j - 1]; if (s[i] == s[j]) j++; net[i] = j;  ...

这道题直接模拟就可以做出来 了。 首先是顺时针旋转90°部分 如图一个3*3的矩阵 1 2 3 4 5 6 7 8 9 顺时针旋转过后 7 4 1 8 5 2 9 6 3 由此可以看出 第a行数字与第a列数字有关系 所以可以得出以下代码 void spin(int x,int y,int r){ for(int i=x-r;i<=x+r;i++) { for(int k=y-r;k<=y+r;k++) temp[i][k]=square[i][k]; }//将以（x,y)为中心的(2r+1）*（2r+1）的矩阵赋给temp int x1=x+r,y1=y-r; for(int i=x-r;i<=x+r;i++) { for(int k=y-r;k<=y+r;k++) { square[i][k]=temp[x1][y1];//将某一列的数字赋值给某一列 x1--; } x1=x+r,y1++; }&# ...

这道题稍微思考一下就可以做出来 由题可知，每行每列可以隔开的同学不会重复， 所以只要将每行每列可以隔开的同学的对数统计出来，再从大到小排序，最后输出即可。 代码如下 #include<iostream>#include<algorithm>using namespace std;int ans_row[2005],ans_cul[2005];//储存每行每列可以隔开的同学struct pos_row{ int x1 time;}row[2005];//储存坐标以及隔开的同学struct pos_cul{ int y1 time;}cul[2005];//同上bool cmp1(pos_row a,pos_row b){ return a.time>b.time;}//从大到小排序bool cmp2(pos_cul a,pos_cul b){ return a.time>b.time;}int main(){ int m,n,k,l,s,d; cin>> ...

这道题可以通过直接一行一行输出 大致可以将数字分为五部分 顶部，顶部下方，中部，中部下方，底部 代码 char top[10]={'-',' ','-','-',' ','-','-','-','-','-'};//如果有就为横线，没有就为空格，如“1”和“0”char left_top[10]={'|',' ',' ',' ','|','|','|',' ','|','|'};char right_top[10]={'|','|','|','|','|& ...

例题：P1397 八数码难题 ###双向BFS 普通BFS 双向BFS 所谓双向广度优先搜索指的是搜索沿两个方向同时进行 正向搜索：从初始点向目标点搜索； 逆向搜索：从目标点向初始点搜索； 从正反两个方向搜索，理论上可以节省二分之一的搜索量，从而提高搜索速度，节约内存空间。 从初始状态和目标状态向两个方向同时进行扩展，如果两颗解答树在某个节点发生一次重合，即可终止此搜索过程，则该节点所连接的两条路径所拼成的路径就是最优解 ●双向广度优先搜索通常有两种搜索方法: ①、两个方向交替扩展; ②、选择结点个数较少的那个方向先扩展; ●实现方法: 建立两个队列分别拓展两个方向出发的状态。 每次while循环时只扩展正反两个方向中节点数目较少的一个，可以使两边的发展速度保持一定的平衡，从而减少总扩展节点的个数,加快搜索速度。 例题代码 #include<iostream>#include<map>#include<queue>#include<cstring>using namespace std;map<string, int> m ...

迭代加深 DFS在一些问题模型中可能无限扩展，如8数码问题，无限扩展会有些问题，增 加深度限制：假设目标状态所处深度不超过某阈值。人为设定，当搜索深度到达阈 值时直接剪枝，不再往下搜索。 Iterative Deepening Depth - First Search 适用：求最优/深度最低/步数最少解，当问题深度和广度都大的时候 方式：不断放宽迭代深度限制第一次找到的目标状态即为最优解。 迭代加深是深搜和广搜的结合,普通深搜求最优解必须遍历所有状态打擂台得到， 迭代加深后，第一次遇见目标状态即可得到最优解。 深度优先搜索优化-迭代加深（IDDFS） for(int dep=1;;dep++){//限定每次搜索的深度 if(dfs(1,dep)) break;//找到答案就退出} 例题1443：【例题4】Addition Chains n范围较小，初略推出最多十项左右就能得到答案，即答案在搜索树的浅层，可 以使用迭代加深的方法，限制每一次的搜索深度。 例题代码 #include<iostream>#include<cstring>using ...

例题P4777 【模板】扩展中国剩余定理（EXCRT） 对于每一个x≡b1(mod  a1)x≡ b_1(\mod a_1)x≡b1​(moda1​),可以设k为x/a1x/a_1x/a1​的商，易得an∗kn+bn=xa_n*k_n+b_n=xan​∗kn​+bn​=x。 对于前两个式子 {a1∗k1+b1=xa2∗k2+b2=x\begin{cases} a_1*k_1+b_1=x \\ a_2*k_2+b_2=x \end{cases} {a1​∗k1​+b1​=xa2​∗k2​+b2​=x​ 可得a1∗k1+b1=a2∗k2+b2a_1*k_1+b_1=a_2*k_2+b_2a1​∗k1​+b1​=a2​∗k2​+b2​ 即a1∗k1−a2∗k2=b2−b1a_1*k_1-a_2*k_2=b_2-b_1a1​∗k1​−a2​∗k2​=b2​−b1​ 通过扩展欧几里得算法，不难算出k1,k2k_1,k_2k1​,k2​的所有解为 {k1+k∗a2dk2+k∗a1d\begin{cases} k_1+k*\frac{a2}{d} \\ k_2+k*\frac{a1}{d} \end ...

裴蜀定理:对于任意x，y，若满足k1x+k2y=dk_1x+k_2y=dk1​x+k2​y=d有解,则d一定为k1,k2k_1,k_2k1​,k2​的最大公约数 证明: ∵d为x,yx,yx,y的最大公约数 ∴x,y一定为d的倍数 ∴k1x+k2yk_1x+k_2yk1​x+k2​y也一定为d的倍数,则一定存在k1,k2k_1,k_2k1​,k2​为方程的一组解 通过欧几里得算法递归来求k1,k2k_1,k_2k1​,k2​ 核心为gcd(a,b)=gcd(b,a%b) 若满足k1x+k2y=dk_1x+k_2y=dk1​x+k2​y=d,则k1y+k2(x%y)=dk_1y+k_2(x\%y)=dk1​y+k2​(x%y)=d, 显然,当x%y=0x\%y=0x%y=0时,k1=1,k2=Nk_1=1,k_2=Nk1​=1,k2​=N 因为x%y=x−⌊xy⌋∗yx\%y=x- \left \lfloor \frac{x}{y} \right \rfloor*yx%y=x−⌊yx​⌋∗y 代入得k1y+k2(x−⌊xy⌋∗y)=dk_1y+k_2(x-\left\lfloor\fra ...

次短路 目前知道的方法有：1.跑一遍最短路，一次枚举删边 2.在跑最短路时同时记录最短路与次短路 3.起点和终点分别跑一次最短路，枚举边来替换最短路上的边 例题P1491 集合位置 #include<cstdio>#include<cmath>#include<queue>#include<cstring>using namespace std;typedef pair<double, int> PDI;const int INF = 1e9;const int N = 100005;int x[N], y[N], head[N], ver[N], net[N], tot, path[N], vis[N], n, m;double edge[N], dist[N];void add(int a,int b,double c){ net[++tot] = head[a]; head[a] = tot; edge[tot] = c; ver[tot] = b;}void Dij(int ...

例题 给定一颗多叉树，求两个点的最近公共祖先 dfs遍历预处理出每个节点的父亲信息，存在fa[x][0]中。 fa[x][j]为x点向上走2^i步所到的节点 depth[x]为x点所在的深度 void dfs(int x,int f){ v[x] = 1; dpth[x] = dpth[f] + 1; fa[x][0] = f; for (int i = 1; i <= t;i++) fa[x][i] = fa[fa[x][i - 1]][i - 1]; for (int i = head[x]; i;i=net[i]) { int v1 = ver[i]; if(v[v1]) continue; dfs(v1, x); }} 每个点向上走任意步数能到达的点都能通过倍增数组表示出来。 1、利用2进制拆分思想，向上调整深度大的点y,直到和点x深度相同 l 从大到小枚举k，比较x和fa[y][k]，一直调整到和x深度相同f=f ...