[国家集训队2011]刷题计划 解题报…

题目:

http://cogs.pro/cogs/problem/problem.php?pid=1883

为了提高自己的实力,gx想要制定一个合理的刷题计划。这里我们用实数来表示题目的难度,并且把刷题计划中由题目难度组成的序列称为刷题序列。gx刷题最喜欢循序渐进的方式,最理想的情况莫过于刷题序列是个等差数列了。但是这很难做到,于是我们定义一个刷题序列a的偏离值 ,其中L是给定的一个常数。

现在gx的老师已经布置给了他n道必做题,同时他还有空余时间从OJ上找m道题目来刷。他不希望改变这n道必做题的相对顺序,但是选做题的难度以及在数列中的位置都是任意的(OJ上的题目太多了,随你怎么挑)。

gx希望你帮他设计一个刷题序列,使得该序列的偏离值最小。
分析:
其实这道题和“骑行川藏”很像,但它是11年的,当时后者还没出来……
首先明确一下题意。假设我们要在a[i]和a[i+1]之间放一些题,那必然是这样的:
[国家集训队2011]刷题计划 <wbr>解题报告” title=”[国家集训队2011]刷题计划 <wbr>解题报告”></a><br />
新放进去这些题目的难度一定均分了a[i]~a[i+1]之间的部分(图画的不太平均,不要在意这些细节)。</div>
<div>为什么呢?</div>
<div>
</div>
<div>假设某一段的长度为c,我们试图在中间加一道题,把它分成两段a,b,自然a+b=c。</div>
<div>其代价为:</div>
<div><a target=[国家集训队2011]刷题计划 <wbr>解题报告” title=”[国家集训队2011]刷题计划 <wbr>解题报告”></a><br />
a+b=c,所以当a=b时a^2+b^2最大,代价最小。</div>
<div>所以相邻两段相等时代价最小。用调整法可以证明,在a[i]~a[i+1]之间放题一定是均分才能使代价最小。</div>
<div>(当然你也可以用柯西不等式证明)</div>
<div>
</div>
<div>所以题目就变成了:将这N-1段分别进行均分,使得新插入的点数之和<=M,并且代价最小。</div>
<div>(至于M道题中没有用上的部分,可以接在最后一道后面成为等差数列,其代价为零)</div>
<div>
</div>
<div>像“骑行川藏”一样,我们来考虑每一段的代价。</div>
<div>假设我们把长度d的一段(注意d可能为负)均分成了k段,代价是:</div>
<div><a target=[国家集训队2011]刷题计划 <wbr>解题报告” title=”[国家集训队2011]刷题计划 <wbr>解题报告”></a></p>
<p>如果分成k+1段,代价是:</p></div>
<div><a target=[国家集训队2011]刷题计划 <wbr>解题报告” title=”[国家集训队2011]刷题计划 <wbr>解题报告”></a></p>
<p>因此,从k段变成k+1段会让代价增加:</p></div>
<div><a target=[国家集训队2011]刷题计划 <wbr>解题报告” title=”[国家集训队2011]刷题计划 <wbr>解题报告”></a><br />
随着k增加,这个值会逐渐增大(也就是说对代价的改进值越来越小)。</div>
<div>
</div>
<div>所以可以设想出一个这样的算法:一开始每一段都分成了1份。然后对于M次操作,每次选取增量最小的(也就是改进值最大的)一段,在其中多加一个点。</div>
<div>
</div>
<div>但是M非常大,怎么办?</div>
<div><a target=[国家集训队2011]刷题计划 <wbr>解题报告” title=”[国家集训队2011]刷题计划 <wbr>解题报告”></a></p>
<p>
假设一开始增量的分布是这样的(y坐标代表增量的值,蓝线是0)</div>
<div>在结束时,增量可能是这样的:</div>
<div><a target=[国家集训队2011]刷题计划 <wbr>解题报告” title=”[国家集训队2011]刷题计划 <wbr>解题报告”></a><br />
由于每次都让最小的增量变大,所以大致是这样的,所有增量都不小于某个值。增量的变大是不连续的,所以可能会在红线之上。</div>
<div>
</div>
<div>算法就很好办了:二分结束时的最小增量,然后计算每一段被分成了多少份。好像没什么奇怪的细节……</div>
<div>
</div>
<div>
</div>
<div><strong>代码:</strong></div>
<div><a target=

http://cogs.pro/cogs/submit/code.php?id=143714

[CF 325E]The Red Button解题报告

题意:

给一个0~N-1的图,点i向点(2*i)%N和点(2*i+1)%N连有向边。求从0到0的哈密尔顿回路。

(怎么又是一道哈密尔顿回路)


做法:

首先明确一点:如果N是奇数那么无解。
为什么无解呢?原因很简单:0的唯一入边是int(N/2),但N-1的唯一入边也是int(N/2)。例如,当N=5时,0的唯一入边是2(0->0的自环不算),而4的唯一入边也是2(4->4的自环不算)。那么问题来了,哈密尔顿回路里时2->0还是2->4呢……显然都不行,所以无解。

然后看N是偶数的情况。
下面为了方便起见,一律省略%N。例如,当我说点X+1的时候,我其实想说的是(X+1)%N。
这时候有一个性质:X和X+N/2连的两条出边都是一样的。为什么呢?这是显然的……都是2X和2X+1.
那么我们先做一个简单的DFS:不走访问过的的点,尽量沿着2X这条边走,不行就沿着2X+1走。
例如当N=8的时候:
从0开始:0->1->2->4->0
从3开始:3->6->5->3
从7开始:7->7
形成了三个环。那么问题来了:一定成若干个环吗?
官方题解中不加证明地使用了“一定成环”的条件。我们在这里证明一下:

假设当前有若干个环和一条链(当前DFS的链)。链是从h开始走到x,我们现在在x。
如果x的某条出边能走,那当然很好,我们接着走就行了。
但是问题来了——如果duang的一声,我们突然发现,x的两条出边指向的点都被访问过了,怎么办?
x的两条出边分别指向2x和2x+1.而除了x,还有什么点能指向这两个点呢?x+N/2.
x+N/2在上面所说的,“若干个环和一条链”中显然只能出现一次,假设它的后继是2x。
那么2x+1是怎么被访问的呢?作为x的后继吗?这不科学,因为x之前未出现过。
所以真相只有一个——2x+1=h。即,它不是被访问,而是被作为DFS的起点遍历到的。
那么x->h,就形成了一个环。然后我们愉快地再找下一个未被访问过的点,就找到了一个新的h,算法继续。
综上,最终的结果一定是若干个环。

如果只有一个环,那当然很好,这就是我们要找的哈密尔顿回路了。
如果有不止一个环呢?官方题解中说,必然有某个数x,使得x和x+N/2在不同的环上。
官方题解把这个结论的证明作为练习留给了读者……_(:з」∠)_我们在此来证明一下。

反设结论不成立,即所有的x和x+N/2所在环都相同。
我们从某个x开始。假如x和x+N/2在同一个环A上。
由于它们的出边都是2x和2x+1,于是2x和2x+1都在环A上。
同理,4x和4x+1和4x+2和4x+3都在环A上。
同理,8x~8x+7都在环A上。
……
这样的“连续段”的长度最终会不小于N,这时我们就得到,0~N-1全部在环A上。
也就是说A是唯一的环,和环数>=2矛盾。
所以必然有某个x和x+N/2在不同的环上。

现在我们得到了若干个环,还有某个x使得x和x+N/2在不同的环上。接下来怎么办呢?
假设x的后继是2x,那么x+N/2的后继必然是2x+1.
我们只需要简单地将x的后继改成2x+1,x+N/2的后继改成2x,就能将这两个环合并起来。
以上面的N=8为例:1在第一个环上,而5在第二个环上。1的后继是2,而5的后继是3.
我们将1的后继改成3,同时5的后继改成2,就变成了:
0->1->3->6->5->2->4->0
这样环的个数就减一了。
如此往复持续下去,直到只剩下一个环,就形成了我们想要的哈密尔顿回路。

那么问题来了:怎么写这个算法呢?
官方题解中给的算法是DFS:如果在x处走了2x,DFS后发现x+N/2没有被访问,就把x的后继改成2x+1.
是不是看上去有点奇怪……其实有一种非常简单的写法,其主要代码是这样的:
void DFS(int x){
	vis[x]=true;
	if(!vis[(x*2)%N]) DFS((x*2)%N);
	if(!vis[(x*2+1)%N]) DFS((x*2+1)%N);
	ans.push_front(x);//在实际代码中其实是push_back,最后倒序输出
}

其原理是这样的:假如在成功DFS(2x)之后,发现2x+1仍然没有被访问,那么显然x+N/2在另外一个环中。设2x在环A中,2x+1在环B中。我们直接沿着2x+1走,其效果就是沿着B走了一圈,由于我们从x+N/2的后继开始走,所以最终一定以x+N/2结束。走完之后,ans数组中存放的就是:先沿着B走一圈,再接着在A上走。这时将x放在ans的开头,就起到了前面所说的,切换x的后继以减少圈数的目的。

以N=8为例:
三个环如下图:

DFS的过程如下图:

虚线代表“被替换的部分”。最开始0->1->2->4走了一圈,走完ans={4},回溯到2时发现5能接着走,于是就走了5->3->6,走完ans={6,4},回溯到3时发现7能接着走,于是走了7,走完ans={7,6,4},然后回溯到3,ans={3,7,6,4},回溯到5,ans={5,3,7,6,4},回溯到2,ans={2,5,3,7,6,4},回溯到1,ans={1,2,5,3,7,6,4},回溯到0,ans={0,1,2,5,3,7,6,4}。

代码:

#include
#include
#include
#include
#include
#include
using namespace std;
const int SIZEN=100010;
vector ans;
int N;
bool vis[SIZEN]={0};
void DFS(int x){
	vis[x]=true;
	if(!vis[(x*2)%N]) DFS((x*2)%N);
	if(!vis[(x*2+1)%N]) DFS((x*2+1)%N);
	ans.push_back(x);
}
int main(){
	freopen("theredbutton.in","r",stdin);
	freopen("theredbutton.out","w",stdout);
	scanf("%d",&N);
	if(N&1){
		printf("-1\n");
	}
	else{
		DFS(0);
		reverse(ans.begin(),ans.end());
		ans.push_back(0);
		for(int i=0;i

TopCoder SRM496 Div1 YetAnotherHamiltonianPath解题报告

题意:

有N<=50个城市,每个城市有一个名字(一个字符串)。从城市s走到城市t的代价是:|s|^2+|t|^2-LCP(s,t)^2.其中LCP(s,t)指s和t的最长公共前缀长度。求一条开始于0号城市,结束于1号城市的最短哈密尔顿路径。


分析:

出于方便起见,我们将问题转化成“求一条最短的哈密尔顿回路,使得回路中0,1号城市相邻”。
先不考虑这个相邻,单看“求一条最短的哈密尔顿回路”:

首先我们按照城市名字的首字母将其分类,并将同一类的放在一起。

例如:城市名可能是“asdf,aqwe,bpdr,btr”,那么”asdf”和”aqwe”就是同一类,”bpdr”和”btr”是同一类。

显然,在最短的哈密尔顿回路中,同一类一定是放在一起的。而对于同一类,我们又可以按照第二个字母将其分类……如此递归下去。

例如:有五个城市,名称是”aab”,“ccf”,”ab”,“aac”,”cd”。

第一层划分:{ “aab” , “ab” , “aac” } , { “ccf” , “cd” }

第二层划分:{ { “aab” , “aac” } , { “ab” } } , { { “ccf” } , { “cd” } }

第三层划分:{ { { “aab” } , { “aac” } } , { “ab” } } , { { “ccf” } , { “cd” } }

这样的结果:”aab” -> “aac” -> “ab” -> “ccf” -> “cd” -> “aab”就一定是一个最短的哈密尔顿回路。

在讨论如何让0和1相邻之前,先看一下如何实现这个“划分”的细节;

step 1:设i,j两个指针,让i从”aab”开始扫描。

step 2:让j指向i的下一个位置,顺序遍历后面的城市名称,如果首字母和 i 指向的城市相同,就将它和 j 指向的城市交换,并把 j 指针加1.

step 3:如此扫描一遍后,数组变成了{“aab”,”ab”,”aac”,”ccf”,”cd”},j指向”ccf”。

step 4:将i赋值为j,回到step 2进行下一次循环。

如何让0和1相邻呢?设0号城市的名字是S0,1号城市的名字是S1.

遵循三个原则:①如果当前这一类中既有S0又有S1,就设法让S0和S1相邻。②如果当前这一类中只有S0没有S1,就设法把S0排在最后。③如果当前这一类中只有S1没有S0,就设法把S1排在最前。

根据上面所述的划分细节不难看出,在①中S0和S1所在的子集一定相邻。②和③保证:S0在当前子集的最后,S1在当前子集的最前。

例如:在上例中S0=”aab”,S1=”cd”。

1:划分{“aab”,“ccf”,”ab”,“aac”,”cd”}:根据①我们将集合改成{“aab”,”cd”,”ccf”,”ab”,”aac”},划分成:{{“aab”,”ab”,”aac”},{“cd”,”ccf”}},”aab”和”cd”所在的子集相邻。

2:从1处递归划分{“aab”,”ab”,”aac”}:根据②我们将集合改成{“ab”,”aac”,”aab”},划分成:{{“ab”},{“aac,aab”}}。

3:从2处递归划分{“aac”,”aab”}:根据②,集合还是{“aac”,”aab”},划分成:{{“aac”},{“aab”}}。

4:从1处递归划分{“cd”,”ccf”}:根据③,集合还是{“cd”,”ccf”},划分成:{{“cd”},{“ccf”}}。

5:所有划分完成,数组变为:{“ab”,”aac”,”aab”,”cd”,”ccf”}。其中S0和S1相邻,并且是一个最短的哈密尔顿回路。

最后求一遍哈密尔顿回路的总长,减去S0->S1的花费即可。这道题数据范围很小,基本不用考虑时间复杂度。


代码:

#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
using namespace std;
#define sqr(x) ((x)*(x))
int LCP(const string &s,const string &t){
	int i=0;
	while(i=s.size()) return '\0';
	else return s[i];
}
void place(vector &s,int l,int r,const string &t,int k){
	for(int i=l;i &s,int l,int r,int p){
	if(r-l<=1) return;
	int h=-1,t=-1;
	for(int i=l;i S){
		head=S[0];
		tail=S[1];
		arrange(S,0,S.size(),0);
		int ans=0;
		for(int i=0;i