篝火晚会

(fire.pas/c/cpp)

【问题描述】
佳佳刚进高中，在军训的时候，由于佳佳吃苦耐劳，很快得到了教官的赏识，成为了“小教官”。在军训结束的那天晚上，佳佳被命令组织同学们进行篝火晚会。一共有n个同学，编号从1到n。一开始，同学们按照1，2，……，n的顺序坐成一圈，而实际上每个人都有两个最希望相邻的同学。如何下命令调整同学的次序，形成新的一个圈，使之符合同学们的意愿，成为摆在佳佳面前的一大难题。

佳佳可向同学们下达命令，每一个命令的形式如下：

(b1, b2,… bm -1, bm)

这里m的值是由佳佳决定的，每次命令m的值都可以不同。这个命令的作用是移动编号是b1，b2，…… bm –1，bm的这m个同学的位置。要求b1换到b2的位置上，b2换到b3的位置上，……，要求bm换到b1的位置上。

执行每个命令都需要一些代价。我们假定如果一个命令要移动m个人的位置，那么这个命令的代价就是m。我们需要佳佳用最少的总代价实现同学们的意愿，你能帮助佳佳吗？

【输入文件】
输入文件fire.in的第一行是一个整数n（3 <= n <= 50000），表示一共有n个同学。其后n行每行包括两个不同的正整数，以一个空格隔开，分别表示编号是1的同学最希望相邻的两个同学的编号，编号是2的同学最希望相邻的两个同学的编号，……，编号是n的同学最希望相邻的两个同学的编号。

【输出文件】
输出文件fire.out包括一行，这一行只包含一个整数，为最小的总代价。如果无论怎么调整都不能符合每个同学的愿望，则输出-1。

【样例输入】
4
3 4
4 3
1 2
1 2

【样例输出】
2

【数据规模】
对于30%的数据，n <= 1000；
对于全部的数据，n <= 50000。

【题解】

至此我就算做完了NOIP05提高组的全部四道题，发现除了第一题外其它题都不水，对于我这样的水平来说很值得一做。过河的状态压缩我想了好久；本题优化方法较过河简单，但也需要动动脑子；至于那个等价表达式则是典型的ws题：思想简单（特值法+用栈求表达式的值），但实现起来却比较繁琐，细节硕多，稍不留神就会出错，我前后一共提交了5次才AC（得到的分数分别是20、30、40、90、100）。还好这些题都是自己独立搞出来的。顺带一提，等价表达式取特值时并不像很多人说的要多个，一个足矣，当然不要取太特殊的，比如取a=1,-2,-3,0这样的就很容易被强数据阴掉，但要是取个a=-5.65742它不就没治了；同时B4数据中括号不匹配的情况。

当然这都是题外话，下面言归正传。

首先需要看到的是，虽然佳佳下达的命令形式很ws，但是在求总代价的时候却完全不需要管它。显然，在佳佳下达完一系列诡异的命令后，最后有几个人离开了原来的位置，这种情况下最小代价就是几（为什么？）。看清了这一点，问题就转化为：要使得所有人满意，最少需要让几个人离开原来的位置？

我们先考虑无解的情况。把每个人看成无向图中的节点，两人相邻则连一条边。当n个人以某种次序围坐成一个圈的时候，每个节点的度一定都是2。而这种状态一定是初始状态通过若干次次序调整能达到的，即一定有解。那么无解的情况就一定是，根据同学们的希望构图后有同学的度不为2。这样，我们只需要构图，然后看是否所有节点的度都为2就可以判断是否有解了。

如果有解，下面就需要计算最小代价了。对于我们构得的图，DFS(1)后一定得到唯一的一个序列。例如1,5,3,2,4。我们现在就需要比较它和初始状态1,2,3,4,5，看有几个人离开了原来的位置。但这个序列实际代表的是一个环，而且方向正反有两种（即1,3,5,2,4和4,2,5,3,1应该是等价的），我们就需要把初始序列正反分别“转”N次（即1,2,3,4,5; 5,1,2,3,4; 4,5,1,2,3; 3,4,5,1,2; 2,3,4,5,1 以及 5,4,3,2,1; 1,5,4,3,2; 2,1,5,4,3; 3,2,1,5,4; 4,3,2,1,5）和DFS得到的序列比较，看其中最少有几个位置上的人编号不相同，就得到了我们要求的最小代价。

DFS是O(N)的；旋转可以通过指针来实现，所以是O(1)的；每次比较是O(N)的，共进行2N次比较。因此总的复杂度是O(N^2)的。期望得分为30分（我没写过这方法哈）。

进行很多次旋转，每次都需要比较，这种方法实在太慢了，是整个算法的瓶颈。怎么改进呢？我们发现转来转去不管怎么转，任意两个人之间的相对位置关系在这过程中都不会变。于是想到做差。

1 5 3 2 4
- 1 2 3 4 5
————-
0 3 0 3 4  （如果差小于0则加上N=5）

这表示序列1,5,3,2,4不转动时1,3两个人在原来的位置上，转动3个位置后5和2两个人在原来的位置上，转动4个位置后只有4一个人会在原来的位置上。这就是说，1,5,3,2,4与1,2,3,4,5在旋转后最多有2个位置上的人编号相同，即最少有3个位置上的人编号不相同。同理：

1 5 3 2 4
- 5 4 3 2 1
————-
1 1 0 0 3  （如果差小于0则加上N=5）

1,5,3,2,4与5,4,3,2,1在旋转后最少有3个位置上的人编号不相同。

取其中的较小者（例子没举好，两个值相同了）为3，即最后要求的最小总代价为3。问题就算解决了。

算法流程总结如下：

1. 根据输入构图，要求每个节点度只能为2，否则无解；
2. dfs得到一个序列seq表示符合条件的环
3. （下标从1开始）
   令a[i]=seq[i]-i（若小于0则+N）
   a中最多有x个相等的值
   令b[i]=seq[i]-(N+1-i)（若小于0则+N）
   a中最多有y个相等的值
4. n-max(x,y)即为所求

改进后的算法复杂度为O(N)，实现起来很简单。期望得分为100。

#include <iostream>
#include <fstream>
#include <cassert>
using namespace std;
long N,seq[50001],p=1;
class{
	private:
		long nbr[50001][3];
		bool flag[50001];
		bool isnbr(long v1,long v2){
			for(int i=1;i<=nbr[v1][0];i++)
				if(nbr[v1][i]==v2)	return true;
			return false;
		}
	public:
		bool AddE(long v1,long v2){
			if(isnbr(v1,v2))	return true;
			else if(nbr[v1][0]==2||nbr[v2][0]==2)	return false;
			else{
				nbr[v1][++nbr[v1][0]]=v2;
				nbr[v2][++nbr[v2][0]]=v1;
				return true;
			}
		}
		void dfs(long i){
			assert(!flag[i]);
			flag[i]=true,seq[p++]=i;
			for(int j=1;j<=nbr[i][0];j++){
				if(!flag[nbr[i][j]]){
					dfs(nbr[i][j]);
					break;
				}
			}
		}
}G;
long solve(void){
	long cnt1[50001]={0},cnt2[50001]={0},ans=0;
	for(int i=1,a,b;i<=N;i++){
		a=seq[i]-i;
		if(a<0)	a+=N;
		b=seq[i]-(N+1-i);
		if(b<0)	b+=N;
		if(++cnt1[a]>ans)	ans=cnt1[a];
		if(++cnt2[b]>ans)	ans=cnt2[b];
	}
	return N-ans;
}
int main(){
	ifstream cin("fire.in");
	ofstream cout("fire.out");
	cin >> N;
	for(int i=1,nbr1,nbr2;i<=N;i++){
		cin >> nbr1 >> nbr2;
		if(!G.AddE(i,nbr1)||!G.AddE(i,nbr2)){
			cout << -1 << endl;
			return 0;
		}
	}
	G.dfs(1);
	cout << solve() << endl;
	return 0;
}

最后再给一个在vijos里看到的算法。我自己没有实现过，有兴趣的试试吧。

见过的最牛最简单的方法……

将此题转换为冒泡排序，记录下所有交换的次数和两数间的距离，加上就行了……—__—|||

具体是这样的，我们反向思维，本来是要求一个有序数列求出成为无序数列的代价，现在我们把无序数列（即目标数列）进行冒泡排序，然后……就是这样…… 看完之后，偶巨汗……

过河

(river.pas/c/cpp)

【问题描述】

在河上有一座独木桥，一只青蛙想沿着独木桥从河的一侧跳到另一侧。在桥上有一些石子，青蛙很讨厌踩在这些石子上。由于桥的长度和青蛙一次跳过的距离都是正整数，我们可以把独木桥上青蛙可能到达的点看成数轴上的一串整点：0，1，……，L（其中L是桥的长度）。坐标为0的点表示桥的起点，坐标为L的点表示桥的终点。青蛙从桥的起点开始，不停的向终点方向跳跃。一次跳跃的距离是S到T之间的任意正整数（包括S,T）。当青蛙跳到或跳过坐标为L的点时，就算青蛙已经跳出了独木桥。

题目给出独木桥的长度L，青蛙跳跃的距离范围S,T，桥上石子的位置。你的任务是确定青蛙要想过河，最少需要踩到的石子数。

【输入文件】

输入文件river.in的第一行有一个正整数L（1 <= L <=10^9），表示独木桥的长度。第二行有三个正整数S，T，M，分别表示青蛙一次跳跃的最小距离，最大距离，及桥上石子的个数，其中1 <= S <= T <= 10，1 <= M <= 100。第三行有M个不同的正整数分别表示这M个石子在数轴上的位置（数据保证桥的起点和终点处没有石子）。所有相邻的整数之间用一个空格隔开。

【输出文件】

输出文件river.out只包括一个整数，表示青蛙过河最少需要踩到的石子数。

【样例输入】

10

2 3 5

2 3 5 6 7

【样例输出】

2

【数据规模】

对于30%的数据，L <= 10000；

对于全部的数据，L <= 10^9。

【题解】

一看题，这无后效性和最优子结构也太明显了，随手就可以列出转移方程。令dp[i]表示处于i位置时，最少还要踩到几个石子（包括当前点）才能到达对岸。bridge[i]为点i处的石子个数（0或1）。则

当0≤i<L时：dp[i] = min{dp[i+j]} + bridge[i]   (S≤j≤T)

当i≥L时：dp[i]=0

问题的解即为dp[0]。

但是这样写完交上去最多只能得30分。直接硬搞，复杂度是O(L*(T-S))的，T-S最大为9，无关紧要，但是L的最大值则是令人发指的10^9（青蛙跳这么长距离不累死么 – -），不TLE……恐怕需要10年以后的CPU了。那怎么办呢？（思考过程也许比较繁琐，要结论请直接看倒数第5段）

数据范围往往是算法选择的最重要的提示。我们看到虽然L这么巨大，但是石子的总数却不超过100个。这说明什么？说明桥上必然有大段大段的无石子区间，而无石子区间的最大长度在极限情况下将接近10^9。即在跳跃中，青蛙经常会很郁闷地在巨长的无石子区间上跳啊跳啊，想踩个石子都踩不到。上面那个普通dp肯定会导致空白区间上大量的无必要决策而无谓耗费大量时间。要减少这种时间浪费，我们可以试图把大段的无石子区间等效转化为较短的无石子区间，从而使时间开销降至可承受范围。

首先考虑最简单的情况：S=T。这种情况下，这个诡异的青蛙只能跳固定的长度。而跳的起点是0位置，那么青蛙经过的就只有S（或者说T，一回事）的整数倍点。如果石子的位置为S的整数倍，那么青蛙就一定会踩到，否则一定踩不到。比如S=T=3，L=100，那么青蛙经过的点就为且仅为0，3，6，…，96，99。在21、27、33、66等处的石子就一定能踩到，而20、40、80、92等处的石子就踩不到。于是，当S=T时，我们只需要数位置为S整数倍的石子有几个就得到了答案，不需要进行上面说到的“等效转化”。

那如果S≠T呢？我们也从一个最简单的例子看起。假如S=5，T=6，青蛙从0位置开始跳，那么它可能到达的点是：

5，6，

10，11，12，

15，16，17，18，

20，21，22，23，24，

25，26，27，28，29，30，31，32，33，……

可以看到，这些点组成了一个个连续的区间，各相邻区间起点间的距离都是S=5，开始区间长度为2，然后长度变为3，4，然后完全连在一起，后面的位置都可达。如果桥上0~999都没有石子，1000处有一个石子，那么我们只关心青蛙是否选择跳到999，998，997，996，995，994这几个位置，因为青蛙在这段无石子区间上跳半天最后总会跳到这6个位置上，在无石子区间中不管怎么跳其实都无所谓。那么，我们完全可以无视25以后的数，把这段区间等效为0~25，以确保25以后所有位置都可达且有20~25这段连续区间来代替994~999这段等长的区间。这样，我们在这段无石子区间上的决策就大大减少了。

桥上的其他无石子区间是否可以如法炮制呢？答案是肯定的。对于以后任何一段长度大于25+6=31的无石子区间（这是采取“等效”措施的“门槛”），我们都可以把它的长度看成31。（25为什么要加上6呢？考虑一下，进入这段无石子区间后，青蛙开始往前跳的的起点，它可能不是区间本身的起点。）这样处理后，即使桥长度达到10^9，也可以在非常短的时间内出解。事实上，我们不仅可以把无石子区间长度等效为31，等效为36，121，500也都可以，只要长度比31大就行（当然“门槛”也要相应升高）。我们把这个等效区间的“最短”长度（本例中为31）称为“等效区间最短长度”。

下面推广。当S≠T时我们发现，在T不变的情况下，T-S越大（即S越小），等效区间最短长度越短。T-S不变的情况下，T越大，等效区间最短长度越长。那么对于题目给出的数据范围，S=9，T=10时（满足T-S最小且T最大）得到最大的“等效区间最短长度”为100。对于其他的S和T，我们不需要专门计算它们对应的等效区间最短长度，直接采用100这个值就可以了。

综上，若S=T，我们直接数位置能被S整除的石子个数；若S≠T，如果某无石子区间长度大于100，则等效为100，否则不变，然后再dp。

至于为什么有同学取比100小的数也AC了，我觉得（不一定对哈，没验证）应该是数据弱了。经实验，即使取20也可以AC，取10也才WA一个点。

对于等效区间最短长度的这番计算其实完全不必要。比赛时最好的方法是：取时间复杂度可接受的最大值……这样最省事。

上面可能做麻烦了，欢迎提供简明解法，谢谢。

最后说点题外话。这题我调了一晚上，郁闷死了。最后发现问题竟然是：石子位置没有按照升序排列，我却想当然这么处理了，结果一个点都过不去……

代码如下：

#include <iostream>
#include <fstream>
#include <bitset>
#include <cstdlib>
using namespace std;
unsigned long L_orig,L,S,T,M,pos[102],dp[12000],ans;
bitset<12000> bridge,flag;
long memo(long i){
	if(i>=L)	return 0;
	if(flag[i])	return dp[i];
	flag[i]=1,dp[i]=INT_MAX;
	for(int j=S;j<=T;j++)
		if(dp[i]>memo(i+j))
			dp[i]=memo(i+j);
	dp[i]+=bridge[i];
	return dp[i];
}
inline int cmp(const void *a,const void *b){
	return *(long*)a-*(long*)b;
}
int main(){
	ifstream cin("river.in");
	cin >> L_orig >> S >> T >> M;
	if(S==T)
		for(int i=1,tmp;i<=M;i++){
			cin >> tmp;
			if(tmp%S==0)	ans++;
		}
	else{
		pos[M+1]=L_orig;
		for(int i=1,counter=0;i<=M;i++)	cin >> pos[i];
		qsort(pos,M+2, sizeof(pos[0]),cmp);
		for(int i=1;i<=M+1;i++){
			if(pos[i]-pos[i-1]-1<=100)	L+=pos[i]-pos[i-1];
			else	L+=100;
			bridge[L]=1;
		}
		ans=memo(0);
	}
	ofstream fout("river.out");
	fout << ans << endl;
	return 0;
}