[算法] 浅讲线段树和树状数组(一)
写在前面
线段树是我最喜欢的数据结构之一了,几乎每一场比赛都能遇到相关的题目,它的强大是有目共睹的。
这篇博客主要是讲讲它的原理及一些应用,顺便提一下线段树的一些应用。
本片博文虽为新手向,但需要你有一定前缀知识,如:
C++语法基础
位运算基础
函数的递归和回溯思想
分治思想(如二分)
基础数据结构(主要为二叉树)
后续还可能会放上讲解可持久化线段树(主席树)的文章(大概
引入 & 建树
对于经常遇见的这样一类问题:
给你nnn个数字(一般是无序序列),接下来再有mmm次操作,每次操作可能是:
求某区间的和/最大值/最小值/乘积……
修改某个数字/某个区间段里的数字
……
其中,nnn和mmm的规模通常在105{10}^5105及以上。
刨去修改,如果只有求区间和/乘积,那么使用前缀和计算将是你最好的选择。
如果是求最大值/最小值,也可以使用DP、RMQ、分块等方式解决。
但是一旦加上修改,上述解决方案都不是很适用,而传统暴力做法的时间复杂度将会高达O(n⋅m)O(n \cdot m)O(n⋅m)。
那么是不是有一种办法可以很好地处理上述问题呢?—— 点我看 ...
Python爬虫学习笔记(一)Scrapy框架实战
写在前面
这篇博客来记录学习Python爬虫
主要是为了应付数据可视化这门课程而写,虽然标题有(一),但可能不会有(二)了
毕竟本人不是走这方面路子的(逃
什么是Scrapy
Scrapy是一个为了爬取网站数据,提取结构性数据而编写的应用框架。 可以应用在包括数据挖掘,信息处理或存储历史数据等一系列的程序中。
其最初是为了 页面抓取 (更确切来说, 网络抓取 )所设计的, 也可以应用在获取API所返回的数据(例如 Amazon Associates Web Services ) 或者通用的网络爬虫。
以上内容引用自初窥Scrapy——Scarpy 0.24.1 文档
Scrapy的框架如下
crapy Engine(引擎): 负责Spider、ItemPipeline、Downloader、Scheduler中间的通讯,信号、数据传递等。
Scheduler(调度器): 它负责接受引擎发送过来的Request请求,并按照一定的方式进行整理排列,入队,当引擎需要时,交还给引擎。
Downloader(下载器):负责下载Scrapy Engine(引擎)发送的所有Re ...
Java Swing组件学习笔记
写在前面
由于最近在做编译原理实验的作业——制作八、十、十六进制计算器,想要得高分需要做个界面。
于是乎想到之前有学过的Java的Swing组件(简单易用),不过也有些忘记了,就顺手写篇博客记录一下制作过程以及期间遇到的细节问题(
So,这篇博客讲的更多的会是计算器怎么做啦。
注意:由于本人用的是macOS系统,默认组件显示效果会与其他系统有所不同。
持续更新中……
前期工作
在使用Swing组件前,你至少需要了解JAVA的基本语法,以及常见错误排查。
那么,先让我们大致了解一下Java Swing吧。
什么是Swing组件?
注意:以下部分内容摘自菜鸟教程 - Java Swing 介绍
Swing 是一个为Java设计的GUI工具包。
Swing是Java基础类的一部分。
Swing包括了图形用户界面(GUI)器件如:文本框,按钮,分隔窗格和表。
Swing提供许多比AWT更好的屏幕显示元素。它们用纯Java写成,所以同Java本身一样可以跨平台运行,这一点不像AWT。它们是JFC的一部分。它们支持可更换的面板和主题(各种操作系统默认的特有主题),然而不是真的使用原生平台提供 ...
[算法] 浅谈莫比乌斯反演
写在前面
这篇博客用来记录一下我学习莫比乌斯反演的过程,以及我是如何理解它的。
期间参考了大量其他博客,这里列出表示感谢:
莫比乌斯反演 by OI-wiki
莫比乌斯反演-让我们从基础开始 by An_Account
莫比乌斯反演-从莫比乌斯到欧拉 by An_Account
莫比乌斯反演学习笔记 by LNRBHAW
莫比乌斯函数 by Grary
数论函数 - 莫比乌斯函数与莫比乌斯反演 - 基础杜教筛 by zhouzhendong
参考的博客包括但不限于以上这些,有些看过的博客忘记了(逃
另外,如果本篇博客涉及侵权,请您及时联系我修改,以免造成不必要的损失。
前置知识
学习莫比乌斯反演以前,需要先了解的一些前置知识。
积性函数
积性函数是数论中一个非常重要的概念,常常可以利用其性质来进行数论分块优化。
定义
若gcd(x,y)=1gcd(x, y) = 1gcd(x,y)=1且f(xy)=f(x)f(y)f(xy) = f(x)f(y)f(xy)=f(x)f(y),则称函数f(x)f(x)f(x)为积性函数。
扩展:若对于任意(x,y)(x, y)(x,y)满足 ...
[题解] 头脑风暴专题
写在前面
这篇博客记录一下这些天来做(和看到)的思维题,昨天是越做越有趣,越做越起劲(其实是奶茶喝多了睡不着),直接导致了我又一不小心想出了一些(可能)很鬼酷的思维题。
持续更新中……
CodeForces 892D Gluttony
传送门
题目大意
给你nnn个不同数字组成的数组aaa,现在再任取kkk个数{x1,x2,…,xk}(1≤xi≤n,0<k<n)\{x_1, x_2,\dots, x_k\} (1 \leq x_i \leq n, 0 < k < n){x1,x2,…,xk}(1≤xi≤n,0<k<n)。
要你求出aaa数组的某种排列bbb,满足:∑i=1kaxi≠∑i=1kbxi\displaystyle\sum_{i = 1}^{k}{a_{x_i}} \neq \displaystyle\sum_{i = 1}^{k}{b_{x_i}}i=1∑kaxi=i=1∑kbxi
其中1≤n≤22,1≤ai≤1091 \leq n \leq 22,1 \leq a_i \leq 10^91≤n≤22,1≤ai ...
[题解] HDU6703 array
题目大意
这是CCPC2019网络预选赛的题目,题目传送门。
给你一个数组aaa,初始是[1,n][1, n][1,n]的某个排列,有mmm个操作,操作分为两种:
(1,pos)(1, pos)(1,pos):将aposa_{pos}apos修改为apos+10,000,000a_{pos} + 10,000,000apos+10,000,000;
(2,r,k)(2, r, k)(2,r,k):询问一个a1,a2,……,ar{a_1, a_2, ……, a_r}a1,a2,……,ar之中未出现的最小正整数AnsAnsAns且满足Ans≥kAns \geq kAns≥k。
这些给出的操作将经过加密,你需要解密,解密方式如下:
每组测试数据的第一个操作前定义一个LastAnsLastAnsLastAns初始化为000;
若给出两个数(1,t1)(1, t1)(1,t1),代表这次操作是操作111,最终的pos=t1⨁LastAnspos = t1 \bigoplus LastAnspos=t1⨁LastAns;
若给出三个数(2,t2,t3)(2, t2, t3)(2, ...
个人模板整理
写在前面
本篇博客主要用于本人的ICPC比赛用模板整理,方便查阅。
如有网友发现哪里写的不好、哪里可以改进,欢迎提出。
持续更新中…
常用C++STL(模板)合集
注意:C++STL全部需要使用命名空间std
万能(误)算法头文件(部分)
123456789101112131415161718192021222324252627282930313233343536#include <algorithm>using namespace std; int main() { iterator begin, end; // 指代某种数据结构首尾迭代器 T i, x, a, b; sort(begin, end, <cmp>); // 排序函数,默认从小到大 // 遇到需要特殊排序的需要编写cmp函数 or 重载内部运算符 next_permutation(begin, end); // 下一个排列 prev_permutation(begin, end); // 前一个排列 set_union(b ...
在Linux上搭建Hexo博客 & 我的搭建博客历程
写在前面
本文是基于本人服务器目前所用的Linux系统CentOS 7编写的,但事实上其他版本的Linux,甚至是macOS、Windows也都大同小异。这里会有一大篇废话来讲我的博客历程,如果不喜欢看的请跳过这一段。
本文实际上就是本人搭建Hexo的全过程啦。
我的博客历史
我的博客历史可以追溯到2015年,那时候还在北京培训OI,心血来潮想写博客记录自己对算法、数据结构的理解,以及刷题记录,对服务器的概念一窍不通,所以使用博客园开启了我的博客生涯。
我的这个Vendetta Blogs算是我现存能找到的最早的博客了,也是唯一被我留在网上的博客
这是我最早的两篇博客,质量的话是这个博客里最高的了(当然阅读量也是
上百度一搜LCA,偶然发现排名第一居然是我的博客,甚至超过了百度百科?
其实自己心里是有窃喜的,但是这里不得不提,Tarjan局限性很高,大家还是去认真地学习一下倍增吧(唔
接下来还用了CSDN、新浪云SAE、主机屋免费的主机,但是仍然觉得不好用,于是购入了人生第一个虚拟主机(为了不用备案所以买了枫叶主机),不得不说当时国外的主机对国内用户不是很友好其实,买了60一 ...
Hello, World
作为我新的博客的第一篇博客
当然要对世界说一声:
123456#include <bits/stdc++.h>int main() { std::cout << "Hello, world!" << endl; return 0;}