宝贵资源

这道题采用贪心的思想就好了，首先我们可以得到所有点横纵两个方向上的最大跨度，用这个最大的跨度作为边长即可框住所有的点，如下图：

代码：

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

The Desire of Asuna

贪心的思想

简单的将两个合在一起需要1的花费，这是显然的。而将三个合在一起的时候，如果其中一个只有一个环，那么就只需要1的花费。从这样的情况中，我们能够预见，如果我们能将一个链作为连接的枢纽去连接其他链，并且将这个链使用干净，那么就能减少一次花费。我们使用的链的个数越多，则减少的花费就越多，所以我们应该从小到大尽量使用链。

如何排序

很多同学在大一的时候都学过冒泡，但是这是个很逗逼的排序方法。效率非常的低。有很多高效的算法，这里就不解释了。不过C++标准库STL给出了sort函数能够在$O(nlogn)$时间进行排序，如要排序数组a，长度为n，则用下面的语句就能从小到大排序：

1	sort(a,a+n);

代码：

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

人民币的构造

子问题1

我们尝试回答这样一个问题，给出$n$张不同的纸币，可以加减，不能使用相同的纸币，不考虑运算结果是否相同，但必须大于0的前提下，有多少种组合方式。
由于运算出来的结果必须大于0，并且加法满足交换律，那么这是个组合问题，而不是排列问题。
相当于我从$n$张纸币中，任取$k$张，并从大到小排好序，再往里面塞运算符号。
从中取$k$张的并塞运算符号的方案数是：
$$C^k_n2^{k-1}$$
所以总方案数应当是对$k$的求和：
$$\sum_{k=1}^nC^k_n2^{k-1}$$
由二项式定理，上式与下式等价：
$$\sum_{k=1}^nC^k_n2^{k-1}=\frac{(1+2)^n-1}{2}=\frac{3^n-1}{2}$$

子问题2

有子问题1我们知道了$n$张纸币最多能构成的方案数，但那是没有考虑运算结果是否相同，现在我们尝试回答这个问题，是否能找到$n$张纸币的组合使得上面算出的所有方案中，得到的结果都不一样。并且恰好覆盖$[1,\frac{3^n-1}{2}]$
这时候我们采取数学归纳法：
首先$n=1$的时候明显是成立的。
我们假设$n=k$的时候成立，即证明$n=k+1$的时候，恰好能够寻找到一个组合覆盖$[1,\frac{3^{k+1}-1}{2}]$
我们尝试这么解决这个问题，由于$n=k$的时候成立，那么我们沿用$n=k$的时候的组合方式，这时候，如果我们能够找到一张纸币满足规则，即能证明。
实际上由于我们能够使用$n=k$的时候的组合，所以我们是寻找一个$x$使得：
$$x-\frac{3^k-1}{2}\leqslant \frac{3^k-1}{2}+1$$
$$x+\frac{3^k-1}{2}\geqslant \frac{3^{k+1}-1}{2}$$
显然$x=3^k$，故证毕。

此题的结论

有了上面的论述，我们知道使用$n$张纸币，并且纸币的面值都是3的幂，那么就能最优的覆盖$[1,\frac{3^n-1}{2}]$的区间。所以我们只需要寻找这个$n$即可回答题目问题。

代码：

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

奇怪的四元数

非常好的一道题（尝试证明的话）

数形转换

首先让我们将$i,j,k$看作一组空间上的正交基，通俗的将就是$(1,0,0)$，$(0,1,0)$，$(0,0,1)$，如同下图：

符号叉是在干嘛

不难发现，符号叉和叉积是一样的，如果一个在$xOz$平面内的向量叉乘$j$，则相当于绕着原点在$xOz$平面逆时针旋转90度：

这是满足结合律的

想想便知道，如果我们尝试采取结合律，那么相当于先将旋转的轴先旋转，这样并不会影响最后的结果，请自行脑补这个过程。

自己乘自己

由于这是满足结合律的，自己乘自己，相当于先转90度，再转90度，所以应当取-1。

所以这道题

由上面的论述可知，如果我改变两个不同的向量的顺序，那么我们就能改变符号，但却无法改变叉乘出来的向量。这是由于，无论我们顺时针，还是逆时针转90度，始终会转到那个向量。
所以综上我们得出以下的结论

如果算出来的是1那么答案就是0
如果算出来是-1，那么除非全部一样，否则我们只用交换一组，答案是1（全部一样是-1）
如果算出来是向量，那么绝对不可能变成数字，答案是-1。

代码：

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

Memory

如果只有一个瓶子有问题

如果只有一个瓶子有问题该怎么办，答案非常简单，我们只需要将瓶子编号，并按照编号1，2，3……拿就好，最后结果中靠和总和的差值就能判断是第几个。

这道题

这道题有两个瓶子，但是算法的思想是不变的，我们只要能够最后能够从差值中得到足够的信息即可。即如果最后得到的差值唯一的确定两个数。
换言之，我们要保证任意取两个数，他们的和是唯一的。这时候，由于需要输出字典序最小的，所以我们从先使用最小的数，维护当前一共出现了哪些和，然后每次寻找最小的数来满足从未出现的和，再更新一下所有的和即可。

代码：

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