hdvsyu's blog

Posted on Edited on In

Eva is trying to make her own color stripe out of a given one. She would like to keep only her favorite colors in her favorite order by cutting off those unwanted pieces and sewing the remaining parts together to form her favorite color stripe. It is said that a normal human eye can distinguish about less than 200 different colors, so Eva’s favorite colors are limited. However the original stripe could be very long, and Eva would like to have the remaining favorite stripe with the maximum length. So she needs your help to find her the best result. Note that the solution might not be unique, but you only have to tell her the maximum length. For example, given a stripe of colors {2 2 4 1 5 5 6 3 1 1 5 6}. If Eva’s favorite colors are given in her favorite order as {2 3 1 5 6}, then she has 4 possible best solutions {2 2 1 1 1 5 6}, {2 2 1 5 5 5 6}, {2 2 1 5 5 6 6}, and {2 2 3 1 1 5 6}.

Input Specification:

Each input file contains one test case. For each case, the first line contains a positive integer N (<=200) which is the total number of colors involved (and hence the colors are numbered from 1 to N). Then the next line starts with a positive integer M (<=200) followed by M Eva’s favorite color numbers given in her favorite order. Finally the third line starts with a positive integer L (<=10000) which is the length of the given stripe, followed by L colors on the stripe. All the numbers in a line are separated by a space.

Output Specification:

For each test case, simply print in a line the maximum length of Eva’s favorite stripe.

Sample Input:

6
5 2 3 1 5 6
12 2 2 4 1 5 5 6 3 1 1 5 6

Sample Output:

7

一个动态规划的题目，我们用一个map类型的order去表示他们的顺序，然后去遍历给出的序列，再用一个map类型的maxLen去记录Eva给出的那个序列在源序列里面的最大长度 比如Eva给的序列是2 3 1 5 6 Origin是2 2 4 1 5 5 那么当i = 0时，maxLen[2] = 1; i = 1时，maxLen[2] = 2; i = 3时，maxLen[1] = 3;

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
# include <cstdio>
# include <map>
# include <cstring>

using namespace std;

int main() {
    int n = 0, m = 0;
    scanf("%d %d", &n, &m);
    map<int, int> order;
    for (int i = 1; i <= m; i++) {
        int t = 0;
        scanf("%d", &t);
        order[t] = i;
    }
    int l = 0;
    scanf("%d", &l);
    int *stripes = new int[l];
    for (int i = 0; i < l; i++) {
        scanf("%d", &stripes[i]);
    }
    int *len = new int[l], i = 0;
    memset(len, 0, sizeof(len[0]));
    map<int, int> maxLen;
    while (order[stripes[i]] == 0) i++;
    len[i] = 1;
    maxLen[stripes[i]]++;
    for (i += 1; i < l; i++) {
        for (auto it = order.begin(); order[stripes[i]] != 0 && it != order.end(); it++) {
            if (it->second <= order[stripes[i]]) {
                len[i] = max(maxLen[it->first] + 1, len[i]);
            }
        }
        maxLen[stripes[i]] = len[i];
    }
    printf("%d", len[l - 1]);
    delete[] len;
    delete[] stripes;
    return 0;
}

Posted on Edited on In

The task is really simple: given N exits on a highway which forms a simple cycle, you are supposed to tell the shortest distance between any pair of exits.

Input Specification:

Each input file contains one test case. For each case, the first line contains an integer N (in [3, 105]), followed by N integer distances D1 D2 … DN, where Di is the distance between the i-th and the (i+1)-st exits, and DN is between the N-th and the 1st exits. All the numbers in a line are separated by a space. The second line gives a positive integer M (<=104), with M lines follow, each contains a pair of exit numbers, provided that the exits are numbered from 1 to N. It is guaranteed that the total round trip distance is no more than 107.

Output Specification:

For each test case, print your results in M lines, each contains the shortest distance between the corresponding given pair of exits.

Sample Input:

5 1 2 4 14 9
3
1 3
2 5
4 1

Sample Output:

3
10
7

所有的数字绕成一个环，从一点到另一个点得距离最小的就是顺时针和逆时针绕的中最小的，顺时针和逆时针是满足顺 + 逆 = 所有的距离的和的，这里的dis保存的是从1到i的顺时针路径

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
#include <cstdio>
#include <algorithm>
#include <cstring>

using namespace std;

int main() {
    int n = 0, sum = 0;
    scanf("%d", &n);
    int *dis = new int[n + 1];
    for (int i = 1; i <= n; i++) {
        int t = 0;
        scanf("%d", &t);
        dis[i] = dis[i - 1] + t;
        sum += t;
    }
    int m = 0;
    scanf("%d", &m);
    for (int i = 0; i < m; i++) {
        int a = 0, b = 0;
        scanf("%d %d", &a, &b);
        if (a > b) swap(a, b);
        int t = dis[b - 1] - dis[a - 1];
        printf("%d\n", min(t, sum - t));
    }
    delete[] dis;
    return 0;
}

Posted on Edited on In

Weibo is known as the Chinese version of Twitter. One user on Weibo may have many followers, and may follow many other users as well. Hence a social network is formed with followers relations. When a user makes a post on Weibo, all his/her followers can view and forward his/her post, which can then be forwarded again by their followers. Now given a social network, you are supposed to calculate the maximum potential amount of forwards for any specific user, assuming that only L levels of indirect followers are counted.

Input Specification:

Each input file contains one test case. For each case, the first line contains 2 positive integers: N (<=1000), the number of users; and L (<=6), the number of levels of indirect followers that are counted. Hence it is assumed that all the users are numbered from 1 to N. Then N lines follow, each in the format: M[i] user_list[i] where M[i] (<=100) is the total number of people that user[i] follows; and user_list[i] is a list of the M[i] users that are followed by user[i]. It is guaranteed that no one can follow oneself. All the numbers are separated by a space. Then finally a positive K is given, followed by K UserID‘s for query.

Output Specification:

For each UserID, you are supposed to print in one line the maximum potential amount of forwards this user can triger, assuming that everyone who can view the initial post will forward it once, and that only L levels of indirect followers are counted.

Sample Input:

7 3
3 2 3 4
0
2 5 6
2 3 1
2 3 4
1 4
1 5
2 2 6

Sample Output:

4
5

这个题目实际上是一个广度优先搜索的题目，当然你也可以用深度优先来解决，结果是一样的。对于要查询的每个节点，用广度优先遍历它的相邻节点知道达到L层

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
45
46
47
48
49
50
51
52
53
#include <cstdio>
#include <vector>
#include <queue>
#include <cstring>

using namespace std;
bool *isVisited;

unsigned long query(const vector<vector<int> > &net, queue<int> q, int l) {
    if (l == 0) return 0;
    queue<int> qt;
    while (q.size() != 0) {
        int v = q.front();
        q.pop();
        for (int i = 0; i < net[v].size(); i++) {
            if (!isVisited[net[v][i]]) {
                qt.push(net[v][i]);
                isVisited[net[v][i]] = true;
            }
        }
    }
    return query(net, qt, l - 1) + qt.size();
}

int main() {
    int n = 0, l = 0;
    scanf("%d %d", &n, &l);
    vector<vector<int> > net(n + 1);
    for (int i = 1; i <= n; i++) {
        int m = 0;
        scanf("%d", &m);
        for (int j = 0; j < m; j++) {
            int t = 0;
            scanf("%d", &t);
            net[t].push_back(i);
        }
    }

    int k = 0;
    scanf("%d", &k);
    for (int i = 0; i < k; i++) {
        int t = 0;
        scanf("%d", &t);
        queue<int> q;
        isVisited = new bool[n + 1];
        fill(isVisited, isVisited + n + 1, false);
        q.push(t);
        isVisited[t] = true;
        printf("%lu\n", query(net, q, l));
    }
    delete[] isVisited;
    return 0;
}

Posted on Edited on In

A Binary Search Tree (BST) is recursively defined as a binary tree which has the following properties:

  • The left subtree of a node contains only nodes with keys less than or equal to the node’s key.
  • The right subtree of a node contains only nodes with keys greater than the node’s key.
  • Both the left and right subtrees must also be binary search trees.

Insert a sequence of numbers into an initially empty binary search tree. Then you are supposed to count the total number of nodes in the lowest 2 levels of the resulting tree.

Input Specification:

Each input file contains one test case. For each case, the first line gives a positive integer N (<=1000) which is the size of the input sequence. Then given in the next line are the N integers in [-1000 1000] which are supposed to be inserted into an initially empty binary search tree.

Output Specification:

For each case, print in one line the numbers of nodes in the lowest 2 levels of the resulting tree in the format: n1 + n2 = n where n1 is the number of nodes in the lowest level, n2 is that of the level above, and n is the sum.

Sample Input:

9
25 30 42 16 20 20 35 -5 28

Sample Output:

2 + 4 = 6

将输入的节点插入到二叉搜索树中，把树的每个节点加入到容器中，然后遍历容器中得每个节点，求得最后两层的节点个数

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
45
46
#include <cstdio>
#include <vector>

using namespace std;

struct Node {
    int level, val;
    struct Node *left, *right;
};

int h = 0;
vector<struct Node *> v;

struct Node *insert(struct Node *root, int x, int l) {
    if (root == NULL) {
        root = new struct Node();
        root->val = x;
        root->level = l;
        v.push_back(root);
        h = l > h ? l : h;
    } else if (root->val >= x) {
        root->left = insert(root->left, x, l + 1);
    } else {
        root->right = insert(root->right, x, l + 1);
    }
    return root;
}

int main() {
    int n = 0;
    scanf("%d", &n);
    struct Node *root = NULL;
    for (int i = 0; i < n; i++) {
        int x = 0;
        scanf("%d", &x);
        root = insert(root, x, 1);
    }

    int n1 = 0, n2 = 0;
    for (vector<struct Node *>::iterator i = v.begin(); i != v.end(); i++) {
        if ((*i)->level == h) n1++;
        if ((*i)->level == h - 1) n2++;
    }
    printf("%d + %d = %d", n1, n2, n1 + n2);
    return 0;
}

Posted on Edited on In

A Binary Search Tree (BST) is recursively defined as a binary tree which has the following properties:

  • The left subtree of a node contains only nodes with keys less than or equal to the node’s key.
  • The right subtree of a node contains only nodes with keys greater than the node’s key.
  • Both the left and right subtrees must also be binary search trees.

Insert a sequence of numbers into an initially empty binary search tree. Then you are supposed to count the total number of nodes in the lowest 2 levels of the resulting tree.

Input Specification:

Each input file contains one test case. For each case, the first line gives a positive integer N (<=1000) which is the size of the input sequence. Then given in the next line are the N integers in [-1000 1000] which are supposed to be inserted into an initially empty binary search tree.

Output Specification:

For each case, print in one line the numbers of nodes in the lowest 2 levels of the resulting tree in the format: n1 + n2 = n where n1 is the number of nodes in the lowest level, n2 is that of the level above, and n is the sum.

Sample Input:

9
25 30 42 16 20 20 35 -5 28

Sample Output:

2 + 4 = 6

建立二叉搜索树，然后求最后两个的节点个数

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
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;

public class Main {
    private static List<Node> list = new ArrayList<>();
    private static int h = 0;

    public static void main(String[] args) throws IOException {

        BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(bufferedReader.readLine());
        String[] values = bufferedReader.readLine().split(" ");
        if (n >= 1 && n <= 1000) {
            Node root = new Node(Integer.parseInt(values[0]), 1);
            list.add(root);
            h = 1;
            for (int i = 1; i < values.length; i++) {
                insertNode(root, Integer.parseInt(values[i]), 1);
            }
            int n1 = 0, n2 = 0;
            for (Node node : list) {
                if (node.height == h) {
                    n1++;
                } else if (node.height == h - 1) {
                    n2++;
                }
            }

            System.out.println(n1 + " + " + n2 + " = " + (n1 + n2));
        }
    }

    private static void insertNode(Node root, int val, int high) {
        if (val <= root.val) {
            if (root.left != null) {
                insertNode(root.left, val, high + 1);
            } else {
                root.left = new Node(val, high + 1);
                h = h < root.left.height ? root.left.height : h;
                list.add(root.left);
            }

        } else {
            if (root.right != null) {
                insertNode(root.right, val, high + 1);
            } else {
                root.right = new Node(val, high + 1);
                h = h < root.right.height ? root.right.height : h;
                list.add(root.right);
            }
        }
    }
}

class Node {
    Node left, right;
    int val, height;

    public Node(int val, int height) {
        this.val = val;
        this.height = height;
        this.left = this.right = null;
    }
}

Posted on Edited on In

This time your job is to fill a sequence of N positive integers into a spiral matrix in non-increasing order. A spiral matrixis filled in from the first element at the upper-left corner, then move in a clockwise spiral. The matrix has m rows and ncolumns, where m and n satisfy the following: m*n must be equal to N; m>=n; and m-n is the minimum of all the possible values.

Input Specification:

Each input file contains one test case. For each case, the first line gives a positive integer N. Then the next line contains N positive integers to be filled into the spiral matrix. All the numbers are no more than 104. The numbers in a line are separated by spaces.

Output Specification:

For each test case, output the resulting matrix in m lines, each contains n numbers. There must be exactly 1 space between two adjacent numbers, and no extra space at the end of each line.

Sample Input:

12
37 76 20 98 76 42 53 95 60 81 58 93

Sample Output:

98 95 93
42 37 81
53 20 76
58 60 76

模拟走的路径

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
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
#include <cstdio>
#include <cmath>
#include <cstdlib>

int cmp(const void *a, const void *b) {
    int arg1 = *static_cast<const int *>(a);
    int arg2 = *static_cast<const int *>(b);

    if (arg1 < arg2) return -1;
    if (arg2 < arg1) return 1;
    return 0;
}

int main() {
    int N = 0;
    scanf("%d", &N);
    int n = sqrt(N);
    while (N % n != 0) {
        n--;
    }

    int *nums = new int[N];
    for (int i = 0; i < N; i++) {
        scanf("%d", &nums[i]);
    }
    qsort(nums, N, sizeof(nums[0]), cmp);

    int m = N / n;
    if (m < n) {
        int temp = m;
        m = n;
        n = temp;
    }
    int **spiral = new int *[m + 2];
    for (int i = 0; i <= m + 1; i++) {
        spiral[i] = new int[n + 2];
        spiral[i][0] = spiral[i][n + 1] = -1;
        if (i == 0 || i == m + 1) {
            for (int j = 1; j <= n; j++) {
                spiral[i][j] = -1;
            }
        } else {
            for (int j = 1; j <= n; j++) {
                spiral[i][j] = 0;
            }
        }
    }

    int i = 1, j = 0;
    while (N > 0) {
        while (spiral[i][j + 1] == 0) {
            j++;
            N--;
            spiral[i][j] = nums[N];
        }
        while (spiral[i + 1][j] == 0) {
            i++;
            N--;
            spiral[i][j] = nums[N];
        }
        while (spiral[i][j - 1] == 0) {
            j--;
            N--;
            spiral[i][j] = nums[N];
        }
        while (spiral[i - 1][j] == 0) {
            i--;
            N--;
            spiral[i][j] = nums[N];
        }
    }

    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            if (j == 1) printf("%d", spiral[i][1]);
            else printf(" %d", spiral[i][j]);
        }
        printf("\n");
    }

    for (int i = 0; i <= m + 1; i++) {
        delete[] spiral[i];
    }
    delete[] spiral;
    delete[] nums;

    return 0;
}

Posted on Edited on In

The Japanese language is notorious for its sentence ending particles. Personal preference of such particles can be considered as a reflection of the speaker’s personality. Such a preference is called “Kuchiguse” and is often exaggerated artistically in Anime and Manga. For example, the artificial sentence ending particle “nyan~” is often used as a stereotype for characters with a cat-like personality:

  • Itai nyan~ (It hurts, nyan~)
  • Ninjin wa iyada nyan~ (I hate carrots, nyan~)

Now given a few lines spoken by the same character, can you find her Kuchiguse?

Input Specification:

Each input file contains one test case. For each case, the first line is an integer N (2<=N<=100). Following are N file lines of 0~256 (inclusive) characters in length, each representing a character’s spoken line. The spoken lines are case sensitive.

Output Specification:

For each test case, print in one line the kuchiguse of the character, i.e., the longest common suffix of all N lines. If there is no such suffix, write “nai”.

Sample Input 1:

3
Itai nyan~
Ninjin wa iyadanyan~
uhhh nyan~

Sample Output 1:

nyan~

Sample Input 2:

3
Itai!
Ninjinnwaiyada T_T
T_T

Sample Output 2:

nai

找到每个字符串都有的后缀，从每个字符串的最后开始检查

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
#include <stack>
#include <cstring>
#include <iostream>
#include <vector>

using namespace std;

stack<char> suffix(vector<string> v) {
    stack<char> s;
    for (auto i = v[0].rbegin(); i != v[0].rend(); i++) {
        s.push(*i);
        for (int j = 1; j < v.size(); j++) {
            if (v[j].size() >= s.size() && v[j][v[j].size() - s.size()] != s.top()) {
                s.pop();
                return s;
            }
        }
    }
    return s;
}

int main() {
    int n = 0;
    cin >> n;
    getchar();
    vector<string> v(n);
    for (int i = 0; i < n; i++) {
        getline(cin, v[i]);
    }
    stack<char> s = suffix(v);
    if (s.size() == 0) {
        cout << "nai";
    }
    while (s.size() != 0) {
        cout << s.top();
        s.pop();
    }
    return 0;
}

Posted on Edited on In

It is said that in 2013, there were about 100 graduate schools ready to proceed over 40,000 applications in Zhejiang Province. It would help a lot if you could write a program to automate the admission procedure. Each applicant will have to provide two grades: the national entrance exam grade GE, and the interview grade GI. The final grade of an applicant is (GE + GI) / 2. The admission rules are:

  • The applicants are ranked according to their final grades, and will be admitted one by one from the top of the rank list.
  • If there is a tied final grade, the applicants will be ranked according to their national entrance exam grade GE. If still tied, their ranks must be the same.
  • Each applicant may have K choices and the admission will be done according to his/her choices: if according to the rank list, it is one’s turn to be admitted; and if the quota of one’s most preferred shcool is not exceeded, then one will be admitted to this school, or one’s other choices will be considered one by one in order. If one gets rejected by all of preferred schools, then this unfortunate applicant will be rejected.
  • If there is a tied rank, and if the corresponding applicants are applying to the same school, then that school must admit all the applicants with the same rank, even if its quota will be exceeded.

Input Specification:

Each input file contains one test case. Each case starts with a line containing three positive integers: N (<=40,000), the total number of applicants; M (<=100), the total number of graduate schools; and K (<=5), the number of choices an applicant may have. In the next line, separated by a space, there are M positive integers. The i-th integer is the quota of the i-th graduate school respectively. Then N lines follow, each contains 2+K integers separated by a space. The first 2 integers are the applicant’s GE and GI, respectively. The next K integers represent the preferred schools. For the sake of simplicity, we assume that the schools are numbered from 0 to M-1, and the applicants are numbered from 0 to N-1.

Output Specification:

For each test case you should output the admission results for all the graduate schools. The results of each school must occupy a line, which contains the applicants’ numbers that school admits. The numbers must be in increasing order and be separated by a space. There must be no extra space at the end of each line. If no applicant is admitted by a school, you must output an empty line correspondingly.

Sample Input:

11 6 3
2 1 2 2 2 3
100 100 0 1 2
60 60 2 3 5
100 90 0 3 4
90 100 1 2 0
90 90 5 1 3
80 90 1 0 2
80 80 0 1 2
80 80 0 1 2
80 70 1 3 2
70 80 1 2 3
100 100 0 2 4

Sample Output:

0 10
3
5 6 7
2 8

1 4

思路信息量有点多，但是题目不难，仔细看看还是能够理解出来的 我用的方法是按他们的分数进行排序，然后遍历他们申请的学校，检查是否符合条件

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
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <vector>

using namespace std;

struct Applicant {
    int ge, gi, final, rank, choices[6], id;
};

int cmp(const void *a, const void *b) {
    struct Applicant arg1 = *static_cast<const Applicant *>(a);
    struct Applicant arg2 = *static_cast<const Applicant *>(b);

    if (arg1.final > arg2.final) return -1;
    if (arg1.final < arg2.final) return 1;
    if (arg1.ge > arg2.ge) return -1;
    if (arg1.ge < arg2.ge) return 1;
    return 0;
}

bool cmpId(struct Applicant arg1, struct Applicant arg2) {
    return arg1.id < arg2.id;
}

int main() {
    int n = 0, m = 0, k = 0;
    scanf("%d %d %d", &n, &m, &k);
    int *school = new int[m];
    for (int i = 0; i < m; i++) {
        scanf("%d", &school[i]);
    }
    struct Applicant *applications = new struct Applicant[n];
    for (int i = 0; i < n; i++) {
        scanf("%d %d", &applications[i].ge, &applications[i].gi);
        applications[i].final = (applications[i].ge + applications[i].gi) / 2;
        applications[i].id = i;
        for (int j = 0; j < k; j++) {
            scanf("%d", &applications[i].choices[j]);
        }
    }

    qsort(applications, n, sizeof(applications[0]), cmp);
    for (int i = 0; i < n; i++) {
        applications[i].rank = i + 1;
        if (i > 0 && cmp(&applications[i], &applications[i - 1]) == 0) {
            applications[i].rank = applications[i - 1].rank;
        }
    }
    vector<vector<struct Applicant> > admission(m);
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < k; j++) {
            int ch = applications[i].choices[j];
            if (admission[ch].size() < school[ch] || (admission[ch].size() >= school[ch] &&
                                                      applications[i].rank ==
                                                      admission[ch][admission[ch].size() - 1].rank)) {
                admission[ch].push_back(applications[i]);
                break;
            }
        }
    }
    for (int i = 0; i < m; i++) {
        sort(admission[i].begin(), admission[i].end(), cmpId);
        for (int j = 0; j < admission[i].size(); j++) {
            if (j != 0) printf(" ");
            printf("%d", admission[i][j].id);
        }
        printf("\n");
    }
    delete[] applications;
    delete[] school;
    return 0;
}

Posted on Edited on In

Given a sequence of positive integers and another positive integer p. The sequence is said to be a “perfect sequence” if M <= m * p where M and m are the maximum and minimum numbers in the sequence, respectively. Now given a sequence and a parameter p, you are supposed to find from the sequence as many numbers as possible to form a perfect subsequence.

Input Specification:

Each input file contains one test case. For each case, the first line contains two positive integers N and p, where N (<= 105) is the number of integers in the sequence, and p (<= 109) is the parameter. In the second line there are N positive integers, each is no greater than 109.

Output Specification:

For each test case, print in one line the maximum number of integers that can be chosen to form a perfect subsequence.

Sample Input:

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

Sample Output:

8

方法：快速排序 + 二分查找 tips：M <= m * p 最好转化成 M / p <= m

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
#include <cstdlib>
#include <cstdio>

int get(int *nums, double x, int l, int r) {
    int mid = (l + r) / 2;
    if (l >= r) return mid;
    if (nums[mid] < x) return get(nums, x, mid + 1, r);
    if (nums[mid] - x < 0.1) return mid;
    else return get(nums, x, l, mid);
}

int cmp(const void *a, const void *b) {
    int arg1 = *static_cast<const int *>(a);
    int arg2 = *static_cast<const int *>(b);

    if (arg1 > arg2) return 1;
    if (arg1 < arg2) return -1;
    return 0;
}

int main() {
    int n = 0, p = 0;
    scanf("%d %d", &n, &p);
    int *nums = new int[n];
    for (int i = 0; i < n; i++) {
        scanf("%d", &nums[i]);
    }
    qsort(nums, n, sizeof(nums[0]), cmp);
    int cnt = 0;
    for (int i = n - 1; i >= 0; i--) {
        int j = get(nums, nums[i] * 1.0 / p, 0, i);
        cnt = i - j + 1 > cnt ? i - j + 1 : cnt;
    }
    printf("%d\n", cnt);
    delete[] nums;
    return 0;
}

Posted on Edited on In

设<A, ≤>是一偏序集合，B是A的子集。

(1) 元素b∈B是B的最大元素，如果对每一元素x∈B，x≤b

(2) 元素b∈B是B的最小元素，如果对每一元素x∈B，b≤x

(3)如果b∈B，且B中不存在元素x，使b≠x且b≤x，那么元素b∈B叫作B的极大元素

(4)如果b∈B，且B中不存在元素x，使b≠x且x≤b，那么元素b∈B叫作B的极小元素

(5)如果对每一b∈B，b≤a，那么a属于A叫做B的上界；如果对每一b∈B，a≤b，那么元素a属于A叫作B的下界 上面的≤特指的时偏序关系而不是≤这个比较运算符

0%