Glacier-elk

未归档

/ 注册

全部文章 / 未归档（共19篇）

Hankson 的趣味题

洛谷原题链接这是一道关于求最小公倍数、最大公约数逆运算的一道题。做这道题首先要会求最大公约数和最小公倍数，对吧…… 题目要求解个数，我们来看一看条件： 50分做法：我们从条件中很容易看出x的范围——大于等于a1并且小于等于b1，所以我们暴力枚举a1到b1，然后对于每个可能的答案...

2018-10-11

0 429

[NOI2001]食物链

洛谷原题链接这是一道分类并查集的题目。我们要根据题目的要求，求出谎话的数目。题目给了我们一些明确的判断标准：但是我们会发现，如果只按照这三个条件和普通的并查集，我们只能得30分。 30分做法：我们可以用普通并查集和一个表示谁是谁的食物的数组来完成。 30分代码： #in...

2018-10-11

0 440

[NOI2002]银河英雄传说

银河英雄传说这是一道带权并查集的题目。首先，按照题目要求，我们可以很容易的想到用并查集来实现。但是我们会发现，如果只用并查集记录队列的合并情况，那么就无法满足C操作，所以我们需要在维护并查集的同时，维护每个结点的信息。这道题目需要查询是否在一个队列中，也就是是否在一个集合中，是并查集的基...

2018-10-10

0 557

[Violet]蒲公英

查看原题戳这里这是一道经典的分块题——用分块求区间众数。分块在线的时间复杂度为O( q sqrt(n) )，离线为O( n sqrt(n) )。分块可以进行区间操作，像求区间最值，区间和，区间修改等等。适用范围：分块>线段树>树状数组。用分块进行区间操作时，中间的完整的块可以...

2018-10-10

0 518

靶形数独

洛谷原题链接靶形数独这道题是一道很经典的搜索题目，有很多的解题方法，但是Dancing-links这中高端操作身为蒟蒻的我…… 我就发一个非常容易理解的题解，你就会发现原来蓝题并不难先说一下解题思路：做这道题你首先要知道数独是什么，对吧……要不然没法做了（不知道的戳这里）然后我们来...

2018-10-08

0 511

转载：字符串HASH

转载自：Slager_Z 字符串Hash总结 Hash是什么意思呢？某度翻译告诉我们： hash 英[hæʃ] 美[hæʃ]n. 剁碎的食物; #号; 蔬菜肉丁;vt. 把…弄乱; 切碎; 反复推敲; 搞糟; 我觉得Hash是引申出把...弄乱的意思。今天就来谈谈Hash的...

2018-10-06

0 593

ST表

ST表是一个用来解决去间最值（RMQ）问题的算法。预处理时间复杂度为O（nlogn），查询复杂度为O（1）。这是一个离线算法，不支持在线修改。这里洛谷模板为例题讲解，洛谷原题链接：https://www.luogu.org/problemnew/show/P3865 用f[i][j]表示[i,...

2018-10-06

0 444

矩阵运算

矩阵加、减法矩阵加法非常简单，对应位置直接加减即可，但是前提是两个矩阵大小相同（即一个矩阵是N*M的，另一个与之相加的矩阵的大小也要是N*M）。就像这样：矩阵乘法矩阵乘法就相对比较复杂了。他需要满足的前提是第一个矩阵的列数要等于第二个矩阵的行数，这样的两个矩阵才可以相乘。下面我用...

2018-10-06

0 563

浅谈单向链表

链表介绍链表是由节点构成的一条链，每一个节点由两部分组成，一部分存储此节点的信息（数据域），另一部分存储链表后继元素的存储位置（指针域），这两部分合在一起就是一个节点。链表的节点通常用结构体来表示，一个表示数据域，一个表示指针域。 struct Node{ int da...

2018-10-04

0 460

快速幂和矩阵快速幂

快速幂快速幂是我们经常用到的一种算法，快速幂顾名思义就是快速的幂运算。我们在很多题目中都会遇到幂运算，但是在指数很大的时候，我们如果用for或者是pow就会超时，这时候就用到了快速幂。快速幂的原理就是，当求b^p的时候，如果p是一个奇数，那么我们就可以把它拆成(b^2)^(p/2)*b，因此...

2018-10-04

0 673