浅谈Codeforces round 217 Summer Reading的两种解法:DP与构造

这是在codeforces上参加的第二场比赛了,虽然最后测评的结果显示在房间排名是第二名,但是与第一名的差距之大却是很难看的。这里,简单地报告一下E题Summer Reading的两种解法。比赛完后,看了作者提供的tutorial仍然是一脸雾水,主要是因为误解block为输入中连续的数字块。之后,借鉴了牛人的代码,才知道block其实是指一本书号的数字块。如给定输入序列为0 0 2 2 3 3 0 0 4 4 0,这其中就存在着三个block,即2 2;3 3;4 ;而非两个block(2 2 3 3;4 ;)。

解法一(思想源于作者的tutorial):

根据作者提供的DP思想,对于每一个block都可以尝试进行向左或向右扩展,如 4 可以向左扩展为 4 4 4 ,然后再向右扩展,就变为了 4 4 4 4 ,并且符号题中所给条件。对于一个特定的block[i]来说,其向左扩展的限制在于其左边的block[i-1]的向右扩展结果,block[i-1]与block[i]间缺少的书号,以及block[i-1]后面紧跟着的0的个数,而其向右扩展的限制在于其向左扩展的结果以及block[i]后面紧跟着的0的个数。

 

示例:0 0 2 2 3 3 0 0 4 0

block[1] = 2 2,此时已无法向左扩展(即向左扩展0位),因为必须block[1]之前缺少的书号的数目为1(即只有书号1缺失),至少要占据两个0。并且由于block[1]后面没有紧跟着的0,所以向右也无法扩展。

block[2] = 3 3,向左无法扩展,因为block[1]与block[2]之间没有0存在。向右可以扩展1位或者2位,都不会打破题中的限制。

block[3] = 4 4,向左扩展讨论:在block[2]扩展1位的情况下,block[3]向左扩展1位;在block[2]扩展2位的情况下,block[3]向左无扩展(即扩展0位)。向右扩展讨论:在block[3]向左扩展1位或者2位的情况下,block[3]向右扩展1位,或者不扩展。

在block[3]向左不扩展时,block[4]向右扩展1位。

 

在上述block扩展的过程中,如果有一个block不管是向右扩展几位(包括扩展0位)都无法满足题中条件时,就直接输出-1,并退出执行。否则,就可以利用block的扩展情况进行还原书号序列。

下面用两个数组exLeft和exRight来分别表示每个block的向左扩展情况和向右扩展情况。为了方便,令block[1]之前还存在着一个block[0]。

block[0]:为了不占用block[0]后面的零,令exRight[0][0]= true,exRight[0][1-4] = false

block[1]:exLeft[1][0] = true,exLeft[1][1-4]= false(block[1]无法向左扩展);同理,exRight[1][0]= true,exRight[1][1-4] = false。

block[2]:exLeft[2][0] = true,exLeft[2][1-4]= false;exRight[2][0-2] = true,exRight[2][3-4]= false(block[2]向右扩展1位或者2位均可)。

block[3]:exLeft[3][0-1] = true,exLeft[3][2-4]= false;exRight[3][0-1] = true,exRight[3][2-4]= false(exRight[3][0] = true对应于exLeft[3][1]= true,而exRight[3][1] = true对应于exLeft[3][0]= true或者exLeft[3][1] = true)。

对于最后一个block,为了使得留出更多的0来填充更大的书号,我们要使用exRight[3][i] = true最小的那个i,即i= 0,但由于此时只剩下一个0,无法完整填充更大的书号,所以i=1。接着寻找可以与exRight[3][1]= true相对应的exLeft[3][j],然后利用exLeft[3][j]找到可以与其相对应的exRight[2][k],如此递归下去。对于每个block,利用找到的合适的exLeft和exRight进行向左、向右扩展,完成书号的填充。

在编码过程中,exLeft[i][j]里面可以记录可以与其相对应的一个exRight[i-1][k]中的k值,这样就可以快速向前递归填充了。

代码:

#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <utility>
#include <set>
#include <map>
#include <cstdio>
#include <cstdlib>
#include <cmath>

using namespace std;

class BLOCK {
    public:
	int elem;
	int numElem;
	int numZero;
    public:
	BLOCK(int _elem = 0, int _numElem = 0, int _numZero = 0)
	{
	    elem = _elem;
	    numElem = _numElem;
	    numZero = _numZero;
	}
};
int n;
vector<int> note;
vector<BLOCK> block;
vector<vector<int> > toLeft, toRight;
vector<int> ans;

bool Work()
{
    block.clear();
    block.push_back( BLOCK(0,0,0) );
    for(int i = 0; i < n; ++i)
    {
	if( !note[i] )
	{
	    block.back().numZero++;
	}
	else 
	{
	    if( note[i] != block.back().elem )
	    {
		block.push_back( BLOCK(note[i], 1, 0) );
	    }
	    else 
	    {
		block.back().numElem += block.back().numZero + 1;
		block.back().numZero = 0;
	    }
	}
    }

    toLeft.assign(block.size(), vector<int>(5,-1));
    toRight.assign(block.size(), vector<int>(5,-1));

    toRight[0][0] = 0;
    for(int i = 1; i < int(block.size()); ++i)
    {
	// calculate toLeft[i], which is only related to toRight[i-1]
	for(int l = 0; l < 5; ++l)
	{
	    if( l + block[i].numElem > 5 ) continue;

	    for(int r = 0; r < 5 && toLeft[i][l] < 0; ++r)
	    {
		if( toRight[i-1][r] < 0 ) continue;

		if( r + l <= block[i-1].numZero )
		{
		    int zeros = block[i-1].numZero - l - r;
		    int diff = block[i].elem - block[i-1].elem;
		    diff -= 1;
		    if( zeros >= diff*2 && zeros <= diff*5 )
		    {
			toLeft[i][l] = r;
		    }
		}
	    }
	}

	// calculate toRight[i], which is only related to toLeft[i]
	bool terminal = false;
	for(int r = 0; r < 5; ++r)
	{
	    if( r > block[i].numZero ) continue;

	    for(int l = 0; l < 5 && toRight[i][r] < 0; ++l)
	    {
		if( toLeft[i][l] < 0 ) continue;

		int num = r + l + block[i].numElem;
		if( num >= 2 && num <= 5 )
		{
		    toRight[i][r] = l;
		    terminal = true;
		}
	    }
	}

	if( !terminal )
	    return false;
    }

    int size = int(block.size());
    int pos = 0;
    while( toRight[size-1][pos] < 0 && pos < 5 ) ++pos;

    int remain = block.back().numZero - pos;

    ans.clear();
    if( remain == 1 )
    {
	++pos;
	if( toRight[size-1][pos] < 0 ) 
	    return false;
	ans.push_back( block.back().elem );
    }
    else if( remain > 1 )
    {
	int val = block.back().elem + 1;
	if( remain&1 )
	{
	    ans.push_back( val );
	    --remain;
	}
	for(int i = 1; i <= remain; ++i)
	{
	    ans.push_back( val );
	    if( !(i&1) )
		++val;
	}
	reverse(ans.begin(), ans.end());
    }

    int lj, rj = pos;
    for(int i = size - 1; i > 0; --i)
    {
	lj = toRight[i][rj];
	int num = lj + rj + block[i].numElem;
	for(int k = 0; k < num; ++k)
	    ans.push_back( block[i].elem );

	rj = toLeft[i][lj]; // cal the position, to which (i-1)th block extends;
	int zeros = block[i-1].numZero - rj - lj;
	int numVal = block[i].elem - block[i-1].elem - 1;
	
	if( !numVal ) continue;

	vector<int> temp;
	int m = zeros/numVal, re = zeros%numVal;
	int val = block[i-1].elem + 1;
	for(int k = 1; k <= numVal; ++k)
	{
	    for(int j = 0; j < m; ++j)
		temp.push_back( val );
	    if( k <= re )
		temp.push_back( val );
	    ++val;
	}
	reverse(temp.begin(), temp.end());

	ans.insert(ans.end(), temp.begin(), temp.end());
    }

    reverse(ans.begin(), ans.end());
    cout << ans.back() << endl;
    for(int i = 0; i < int(ans.size()); ++i)
	cout << ans[i] << " ";
    cout << endl;

    return true;
}

int main()
{
    ios::sync_with_stdio(false);
    //freopen("data.tst", "r", stdin);
    while( cin >> n )
    {
	note.resize( n );
	for(int i = 0; i < n; ++i)
	    cin >> note[i];

	if( !Work() )
	    cout << -1 << endl;
    }
    return 0;
}

解法二:构造解

把Vasya做n天的SummerReading想象成骑车穿过n米的长路。那么Vasya最快的方式是每隔两米,速度就增加1,最慢的方式是每隔五米,速度才增加1。输入中的非零数代表Vasya在此点时的速度。如果这个非零值小于Vasya以最慢的方式达到此点的速度,或者大于Vasya以最快的方式达到此点的速度,那么肯定是不合法的。

示例:0 0 2 2 3 3 0 0 4 4 0

最快方式:1 1 2 2 3 3 4 4 4 4 5

最慢方式:1 1 2 2 3 3 4 4 4 4 4

根据题中要求对于出现的书号,至少要出现两次。所以,对于达到的速度值至少要出现两次。最快的方式里面5只出现一次,为了满足条件,必须减1。最快方式就变成了 1 1 2 2 3 3 4 4 4 4 4。然后,利用最快方式的速度序列,从后往前把给定的原速度序列进行恢复即可。

#include <iostream>
#include <vector>
#include <map>
#include <cstdio>
#include <cstdlib>

using namespace std;

int n;
vector<int> note;
vector<pair<int,int> > maxNote;
vector<pair<int,int> > minNote;

bool Work()
{
    maxNote.resize( n );
    minNote.resize( n );
    maxNote[0] = make_pair(1, 1);
    minNote[0] = make_pair(1, 1);

    if( note[0] > 1 )
	return false;

    for(int i = 1; i < n; ++i)
    {
	if( maxNote[i-1].second < 2 )
	    maxNote[i] = make_pair(maxNote[i-1].first, maxNote[i-1].second + 1);
	else maxNote[i] = make_pair(maxNote[i-1].first+1, 1);

	if( minNote[i-1].second < 5 )
	    minNote[i] = make_pair(minNote[i-1].first, minNote[i-1].second + 1);
	else minNote[i] = make_pair(minNote[i-1].first+1, 1);

	if( note[i] )
	{
	    if( note[i] > maxNote[i].first || note[i] < minNote[i].first )
		return false;
	    if( note[i] < maxNote[i].first )
		maxNote[i] = make_pair(note[i], 5);
	    if( note[i] > minNote[i].first )
		minNote[i] = make_pair(note[i], 1);
	}
    }

    if( maxNote[n-1].second == 1 )
	maxNote[n-1] = maxNote[n-2];

    if( note[n-1] > maxNote[n-1].first )
	return false;

    return true;
}

int main()
{
    //freopen("data.tst", "r", stdin);
    while( cin >> n )
    {
	note.resize( n );
	for(int i = 0; i < n; ++i)
	    cin >> note[i];

	bool ans = Work();
	if( !ans )
	{
	    cout << -1 << endl;
	    continue;
	}

	note[n-1] = maxNote[n-1].first;
	int len = 1;
	for(int i = n - 2; i >= 0; --i)
	{
	    if( maxNote[i].first >= note[i+1] )
	    {
		note[i] = note[i+1];
		++len;
		if( len > 5 )
		{
		    --note[i];
		    len = 1;
		}
	    }
	    else 
	    {
		note[i] = maxNote[i].first;
		len = 1;
	    }
	}

	cout << note[n-1] << endl;
	for(int i = 0; i < n; ++i)
	    cout << note[i] << " ";
	cout << endl;
    }
    return 0;
}

 

总结:算法题总是一题多解的,以前总是认为对于DP算法题,只要找出最优子结构,然后列出递推公式就ok了,但是从这道题来看,难点还止于此,后处理工作仍然不容小觑。关于构造解,个人的观点是,思路虽然很简单,但是要想在短时间内说服别人却是不容易的。


浅谈Codeforces round 217 Summer Reading的两种解法:DP与构造

上一篇:UVALive - 4328 Priest John's Busiest Day


下一篇:EasyUI批量添加数据