1001

Missing number

There is a permutation without two numbers in it, and now you know what numbers the permutation has. Please find the two numbers it lose.

There is a number T shows there are T test cases below. (T≤10)
For each test case , the first line contains a integers n , which means the number of numbers the permutation has. In following a line , there are n distinct postive integers.(1≤n≤1,000)

For each case output two numbers , small number first.

2
3
3 4 5
1
1

1 2
2 3

解题思路：题意给的n个数是1~n+2之间的数，因此只需要将在1~n+2之间却不在给定的n个数的数找出来即可。

参考代码：

#include <iostream>
#include <string.h>
#include <iomanip>
#include <algorithm>
#include <cmath>
using namespace std;
typedef long long ll;
int main(){
    int n,t,a;
    bool used[1003];
    cin>>t;
    while (t--){
        cin>>n;
        memset(used,false,sizeof(used));
        for (int i=0;i<n;i++){
            cin>>a;
            used[a]=true;
        }
        int flag=0;
        for (int i=1;i<=n+2;i++){
            if (used[i]==false){
                flag++;
                if (flag==1)
                    cout<<i<<" ";
                if (flag==2)
                    cout<<i<<endl;
            }
        }
    }
    return 0;
}

Fibonacci

Following is the recursive definition of Fibonacci sequence:
Fi=???01Fi?1+Fi?2i = 0i = 1i > 1

Now we need to check whether a number can be expressed as the product of numbers in the Fibonacci sequence.

There is a number T shows there are T test cases below. (T≤100,000)
For each test case , the first line contains a integers n , which means the number need to be checked. 
0≤n≤1,000,000,000

For each case output "Yes" or "No".

3
4
17
233

Yes
No
Yes

解题思路：首先用一个数组将fib数列保存下来，然后求出用一个数组将Fibonacci数组中属于n的因子的数保存，最后在递归搜索求解是否存在n是这些Fibonacci数组成的积；

参考代码：

#include <iostream>
#include <stdio.h>
#include <algorithm>
#include <queue>
#include <stack>
#include <cmath>
#include <string.h>
using namespace std;
int fib[100],a[100],i,k;
bool work(int n,int step){	//递归搜索求解是否存在n是这些Fibonacci数组成的积
	if (n==1)
		return true;
	for (int j=step;j<k;j++){
		if (n%a[j]==0){
			if (work(n/a[j],j)==true)
				return true;
		}
	}
	return false;
}
int main(){
	int t,n;
	/*构造Fibonacci数组*/
	fib[0]=0;
	fib[1]=1;
	for (i=2;i<46;i++){
		fib[i]=fib[i-1]+fib[i-2];
	}
	cin>>t;
	while (t--){
		cin>>n;
		if (n==0){
			cout<<"Yes"<<endl;
			continue;
		}
		k=0;
		for (int j=3;j<46;j++){	//用一个数组将Fibonacci数组中属于n的因子的数保存
			if (n%fib[j]==0)
				a[k++]=fib[j];
		}
		if (work(n,0)==true)
			cout<<"Yes"<<endl;
		else
			cout<<"No"<<endl;
	}
	return 0;
}

BestCoder Round #28