1551LA

未归档

/ 注册

全部文章 / 未归档（共47篇）

EOJ Monthly 2020.7 E

题意：我们需要按照一定的顺序输出a的所有因数，同时要保证，从第二个数开始每个数都必须由其前一个数乘以某个质数或除以某个质数得出的。思路：各质数的幂次方组合，每次每个幂方之和大小改变为1。以题目中样例来说 a=(2^3)*(3^2)=72。易得a所有因数为: #include&...

2020-07-18

0 484

AC自动机

我们来讲讲AC自动机，单看这个名字我们恐怕还不知道这是用来干嘛得，但我们之前已经学了KMP以及trie树，我们知道KMP 大多是用来解决单串单串匹配的问题的，而AC自动机=KMP+trie树，AC自动机是一种多模匹配算法，AC自动机的关键是构建字典图实现自动跳转，构建失配指针实现多模式匹配。首先...

2020-05-26

0 579

扩欧的应用

之前简单的总结了下扩欧，这次来说说扩欧具体有哪些用法总的来说扩展欧几里德算法的应用主要有以下两个方面：（1）求解不定方程；（2）求解模线性方程（线性同余方程）与逆元；（1）求解不定方程所谓不定方程就是形如：ax+by=c 我们通过扩欧可以知道若 c mod Gcd(a, b)=0,则该方程存在整数...

2020-05-26

0 579

扩展欧几里得

讲扩欧前先来回顾以下gcd，直接上代码int gcd(int a,int b){ if(b==0) return a; return gcd(b,a%b);}扩展欧几里得算法：对于不完全为 0 的非负整数 a，b，gcd（a，b）表示 a，b 的最大公约数，必然存在整数对 x，y ，使得...

2020-05-23

0 451

trie树

这篇讲讲trie树什么是trie树，trie树是一种树形结构，是一种哈希树的变种。典型应用是用于统计、排序和保存大量的字符串（但不仅限于字符串），所以经常被搜索引擎系统用于文本词频统计。优点：利用字符串的公共前缀来减少查询时间，最大限度地减少无谓地字符串比较，查询效率比哈希树搞。看了这个解释，可能会...

2020-05-16

0 651

线段树

这篇讲讲线段树，个人认为直接上代码配注释好理解。。。 /*线段树：线段树，是一种二叉搜索树。它将一段区间划分为若干单位区间，每一个节点都储存着一个区间。基本思想：二分基础操作：建树单点查询单点修改区间查询区间修改*/ include <stdio.h> incl...

2020-05-16

0 579

KMP算法

先简单解释下KMP是用来干嘛，简单来说就是解决的问题就是在字符串中的模式定位问题。直接举例吧目标串s="aaaaab",模式串t="aaab"，看道这里有的人肯定会想，这么简单，暴力一下不就出来了。但暴力也只是适用于数据小的情况下，而KMP算法就是起到了消除主...

2020-05-09

0 616