2013年省选赛结束

21 4

Posted by: Qheldiv in: 事件与轶事

又是一年省选时，昨天比赛了一天，比较累，但是结局还好。

比赛的成绩wyfenger第一，我第二，认识的人中进入省队的还有省实验中学的3个（王梦迪（初三），王宇飞，常跃如），郑外的陈科。

结果出来前比较忐忑，因为毕竟这可能是OI生涯的结尾，不过即使可以参加Noi，也只剩下3个月了。

上午的比赛

前两题很简单，简直是NOIP普及组水平，以至于刚开始看到第2题还以为是最小费用最大流，但问题是没有搞到200的人很多，也许河南真的是没有多少人好好学Oi吧！至于第三题，是和牛棚的灯一摸一样原题！（比赛前我还看到了这题，但是没有写）其实我已经写出 Gauss-Jordan消元法，但是没有考虑多解的情况，检查了半天不对，所以最后还是写了个暴力，总共230

下午的比赛

下午的比赛比上午难一些，第一个问题可以用线段树Ac，但是形式不太一样，不过不是很难想，想了10分钟，加之看到第二题像是个恶心的搜索……所以就决心搞第一题，写了1h，调试+对拍了1.5h（手动对拍），最后还好100分，否则就很悲剧了，（无力吐槽这题的数据，最裸的暴力算法就可以搞到60分）

而第二题其实可以用最短路做，甚至也有模拟Ac的办法，而我在第一题上花了大部分时间，最后仅仅交了个骗分（输出-1能得30……）

总共130

去年省选比今年质量高多了，难度也大多了。。

今后恐怕就不能用win8了，

第一

还有大约5天就到期了

第二，Noi是在Linux下的，所以只能乖乖的用Ubuntu了。

时间已经很少了，水平还差得很远。

[NOI 2005]维护序列

20 2

Posted by: Qheldiv in: 题解

中午的时候突然想起NOI2005的维护序列,于是就写了8小时搞出来,3小时写,5小时调,效率真够低的...

这是个很麻烦的问题,我用Splay解决的,首先题目要求的操作有6种,

其中翻转,求最大和比较麻烦.

对于insert操作,效仿NOI2003的文本编辑器,我直接建了一颗几乎平衡的二叉树,然后塞到Splay中相应的位置(这样快一点点)
delete操作比较简单,找到相应的子树,删去即可.
MakeSame操作:用delta表示要改变成什么,并传递这个值,每次改变delta都覆盖原有的,注意,如果没有delta值,是不能传递或是更改的,否则就会出错,所以我用了一个极小的常量NA表示没有delta值
reverse操作:刚看过去感觉有点奇怪,稍稍思考一下发现reverse操作可以像MakeSame操作那样传递(翻转操作其实就是某棵树中所有的子树位值取反一下(左子树放右边,右子树放左边)),然后向下传递就行了
GetSum也好做,用Sum记录该子树的和,每次MakeSame或者是进行Splay操作后维护一下就好了(Sum=左子树的Sum+右子树的Sum+1)
MaxSum这个比较不好做,但是之前遇到在过线段树上比这个还要麻烦的问题(求某区间所有子串和的和...),就很容易想到了,即LMax表示某子树构成的序列中最大的前缀和是多少RMax表示最大的后缀和是多少,Max_Sum就表示最大子串和是多少,Max_Sum根据LMax和RMax算出就行了

Splay的两个维护函数:deliver()和maintain()

deliver()负责传递树根信息(翻转和MakeSame)

maintain()负责维护Splay的正确性(重新计算相关信息如Sum,LMax...)

我写了6K的代码,花了我很长的时间,然而并没有结束,因为明天还有继续优化代码和算法结构,以便下次再遇到能很快的写出.

NOI2001 全部题解

6 1

Posted by: Qheldiv in: NOI题解

相对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即要求的最小值。