相对1999年和2000年的问题我花了更少的时间（其实是更集中精力）

以下排列大约是按难度排的。

“聪明的打字员”是个简单的广度有限搜索，是个基础的问题，但是我花了不少时间。。。

“反正切函数的应用”有数学方法，但是我时暴力过得

“食物链”要用到并查集，算是一个小小的变形。

“炮兵阵地”是状态压缩的动态规划的典型问题，很早之前就写过了

“方程的解数”需要想到技巧的搜索，是这类方程类搜索的典型，没有想全面（只想到了将正负系数分开。。）。

“陨石的秘密”稍复杂的动态规划，我没有想出来，看Byvoid的题解才想出，不过我加以优化（降维）才通过了所有的测试点。

聪明的打字员

聪明的打字员

简单的搜索，需要记录状态（可以用平衡树也可以用hash（这个属于直接寻址表）），然后就没了

反正切函数的应用

反正切函数的应用

可以用高效率的数学方法,也可以朴素:

#include <fstream>
using namespace std;
ifstream fin("arctan.in");
ofstream fout("arctan.out");
long long A,Min=123456789;
int main()
{
	fin>>A;
long long B,C;
	for(B=1;B<=1234567;B++)
	{
		if(B==A)continue;
		if((A*B+1)%(B-A)!=0)continue;
		C=(A*B+1)/(B-A);
		if(C<=0)continue;
		Min=min(Min,B+C);
	}
	fout<<Min<<endl;
	fin.close();
	fout.close();
	return 0;
}

即枚举b的数值,然后c的值就是(A*B+1)/(B-A) 检查该值是否合法(是非负整数),如果合法,就更新Min变量记录的最小值(用b+c的值更新)

数学方法:

 

根据题中公式，可以推出 a=(b*c-1)/(b+c)。由此得出c=(a*b+1)/(b-a)。因为b,c均为正整数，所以b>a。

我们要求b+c最小，设函数y=f(x)，自变量x为b的取值，但不限于正整数。则有

• f(x) = (a*x+1)/(x-a) + x = a + ((1+a^2)/(x-a)) + x

对f(x)求导，得导数

• f’(x)=1-(1+a^2)/(x-a)^2

f’(x)=0 得出 x = a+(a^2+1)^0.5 或 x = a-(a^2+1)^0.5，由于x>0，取 x = a+(a^2+1)^0.5。

且x > a+(a^2+1)^0.5时，f’(x)>0，x < a+(a^2+1)^0.5时，f’(x)<0，所以当x = a+(a^2+1)^0.5时，f(x)取得最小值。

由于b和c都是正整数，只需在x一边寻找距离x最近的整数b,c，b+c即要求的最小值。

该段转自http://www.byvoid.com/blog/noi-2001-solution/ ,版权为BYvoid所有.

食物链

食物链

并查集,关于并查集这里不说了,以下内容均为带路径压缩的树形并查集

每个元素都有3个信息,分别表示

1. 同类的集合
2. "吃我的东西"的集合
3. "我吃的东西"的集合

在去除

1. 当前的话中X或Y比N大，就是假话；
2. 当前的话表示X吃X，就是假话。

这两种假话后,剩下来就是要去除前后矛盾的话,输入关系要么是同类,要么是吃与被吃,那么就有两种合并模式:

同类:1对1合并,就是两个元素的3个信息代表的集合,一一合并,同类和同类合并,吃我的东西之间合并,我吃的东西之间合并

吃与被吃:错位合并,比如1吃2,1的同类合并到2的"我吃的东西"的集合,1的第二个信息代表的集合合并到2的第一个信息(同类)代表的集合,1的第三个信息代表的集合合并到2的第二个信息代表的集合(这么说挺麻烦的,其实意思很简单了)

总的来说就是:该问题中每个元素的合并是要合并3个集合.

炮兵阵地

炮兵阵地

方程的解数

方程的解数

陨石的秘密

陨石的秘密