1001 Saber (DFS)

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

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.

1001 Saber (DFS)

Summer 2018 - Problems - 1001 Saber

Input

Output

Sample Input

Sample Output

全站热榜