HDU 5877 Weak Pair (线段树+离散化+DFS)

HDU 5877 Weak Pair (线段树+离散化+DFS)

题目链接:点我~~ 题意:给出一棵n个结点的树和一个数k, 每个节点上有权值ai, 问有多少个有序对(u,v)满足u是v的祖先, 且au*av≤k. 思路:从根开始dfs, 用线段树维护当前节点u到根的节点权值序列, 数据很大,需要离散化,然后就查询小于等于k/au的数的个数. 之后把au插入, 然后继续查找子节点,回溯的时候再删去该节点。其实就是查找每个节...
09月21日 2,155
HDU 5692 Snacks (欧拉序列+线段树)

HDU 5692 Snacks (欧拉序列+线段树)

题目链接:点我~~ 先dfs求出欧拉序列,就是dfs遍历的顺序,然后更新是更新区间加一个数,查询是查询区间的最大值,即l[x]到r[x]间的最大值,l[x]表示第一次遍历到x点,r[x]表示遍历完有关x节点时的值,区间内就表示有关x的所有值~ #pragma comment(linker,"/STACK:1024000000,1024000000") #i...
05月21日 2,922
Poj 2528 Mayor's posters (成段更新+离散化)

Poj 2528 Mayor's posters (成段更新+离散化)

题意:在墙上贴海报,海报可以互相覆盖,问最后可以看见几张海报 线段树功能:update:成段替换 query:简单 hash 思路:这题数据范围很大,直接搞超时+超内存,需要离散化: 离散化简单的来说就是只取我们需要的值来用,比如说区间[1000,2000],[1990,2012] 我们用不到[-∞,999][1001,1989][1991,1999][20...
03月19日 2,726
  1. .01 4:06
  2. .02 1:47
  3. .03 3:39
  4. .04 1:40