由于要按字典序输出，所以优先访问坐标较小的点，第一次得到的序列就是所求结果

如图，每条路径上保存一个字母，从根节点开始进行dfs，每遍历到一个标记节点（图中的红点），从根节点到当前节点路径上所有字母连起来即为一个单词

上图中存储了 abc, abcd, b, bcd, efg, hij.

对于Trie树主要有三种操作：

1. 新建一个结点
2. 插入一个单词
3. 在trie树中查找单词

Description

Stan has n sticks of various length. He throws them one at a time on the floor in a random way. After finishing throwing, Stan tries to find the top sticks, that is these sticks such that there is no stick on top of them. Stan has noticed that the last thrown stick is always on top but he wants to know all the sticks that are on top. Stan sticks are very, very thin such that their thickness can be neglected.                                                             
                                                                                                                                                                                      

Input

Output

Sample Input

5
1 1 4 2
2 3 3 1
1 -2.0 8 4
1 4 8 2
3 3 6 -2.0
3
0 0 1 1
1 0 2 1
2 0 3 1
0

Sample Output

Top sticks: 2, 4, 5.
Top sticks: 1, 2, 3.

Hint

/**//***********************************
暴力就行，从第一个开始判断
如果两条线段相交就把前面一条筛选掉
判断线段相交直接贴的吉大模板。。。
***********************************/
#include <iostream>
#include <cstdio>
#include <cstring>

using namespace std;

const int maxn = 100000 + 5;
const double eps=1e-10;

struct point { double x, y; };

point p[maxn], b[maxn];
bool ans[maxn];

double min(double a, double b) { return a < b ? a : b; }

double max(double a, double b) { return a > b ? a : b; }

bool inter(point a, point b, point c, point d)
{
    if( min(a.x, b.x) > max(c.x, d.x) ||
        min(a.y, b.y) > max(c.y, d.y) ||
        min(c.x, d.x) > max(a.x, b.x) ||
        min(c.y, d.y) > max(a.y, b.y) )
    return 0;

    double h, i, j, k;

    h = (b.x - a.x) * (c.y - a.y) - (b.y - a.y) * (c.x - a.x);
    i = (b.x - a.x) * (d.y - a.y) - (b.y - a.y) * (d.x - a.x);
    j = (d.x - c.x) * (a.y - c.y) - (d.y - c.y) * (a.x - c.x);
    k = (d.x - c.x) * (b.y - c.y) - (d.y - c.y) * (b.x - c.x);

    return h * i <= eps && j * k <= eps;
}

int main()
{
    int n;
    int res[maxn];
    while( cin >> n, n )
    {
        memset( ans, 0, sizeof( ans ) );
        for( int i = 0; i < n; i++ )
        {
            cin >> p[i].x >> p[i].y >> b[i].x >> b[i].y;
        }

        for( int i = 0; i < n; i++ )
        {
            for( int j = i + 1; j < n; j++ )
            {
                if( inter(p[i], b[i], p[j], b[j] ) )
                {
                    ans[i] = 1;
                    break;              //不加break会超时。。。
                }
            }
        }
        int ct = 0;
        cout << "Top sticks: ";
        for( int i = 0; i < n; i++ )
            if( !ans[i] )  res[ct++] = i + 1;
        for( int i = 0; i < ct - 1; i++ )
            cout << res[i] << ", ";
        cout << res[ct-1] << "." << endl;
    }
    return 0;
}

Description

Input

Output

Sample Input

5
0 0 4 4 0 4 4 0
5 0 7 6 1 0 2 3
5 0 7 6 3 -6 4 -3
2 0 2 27 1 5 18 5
0 3 4 0 1 2 2 5

Sample Output

INTERSECTING LINES OUTPUT
POINT 2.00 2.00
NONE
LINE
POINT 2.00 5.00
POINT 1.07 2.20
END OF OUTPUT

/**//*************************************
计算几何基础题，判断直线相交及求交点
注意斜率不存在的情况
**************************************/
#include <iostream>
#include <cstdio>

int main()
{
    double x1, y1, x2, y2, x3, y3, x4, y4;
    int n;
    double k1, k2;
    double b1, b2;
    double i_x, i_y;
    scanf("%d", &n);
    std::cout << "INTERSECTING LINES OUTPUT" << std::endl;
    while( n-- )
    {
        scanf("%lf%lf%lf%lf%lf%lf%lf%lf", &x1, &y1, &x2, &y2, &x3, &y3, &x4, &y4);

        if( x1 != x2 && x3 != x4 )
        {
            k1 = ( y2 - y1 ) / ( x2 - x1 );
            k2 = ( y4 - y3 ) / ( x4 - x3 );
            b1 = y1 - k1 * x1;
            b2 = y3 - k2 * x3;
            if( k1 == k2 )
            {
                if( b1 == b2 )
                    printf("LINE\n");
                else
                    printf("NONE\n");
            }
            else
            {
                i_x = (b2 - b1) / (k1 - k2);
                i_y = k1 * i_x + b1;
                printf("POINT %.2lf %.2lf\n", i_x, i_y);
            }
        }
        else if( x1 == x2 && x3 == x4 )
        {
            if( x1 == x3 )
            std::cout << "LINE\n";
            else
            std::cout << "NONE\n";
        }
        else if( x1 == x2 && x3 != x4 )
        {
            k2 = ( y4 - y3 ) / ( x4 - x3 );
            b2 = y3 - k2 * x3;
            i_x = x1;
            i_y = k2 * x1 + b2;
            printf("POINT %.2lf %.2lf\n", i_x, i_y);
        }
        else
        {
            k1 = ( y2 - y1 ) / ( x2 - x1 );
            b1 = y1 - k1 * x1;
            i_x = x3;
            i_y = k1 * x3 + b1;
            printf("POINT %.2lf %.2lf\n", i_x, i_y);
        }
    }
    std::cout << "END OF OUTPUT\n";
    return 0;
}

Time Limit: 4000/2000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 252    Accepted Submission(s): 125

2 5
4 2
3 5

4

 

//简单贪心
#include <iostream>
#include <cstdio>
#include <algorithm>

const int maxn = 1000 + 5;

using namespace std;

bool cmp( int a, int b )
{
    return a > b;
}

int main()
{
    int a[maxn], b[maxn];
    int n, t, ans = 0;
    while( cin >> n >> t )
    {
        ans = 0;
        for( int i = 0; i < n; i++ )
            cin >> a[i];
        for( int i = 0; i < n; i++ )
            cin >> b[i];

        sort( a, a + n );
        sort( b, b + n, cmp );

        for( int i = 0; i < n; i++ )
            if( a[i] + b[i] > t )
                ans += a[i] + b[i] - t;
        cout << ans << endl;
    }
    return 0;
}

n很小的时候，斯特灵公式的取值已经十分准确。

公式为：

这就是说，对于足够大的整数n，这两个数互为近似值。更加精确地：

或者：

Big Number

Time Limit: 20000/10000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 8759    Accepted Submission(s): 3879

2
10
20

7
19

//log10(n!)=(0.5*log(2*PI*n)+n*log(n)-n)/log(10)

#include <iostream>
#include <cstdio>
#include <cmath>

const double PI = 3.1415926;

int main()
{
    int n;
    int tmp;
    while( ~scanf("%d", &n ) )
    {
        for( int i = 0; i < n; i++ )
        {
            scanf("%d", &tmp);
            double cnt = 1;
            cnt += (0.5 * log( 2 * PI * tmp ) + tmp * log( tmp ) - tmp ) / log(10);
            printf("%d\n", (int)(cnt));
        }
    }
    return 0;
}