首页 程序设计 Codeforces

# A

输出 n−1n-1 即可

1
2
3
4
void solve () {
    cin >> n;
    cout << n - 1 << endl;
}

# B

遇到 p 输出 q ，遇到 q 输出 p ， w 保持不变，记得输出前 reversereverse 一下整个字符串

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
void solve () {
    string s;
    cin >> s;
    reverse(s.begin(), s.end());
    for (char c : s) {
        if (c == 'p')
            cout << 'q';
        else if (c == 'q')
            cout << 'p';
        else
            cout << c;
    }

    cout << endl;
}

# C

# 题意

一个教室有 mm 列，22 行座位
三种猴子

  1. AA 猴子只坐第一排
  2. BB 猴子只坐第二排
  3. CC 猴子随便坐

问：最多能给多少只猴子上课

# 题解

只需要先行排 AA 和 BB 猴子，剩下的若还有空位，插 CC 猴子即可

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
void solve () {
    cin >> m >> a >> b >> c;
    int line1 = m, line2 = m, res = 0;

    if (line1 >= a)
        res += a, line1 -= a, a = 0;
    else
        res += line1, a -= line1, line1 = 0;
    
    if (line2 >= b)
        res += b, line2 -= b, b = 0;
    else
        res += line2, b -= line2, line2 = 0;

    res += min(line1 + line2, c);

    cout << res << endl;
}

# D

# 题意

给定一个序列 A=(a1,a2,...,an)A=(a_1, a_2,...,a_n)，构造一个 BB 序列，使得
对于 ∀ai\forall a_i，满足 b1→bib_1 \to b_i 中，aia_i 的出现次数是最多的之一

# 错解

没注意到题目说的 bi≤nb_i \le 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
void solve () {
    memset(b, 0, sizeof b);
    memset(cnt, 0, sizeof cnt);

    cin >> n;
    for (int i = 1; i <= n; i++)
        cin >> a[i];

    b[1] = a[1], cnt[a[1]] = 1;

    int maxLen = 1;
    priority_queue<int, vector<int>, greater<int>> heap;

    for (int i = 2; i <= n; i++) {
        int happen = cnt[a[i]];

        while (!heap.empty() && happen < maxLen) {
            auto t = heap.top();
            heap.pop();

            b[t] = a[i], happen++;
        }

        if (happen < maxLen)
            b[i] = a[i], happen++;

        cnt[a[i]] = happen;

        maxLen = max(maxLen, cnt[a[i]]);

        if (b[i] == 0)
            heap.push(i);
    }

    int more = n + 1;
    for (int i = 1; i <= n; i++)
        cout << (b[i] == 0 ? more++ : b[i]) << " ";
    cout << endl;
}

# 正解

注意到 ∀bi≤n\forall~b_i \le 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
int n, a[N], b[N];
bool flag[N];

void solve () {
    memset(flag, 0, sizeof flag);
    memset(b, 0, sizeof b);

    int idx = 1;
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        if (!flag[a[i]])
            b[idx] = a[i], flag[a[i]] = true, idx++;
    }

    int num = 1;
    while (idx <= n) {
        while (flag[num])
            num++;
        b[idx++] = num, flag[num] = true, num++;
    }

    for (int i = 1; i <= n; i++)
        cout << b[i] << " ";

    cout << endl;
}

# E

# 题意

本质上其实是个数学题，给定两个 rangerange，x:l1→r1x:~l1 \to r1，y:l2→r2y:~l2 \to r2，再给定一个 kk
问：能找到多少对数，满足 yx=kn,n≥0\frac{y}{x} = k^n,~n \ge 0
1≤l1,r1,l2,r2≤1091 \le l_1,r_1,l_2,r_2 \le 10^9

# 题解

数的范围很大，不如换个思路，枚举 knk^n 呢？
题目的是 yx=kn\frac{y}{x} = k^n，可以想成 y=kn∗xy = k^n * x。
我们不妨从 kk = 1 (kk = k^n) 开始枚举，枚举到 kk≤r2kk \le r2
对于每一个确定的 kkkk，我们可以找一个确定的 yy 的界限或者 xx 的界限
假设找 xx 的界限

  • x=llx = ll 最小可以取到多少：
    • 从 l1l_1 开始？
    • 从 ⌈l2kk⌉\lceil\frac{l_2}{kk}\rceil 开始？
    • 两者之间取 maxmax
  • x=lrx = lr 最大可以到多少：
    • 取到 r1r_1（从最小到 r1r_1 所有都能取）
    • 取到 ⌊r2kk⌋\lfloor\frac{r_2}{kk}\rfloor
    • 两者取 minmin

对于一个指定的 kk=knkk = k^n，则 ll→lrll \to lr 的 x∗x^*，都能被取且都能再 y:l2→r2y: l_2 \to r_2 中找到对应的 y∗y^*

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
void solve () {
    cin >> k >> l1 >> r1 >> l2 >> r2;

    int ans = 0, kk = 1;

    while (kk <= r2) {
        int ll = max(l1, (l2 + k - 1) / kk), lr = min(r1, r2 / kk);

        if (ll <= lr)
            ans += lr - ll + 1;

        kk *= k;
    }

    cout << ans << endl;
}

# F

# 题意

给定 A=(a1,a2,...,an)A=(a_1,a_2,...,a_n) 和 B=(b1,b2,...,bm)B=(b_1,b_2,...,b_m)，构造出 MM 矩阵，Mij=ai∗bj,1≤i≤n,1≤j≤mM_{ij} = a_i * b_j,~1 \le i \le n, 1 \le j \le m
问：给定若干个 xx，对于每一个 xx，令 Mxy=0,(x==i)+(y==j)>=1M_{xy} = 0,~(x == i) + (y == j) >= 1 后，矩阵总和为 xx

# TLE 寄答案

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
void solve() {
    int sumA = 0, sumB = 0, sum = 0;

    cin >> n >> m >> q;
    for (int i = 1; i <= n; i++)
        cin >> a[i], sumA += a[i];
    for (int i = 1; i <= m; i++)
        cin >> b[i], sumB += b[i];

    sort(b + 1, b + m + 1);

    sum = sumA * sumB;

    while (q--) {
        bool flag = false;

        cin >> x;

        for (int i = 1; i <= n; i++) {
            if (sumA - a[i] == 0)
                continue;
            if (x % (sumA - a[i]) != 0)
                continue;

            int bJ = sumB - x / (sumA - a[i]);

            int l = 1, r = m;

            while (l <= r) {
                int mid = l + r >> 1;
                if (b[mid] == bJ) {
                    cout << "YES" << endl;
                    flag = true;
                    break;
                }

                if (b[mid] > bJ)
                    r = mid - 1;
                else
                    l = mid + 1;
            }

            if (flag)
                break;
        }

        if (!flag)
            cout << "NO" << endl;
    }
}

# 正解

上面那个错误解法的时间复杂度是 O(Q⋅N⋅log⁡M)O(Q·N·\log{M})
不如换种想法，只要预处理好每一个 sumA - a[i] 和 sumB - b[i] ，分别放在两个 setset 中
对于每个 xx，从 i = 1 找到 i * i <= abs(x)
只要能在 AA 和 BB 中找到无论顺序的 ii 和 xi\frac{x}{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
29
30
31
32
33
34
35
36
37
38
int n, m, a[N], b[N], q, x;
set<int> A, B;

void solve() {
    int sumA = 0, sumB = 0, sum = 0;

    cin >> n >> m >> q;
    for (int i = 1; i <= n; i++)
        cin >> a[i], sumA += a[i];
    for (int i = 1; i <= m; i++)
        cin >> b[i], sumB += b[i];

    for (int i = 1; i <= n; i++)
        A.insert(sumA - a[i]);
    for (int i = 1; i <= m; i++)
        B.insert(sumB - b[i]);
    
    while (q--) {
        cin >> x;

        bool flag = 0;
        int res = abs(x);
    
        for (int i = 1; i <= res / i&& !flag; i++)
            if (res % i == 0) {
                if(A.count(i) && B.count(x / i))
                    flag = 1;
				else if(A.count(-i) && B.count(-x / i))
                    flag = 1;
				else if(B.count(i) && A.count(x / i))
                    flag = 1;
                else if(B.count(-i) && A.count(-x / i))
                    flag = 1;
            }

        cout << (flag ? "YES" : "NO") << endl;
    }
}

# 时间复杂度分析

初始化复杂度：O(n+m+nlog⁡n+mlog⁡m)O(n+m+n\log n+m\log m)
每个查询的复杂度：O(Q∗(x∗(log⁡n+log⁡m)))O(Q * (\sqrt {x} * (\log{n} + \log{m})))
总时间复杂度：O(nlog⁡n+mlog⁡m+(Q∗(x∗(log⁡n+log⁡m)))O(n\log n+m\log m + (Q * (\sqrt {x} * (\log{n} + \log{m})))

更新于 阅读次数 次

请我喝[茶]~(￣▽￣)~*

duoxichangan 微信支付

微信支付

duoxichangan 支付宝

支付宝