题目点击这里 这个,题目的数据是100×100的,所以暴力DFS肯定是不行的啦~ 由于每行每列最多只能放2个炮,所以可以用一个三维DP 用f[i,j,k]表示放完第i行的炮后,现在有j列有1个炮,k列有2个炮,当然,1个炮都没有的列数就是m…
树链剖分,用来解决树上路径的统计问题,对树进行DFS,结合线段树等数据结构可以在logN的时间内解决问题。 由于要解决树上的路径问题,而线段树对边建树或者是对点建树都很难将大部分路径上的点或边在一段连续的区间里面,所以我们将树上的路径,或者…
前言 其实吧,我个人是很不想去学农的,但是没办法,【数据删除】的设定就是这样,那也就只好去了。这几天每天都很累,而且还有各种各样的事情发生,从根本上来说就是换了个地方学习。考虑到这可能是我一生中唯一一次能零距离接触土地,那还是写篇文章记录一…
第一道树链剖分题~ 题目点击这里 就是树链剖分的裸题啦~直接套模板就行,关于树链剖分的讲解点这里。 代码: type node=record l,r,max,sum:longint; end; var t:array[1..6553…
前言 偶尔写一点与OI无关的也没啥问题嘛。。。 win10出来了也有一点时间了,刚刚发布的时候本人还在夏令营,于是就没法第一时间享受新版操作系统的美好了555 安装 对于win8和win7用户,会在右下角出现新微软的图标,也就是那个四边形,…
暑期专题三~ 这次内容有点多,所以也不是每道题都写了代码,这里都不贴出来,毕竟有的有代码有的没有有点怪怪的。。。 题目与部分题解来源于BYvoid大神,这里就不打出题目了。 部分原题没有给出数据范围,这里补充一下,以方便各位。 完结撒花~~…
暑期专题二 距离上个专题总结连一个星期都没到。。。但刚放假时没怎么搞OI然后下个星期又要出外8天又没有时间,下个月还有3个专题,所以得稍微快一点。。。 平衡树是二叉搜索树的强化版,首先说一说二叉搜索树: 二叉搜索树是一种二叉树,它每个节点都…
这里的第一道平衡树~ 题目点击这里 总之题目很长但题意不难理解,其实也就是平衡树的一道裸题,用到的操作都很基本,入门可以做一做。 这里用了splay,当然只要是平衡树应该都是可以的。。。 代码照抄借鉴于这里 type node=record…
暑期专题一 前面一段时间复习了一下并查集这个东西,其实原本初一有学过一点但是当时没怎么听懂,现在重新回过头看就很好理解了。 并查集可以处理不相交集合的问题,这里说的有点不容易懂,可以用一道例题说明。 【例1】 有n个人,其中有…
这里的第一道并查集~ 题目点击这里 题目大意: 有一个人(编号为0)感染了SARS,然后一共有M个社团,如果社团中有一个人感染了SARS那么整个社团都会感染SARS,问最后会有多少个人感染了SARS。 题解: 因为这题实际上是合并多个集合,…
没错又是后缀数组,放心这是这一段时间内的最后一题了。。。 题目点击这里 总之还是后缀数组的题目,把题目翻译一下就变成了求一个字符串的不重叠相同子串的最大的(长度×数量)(好吧我语文不行。。。) 官方题解神秘失踪了。。。这里讲一下官方题解的做…
试一下用Word 2013来写写博客。
后缀数组三连发~ 题目:某人读论文,一篇论文是由许多单词组成。但他发现一个单词会在论文中出现很多次,现在想知道每个单词分别在论文中出现多少次。 注意题目所说的文章是把读入的每一个单词中间加一个空格隔开的一个长字符串,还有题目所说的单词长度不…
后缀数组的简单题。 题目: 喜欢钻研问题的JS 同学,最近又迷上了对加密方法的思考。一天,他突然想出了一种他认为是终极的加密办法:把需要加密的信息排成一圈,显然,它们有很多种不同的读法。例如下图,可以读作: JSOI07 SOI07J OI…
顾名思义啦,后缀数组的模板 题目: 这是一道模板题。 读入一个长度为 n 的由小写英文字母组成的字符串,请把这个字符串的所有非空后缀按字典序从小到大排序,然后按顺序输出后缀的第一个字符在原串中的位置。位置编号为 1 到 n。 除此之外为了进…
更多...
加载中...