搜索结果
查询Tags标签： nxt，共有 36条记录-
2022-9-11/12 #27 自弹 自唱 自赏 不如自封为王
发现了栀子的一首歌 Go crazy for me，真上头。 昨天有一根木刺扎进了我右手中指，伤口愈合后挑不出来了，写代码按到那里就会痛一下。 匈牙利跑二分图匹配可以找到增广路后再清空 vis 数组，某些题中会有优越性。（反正不劣） 做了 CF848D Shake It!，觉得挺简单，就不记…
2022/9/15 23:18:40 人评论 次浏览 -
C 栗酱的数列 kmp结论题 模运算移项差分
链接：https://ac.nowcoder.com/acm/contest/27589/C来源：牛客网 题目描述栗酱有一个长度为n的数列A，一个长度为m的数列B，现在询问A中有多少个长度为m的连续子序列A， 满足(a1+b1)%k = (a2+b2)%k = …… = (am + bm)%k。 输入描述: 第一行一个数T，表示有T组数据。 对于…
2022/9/12 23:23:17 人评论 次浏览 -
D K匹配 kmp 区间匹配计算贡献
链接：https://ac.nowcoder.com/acm/problem/213329来源：牛客网 题目描述牛牛是赫赫有名的字符串高手，现在牛牛发现了一种新的匹配方式。给定一个字符串SSS和一个字符串TTT，如果SSS存在一个长度为kkk的子串Sl1,l1+k−1S_{l_1, l_1 + k - 1}Sl1,l1+k−1和TTT的某个…
2022/9/12 23:23:15 人评论 次浏览 -
【题解】后缀自动机（SAM）选做（22.8.11）
做完这些我才感觉我的后缀自动机入门了之前写的东西就是一坨屎 对于后缀自动机的学习，我总结了以下三句话： 千万不要死磕模板！！！ 千万不要死磕模板！！！ 千万不要死磕模板！！！ 谁死磕模板谁&#*%#(@# 这次就主要是我对于后缀自动机的理解，只是纯纯的自动机，不…
2022/8/11 23:30:08 人评论 次浏览 -
后缀自动机(SAM)习记
前言 本文没有构造证明，因为我不会 基础概念看看就好，自娱自乐。 后期重点更新相关题目的简单总结，方便复习 SAM 基础概念 S 的后缀自动机是一种能够识别所有 S 的子串的自动机类型的数据结构（DFA）。 暴力后缀自动机 对于字符串 \(S\)，建立插入了 \(|S|\) 个后缀的 …
2022/8/1 23:25:27 人评论 次浏览 -
2022/7/27 自学记录
发现自己 KMP 忘了，于是再学一遍。 懒得写了，直接写题。 P3375 【模板】KMP字符串匹配 挂一个模板 #include <bits/stdc++.h>using namespace std; using i64 = long long;int main() {ios::sync_with_stdio(false);cin.tie(0);string a, b;cin >> a >&g…
2022/7/27 23:25:32 人评论 次浏览 -
dijkstra最短路算法（堆优化）
这个算法不能处理负环情况，请转到Floyd算法或SPFA算法（SPFA不能处理负环，但能判断负环） SPFA(SLF优化)：https://www.cnblogs.com/yifan0305/p/16391419.html 代码很长，耐下心来看完，存储方法为链式前向星存储。 (如果内存放得下的话，建议稠密图用邻接矩阵(或者跑f…
2022/7/23 1:26:25 人评论 次浏览 -
剪花布条 HDU-2087
题目链接：https://vjudge.net/problem/HDU-2087 居然WA#include<cstdio> #include<cstring> #include<cmath> #include<algorithm> using namespace std; int nxt[1010]; void get_nxt(char t[]){int j=0, k=-1;nxt[0]=-1;int tlen=strlen(t);wh…
2022/5/5 23:43:12 人评论 次浏览 -
期望
众所周知，期望大部分题目时放在dp里面的 对于期望的题使用的dp一般都倒序进行 为什么呢？ 我们在看期望的题时总会出现这么一句话每一个状态将等概率转移给后面的某些点。 而倒序枚举恰好能够满足转移至本点的各个状态所对应的概率相等。 例如本题点击查看代码 #include&…
2022/2/25 23:22:55 人评论 次浏览 -
【题解】【白雪皑皑】
题目传送门 题目大意： 给定一个序列，初始全为0，每次区间赋值为一个数，求最终的序列。 Solution： 观察数据范围，nlog n的时间复杂度无法通过此题，考虑线性做法。 可以将操作离线下来，则每个点第一次被覆盖时即为答案。 那么我们需要一个数据结构，能够帮助我们快速…
2022/2/16 23:15:46 人评论 次浏览 -
洛谷P6175 无向图的最小环问题
传送门： https://www.luogu.com.cn/problem/P6175 floyd以外无脑暴搜取得伟大胜利（部分得益于数据小 注释小能手又双上线了（天下苦题解不说数组是干什么用的久矣1 #include<bits/stdc++.h>2 #define ff(i,s,e) for(int i=s;i<=e;i++)3 #define fff(i,s,e) for…
2022/2/10 23:14:51 人评论 次浏览 -
C++ STL：std::unorderd_map 物理结构详解
拉链法的 unordered_map 和你想象中的不一样 根据数组+拉链法的描述，我们很快能想到下面这样的拉链法实现的哈希表，但真的是这样吗？一起看下源码里的实现是怎么样的。深入STL源码 代码不会骗人的，可以写一个简单的代码研究一下实现，然后通过gdb跟踪执行： #include &…
2022/1/30 17:04:19 人评论 次浏览 -
学习笔记——字符串算法
字符串哈希 设一个字符串 \(s\)，长度为 \(len\)，定义一个大质数 \(base\)，那么求哈希的式子为： \[hash(s)=\sum^{len}_ {i=1} s_i \times base^{len-i} \]\(base\) 的次方可以由 \(power\) 数组初始化得到，那么如果把哈希当做一个 \(base\) 进制的数的话，不难想出用…
2022/1/26 17:08:57 人评论 次浏览 -
Secret of Tianqiu Valley 题解
link Solution 不难看出，我们可以通过枚举 \(1,2\) 位置来确定每个位置的奇偶性，然后考虑如何对着我们构造的奇偶性来构造解。 不难发现，对于暗着的灯且奇偶性为奇数，我们肯定直接操作最优。然后对于当前没有暗灯且为奇数，如果存在暗灯且为偶数，那么两边一定存在一个…
2022/1/25 23:07:02 人评论 次浏览 -
【Luogu P3426】[POI2005]SZA-Template
链接： 洛谷 题目大意： 给定一个字符串 \(s\)，找到最小的 \(t\) 使得 \(t\) 匹配的位置能覆盖 \(s\)。 思路： \(t\) 一定是 \(s\) 的一个前后缀（\(s\) 也算），考虑 DP。设 \(f_i\) 表示前缀 \(i\) 的答案，那么 \(f_i\) 要么是 \(i\)，要么是 \(f_{\mathrm{border}(i…
2021/11/20 6:11:33 人评论 次浏览
