p1873 [coci 2011/2012 #5] eko / 砍树

### 回答1：
题目描述：

Eko 有一排树，每棵树的高度不同。他想要砍掉一些树，使得剩下的树的高度都相同。他希望砍掉的树的高度尽可能地少，你能帮他算出最少要砍掉多少棵树吗？

输入格式：

第一行包含两个整数 N 和 M，分别表示树的数量和 Eko 希望的树的高度。

第二行包含 N 个整数，表示每棵树的高度。

输出格式：

输出一个整数，表示最少要砍掉的树的数量。

输入样例：

9 5
2 3 4 7 8 9 10 11 12

输出样例：

3

解题思路：

二分答案

首先，我们可以发现，如果我们知道了 Eko 希望的树的高度，那么我们就可以计算出砍掉多少棵树。

具体来说，我们可以遍历每棵树，如果它的高度大于 Eko 希望的树的高度，那么就将它砍掉，否则就保留它。

然后，我们可以使用二分答案的方法来确定 Eko 希望的树的高度。

具体来说，我们可以将树的高度排序，然后二分一个可能的 Eko 希望的树的高度，然后计算砍掉多少棵树，如果砍掉的树的数量小于等于 M，那么说明 Eko 希望的树的高度可能更小，否则说明 Eko 希望的树的高度可能更大。

最后，我们可以得到最少要砍掉的树的数量。

时间复杂度：O(NlogN)。

参考代码：

### 回答2：
这道题目是一道模拟题，需要模拟机器人的移动过程以及得出最终机器人的位置和朝向。首先需要明确机器人的起始位置以及朝向，其次需要读取输入的指令，根据指令逐步移动机器人，并顺便判断是否会越界或者碰到障碍物。最后输出最终机器人的位置和朝向。

在本题中，需要按照从西向东、从北向南、从东向西、从南向北的顺序判断机器人的朝向。为了方便表述，我把机器人的朝向表示为0、1、2、3，分别代表从西向东、从北向南、从东向西、从南向北。

具体地说，机器人按照指令逐步移动时需要分情况讨论，比如：

1.当前机器人朝向为0，即从西向东：

若指令为F，则x坐标+1，但需要判断是否越界或者碰到障碍物。

若指令为L，则朝向变为3。

若指令为R，则朝向变为1。

2.当前机器人朝向为1，即从北向南：

若指令为F，则y坐标-1，但需要判断是否越界或者碰到障碍物。

若指令为L，则朝向变为0。

若指令为R，则朝向变为2。

3.当前机器人朝向为2，即从东向西：

若指令为F，则x坐标-1，但需要判断是否越界或者碰到障碍物。

若指令为L，则朝向变为1。

若指令为R，则朝向变为3。

4.当前机器人朝向为3，即从南向北：

若指令为F，则y坐标+1，但需要判断是否越界或者碰到障碍物。

若指令为L，则朝向变为2。

若指令为R，则朝向变为0。

最后输出最终机器人的位置和朝向即可。

在编写程序时需要注意判断边界和障碍物，以及要用scanf读取输入，不要用C++的cin，否则会TLE。此外，由于本题没有给出边界和障碍物，需要自己设置。最后，本题的思路不难，但是需要认真仔细地处理各种情况，多测试几组数据找出程序的漏洞，这样才能通过本题。

### 回答3：
本题为一道组合数学题，需要运用排列组合知识进行分析。

题目要求将n个方块填入3*3的网格中，每个方块可以是红色、绿色或蓝色的一个。要求每行、每列和对角线上的方块颜色都不相同。求方案总数。

首先考虑对第一行进行颜色选取。由于第一行每个位置的颜色都不影响其他行和列，故第一行的颜色选取不影响总方案数。所以假设第一行颜色已经确定，考虑第二行的颜色选取。第二行中各位置的颜色受到第一行的限制，只有第一行某位置颜色的补集才能选取。例如，若第一行第一个位置是红色，那么第二行第一个位置不能选取红色。因为每行颜色不能相同，所以第二行受到第一行限制的位置只有3个。第三行同理，由于前两行的限制，只有2个位置可选。做完颜色选取后，再将每行的方块进行排列，此时我们可以使用错排公式得到方案数：

D(n) = n!(1 - 1/1! + 1/2! - 1/3! + ... + (-1)^(n)/n!)

最终，方案总数即为每个第一行颜色选取方法下的错排方案数之和。按题意枚举第一行的颜色，就可以得到最终的方案总数了。

总结一下，本题所需要的知识点为：错排公式、颜色限制对组合数的影响、暴力枚举法。