Feng003

分类

codeforces(2) DP(3) 图论(2) 基础数据结构(2) 字符串(1) 数据结构课程(1) 概率期望(1) 算法课课程作业(4) 题解(6)

/ 注册

全部文章（共22篇）

DP入门

动态规划算法（DP,Dynamic Programming）它针对满足特定条件的一类问题，对各状态维度进行分阶段、有顺序、无重复、决策性的遍历求解。阶段动态规划算法把原问题视作若干个重叠子问题的逐层递进，每个子问题的求解过程都构成一个阶段。在完成前一个阶段的计算后，动态规划才会执行下一阶段的计...

DP

2021-01-26

0 746

codeforces 1437E Make It Increasing(确定首位和末位的最长严格上升子序列)

题意：给出一个长度为n的序列，k个位置，代表序列里这些位置上的数是固定的。每次可以修改序列里没被固定的一个数，问最少几次修改可以使得整个序列变成严格递增的，或者不可能。两个小结论 1、把一个序列A变成非严格单调递增(单调不下降的)，至少需要修改的数个数为序列A的总长度减去A的最长不下降子序列长度...

LIS 思维

2020-10-29

0 959

2020 计蒜之道预赛第二场虫洞（中等）(dsu on tree)

比赛的时候想到是dsu on tree了，但是没想到如何去高效的维护答案，赛后听了大佬的做法后，恍然大悟。然而后面还是调了半天才调处来...看来我对树上启发式合并的理解还不够深刻。新学了一个卡常小技巧，枚举子树的时候之前是用dfs去遍历的，但是其实可以预处理整棵树的dfs序，之后只要枚举dfs序就可...

树上启发式合并

2020-10-04

0 626

一类具有单调性的经典区间查询问题

题意：给定一个正整数序列a1,…,an。你可以进行若干次操作，每次操作可以选择一个满足ai=i的位置i，将其删去。删去后，左右两边会自动拼合到一起（也就是右边所有数下标都会相应地变化）。你想要最大化删去的元素数量。但是这个问题太简单了，所以你需要回答q次询问。每次询问给定两个正整数x,y，求如...

二分数据结构

2020-09-08

0 653

1401F - Reverse and Swap（线段树之左右儿子交换）

看题面很显然的一道数据结构题，但是对于2和3操作我想了一会没有啥思路，网上看了大佬的博客，发现只需要维护线段树上的每个结点的左右儿子是否交换就行了，在纸上模拟了几遍就想通了。唉，这就是思维的差距吧... AC代码 // Author: Feng #include<bits/stdc++.h&g...

线段树思维

2020-09-01

0 894

Polynomial(拉格朗日插值法)

先通过前(n+1)项，插值求出f(n+1)，然后通过这(n+2)项来插值求出f(x)的前缀和函数S(x)，答案为S(r)-S(l-1)。 // Author: Feng #include<bits/stdc++.h> using namespace std; typedef long l...

数学

2020-08-28

0 773

八数码（A* + 康托展开）

题目让我们求出将八数码复原的最小步数并且输出出具体方案，这是一道搜索题，因为数据范围很小。但是这道题可以借助两个算是比较高级的知识来优化，A* 算法和康托展开，A*是因为加入评估函数后可以大大的加快搜索速度。这道题的评估函数便是每个数当前所在位置和那个数最终所在位置的曼哈顿距离总和。而这里因为棋盘上...

康托展开 A*

2020-08-23

0 795

破忒头的匿名信(AC自动机套dp)

题意：给你n个字符串，每个字符串s[i]都有相应的花费代价cost[i]。问用这些已有的串拼出一个给定的T串的最小花费是多少。思路：已知有n个模式串，再给出一个匹配串。很标准的一道AC自动机的题，花费最小的话也很容易想到用dp来做，dp[i]代表能拼出T[1~i]的最小花费,转移方程 dp[i]=...

DP AC自动机

2020-07-07

0 620

托米的字符串(全区间的概率问题)

问题：给定一个字符串，随机取一个子串，求元音(a,e,i,o,u,y)字母占子串长度比的期望是多少？思路：比赛的时候我一直想的是如何计算原字符串中每个元音字母对最后答案的贡献，但是想了好久都没理清其中的关系，最后还是靠队友手模所有情况找出了规律... 后面到网上看了大佬们的博客后才发现这题是要枚...

期望数学

2020-07-05

0 582

最大连续乘积子数组

给定一个长度为N的浮点数数组a。请找出其中乘积最大的子数组。例如，给定数组{-2.5, 4, 0, 3, 0.5, 8, -1}，则取出的最大乘积子数组为{3, 0.5, 8}。也就是说，在上述数组中，3 , 0.5和8这三个数是连续的，而且乘积是最大的。思路：设计状态代表以结尾的子数组中，乘积...

DP

2020-05-22

0 585