首页 > ACM题库 > HDU-杭电 > Hdu 1843 Horizontal and Vertical Rays-数学[解题报告] C++
2013
12-23

Hdu 1843 Horizontal and Vertical Rays-数学[解题报告] C++

Horizontal and Vertical Rays

问题描述 :

There are H horizontal rays and V vertical rays. A horizontal ray is a straight line which originates at some point and extends infinitely far to the right (towards increasing X coordinates). A vertical ray is a straight line which originates at some point and extends infinitely far down (towards decreasing Y coordinates). A horizontal ray whose origin is (Xh,Yh) touches a vertical ray whose origin is (Xv,Yv) if Xh<=Xv and Yh<=Yv.
You must choose a subset S consisting of the minimum number of vertical rays such that each horizontal ray is touched by at least one vertical ray in S. It is guaranteed that it will always be possible to choose such a subset for the given test data.

输入:

The first line of input contains an integer number T, representing the number of test cases to follow. The first line of each test case contains 2 integer numbers: H (1<=H<=100.000) and V (1<=V<=100.000). The next H lines contain 2 integers each: X and Y, representing the (X,Y) coordinates of the origins of the horizontal rays. The next V lines contain 2 integers each: X and Y, representing the (X,Y) coordinates of the origins of the vertical rays. All the X and Y coordinates in the input are in the range 0 … 50.000.000.

输出:

For each of the T test cases, in the order given in the input, print one line containing the minimum number of vertical rays chosen.

样例输入:

1
3 3
1 6
4 4
6 2
3 8
5 7
9 4

样例输出:

2

// 这题主要求S
// 结论: S = (251^(n+1)-1) * (2^(3n+1)-1) / 250 
// 是两个等比数列和相乘 
// 
// 推理:
// 2008 = 2^3 * 251 
// 所以 2008^N 有 3N 个 2 和 N 个251 
// 所有仅由2组成的因子有
// 2^0 2^1 2^2 ... 2^(3N)
// 设集合 C = {2^0, 2^1, 2^2 ...,2^(3N)};
// SUM(C) =  2^(3n+1)-1

// 跟251组合产生的因子有
// 251^0 * C
// 251^1 * C
// ...
// 251^N * C

// 所有因子和为:
// S = (251^(n+1)-1))/250 * (2^(3n+1)-1)

// 计算S%K:
// S 很大, 不能保存在普通的数据类型中, 需要直接计算S%K
// 因为S有个分母250, 设 S = X/250
// 则S%K = (X/250)%K = (X%(250*K))/250
// 变成先求余数再除法的形式

#include <stdio.h>

// 求 (x^exp)%p 的值  O(LOG(exp))
int ExpMod(int x, int exp, int p) {
     if( exp==0 ) {
          return 1;
     }
     long long ret = ExpMod(x, exp>>1, p);
     ret = (ret*ret)%p;
     if( exp & 1 ) {
          ret = (ret*x)%p;
     }
     return (int)ret;
}

int main() {
     int N, K;
     while( scanf("%d %d", &N, &K), N && K ) {
          long long M = ExpMod(251, N+1, 250*K);
          M = (M+250*K-1)%(250*K);          // M--;

          long long M2 = ExpMod(2, 3*N+1, 250*K);
          M2 = (M2+250*K-1)%(250*K);          // M--;

          M = (M*M2)%(250*K);
          M /= 250;

          printf("%d\n", ExpMod(2008, M, K));
     }

     return 0;
}

 


  1. 代码不对,仔细对比一下输入输出, 怎么会有‘‘printf("The winning moves are:");’’这种输出呢?

  2. 这道题目虽然简单,但是小编做的很到位,应该会给很多人启发吧!对于面试当中不给开辟额外空间的问题不是绝对的,实际上至少是允许少数变量存在的。之前遇到相似的问题也是恍然大悟,今天看到小编这篇文章相见恨晚。

  3. 您没有考虑 树的根节点是负数的情况, 若树的根节点是个很大的负数,那么就要考虑过不过另外一边子树了