11D_Beyonder's Blog

Longest Common Palindrome Substring ↬\looparrowright↬ 题目描述 A palindrome is a symmetrical string, that is, a string read identically from left to right as well as from right to left. Given two strings which consists of lowercase letters, find the length of the longest common palindrome substring among these strings. 输入描述 There are several test cases. For each test case, there are two single lines contains two string SSS and TTT which only consist of lowercase English letters. (1≤∣S∣,∣T∣≤1051≤|S|, ...

概述 在计算机科学中，Trie\text{Trie}Trie，又称前缀树或字典树，是一种有序树，用于保存关联数组，其中的键通常是字符串。与二叉查找树不同，键不是直接保存在节点中，而是由节点在树中的位置决定。一个节点的所有子孙都有相同的前缀，也就是这个节点对应的字符串，而根节点对应空字符串。一般情况下，不是所有的节点都有对应的值，只有叶子节点和部分内部节点所对应的键才有相关的值。 Trie\text{Trie}Trie这个术语来自于retrieval\text{retrieval}retrieval。 在图示中，键标注在节点中，值标注在节点之下。每一个完整的英文单词对应一个特定的整数。Trie\text{Trie}Trie可以看作是一个确定有限状态自动机，尽管边上的符号一般是隐含在分支的顺序中的。 键不需要被显式地保存在节点中。图示中标注出完整的单词，只是为了演示Trie\text{Trie}Trie的原理。 Trie\text{Trie}Trie中的键通常是字符串，但也可以是其它的结构。Trie\text{Trie}Trie的算法可以很容易地修改为处理其它结构的有序序列，比如一串数字或 ...

朴素的模式匹配算法 主串为S=“abcdefgab”S=\text{“abcdefgab”}S=“abcdefgab”，我们要匹配T=“abcdex”T=\text{“abcdex”}T=“abcdex”。定义两个指针 i,ji,ji,j，分别指向字符串S,TS,TS,T。 最初，i,ji,ji,j 指向两个字符串的头，将两个字符串的头对其，开始同步向后移动两个指针，当 i=j=6i=j=6i=j=6 时，发现s[i]≠t[j]s[i]\ne t[j]s[i]=t[j]，这时就将 TTT 相对 SSS 整体向右移动一位，iii 指针不变，令 jjj 回到 111 。此时发现 TTT 的第一个字符就不匹配，继续进行如图的步骤。 朴素算法的最坏时间复杂度为O((n−m+1)×m)O((n-m+1)\times m)O((n−m+1)×m)，这样的算法实在是不能接受的。 KMP算法概述 在计算机科学中，Knuth-Morris-Pratt\text{Knuth-Morris-Pratt}Knuth-Morris-Pratt 字符串查找算法（简称为KMP\text{KMP}KMP算法） ...

小 C 的数学题 题目描述 已知某函数 f(n)f(n)f(n)的定义如下： f(n)={1,n≤2f(n−1)+f(n−2)+⌊log2n⌋,n≥3{\displaystyle f(n)={\begin{cases}1,&{n\le2}\\ f(n-1)+f(n-2)+\lfloor log_2n\rfloor,&{n\ge 3}\end{cases}}} f(n)={1,f(n−1)+f(n−2)+⌊log2​n⌋,​n≤2n≥3​ 求函数 f(n)f(n)f(n)的值，为了防止数据过大，你只需要输出答案对 109+710^9+7109+7 取模之后的结果。 输入 最多十行，每行一整数 nnn，1≤n<1091\le n < 10^91≤n<109 输出 f(n)f(n)f(n) 样例输入 666 666666 666666666 样例输出 581824003 310868947 609519880 分析 乍一看是矩阵快速幂，但是随着 nnn 的增大，⌊log2n⌋\lfloor log_2n\rfloor⌊log2​n⌋也会随之改变。 \begi ...

概述 强连通分量 强连通图（Strongly Connected Graph\text{Strongly Connected Graph}Strongly Connected Graph）是指在有向图 GGG 中，如果对于每一对 vi,vjv_i,v_jvi​,vj​，vi≠vjv_i≠v_jvi​=vj​，从 viv_ivi​ 到vjv_jvj​和从 vjv_jvj​ 到 viv_ivi​ 都存在路径，则称 GGG 是强连通图。有向图中的极大强连通子图称做有向图的强连通分量。 （来源：百度百科） 如上图所示，由节点1,2,31,2,31,2,3构成的环组成一个强连通分量。 算法思路 Tarjan\text{Tarjan}Tarjan算法（以发现者Robert Tarjan\text{Robert Tarjan}Robert Tarjan命名）是一个在图中查找强连通分量的算法。 此算法以一个有向图作为输入，并按照所在的强连通分量给出其顶点集的一个划分。图中的每个节点只在一个强连通分量中出现，即使是在有些节点单独构成一个强连通分量的情况下（比如图中出现了树形结构或孤立节点）。 算法的 ...

概念 线段树是一种二叉树形数据结构，1977年由Jon Louis Bentley\text{Jon Louis Bentley}Jon Louis Bentley发明，用以存储区间或线段，并且允许快速查询结构内包含某一点的所有区间。 一个包含n{\displaystyle n}n个区间的线段树，空间复杂度为O(n){\displaystyle O(n)}O(n)，查询的时间复杂度则为O(log⁡n+k){\displaystyle O(\log n+k)}O(logn+k)，其中k{\displaystyle k}k是符合条件的区间数量。 此数据结构亦可推广到高维度。 （来源：WikiPedia） 用途 一般来说，在线段树内进行单词查询和更新的时间复杂度为O(log⁡n)O(\log n)O(logn)。主要可以实现单点更新、区间更新、区间查询、单点查询等操作，求解一系列区间问题（区间求和，求区间最大值，求区间最小值……）。 线段树的结构 上图是一棵表示区间[1,20][1,20][1,20]的线段树。 可以看到，线段树将每个长度不为111的区间划分成左右两个区间递归求解，把整个线 ...

C. 小 C 的爱情 CUGOJ 2170\text{CUGOJ 2170}CUGOJ 2170 题目描述 某天晚上，小C在操场中心完成了乐跑打卡，准备回寝室研究BZOJ 1000\text{BZOJ 1000}BZOJ 1000.这时（前方高能），他看到一个漂亮的mm正在绕着操场匀速率圆周运动（啥？匀速率你都能看出来，我去）。小C被mm深深的吸引。但是这个时候，他又想起了自己的BZOJ\text{BZOJ}BZOJ还没有刷完。 于是他想了一个折中的办法：把自己交给命运，他以vvv的速度追mm，但是只走NNN米。如果追上，就问妹子要QQ，否则就回寝室。 现在我们假设操场是一个圆形，半径为rrr，二者的速率不变，mm跑步的速率的v1v_1v1​,小C的速率是v2v_2v2​，他最多走NNN米，并且在小C追mm的时候，二者和圆心始终在同一直线。 那么小C的命运如何呢？ 输入 多组输入，mm的速率v1v_1v1​，小C的速率v2v_2v2​，操场半径 rrr,以及NNN. 所有的数据保证在double的范围以内。 输出 如果能够追上，输出：Yes 如果追不上，输出：No 样例输入 1 1 ...

贝尔曼-福特算法(Bellman–Ford algorithm) 贝尔曼-福特算法是求解单源最短路径问题的一种算法，由 Richard Bellman\text{Richard Bellman}Richard Bellman 和 Lester Ford\text{Lester Ford}Lester Ford 创立的。有时候这种算法也被称为 Moore-Bellman-Ford\text{Moore-Bellman-Ford}Moore-Bellman-Ford 算法，因为 Edward F. Moore\text{Edward F. Moore}Edward F. Moore 也为这个算法的发展做出了贡献。它的原理是对图进行 ∣V∣−1{\displaystyle |V|-1}∣V∣−1 次松弛操作，得到所有可能的最短路径。其优于迪科斯彻算法的方面是边的权值可以为负数、实现简单，缺点是时间复杂度过高，高达 O(∣V∣∣E∣){\displaystyle O(|V||E|)}O(∣V∣∣E∣)。但算法可以进行若干种优化，提高了效率。 迪杰斯特拉算法(Dijkstra’s algori ...

PORTAL\text{PORTAL}PORTAL A - The Number of Even Pairs Time Limit: 2 sec / Memory Limit: 1024 MB Score : 100100100 points Problem Statement We have N+MN+MN+M balls, each of which has an integer written on it. It is known that: The numbers written on NNN of the balls are even. The numbers written on MMM of the balls are odd. Find the number of ways to choose two of the N+MN+MN+M balls (disregarding order) so that the sum of the numbers written on them is even. It can be shown that this count ...

B-阶乘 题目描述 给定一个正整数 p{p}p。 求一个最小的正整数 n{n}n，使得 n!{n!}n!是p{p}p的倍数。 输入描述 第一行输入一个正整数T{T}T表示测试数据组数。 接下来T{T}T行，每行一个正整数p{p}p。 输出描述 输出T{T}T行，对于每组测试数据输出满足条件的最小的n{n}n。 示例1 输入 4 1 2 4 8 输出 1 2 4 4 备注 T⩽103,p⩽109T \leqslant 10^3, p \leqslant 10^9T⩽103,p⩽109 思路 如果对于任意ppp的质因子iii，iii的个数是qqq，总有，x!x!x!中有超过qqq个质因子iii，那么x!x!x!就是ppp的倍数。 可以采用二分，每一次check\text{check}check枚举所有ppp的质因子，看此时的答案是否符合条件。计算质因子iii的个数时，可以将x!x!x!看成xxx个数相乘，每隔iki^kik个数字一定会出现一个iii的倍数，计算∑k=1∞⌊xik⌋\sum \limits_{k=1}^{\infty}\lfloor \frac{x}{i^k}\rfl ...