分类目录归档:ACM

POJ 3304 Segments 计算几何基础,点的表示和叉积

题意:给出n条线段,求是否有一条直线能够与全部线段相交.

由于一条穿过所有的线段的直线,总可以通过平移来使得其通过某两个端点,故枚举端点,判断过端点的直线是否能穿过所有线段即可.

此题WA几次..究其原因为: 叉积之前需要判断给出的向量是否为0,为0则不能进行叉积操作..

刚刚开始做计算几何…orz各路神犇..希望能够快快长进!

# include <iostream>
# include <cmath>
# define sqr(x) ((x)*(x))
# define rep(x, n) for (int x = 0; x < n; ++x )
using namespace std;

const double eps = 1e-8;
int dcmp(double x){ return (x > eps) - (x < -eps);}

class Point
{
    public:
    double x, y;
    Point(){x = y = 0.0;}
    Point(double a, double b){ x = a; y = b; }

    inline Point operator -(const Point& b)
    { return Point(x-b.x, y-b.y);}

    inline double cross(const Point& b, const Point& c)
    { return (b.x - x) * (c.y - y) - (c.x - x) * (b.y - y); }

    inline double dis(const Point& b)
    { return sqrt( sqr(b.x - x) + sqr(b.y - y) ); }

}line[103][2];

int t, n;
bool ok;

void check(Point& a, Point& b)
{
    if ( dcmp(a.dis(b)) == 0 ) return;
    rep(i, n)
        if ( dcmp(a.cross(b, line[i][0]) * a.cross(b, line[i][1])) > 0 )
            return;
    ok = true;
    return;
}
int main()
{
    double x, y;
    cin >>t;
    while( t-- )
    {
        cin >>n;
        rep(i, n)
        {
            cin >> x >> y;
            line[i][0] = Point(x, y);
            cin >> x >> y;
            line[i][1] = Point(x, y);
        }
        ok = false;
        rep(i, n)
            for (int j = i+1; j < n; ++j )
            {
                if ( ok ) break;
                check(line[i][0], line[j][0]);
                check(line[i][0], line[j][1]);
                check(line[i][1], line[j][0]);
                check(line[i][1], line[j][1]);
            }
        if ( n == 1 ) ok = true;
        if ( ok ) cout << "Yes!" <<endl;
        else cout << "No!" << endl;
    }
    return 0;
}

POJ 2551 Ones 简单的数论

题目所求为。给定一个n,求数列 { 1, 11, 111, 1111… } 第几项可以整除n。

设 x 整除 n,即 x % n == 0。

考虑到: 若 a + b = x,则 x % n == a %n + b % n。。这种奇怪的定理,

于是可以由 x = 1 % n 开始,每次 x = (x * 10 + 1) % n。直到 x %n 为0时,即为这个数。

# include <iostream>
using namespace std;

int n;

int main()
{
    while ( cin >> n )
    {
        int m = 1, c = 1;
        while ( m % n )
        {
            m = (m*10 + 1) % n ;
            ++c;
        }
        cout << c <<endl;
    }
    return 0;
}

POJ 2309 BST

此题一看,树状数组里神奇的 n & -n 就派上用场了。

输入你,输出 n-(n&-n)+1 和 n+(n&-n)-1 即可。

当然可以用一个递归来划分区间。同样我也写了一下。。比上面的方法可慢了不少。。

# include <iostream>
using namespace std;

int t, n;

void dfs(long long root, long long min, long long max)
{
    if ( root == n )
    {
        cout << min << " " << max << endl;
        return;
    }
    if ( n < root )
        dfs((root+min)>>1, min, root-1);
    else dfs( ((root+max)>>1)+1, root+1, max );
}

int main()
{
    cin >> t;
    while ( t-- )
    {
        cin >> n;
        dfs((1<<30), 1, 2147483647);
    }
    return 0;
}

124 – ZOJ Monthly, March 2013 – A, A Simple Tree Problem, 修改子树 和查询。

Given a rooted tree, each node has a boolean (0 or 1) labeled on it. Initially, all the labels are 0.

We define this kind of operation: given a subtree, negate all its labels.

And we want to query the numbers of 1’s of a subtree.

Input

Multiple test cases.

First line, two integer N and M, denoting the numbers of nodes and numbers of operations and queries.(1<=N<=100000, 1<=M<=10000)

Then a line with N-1 integers, denoting the parent of node 2..N. Root is node 1.

Then M lines, each line are in the format “o node” or “q node“, denoting we want to operate or query on the subtree with root of a certain node.

Output

For each query, output an integer in a line.

Output a blank line after each test case.

Sample Input

3 2
1 1
o 2
q 1

Sample Output

1

Problem’s Author: CUI, Tianyi

批量地 修改子树 可以被看做段修改(把树通过一个入点出点路径序列来表示),这样即转化为了线段树的段修改和段查询。