比赛链接

D题

将1的移动转换为0的移动，所有的0都要移动到1的两侧，统计每个0左右两侧1的个数，取最小值，则为移动该0所需的最小步数。

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
int main() {
    std::ios::sync_with_stdio(false);
    cin.tie(nullptr), cout.tie(nullptr);
    
    int n;
    string s;
    cin >> n >> s;
    std::vector<int> dp1(n), dp2(n);
    
    for (int i = 1; i < n; i++) {
        if (s[i - 1] == '1') {
            dp1[i] = dp1[i - 1] + 1;
        } else {
            dp1[i] = dp1[i - 1];
        }
    }
    for (int i = n - 2; i >= 0; i--) {
        if (s[i + 1] == '1') {
            dp2[i] = dp2[i + 1] + 1;
        } else {
            dp2[i] = dp2[i + 1];
        }
    }
    i64 ans = 0;
    for (int i = 0; i < n; i++) {
        if (s[i] == '0') {
            ans += std::min(dp1[i], dp2[i]);
        }
    }
    cout << ans;
    return 0;
}

E题

枚举**$[1,N]$中的每一个数字i，查找i可以是A数组中多少个数字的因子，取个数$\geq k$的因子，从小到大枚举这些因子可以作为数字$[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
int main() {
    int n, k;
    const int N = 1000005;
    n = read<int>();
    k = read<int>();
    std::vector<int> a(n);
    std::vector<int> cnt(N);
    std::vector<int> fcnt(N);
    for (int i = 0; i < n; i++) {
        a[i] = read<int>();
        cnt[a[i]]++;
        fcnt[a[i]]++;
    }
    for (int i = 1; i < N; i++) {
        for (int j = 2; i * j < N; j++) {
            fcnt[i] += cnt[i * j];
        }
    }
    std::vector<int> fac;
    std::vector<int> ans(N);
    for (int i = 1; i < N; i++) {
        if (fcnt[i] >= k) {
            fac.push_back(i);
        }
    }
    for (int i : fac) {
        for (int j = 1; j * i < N; j++) {
            ans[j * i] = i;
        }
    }
    for (int i : a) {
        print(ans[i], '\n');
    }

    return 0;
}

F题

从1到n枚举A[i]，并修改dp表，dp[j]表示长度为j的LIS的最小结尾。将询问按Ri的下标索引存储起来，以便于离线查询。二分寻找对应位置：

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
int main() {
    std::ios::sync_with_stdio(false);
    cin.tie(nullptr), cout.tie(nullptr);
    int n, q;
    cin >> n >> q;
    std::vector<int> a(n);
    for (int & i : a) {
        cin >> i;
    }
    
    std::vector<std::vector<PII>> que(n);
    for (int i = 0; i < q; i++) {
        int r, x;
        cin >> r >> x;
        que[r - 1].push_back({i, x});
    }
    
    std::vector<int> dp(n, INF);
    std::vector<int> ans(q);
    for (int i = 0; i < n; i++) {
        *(std::lower_bound(dp.begin(), dp.end(), a[i])) = a[i];
        for (auto & [id, x] : que[i]) {
            ans[id] = std::upper_bound(dp.begin(), dp.end(), x) - dp.begin();
        }
    }
    for (int i : ans) {
        cout << i << "\n";
    }
    return 0;
}