Absoler

分类

Java开发(1) MFC(1) 动态规划(5) 图论(7) 基本算法(6) 字符串(3) 思维(2) 搜索(7) 数学(2) 数据结构(4) 未归档(29) 杂项(1) 树(2) 模板(3) 真题(9) 计算几何(1)

/ 注册

TA的专栏 9篇文章 0人订阅

9篇文章 1290人学习

全部文章（共83篇）

2019杭电多校第一场

[toc] A Blank Blank 计数dp，长为n的数列，每个位置上四种数字选择，题目会给出m个限制条件，每个条件要求在[l,r]范围内有且仅有几种数字。要求给出所有合法方案数。我们可以用dp来对每种数字上次出现的位置做情况讨论，例如用dp[x][y][z][w][len]来表...

2020-05-09

0 665

线性基模板

线性基类似于线性代数中的基向量，我们找一个整数集的线性基，实际上是找这样一个集合P，使得P中的元素互相异或运算得到的结果集和原集合相等。从二进制上看，最终我们期望得到 1—– 01— 001- 这样的集合，同时也可以进一步将低位的0消去。向原集合插入一个新数字 ...

2020-05-09

0 575

codeforces 724G. Xor-matic Number of the Graph

题目链接给一个无向图，含边权，并定义这样一种三元组(u, v, t)满足：从u到v有一条路径且路径上的边权异或和为t。求所有三元组的t的和我们对它逐步拆解分析，先考虑最简单的情况——如果这个图是一棵树。首先我们发现由于异或的特殊性，经过相同的边两次等价于没有经过，所以对于所有的点...

2020-05-09

0 464

网络流&dij模板题HDU6582

题目给出一个有向图，要求阻挡其中的一些边，使得从1到n的最短路径变长，阻挡一条边的代价是这条边的长度。问题其实就转化为，找到从1到n的所有最短路，并在这些路中找到能阻挡最短路的一些边且边权和最小——也就是找到最短路构成图的最小割。找所有最短路可以贪心地去找合适的边，什么样的边(u, v)...

2020-05-09

0 506

算法竞赛中常用的STL

C++标准模板库（STL）封装了大量十分有用的数据结构和算法，熟练使用STL将会使我们的程序编写如虎添翼。接下来会介绍几种在程序竞赛中常用到的STL类。如果想了解更多，推荐直接访问官方文档搜索查阅 [TOC] bitset 可以理解为bit这个数据类型的数组（即取值只为0/1），大多...

2020-05-09

0 887

计算几何模板

点、线段 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 ...

2020-05-09

0 503

poj2079 旋转卡壳

题目题目给出一个点集，要求其中选三个点能构成的最大三角形的面积。我的方法是O(n^2)，似乎能通过二分降成nlogn，不过好在这题数据不大可以过。可以证明这三个点必在凸包点中，如果说存在一个面积更大的三角形而它有的点不在凸点上，那么必定可以在凸点上找到一点，使得（替换后）三角形面积更大。...

2020-05-09

0 614

2-sat模板

2-sat用于解决这样一类问题：给出n个二元组，每个二元组必选出一个元素，而这些元素间可能有互斥的情况，要求给出合理方案。我们可以知道，对于二元组，如果因为被排斥而不选择某个元素，那么意味着必定选择另一个，这就使得问题可解，3-sat及以上似乎没有多项式算法……？ tarjan方法利用tar...

2020-05-09

0 576

构造算法题目积累

cf1304D 题目给出n-1个‘<’‘>’约束，第i个位置的<意味着结果串中a[i]<a[i+1]，要求用1~n个数构造出两个串，分别拥有最小和最大的LIS。思路：我们将升序1~n中连续>的区间执行reverse操作，执行完毕后的结果就是拥有最大LIS的满足约...

2020-05-09

0 482

lca倍增模板

lca即最近公共祖先，倍增法可以在O(n)的预处理后以每次logn的代价进行查询操作。思路：预处理出fa[n][i]数组，表示第n号点的第（1<<i）个父亲，之后在寻找u、v的lca时，可以对二进制上的每一位进行向上跳跃。例题：cf1304E 给出一棵树，有q个询问，格式...

2020-05-09

0 642