30
2019
08

如何理解splay树

本文参考资料:https://www.cnblogs.com/cjyyb/p/7499020.html学习splay树首先要学习SBT,即二叉搜索树,二叉搜索树,对于任意一个节点,左儿子的值比它小,右儿子的值比它大并且任意一棵子树单独拎出来也是一棵二叉搜索树二叉搜索树进行中序遍历后序列正好是有序的,查找复杂度o(lgn)。但是如果一开始给定的序列就是有序的,我们构造的SBT会是一条长链,查找复杂度就变会o(n)了。各位大佬们为了解决平衡树这个尴尬的问题,想出了各种方法。。也就是弄出了各种树,AV
23
2019
08

信息学奥赛一本通 树链剖分 1560:【例 1】树的统计

这题是模板题,先两个dfs把树剖开,重新编号,再借助线段树求解,求路径上的权值和还需要借助lca的思路先跳到同一条链上再利用区间求和。#include <iostream> #include <cstring> #include <cstdio> #define MIN -0x3f3f3f3f #define mem(a,b) memset((a),(b),sizeof((a)))
16
2019
08

信息学一本通-1579:皇宫看守 树形dp

一棵树有 N 个节点,现在需要将所有节点都看守住,如果我们选择了节点 i,那么节点 i 本身,节点 i 的父亲和儿子都会被看守住,每个节点有一个选择代价,求完成任务所需要的最小的代价。显然这是一道树形DP。根据每个节点其实有只有三个状态:①被自己看守;②被儿子看守;③被父亲看守。我们设这三种状态分别为 F1,F2,F3。当然最终作为答案的根节点没有父亲就从 F1,F2 里面选小的。接下来我们要考虑怎么转移。首先看 F1,我们规定 F1[ i ] 代表的是 i 节点被自己看守且以 i 为根的子树都
01
2019
08

详解归并排序和树状数组两种求逆序对数得思路

首先通过题目看看如何考察逆序数,什么是逆序数?逆序数就是找前面有几个比自己大的数即如果i<j&&a[i]>a[j] 则a[i]和a[j]构成一个逆序对这里排序求交换次数比正好就是我们前面讲到的逆序对吗?因此我们首先就想到了o(logn)方法的归并排序 mergesort(int l,int r)归并排序的思路就是:先二分分到不能再分,保证(l<r),再将两个有序的序列合并起来。如一个序列a[7]={100,29,8,9,10,5} 对齐归并排序步骤如下:100,
25
2019
06

信息学奥赛一本通 提高组 1576:选课

时间限制: 1000 ms         内存限制: 524288 KB提交数: 135     通过数: 107 【题目描述】原题来自:CTSC 1997大学实行学分制。每门课程都有一定的学分,学生只要选修了这门课并通过考核就能获得相应学分。学生最后的学分是他选修各门课的学分总和。每个学生都要选择规定数量的课程。有些课程可以直接选修,有些课程需要一定的基础知识,必须在选了其他的一些课程基础上才
13
2019
04

信息学一本通:1174:大整数乘法

【题目描述】求两个不超过200位的非负整数的积。【输入】有两行,每行是一个不超过200位的非负整数,没有多余的前导0。【输出】一行,即相乘后的结果。结果里不能有多余的前导0,即如果结果是342,那么就不能输出为0342。【输入样例】12345678900 98765432100【输出样例】1219326311126352690000#include<bits/stdc++.h> using namespace std; int main(){
12
2019
04

信息学一本通 1168:大整数加法

题目描述】求两个不超过200位的非负整数的和。【输入】有两行,每行是一个不超过200位的非负整数,可能有多余的前导0。【输出】一行,即相加后的结果。结果里不能有多余的前导0,即如果结果是342,那么就不能输出为0342。【输入样例】22222222222222222222 33333333333333333333【输出样例】55555555555555555555#include <bits/stdc++.h> using namespace std
11
2019
04

信息学奥赛一本通 1278:【例9.22】复制书稿(book)

【题目描述】现在要把m本有顺序的书分给k个人复制(抄写),每一个人的抄写速度都一样,一本书不允许给两个(或以上)的人抄写,分给每一个人的书,必须是连续的,比如不能把第一、第三和第四本书给同一个人抄写。现在请你设计一种方案,使得复制时间最短。复制时间为抄写页数最多的人用去的时间。【输入】第一行两个整数m,k;(k≤m≤500)第二行m个整数,第i个整数表示第i本书的页数。【输出】共k行,每行两个整数,第i行表示第i个人抄写的书的起始编号和终止编号。k行的起始编号应该从小到大排列,如果有多解,则尽可
30
2019
03

NOIP 2000 方格取数

#include <bits/stdc++.h> using namespace std; /* 思路: 有来、回两次行走,而且不能有路径交叉。我们可以转换为一次行走,有两个人同时行走,形象地说为多线程。 只要每一时刻都保证两个人不在同一点上就可以保证路径不会交叉(这个仔细想想或者画一画就可以证明是对的)。 那么状态表示可以是f[i][j][k][l]表示第一个人在(i,j)第二个人在(k,l)时的最优解。 */ int N;
25
2019
03

信息学奥赛一本通1276:【例9.20】编辑距离

题目: 设A和B是两个字符串。我们要用最少的字符操作次数,将字符串A转换为字符串B。这里所说的字符操作共有三种: 1、删除一个字符; 2、插入一个字符; 3、将一个字符改为另一个字符。 对任意的两个字符串A和B,计算出将字符串A变换为字符串B所用的最少字符操作次数。 #include <bits/stdc++.h> using namespace std; /* 思路: f[i][j]表示A的前i个字符变成B的前j个字符所