Practice.

A. Echo

题意

给定一个字符串，遍历所有字符，并按顺序输出两个。

如 \(abc \rightarrow aabbcc\)。

思路

如题。

时间复杂度：\(O(n)\)

对应AC代码

#include <bits/stdc++.h>

using namespace std;

#define int long long
#define pii pair<int, int>
#define ppii pair<int, pii>
#define pci pair<char, int>
#define fs first
#define sc second
#define pb emplace_back
#define all(x) x.begin(),x.end()

const int N = 2e5 + 10, mod = 998244353, inf = 0x3f3f3f3f3f3f3f3f;

void solve() {
    int n;
    string s;
    cin >> n >> s;
    for(int i=0;i<n;i++) cout << s[i] << s[i];
    cout << '\n';
}

signed main(){
    ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    int t = 1;
    //cin >> t;
    while(t --) solve();
}

签到

B. Base 2

题意

给定一个长为 \(64\) 的序列 \(A\)，下标从 \(0\) 开始。

输出 \(A_02^0 + A_12^1 + \ldots+A_{63}2^{63}\)。

思路

如题。

时间复杂度：\(O(n)\)

对应AC代码

#include <bits/stdc++.h>

using namespace std;

#define int long long
#define pii pair<int, int>
#define ppii pair<int, pii>
#define pci pair<char, int>
#define fs first
#define sc second
#define pb emplace_back
#define all(x) x.begin(),x.end()

const int N = 2e5 + 10, mod = 998244353, inf = 0x3f3f3f3f3f3f3f3f;

void solve() {
    vector<int> in(64);
    for(int i=0;i<64;i++) cin >> in[64 - i - 1];
    unsigned int ans = 0;
    for(int i=0;i<64;i++) ans = ans * 2 + in[i];
    cout << ans << '\n';
}

signed main(){
    ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    int t = 1;
    //cin >> t;
    while(t --) solve();
}

记得加个 \(unsigned\)，不然会爆 \(long\ long\)

C. Centers

题意

给定一个长为 \(3n\) 的序列 \(A\)，\(A\) 为 \(\{1, 1, 1, 2, 2, 2, \ldots, n, n, n\}\) 打乱顺序后的序列。

对于排列 \(\{1, 2, 3, \ldots,n\}\)，将其按照每个数在序列 \(A\) 中第二次出现的下标升序排序，并输出结果。

思路

如题。

时间复杂度：\(O(3n)\)

对应AC代码

#include <bits/stdc++.h>

using namespace std;

#define int long long
#define pii pair<int, int>
#define ppii pair<int, pii>
#define pci pair<char, int>
#define fs first
#define sc second
#define pb emplace_back
#define all(x) x.begin(),x.end()

const int N = 2e5 + 10, mod = 998244353, inf = 0x3f3f3f3f3f3f3f3f;

void solve() {
    int n;
    cin >> n;
    vector<int> pre(n, -1);
    vector<pii> mid(n, {-1, - 1});
    for(int i=0;i<3*n;i++){
        int cur;
        cin >> cur;
        cur --;
        if(pre[cur] == -1) pre[cur] = inf;
        else if(mid[cur].fs == -1){
            mid[cur] = {i + 1, cur + 1};
        }
    }
    sort(all(mid));
    for(auto [ind, what] : mid) cout << what << ' ';
    cout << '\n';
}

signed main(){
    ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    int t = 1;
    //cin >> t;
    while(t --) solve();
}

就是略微有点小麻烦

D. Poisonous Full-Course

题意

给定 \(n\) 道菜，每道菜具有美味值以及类型，类型分为有毒和无毒。

规定需要按顺序吃菜，但可选择是否跳过这道菜，输出满足下面条件的美味值之和的最大值：

  1. 吃两道有毒的菜会去世

  2. 无毒的菜可以抵消有毒的菜

换言之，连续吃两道有毒的菜会去世。

思路

既然美味值可以为负，我们就无法贪心，因此我们考虑 \(dp\)。

记 \(dp[i][j]\) 为前 \(i\) 道菜的方案中美味值的最大值，\(j\) 表示当前是否刚吃有毒的菜。

那么我们设当前菜的美味值为 \(y\)，我们进行分讨：

  1. 当前菜有毒，那么 \(dp[i][0] = dp[i - 1][0], dp[i][1] = \max(dp[i][1], dp[i - 1][0] + y)\)；

  2. 当前菜没毒，那么 \(dp[i][0] = \max(dp[i - 1][0], \max(dp[i - 1][0], dp[i - 1][1]) + y), dp[i][1] = dp[i - 1][1]\)。

时间复杂度：\(O(n)\)

对应AC代码

#include <bits/stdc++.h>

using namespace std;

#define int long long
#define pii pair<int, int>
#define ppii pair<int, pii>
#define pci pair<char, int>
#define fs first
#define sc second
#define pb emplace_back
#define all(x) x.begin(),x.end()

const int N = 2e5 + 10, mod = 998244353, inf = 0x3f3f3f3f3f3f3f3f;

void solve() {
    int n;
    cin >> n;
    vector<vector<int>> dp(n + 1, vector<int>(2)); //前面是否有毒的
    for(int i=1;i<=n;i++){
        int x, y;
        cin >> x >> y;
        dp[i][0] = dp[i - 1][0], dp[i][1] = dp[i - 1][1];
        if(x == 0) dp[i][0] = max(dp[i][0], max(dp[i - 1][0], dp[i - 1][1]) + y);
        else dp[i][1] = max(dp[i][1], dp[i - 1][0] + y);
    }
    cout << max(dp[n][0], dp[n][1]) << '\n';
}

signed main(){
    ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    int t = 1;
    //cin >> t;
    while(t --) solve();
}

我居然会写.jpg

E. Best Performances

题意

给定一个序列 \(A\)，初始状态下全是 \(0\)。记序列 \(A\) 降序排序后的新序列为 \(B\)。

给定一个整数 \(k\)，现在，给定 \(q\) 次查询，每次查询给定两个整数 \(x, y\)，将 \(A_x := y\)，并输出序列 \(B\) 的前 \(k\) 项和。

思路

我们考虑用多重集来维护。

我们用两个多重集分别维护前 \(k\) 项 以及剩余的项。

那么，在每次更改后，我们分讨并更新多重集以及答案即可。

时间复杂度：\(O(n \log n)\)

对应AC代码

#include <bits/stdc++.h>

using namespace std;

#define int long long
#define pii pair<int, int>
#define ppii pair<int, pii>
#define pci pair<char, int>
#define fs first
#define sc second
#define pb emplace_back
#define all(x) x.begin(),x.end()

const int N = 2e5 + 10, mod = 998244353, inf = 0x3f3f3f3f3f3f3f3f;

void solve() {
    int n, k, q;
    cin >> n >> k >> q;
    multiset<pii> g, l;
    vector<int> a(n + 1, 0);
    int sum = 0;
    for(int i=1;i<=k;i++) g.emplace(0, i);
    for(int i=k+1;i<=n;i++) l.emplace(0, i);
    while(q --){
        int x, y;
        cin >> x >> y;
        auto gp = g.find({a[x], x}), lp = l.find({a[x], x});
        if(gp != g.end()){
            g.erase(gp);
            sum -= a[x];
            a[x] = y;
            if(l.empty() || y >= (*l.rbegin()).fs){
                g.emplace(y, x);
                sum += y;
            }else{
                auto ll = *l.rbegin();
                l.erase(l.find(ll));
                l.emplace(y, x);
                g.emplace(ll);
                sum += ll.fs;
            }
        }else{
            l.erase(lp);
            a[x] = y;
            if(g.empty() || y <= (*g.begin()).fs){
                l.emplace(y, x);
            }else{
                auto gg = *g.begin();
                g.erase(g.find(gg));
                g.emplace(y, x);
                l.emplace(gg);
                sum -= gg.fs;
                sum += y;
            }
        }
        cout << sum << '\n';
    }
}

signed main(){
    ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    int t = 1;
    //cin >> t;
    while(t --) solve();
}

这分讨就很史

F. Merge Sets

题意

给定 \(n\) 个长为 \(m\) 的序列 \(S_i\)，所有序列中的元素均不相同。

对于序列 \(A, B\)，记 \(C\) 为 \(A \cup B\) 升序排序后的新序列，找出 \(A\) 中的所有元素在 \(C\) 中的新下标 \(k_i\)，下标之和即为 \(f(A, B)\)。

求 \(\displaystyle{\sum_{1 \leq i < j \leq n} f(A_i, S_j)}\)。

思路

对于第 \(i\) 个元素，如果它的序列编号为 \(p\)，我们就需要知道 \(p\) 和 \([p + 1, n]\) 中的序列进行一一组合后，该元素在所有合并序列中的下标之和。

那么，如果设 \(q \in [p + 1, n]\)，序列 \(p, q\) 合并后，新序列中，该元素位于的下标为 \((p\) 中小于它的元素数量 \(+\) \(q\) 中小于它的元素数量 $ + 1)$。

不难发现，大小关系的判断可以通过排序实现。而排序之后，所需求的数量问题即可转化为前缀和问题。

因而，更具体地说：

  1. 将 所有元素 以及 他所在序列的编号 一起放入序列中，然后按照元素的大小升序排序；

  2. 在遍历的同时记录前缀和。在遍历到第 \(i\) 个元素时，我们记 \(pre[x]\) 为编号为 \(x\) 的序列中有多少个数比这个数小；

  3. 若第 \(i\) 个元素对应的序列编号为 \(p\)，那么遍历 \(q \in [p + 1, n]\)，统计 \(pre[p] + pre[q] + 1\) 之和。

自然，上述操作有点过于暴力，若需优化可使用树状数组。

时间复杂度：\(O(nmq),q\in[1,n]\)

对应AC代码

#include <bits/stdc++.h>

using namespace std;

#define int long long
#define pii pair<int, int>
#define ppii pair<int, pii>
#define pci pair<char, int>
#define fs first
#define sc second
#define pb emplace_back
#define all(x) x.begin(),x.end()

const int N = 2e5 + 10, mod = 998244353, inf = 0x3f3f3f3f3f3f3f3f;

void solve() {
    int n, m;
    cin >> n >> m;
    vector<pii > merge(n * m);
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            int x;
            cin >> x;
            merge[i * m + j] = {x, i};
        }
    }
    sort(all(merge));
    int ans = 0;
    vector<int> pre(n);
    for (int i = 0; i < n * m; i++) {
        auto [val, ind] = merge[i];
        pre[ind]++;
        for (int j = ind + 1; j < n; j++) ans += pre[ind] + pre[j];
    }
    cout << ans << '\n';
}

signed main(){
    ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    int t = 1;
    //cin >> t;
    while(t --) solve();
}

抽象