1540
HDU1540 Tunnel Warfare 题解
Question HDU1540 Tunnel Warfare 在一条线上有 \(n\) 个村庄,两个相邻的村庄之间用地道连接,做 \(m\) 次操作 D x 第 \(x\) 个村庄被摧毁,它的地道也一同被摧毁 Q x 查询第 \(x\) 个村庄所能到达的村庄总数(包括村庄 \(x\)) R 重建刚 ......
P1540 [NOIP2010 提高组] 机器翻译
传送门 题目背景 小晨的电脑上安装了一个机器翻译软件,他经常用这个软件来翻译英语文章。 题目描述 这个翻译软件的原理很简单,它只是从头到尾,依次将每个英文单词用对应的中文含义来替换。对于每个英文单词,软件会先在内存中查找这个单词的中文含义,如果内存中有,软件就会用它进行翻译;如果内存中没有,软件就会 ......
CF1540D
牛逼题,贺的强大 [$O((n+q) \sqrt{n})$](https://www.luogu.com.cn/blog/ryoku/solution-cf1540d) 做法(。 很有根号智慧 /hs /bx *** 先把 $b_i \leftarrow i-1-b_i$,也就是变成 $j \lt ......
P1540 [NOIP2010 提高组] 机器翻译
题目背景 小晨的电脑上安装了一个机器翻译软件,他经常用这个软件来翻译英语文章。 题目描述 这个翻译软件的原理很简单,它只是从头到尾,依次将每个英文单词用对应的中文含义来替换。对于每个英文单词,软件会先在内存中查找这个单词的中文含义,如果内存中有,软件就会用它进行翻译;如果内存中没有,软件就会在外存中 ......
w4 P1540 [NOIP2010 提高组] 机器翻译
主要思路:因为题目要求内存满后要扔出最先进去的单词,于是就想到用queue。每查找一次要查找的单词是否已在内存内,不在则查找次数+1,把单词放入内存,同时内存大小+1。然后判断此时的内存大小是否超出给定大小,超出则pop,为超出则继续。 代码如下: #include<iostream>#includ ......
hdu-1540(线段树+区间合并)
Tunnel Warfare HDU - 1540 思路: 没被摧毁的村庄为1,否则为0,用len记录 线段树维护区间的两个信息: 前缀最长1的序列pre 后缀最长1的序列suf 父节点与左右子节点的关系: //lc为左节点,rc为右节点 1.若左右结点都不满1,则tr[p].pre = tr[lc ......