CC

题目链接:点我

题目

    An array of size n ≤ 10 6 is given to you. There is a sliding window of size k which is moving from the very left of the array to the very right. You can only see the k numbers in the window. Each time the sliding window moves rightwards by one position. Following is an example: 

题目链接:点我

题目

Some of Farmer John’s N cows (1 ≤ N ≤ 80,000) are having a bad hair day! Since each cow is self-conscious about her messy hairstyle, FJ wants to count the number of other cows that can see the top of other cows’ heads.
Each cow i has a specified height hi (1 ≤ hi ≤ 1,000,000,000) and is standing in a line of cows all facing east (to the right in our diagrams). Therefore, cow i can see the tops of the heads of cows in front of her (namely cows i+1, i+2, and so on), for as long as these cows are strictly shorter than cow i.

题目链接:点我

题目

    Given a m-by-n (0,1)-matrix, of all its submatrices of all 1’s which is the largest? By largest we mean that the submatrix has the most elements.

题目链接:点我

题目

    Let N be the set of all natural numbers {0 , 1 , 2 , . . . }, and R be the set of all real numbers. wi, hi for i = 1 . . . n are some elements in N, and w0 = 0. 
    Define set B = {< x, y > | x, y ∈ R and there exists an index i > 0 such that 0 <= y <= hi ,∑ 0<=j<=i-1wj <= x <= ∑ 0<=j<=iwj} 
    Again, define set S = {A| A = WH for some W , H ∈ R + and there exists x0, y0 in N such that the set T = { < x , y > | x, y ∈ R and x0 <= x <= x0 +W and y0 <= y <= y0 + H} is contained in set B}. 
    Your mission now. What is Max(S)? 
    Wow, it looks like a terrible problem. Problems that appear to be terrible are sometimes actually easy. 
    But for this one, believe me, it's difficult.

题目链接:点我

题目

    In this problem, you have to analyze a particular sorting algorithm. The algorithm processes a sequence of n distinct integers by swapping two adjacent sequence elements until the sequence is sorted in ascending order. 

题目链接:点我

题目

    Mery has a beautiful necklace. The necklace is made up of N magic balls. Each ball has a beautiful value. The balls with the same beautiful value look the same, so if two or more balls have the same beautiful value, we just count it once. We define the beautiful value of some interval x,yx,y as F(x,y). F(x,y) is calculated as the sum of the beautiful value from the xth ball to the yth ball and the same value is ONLY COUNTED ONCE. For example, if the necklace is 1 1 1 2 3 1, we have F(1,3)=1, F(2,4)=3, F(2,6)=6. 

题目链接:点我

题目

Farmer John’s cows have discovered that the clover growing along the ridge of the hill (which we can think of as a one-dimensional number line) in his field is particularly good.
Farmer John has N cows (we number the cows from 1 to N). Each of Farmer John’s N cows has a range of clover that she particularly likes (these ranges might overlap). The ranges are defined by a closed interval [S,E].

题目链接:点我

题目

    Astronomers often examine star maps where stars are represented by points on a plane and each star has Cartesian coordinates. Let the level of a star be an amount of the stars that are not higher and not to the right of the given star. Astronomers want to know the distribution of the levels of the stars.

    For example, look at the map shown on the figure above. Level of the star number 5 is equal to 3 (it's formed by three stars with a numbers 1, 2 and 4). And the levels of the stars numbered by 2 and 4 are 1. At this map there are only one star of the level 0, two stars of the level 1, one star of the level 2, and one star of the level 3. 

    You are to write a program that will count the amounts of the stars of each level on a given map.

Input

    The first line of the input file contains a number of stars N (1<=N<=15000). The following N lines describe coordinates of stars (two integers X and Y per line separated by a space, 0<=X,Y<=32000). There can be only one star at one point of the plane. Stars are listed in ascending order of Y coordinate. Stars with equal Y coordinates are listed in ascending order of X coordinate. 

Output

    The output should contain N lines, one number per line. The first line contains amount of stars of the level 0, the second does amount of stars of the level 1 and so on, the last line contains amount of stars of the level N-1.

Sample Input

5
1 1
5 1
7 1
3 3
5 5

Sample Output

1
2
1
1
0

Hint

    This problem has huge input data,use scanf() instead of cin to read data to avoid time limit exceed.

题意:

给你一群星星的坐标,要你求每个星星的左下共有多少颗星星.输出level由0 到n-1的星星的个数.

思路:

树状数组,由于题目中所有的星星是按照y的升序来输入的,所以我们只需要查询坐标小于等于它的星星共有多少颗即可.

代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<iostream>
using namespace std;

const int maxn = 32005;
int a[maxn];
int level[maxn];
int n;

void add(int x){
    while(x < maxn){
        a[x] ++;
        x += x&-x;
    }
}

int sum(int x){
    int ans = 0;
    while(x > 0){
        ans += a[x];
        x -= x&-x;
    }
    return ans;
}

int main(){
    while(scanf("%d", &n) != EOF){
        memset(a, 0, sizeof(a));
        memset(level, 0, sizeof(level));
       for(int i = 0;i < n; ++i){
        int x, y;
        scanf("%d %d", &x, &y);
        ++ x;
        level[sum(x)] ++;
        add(x);
       }
       for(int i = 0; i < n; ++ i)
        printf("%d\n",level[i]);
    }
    return 0;
}

题目链接:点这里

题目

    A number of rectangular posters, photographs and other pictures of the same shape are pasted on a wall. Their sides are all vertical or horizontal. Each rectangle can be partially or totally covered by the others. The length of the boundary of the union of all rectangles is called the perimeter. 

题目链接: POJ HDU

题目

There are several ancient Greek texts that contain descriptions of the fabled island Atlantis. Some of these texts even include maps of parts of the island. But unfortunately, these maps describe different regions of Atlantis. Your friend Bill has to know the total area for which maps exist. You (unwisely) volunteered to write a program that calculates this quantity.