什么都没学会。

传送门

POI的题都好神仙啊。

传送门

先说句闲话，好久没写题解了，主要是因为我的懒惰以及人类能鸽善鹉的本性。

但既然搭好了新blog，还是用一下吧，现在开始更新，不定时咕咕咕。

这会是篇怎样的游记呢？

Day 0

中午就要发车了，我现在就坐在slyz的机房里颓废。屋里其他的大爷们都在切着神题，loli坐在讲台上玩着手机，只有我什么都不想干。

于是开始水大爷们的blog，在看到Menci的《梦结束的地方》的时候，颇有感触。然后冒着禁赛的危险写下了这篇游记。

2-SAT定义

$SAT$是$Satisfiability$的缩写，意为可满足性。即一串布尔变量，每个变量只能为真或假。要求对这些变量进行赋值，满足布尔方程。
例如$($$a$ $or$ $b$$)$$and$$($$a$ $or$ $!c$$)$$and$$($$a$ $and$ $c$ $or$ $b$$)$，求解这个问题就是让你找出一组a,b,c的取值使得这个表达式为真。
而这个问题当一个括号里有多于2个元素时只能枚举，是NP问题。$2-SAT$就是括号里只有两个元素的情况。

题目描述：

$N$ 个柱子排成一排，一开始每个柱子损伤度为0。

接下来勇仪会进行$M$ 次攻击，每次攻击可以用4个参数$l$ ,$r$ ,$s$ ,$e$ 来描述：

表示这次攻击作用范围为第$l$ 个到第$r$ 个之间所有的柱子(包含$l$ ,$r$ )，对第一个柱子的伤害为$s$ ，对最后一个柱子的伤害为$e$ 。

攻击产生的伤害值是一个等差数列。若$l=1$ ,$r=5 $, $s=2$ ,$e=10$ ，则对第1~5个柱子分别产生2,4,6,8,10的伤害。

鬼族们需要的是所有攻击完成之后每个柱子的损伤度。

线段树练习（也有树状数组）

洛谷 P2184 贪婪大陆

题目背景

面对蚂蚁们的疯狂进攻，小FF的Tower defence宣告失败……人类被蚂蚁们逼到了Greed Island上的一个海湾。现在，小FF的后方是一望无际的大海， 前方是变异了的超级蚂蚁。 小FF还有大好前程，他可不想命丧于此， 于是他派遣手下最后一批改造SCV布置地雷以阻挡蚂蚁们的进攻。

题目描述

小FF最后一道防线是一条长度为N的战壕， 小FF拥有无数多种地雷，而SCV每次可以在[ L , R ]区间埋放同一种不同于之前已经埋放的地雷。 由于情况已经十万火急，小FF在某些时候可能会询问你在[ L’ , R’] 区间内有多少种不同的地雷， 他希望你能尽快的给予答复。

洛谷 P3740 HAOI2014贴海报

题目描述

Bytetown城市要进行市长竞选，所有的选民可以畅所欲言地对竞选市长的候选人发表言论。为了统一管理，城市委员会为选民准备了一个张贴海报的electoral墙。

张贴规则如下：

1. electoral墙是一个长度为N个单位的长方形，每个单位记为一个格子；
2. 所有张贴的海报的高度必须与electoral墙的高度一致的；
3. 每张海报以“A B”表示，即从第A个格子到第B个格子张贴海报；
4. 后贴的海报可以覆盖前面已贴的海报或部分海报。

现在请你判断，张贴完所有海报后，在electoral墙上还可以看见多少张海报。

这题其实没什么，但用到的算法都十分有用。做一个不恰当的比喻，这是一只必须用牛刀杀的鸡，但因为我这个蒟蒻杀不死牛，所以只能找只鸡来练练手。

洛谷P1901 发射站

题目描述

某地有 N 个能量发射站排成一行，每个发射站 i 都有不相同的高度 Hi，并能向两边（当 然两端的只能向一边）同时发射能量值为 Vi 的能量，并且发出的能量只被两边最近的且比 它高的发射站接收。

显然，每个发射站发来的能量有可能被 0 或 1 或 2 个其他发射站所接受，特别是为了安 全，每个发射站接收到的能量总和是我们很关心的问题。由于数据很多，现只需要你帮忙计 算出接收最多能量的发射站接收的能量是多少。