Andrewei's Blog
0%

Codeforces #323(div.2) C D题

发表于 更新于 分类于 ，

C题（GCD Table）

题目链接: http://codeforces.com/contest/583/problem/C

题目大意:

定义 gcd 矩阵 b 为数组 a 中的元素两两求 GCD 得到， 即 b[i][j] = GCD(a[i], a[j]), 现给出数组 b 中所有数的乱序，求数组 a 中的元素，存在多种解时，给出任意一个解的任意一种排列。

解题思路:

观察矩阵 b 的结构可知，首先矩阵 b 是一个对称矩阵，我们所求的其实就是矩阵 b 的主对角元素，其次矩阵 b 的对角元素其实是所在行和列的最大的元素。

由此我们可以这么求解这道题（以 N <= 2 为例）, 首先从所给的 N * N 个数的集合中选出最大的两个值， 这两个值一定是答案中的值，把它们放入答案中并从集合中删掉，然后求出这两个值的 GCD， 把这个 GCD 删掉，再找出剩下的所有数中的最大值放入答案中并从原来的集合中删掉， 以此类推， 最终可以求出需要的 N 个数。

贴出代码：

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
/*=============================================================================
# Author:			DATASOURCE
# Last modified: 	2015-10-05 14:35
# Filename: 		323C.cpp
# Description: 
=============================================================================*/

#include <map>
#include <cmath>
#include <queue>
#include <stack>
#include <vector>
#include <cstdio>
#include <string>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <algorithm>
#define lson l, mid, ls
#define rson mid, r, rs
#define ls (rt << 1) + 1
#define rs (rt << 1) + 2
using namespace std;

int res[550];
map <int, int> ma;
map <int, int>::reverse_iterator riter;

int GCD(int a, int b){
    if(a < b) return GCD(b, a);
    else if(a == 0) return b;
    return GCD(b % a, a);
}

int main(){
    int n, v;
    while(~scanf("%d", &n)){
        for(int i = 0; i < n * n; i++){
            scanf("%d", &v);
            ma[v]++;
        }
        int cnt = 0;
        while(cnt < n){
            riter = ma.rbegin();
            int tmp = riter -> first;
            ma[tmp]--;
            if(ma[tmp] == 0) ma.erase(tmp);
            for(int i = 0; i < cnt; i++){
                int gcd = GCD(res[i], tmp);
                ma[gcd] -= 2;
                if(ma[gcd] == 0) ma.erase(gcd);
            }
            res[cnt++] = tmp;
        }
        for(int i = 0; i < cnt; i++)
            printf("%d%c", res[i], i == cnt - 1 ? '\n' : ' ');
    }
    return 0;
}

D题（Once Again）

题目链接：http://codeforces.com/contest/583/problem/D

题目大意：

有一个元素个数为 n * t 的数组，数组中的元素满足 $a[i] = a[i + n]$, 求解最长不降子序列的长度。

数据范围：$1 <= n <= 100, 1 <= t <= 10^7, 1 <= a[i] <= 300$;

解题思路：

  1. 当 t < n 时, 直接 n(log(n))求解最长不减子序列。
  2. 当 t <= n 时, 通过观察可以知道，最多取 n 次就可以将前n个元素完全取到（比如序列 5, 4, 3, 2,1 我们第一次取 1, 第二次取 2, …… 第五次取 5, 这样取五次就可以取完，然而对于 1, 2, 3, 4, 5 这个序列只需要一次就可以取完所有的数）， 所以对于 t <= n 的情况我们可以直接求解 n * n 这么个长度， 然后再加上我们抛弃的那一段某些数字的重复（ 比如样例 n = 4, t = 3, a[i] =  3, 1, 4, 2 , 我们最终选择的序列为 1, 2, 3, 4, 4，在这里也就是最后选择了 4 不断重复）。
  3. 需要注意的是 1, 2, 3, 3, 4, 这种情况，在这种情况下，我们最终取到的最长不降子序列应该是 1, 2, 3, 3, 3, 3, … 3, 3, 4. 也就是说我们选择的那个不断重复的数字应该是在 a[1….n] 中重复出现最多的那个数字。

贴出代码：

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
/*=============================================================================
# Author:			DATASOURCE
# Last modified: 	2015-10-05 17:56
# Filename: 		323D.cpp
# Description: 
=============================================================================*/

#include <map>
#include <cmath>
#include <queue>
#include <stack>
#include <vector>
#include <cstdio>
#include <string>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <algorithm>
#define lson l, mid, ls
#define rson mid, r, rs
#define ls (rt << 1) + 1
#define rs (rt << 1) + 2
using namespace std;
const int MAXN = 11000; 
int a[MAXN];
int b[MAXN];
int cnt[MAXN];

int Find(int i, int R){
    int l = 0, r = R, mid;
    while(r - l < 1){
        mid = (l + r) /2;
        if(b[mid] <= a[i]) l = mid;
        else r = mid;
    }
    return r;
}

int main(){
    int n, t;
    while(scanf("%d%d", &n, &t) != EOF){
        memset(cnt, 0, sizeof(cnt));
        for(int i = 1; i <= n; i++){
            scanf("%d", &a[i]);
            cnt[a[i]]++;
        }

        int num = 0;
        for(int i = 0; i < 330; i++)
            if(cnt[i]) num = max(num, cnt[i]);

        int end = min(t, n), dx = n + 1;
        for(int j = 1; j < end; j++)
            for(int i = 1; i <= n; i++)
                a[dx++] = a[i];

        int ans = 1;
        b[1] = a[1];
        for(int i = 2; i < dx; i++){
            if(a[i] <= b[ans]) b[++ans] = a[i];
            else b[Find(i, ans)] = a[i];
        }

        ans += num * max(t - n, 0);
        printf("%d\n", ans);
    }
    return 0;
}