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

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

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

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

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

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

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

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

4.1中的奶牛家秘术和Fence Rails都是要加好几个剪枝才可以AC的问题

搜索对象:每个栅栏(rail)对应那个Board(可能的深度太大而答案很可能在很浅的地方,所以迭代深度去找(DFSID),如果某个深度找到一个可行解,立刻退出,再搜索下一个深度)

一般优化都可以从以下3点考虑:

1.可行性剪枝   如果我们预料到某种情况无论再怎么搜索也得不到可行解,那就直接退出

2.最优化剪枝   如果我们预料到某种情况无论再怎么走索也得不到比当前最优解更优的解,那也直接退出

3.搜索顺序      良好的搜索顺序会更快的找到答案

其他技巧因问题而不同

那么Fence Rails可以这样剪枝:

1.可行性:     如果当前剩下的不可用的Board(即不能再切出rails的board)的和比board总面积减去rails的总面积还大,那肯定不可行(通俗地讲就是不能再装Rails的面积比装满所有rails剩下来的面积大)

2.搜索顺序:  容易想到,如果刚开始的时候就用大的rail塞到较小的board中,很快就能找到可行解

3.注意有很多重复,考虑到重复的元素位置不同没有影响,所以如果上一个元素和该元素相同,那么所在的board就直接从上一个开始枚举

这样就可以AC了

我的代码(有些慢):

1.构图

2.求出所有可能的满足拓扑序的答案并输出

1.的关键是题目的条件(每条边至少能看到1点)

2.这时用DFS求拓扑序好像就不管用了,所以采用暴力搜索去寻求答案,并满足拓扑序,

那就是记录一下每个矩形的出度,如果出度为0,说明当前可以继续搜(没有矩型被他压着),继续向下搜索,并删除该矩形(把压着他的矩形的出度-1),然后递归到下一层再找出度为0的矩形,这样就可以了.

描述

看下面的五张 9 x 8 的图像：

........   ........   ........   ........   .CCC....
EEEEEE..   ........   ........   ..BBBB..   .C.C....
E....E..   DDDDDD..   ........   ..B..B..   .C.C....
E....E..   D....D..   ........   ..B..B..   .CCC....
E....E..   D....D..   ....AAAA   ..B..B..   ........
E....E..   D....D..   ....A..A   ..BBBB..   ........
E....E..   DDDDDD..   ....A..A   ........   ........
E....E..   ........   ....AAAA   ........   ........
EEEEEE..   ........   ........   ........   ........

   1          2           3          4          5 

现在，把这些图像按照 1—5 的编号从下到上重叠，第 1 张在最下面，第 5 张在最顶端。如果一张图像覆盖了另外一张图像，那么底下的图像的一部分就变得不可见了。我们得到下面的图像：

 .CCC....
 ECBCBB..
 DCBCDB..
 DCCC.B..
 D.B.ABAA
 D.BBBB.A
 DDDDAD.A
 E...AAAA
 EEEEEE.. 

对于这样一张图像，计算构成这张图像的矩形图像从底部到顶端堆叠的顺序。

下面是这道题目的规则：

• 矩形的边的宽度为 1 ，每条边的长度都不小于 3 。
• 矩形的每条边中，至少有一部分是可见的。注意，一个角同时属于两条边。
• 矩形用大写字母表示，并且每个矩形的表示符号都不相同。

PROGRAM NAME: frameup

INPUT FORMAT(file frameup.in)

OUTPUT FORMAT

SAMPLE OUTPUT (file frameup.out)

按照自底向上的顺序输出字母。如果有不止一种情况，按照字典顺序输出每一种情况（至少会有一种合法的顺序）。

SAMPLE INPUT (file frameup.in)

9 8
.CCC....
ECBCBB..
DCBCDB..
DCCC.B..
D.B.ABAA
D.BBBB.A
DDDDAD.A
E...AAAA
EEEEEE.. 

SAMPLE OUTPUT (file frameup.out)

EDABC

priority_queue：优先队列

顾名思义，这个东西可以用于存放单调的数据，后面将会看到用于优化Dijkstra

有3个类函数：

void push(元素类型   变量)

void pop()

int top()

int size()

bool empty()

分别是：

• 加入类型是XXX的变量XXX
• 弹出队列首元素
• 取优先队列的队首元素的值
• 返回队列元素数量
• 查看队列是否为空

定义：

1. priority_queue <数据类型，容器类型，元素比较方式>
2. priority_queue <数据类型，容器类型>
3. priority_queue <数据类型>

数据类型：int,double.....

容器类型：vector（默认），deque，但不能是list

元素比较方式：less（默认，不上升序），greater（不下降序）

比如要定义一个元素值为整数，容器为vector<int>的不下降序的优先队列PQ：

priority_queue <int,vector<int> ,greater<int> >PQ

如果是第3种定义方式，容器默认为vector，比较方式默认是less（第二种的默认比较方式也是less）

实用的例子：

堆优化的Dijkstra算法，写出堆不难，但麻烦，如果想更快的写出高效的Dijkstra，用priority_queue就很不错：

#include <queue>
priority_queue <pair<int ,int>,vector<pair<int ,int> >,greater<pair<int,int> > > PQ;

void Dijkstra()
{
	while(!PQ.empty())
		PQ.pop();
	MC[1]=0;
	PQ.push(pair<int,int>(MC[1],1));
	while(!PQ.empty())
	{
	int Index=PQ.top().second;
		PQ.pop();
		if(!flag[Index])
		{
			flag[Index]=true;
			for(Node *p=last[Index];p;p=p->Prev)
				if(!flag[p->Name] && MC[p->Name]>MC[Index]+p->Dis)
				{
					MC[p->Name]=MC[Index]+p->Dis;
					PQ.push(pair<int,int>(MC[p->Name],p->Name));
				}
		}
	}
}

MC是最小花费

flag标志数组

last 邻接表

更详细的信息请参阅：

http://www.cplusplus.com/reference/queue/priority_queue/priority_queue/

参考

cplusplus.com

http://blog.chinaunix.net/space.php?uid=533684&do=blog&cuid=2615612

相对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个集合.

炮兵阵地

炮兵阵地

方程的解数

方程的解数

陨石的秘密

陨石的秘密

hey!

hey!

这是我第一次使用这个网站!

#include <fstream>
using namespace std;
ifstream fin("try.in");
ofstream fout("try.out");

int main()
{
    fout<<"Just Have A Try!");
    return 0;
}