2017年12月

HDU 3555: Bomb(不要49)

Problem给定一个 n ,求 [1, n] 有多少个数包含 49。Code数位 DP#include <cstdio> #include <algorithm> #include <cstdlib> #include <cstring> #define long unsigned long long using namespace std; long a[100]; long dp[100][3]; /* dp[i][0] 前 i 位不包含 49 的个数 dp[i][1] 前 i 位以 9 开头但不包含 49 的个数 dp- 阅读剩余部分 -

主席树学习笔记

主席树就是可持久化线段树,可以随时访问任何一个历史版本的线段树,所有操作的时间复杂度和线段树完全一致,是 O(logn),空间变成了 O(nlogn),是一种十分优秀的数据结构。对于线段树来说,每次操作都只会更改 logn 个节点,我们可以单独把这些节点存下来,然后剩下的节点和前一个版本的线段树共用就可以了,这样对于 n 个操作就需要存储 nlogn 个节点,这样空间复杂度 O(nlogn) 就证明出来了。具体来说怎么和前一个版本的线段树共用节点从而降低空间占用呢?当我们修改了一个节点,那么他的左右孩子中肯定有一个需要修改,那么修改其中的一个孩子,而另一个孩子我们直接指向上- 阅读剩余部分 -

BZOJ 1733: [Usaco2005 feb]Secret Milking Machine 神秘的挤奶机

Description约翰正在制造一台新型的挤奶机,但他不希望别人知道.他希望尽可能久地隐藏这个秘密.他把挤奶机藏在他的农场里,使它不被发现.在挤奶机制造的过程中,他需要去挤奶机所在的地方T(1≤T≤200)次.他的农场里有秘密的地道,但约翰只在返回的时候用它.农场被划分成N(2≤N≤200)块区域,用1到200标号.这些区域被P(1≤P≤40000)条道路连接,每条路有一个小于10^6的长度L.两块区域之间可能有多条道路连接.为了减少被发现的可能,约翰不会两次经过农场上的任何一条道路.当然了,他希望走最短的路. 请帮助约翰寻找这T次从仓库走到挤奶机所在地的路线.仓库是区域- 阅读剩余部分 -