Feng003

题解

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

/ 注册

全部文章 / 题解（共6篇）

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

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

LIS 思维

2020-10-29

0 958

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

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

树上启发式合并

2020-10-04

0 624

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

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

二分数据结构

2020-09-08

0 652

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

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

线段树思维

2020-09-01

0 893

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 772

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

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

康托展开 A*

2020-08-23

0 793