Absoler

真题

Java开发(1) MFC(1) 动态规划(5) 图论(7) 基本算法(6) 字符串(3) 思维(2) 搜索(7) 数学(2) 数据结构(4) 未归档(29) 杂项(1) 树(2) 模板(3) 计算几何(1)

/ 注册

全部文章 / 真题（共9篇）

2016 北京 ICPC (部分)

I - A Boring Problem 题目大意数列求和，其中每一项都是一个子段和的k次幂，例如：给定原字符串为 “12345” 输出结果：1^k (1+2)^k+2^k (1+2+3)^k+(2+3)^k+3^k…… (1+2+3+4+5)^k+(2+3+4+5)^k+…+...

2020-05-09

0 426

牛客网NOIP赛前集训营-普及组（第一场）

C 括号题目大意：对于输入的一串括号“()))(()()((”，可以删去若干位（删除位置不完全相同时均算作两种操作），若想最终得到合法括号串，求共有多少种操作方法可选。先说算法后解释： dp[i][j]表示，加入第i个元素后，能将前i个字符转化为有j个未配对左括号‘（’的方法数。 ...

2020-05-09

0 445

一些数学知识补充

1 分数取模需要对一个分数 p q \fra...

2020-05-09

0 415

单调队列

单调队列是一种在直觉上很容易想到的数据结构。有一个经典例子是滑动窗口问题，对于一串数字（长为n），存在一个在其上滑动的矩形窗（长为k），要求线性时间内求出每个窗口中的最大值。我们可以想见在窗口的每次右移后，新的最大值与原最大值会具有很密切的关系。我们可以设置一个单调减队列q，添加元素时从队尾添加，遇...

2020-05-09

0 455

牛客多校2019——Big Integer——欧拉定理，质因数分解

题目链接官方给的题解是这样的：直接从别的博客复制过来了，有几点需要补充解释一下： d为满足的最小正整数，求它的目的是为了更方便的去求，因为它一定是d的倍数。求g的时候，指数向上取整是为了保证j次方之后一定为d的倍数，当然大概率是会多乘几个质因数强...

2020-05-09

0 729

字符串算法汇总

字符串哈希：讲解大意就是将字符串视为一个多位的数，用unsigned long long 保存，溢出可以视为对2^64取模。回文树：博客另一篇博客推荐配合OIWiki上的图食用每个节点代表当前前缀的最大回文串后缀，next指向的是代表[通过前后加上...

2020-05-09

0 580

Palindrome Mouse - 回文树 & dfs

这道题是牛客2019暑期多校第六场的C题，题目链接大意是，给出一个字符串，对于它所有的回文子串，若其中某个是另一个的子串，则视其为一对，求总对数。看到回文子串就想到了回文树。简单回顾一下，回文树每个节点代表以当前字符结尾的最长回文子串，next指向前后添上某个字符后更大的那个子串，fail（...

2020-05-09

0 565

HDU6602线段树+思维

http://acm.hdu.edu.cn/showproblem.php?pid=6602 题意：给出一个1e5规模数列，数字范围也在1e5内，给出K，求最长子序列，使得序列中出现的任一数字都至少出现K次。考虑枚举右端点，尺取法不好做，因为左端点没有简单的找法，，我们这样拆分问题：首先考虑每...

2020-05-09

0 422

牛客多校graph games（部分分块+哈希）

https://ac.nowcoder.com/acm/contest/883/A 题目大意，给出一个无向图，设S(x)表示x的临近点集合，临近点即通过一条边直接相连的点。有两种操作，1是把边集合（读入顺序）从l到r的边状态反转（相连变断开，断开变相连），2是询问两个点的临近集是否相等。这里首...

2020-05-09

0 591