三角形和斐波那契数列结合(当做优化)

B - Triangle

HDU - 5914

Mr. Frog has n sticks, whose lengths are 1,2, 3⋯⋯n respectively. Wallice is a bad man, so he does not want Mr. Frog to form a triangle with three of the sticks here. He decides to steal some sticks! Output the minimal number of sticks he should steal so that Mr. Frog cannot form a triangle with
any three of the remaining sticks.

Input

The first line contains only one integer T (T≤20T≤20), which indicates the number of test cases.
For each test case, there is only one line describing the given integer n (1≤n≤201≤n≤20).

Output

For each test case, output one line “Case #x: y”, where x is the case number (starting from 1), y is the minimal number of sticks Wallice should steal.

Sample Input

3
4
5
6
Sample Output
Case #1: 1
Case #2: 1
Case #3: 2

本题的主要意思是在讲给一个数n 即从1——n的数最少去掉n个数，剩余的任意三个数都不可以组成三角形。输出n的值。

这里可以想到一个函数它的的所有的任意三个数都不能组成一个三角形。这个函数就是斐波那契数列。如下

1 2 3 5 8 13 21 34

所以说 的在n个数中把不是此函数中的数删去即可。
参考：https://blog.csdn.net/TJICSHAN/article/details/82391497
AC代码：

#include<vector>
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<map>
#include<algorithm>
#include<stdlib.h>

using namespace std;
typedef long long ll;
const int maxn=100000;
const int mod=998244353;
const int inf=0x3f3f3f3f;
char a[maxn],s[maxn];

int main()
{
    int i,m,t,sum;
    int a[6]={1,2,3,5,8,13};//20以内 
    int b=0;
    scanf("%d",&t);
    while(t--){
        scanf("%d",&m);
        for( i=0;i<6;i++){
            if(m<a[i]) break;
            //printf("%d ",i); 
        }   
        printf("Case #%d: %d\n",++b,m-i);
    }

    return 0;
}

那么接下来来看题：

Summer 2018 - Problems - 1001 Saber

Saber is a Class in the Holy Grail War. This Class is regarded as one of the most powerful Class.

Saber is a tree-lover. She loves all kinds of trees. One day, she suddenly comes up with a curious problem. She wants to know that in the path between x and y, whether it exists that when we choose three different edges i,j,k, the length of these three edges can build a triangle. Now she wants you to solve this problem.

Input

There are multiple test cases. The first line of input contains an integer T (T ≤ 5), indicating the number of test cases. For each test case:

The first line contains one integer N (1 ≤ N ≤ 100000), indicating the number of tree’s vertices. In the following N-1 lines, there are three integers x, y, w (1 ≤ w ≤ 1000000000), indicating an edge weighted <var>w</var> between x and y.

In the following line also contains one integer Q (1 ≤ Q ≤ 100000), indicating the number of queries. In the following <var>Q</var> lines, there are two integers x, y, indicating a query between x,and y.

Output

For each test case output ‘Case #i:’ in the first line i equals to the case number. Then for every query output ‘Yes’ or ‘No’ in one line.

Sample Input

2
5
1 2 5
1 3 20
2 4 30
4 5 15
2
3 4
3 5
5
1 4 32
2 3 100
3 5 45
4 5 60
2
1 4
1 3
</pre>

Sample Output

<pre>Case #1:
No
Yes
Case #2:
No
Yes</pre>

|

#include<vector>
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<map>
#include<algorithm>
#include<stdlib.h>

using namespace std;
typedef long long ll;
const int maxn=100110;
const int mod=998244353;
const int inf=0x3f3f3f3f;
struct tree{
    int point;  //结点
    ll w;       //权值
};
int n,T,u,v,q;//
int found,flag;//作为标记的作用
vector <tree> va[maxn];//二维数组，一个是动态，一个是静态
int vis[maxn];
ll path[maxn];//存边用的数组

int ok(int a,int b,int c){
    return a+b>c;
}
void init(){
    for(int i=0;i<=maxn;i++)
        va[i].clear();
    q=n-1;
    memset(vis,0,sizeof vis);
}
void dfs(int s,int step){///一个深度一个用来遍历的变量
    ///退出条件
    if(step>=50||found)return ;///退出条件1
    if(s==v){///这里用了v调用的时候用的u）u,v相等的时候判断
        found=1;
        if(step>50){///退出条件2
            flag=1;
            return;
        }
        sort(path,path+step);///排序
        
        for(int i=2;i<step;i++){///从2开始?调用的时候从0开始
            if(ok(path[i-2],path[i-1],path[i]))///是否构成三角形
            {
                flag=1;return;
            }
        }
        return;
    }
    ///回溯
    for(int i=0;i<va[s].size();i++){
        if(!vis[va[s][i].point]){
            vis[va[s][i].point]=1;///标记为1
            path[step]=va[s][i].w;///把权值保存起来（存边）
            dfs(va[s][i].point,step+1);///最爱的递归环节
            vis[va[s][i].point]=0; ///用完之后标记为0
        }
    }
}
/*inline int read(){//内联函数 :判断是否是数字，是则把字符转为数值，不是则加上'-'
    char ch=getchar();
    int x=0,f=1;
    while(ch<'0'||ch>'9')
    {
        if(ch=='-')
            f=-1;
            ch=getchar();
    }
    while(ch>='0'&&ch<='9'){
        x=x*10+ch-'0';
        ch=getchar();
    }
    return x*f;//
}*/
int main()
{
    int i,m,t,sum;
    scanf("%d",&t);
    int count=0;
    while(t--&&~scanf("%d",&n)){
        init();

        tree p;//建立一棵树
        for(int i=0;i<q;i++){
            scanf("%d %d %lld",&u,&v,&p.w);
            p.point=v;
            va[u].push_back(p);//(1)
            p.point=u;
            va[v].push_back(p); //(2)
        }
        scanf("%d",&m);
        printf("Case #%d:\n",++count);
        for(int i=0;i<m;i++){
            scanf("%d%d",&u,&v);
            found=flag=0;//标记作用
            vis[u]=1;//一开始经过u点
            dfs(u,0);//范围从u到v
            vis[u]=0;//用之后的位置的标记
            puts(!found||flag?"Yes":"No");
        }

}
    return 0;
}