昊昊爱运动

前缀和

要做这道题首先要会前缀和这个技巧。现在给出一个不变的序列$A$，每次询问$[L,R]$这个区间内的和该怎么做呢？既是求：
$$\sum_{i=L}^RA_i$$
如果每次都从$L$加到$R$将是一个不小的花费，所以我们可以选择间接地求解，即：
$$\sum_{i=L}^RA_i=\sum_{i=0}^RA_i-\sum_{i=0}^{L-1}A_i$$
后面的两项既是前缀和，是可以扫一遍就得到的序列：

1 2	for(int i=1;i<=n;i++) sum[i]=sum[i-1]+a[i];

每次询问$[L,R]$的和的时候就返回sum[R]-sum[L-1]就好了。

关于这道题

有了前缀和的知识，这道题就迎刃而解了。如果第$i$个位置上有颜色$c$，那么a[c][i]=1，否则a[c][i]=0，然后对每个颜色都构建前缀和。每次询问的时候，只要检查每个颜色在这个区间的和是否是0即可。

代码：

https://github.com/HarryGuo2012/ACMCode/blob/worldLine/CDOJ/1256.cpp

谕神的密码

贪心的思想

想想怎样的数是足够大的，自然是首位足够大就足够大了，足够小也是一样的道理。有了这个想法，这道题就相当简单了，只要从高往低每一位枚举数即可，如果要数字足够大，那么每次就从9枚举到0，如果要数字足够小，那么每次就从0枚举到9，当然首位要特殊判断。
枚举到什么时候呢？自然，如果要数字足够大，只要当前的和还有剩下的，就继续枚举，如果要数字足够小，那么只要我们后面能全部放9来达到和的话，就继续枚举。
很细致的一道题。

代码：

https://github.com/HarryGuo2012/ACMCode/blob/worldLine/CDOJ/1251.cpp

斓少摘苹果

怎样拿比较优越？

仔细想想整个过程，要使得拿的次数最少，自然每次要拿的足够多，最好每次都能拿m个，这样一来一定是最优越的。

模型的转换

为了保证每次都能拿到m个，我们需要一个非常巧妙地想法，想想这个问题其实是将苹果分成m堆，每堆的苹果都来自不同的树。那么我们可以将每棵树都染个色，把每个苹果考虑成方块，这样我们就得到了许许多多不同颜色的方块。现在我们只需要将这些方块铺成一个$m*t$的矩形即可。其中$t$是拿的次数。

自然我们能够想到，一行一行的铺，每次用完一种颜色再换下一种颜色，最后一行不必铺完。这样一来除非某一种颜色特别多，否则每一列就不会有相同的颜色了，并且是最快的，因为每次我们取$m$个，那么我们能得到$t=sum/m$向上取整。

那么加入某一种颜色特别多怎么办，那么我们只能将$t$取那种颜色那么多，否则一定会有相同的颜色。
所以最后的结果应当是
$$t=max(maxColor,\left \lceil \frac{sum}{m} \right \rceil)$$

代码：

https://github.com/HarryGuo2012/ACMCode/blob/worldLine/CDOJ/1255.cpp

阿里巴巴和n个大盗

其实很简单。。

我们一步步的来推理。阿里巴巴先提出方案，然后编号大的再提出。

n=1，那么阿里巴巴一定死定了，因为他无论怎么做，都无法获得半数以上的票
n=2，现在有两个海盗，2号很清楚，假如弄死阿里巴巴，就变成了上面那种状态，所以自己也活不了。在这种情况下，自然投阿里巴巴一票，那么阿里巴巴就零成本拿到了半数以上的票，所以他把金子都拿了。
n=3，现在有点复杂了，此时如果要活下来，首先我们需要弄到半数以上的票，给1个金子给1号，就能把1号收买了，这是因为如果1号投反对，那么1号得不到任何东西。2号同样的道理。所以分别给1号和2号一个金子，自己就能拿m-2个金子。
n=4，这时候你或许有点感觉了，要让别人帮你，只需提出比下家更有利的方案即可，自然，要给3号海盗1个金币。此时有了两票了（阿里巴巴自己有一票），还差1票（现在有5个人），所以我们应该给1号或者2号更多的金子，他们就能帮助阿里巴巴。但是给谁呢？自然，随便给谁2个金币都可以。所以此时阿里巴巴能得到m-3个金子。
n=5，这时候海盗的贪婪就十分明显了。。如果我们采用前面的策略，其实不是最优的。由于下家有个随便给谁2个金币的设定，所以只要给1号1个金币，2号一个金币，他们就一定会帮你，因为他们如果不帮你，也许他们能获得2个金币，也许什么都拿不到，由于金币本身是价值连城的，所以海盗们一定不会走一步险棋。同样再给4号一个金币。所以能得到m-3个金币。
。。。

你可以继续推理，不过到这里，想必你已经得到答案了。由于是两项两项交错着分配金币的。所以答案应当就是m-n/2-1。如果计算出来是负数，那么必死无疑。

代码：

https://github.com/HarryGuo2012/ACMCode/blob/worldLine/CDOJ/1253.cpp

24点游戏

dfs

首先你要学会dfs，这个其实很简单，就是利用了计算机栈入栈出的性质。这里不细讲，直接看代码就懂了

eps

这道题要考虑eps，什么是eps呢，就是能容忍的最大误差，其实计算机保存浮点数是靠二进制的，那么一定是不准确，所以两个数大约相等，我们就应该认为他们是相等的。所以等于应该改成这样：

1
2
3

bool equal(double a,double b){
	return abs(a-b)<eps;
}

一般eps取1e-8

代码：

https://github.com/HarryGuo2012/ACMCode/blob/worldLine/CDOJ/1252.cpp