Question

noip2010提高组初赛试题求解

3．
#include<iostream>
using namespace std;
const int NUM=5;
int r(int n)
{
int i;
if(n<=NUM)
return 0;
for(i=1;i<=NUM;i++)
if( r(n-i)<0)
return i;
return -1;
}

int main()
{
int n;
cin>>n;
cout<<r(n)<<endl;
return 0;
}
输入：
16
输出：10______________

4．
#include<iostream>
#include<cstring>
using namespace std;
const int SIZE=100;
int n,m,r[SIZE];
bool map[SIZE][SIZE],found;
bool successful()
{
int i;
for(i=1;i<=n;i++)
if(!map[r[i]][r[i%n+1]])
return false;
return true;
}
void swap(int *a,int *b)
{
int t;
t=*a;
*a=*b;
*b=t;
}
void perm(int left,int right)
{
int i;
if(found)
return ;
if(left>right)
{
if(successful())
{
for(i=1;i<=n;i++)
cout<<r[i]<<' ';
found=true;
}
return ;
}
for(i=left;i<=right;i++)
{
swap(r+left,r+i);
perm(left+1,right);
swap(r+left,r+i);
}
}
int main()
{
int x,y,i;
cin>>n>>m;
memset(map,false,sizeof(map));
for(i=1;i<=m;i++)
{
cin>>x>>y;
map[x][y]=true;
map[y][x]=true;
}
for(i=1;i<=n;i++)
r[i]=i;
found=false;
perm(1,n);
if(!found)
cout<<"Nosolution!"<<endl;
return 0;
}

输入：
9 12
1 2
2 3
3 4
4 5
5 6
6 1
1 7
2 7
3 8
4 8
5 9
6 9
输出：_________
请问这两段程序分别为了实现什么

Answer 1

求r(n)的值

要很好地解决这道题，首先我们要明确一个定理：r(n)无论在什么时候调用，其值不变。这样我们就可以反复调用我们之前算过的r(n)的结果。

注意到程序有一个判断n<=num则exit(n)/return n的过程，很容易就可以知道r(1)~r(5)=1~5。那么对于大于5的数都要经过一个主要的判断过程是检索n-5~n-1的r值，如果小于0则赋值5~1，则r(6)就能很明显看出来是-1了（这点非常关键，有许多同学认为大于5的数都大于0，这是不对的），那么r(7)~r(11)就能依次等于1~5了。而第二个难点是r(12)的计算，r(12)与r(6)面对的处境是一样的（r(7)-r(11)都大于0），所以r(12)也等于-1，那么题目要求的r(16)也就容易得到答囗案了。

这题的本质是定义了一个周期为6的函数r(n)，其中

n%6 (n%6!=0)
r(n)=
-1 (n%6=0)
因此输出结果为4。

当然对于大部分同学来说这道题就到此为止了，但按照出题人的说法，这个程序实际上为了解决经典的取石子问题，具体交给各位思考。

④ 求哈密尔顿回路

这题的关键是看懂successful函数的含义。搜索的过程并不难看懂，如果实在看不懂手动模拟一下也能看出来是一个对于r[n]方案的枚举，successful是判断r[n]里储存的方案是否是一个合法的哈密尔顿回路。当然这题一个非常非常易错的地方就是搜索的顺序决定了输出的方案必定是所有可行方案的字典序最小的一个，尽管输入数据只有两组方案，但是由于输入数据给定的顺序问题，也有许多同学忽略了这个问题，造成不必要的失分。

输出结果为1 6 9 5 4 8 3 2 7。