Contestant(alt). Rank 4431. Rating -40 (+310 -350).

A. Recent Actions

题意

给定一个整数 ，以及 的排列，给定 个大于 的数，若这个数不在序列里，那么将整个序列右移一位，删去多出的元素，并将第一个空位放入该数。输出原排列的每一个数在第几个数放入的时候被移除。

思路

直接用 或者数组存一下是否在序列里即可，然后统计即可。

时间复杂度：

对应AC代码

#include <bits/stdc++.h>

using namespace std;

#define int long long
#define pii pair<int, int>

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

int a[N];

signed main() {
    ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
    int q;
    cin >> q;
    while(q --){
        int n, m;
        cin >> n >> m;
        map<int, bool> st;
        vector<int> ans(n, -1);
        int r = n - 1;
        for(int i=0;i<m;i++){
            int cur;
            cin >> cur;
            if(!st[cur] && r >= 0){
                ans[r] = i + 1;
                r --;
            }
            st[cur] = true;
        }
        for(auto e : ans) cout << e << ' ';
        cout << '\n';
    }
}

题目怎么那么绕

B. Equalize by Divide

题意

给定一个数组 ，所有数均为正数，定义操作为选择两个不同的下标 ，将 改为 。输出一种方案，使所有数相等。若无方案输出无解。

思路

首先，我们不可能将所有数都变为 ，除非原来就全是 。所以我们不妨先特判是否所有数都相等，若都相等那么无需操作，否则，若数组中含有 ，就为无解。

否则，我们只需避免产生 即可，也就是用当前序列的最小值将所有数除到比最小值小或者等于为止。

上述做法可以保证最后的答案一定是有解的，若第一次操作可以构建出一个 的数组，那么就无需操作，否则最后的结果一定是 。

时间复杂度：有点复杂

对应AC代码

#include <bits/stdc++.h>

using namespace std;

#define int long long
#define pii pair<int, int>

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

int a[N];

signed main() {
    ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
    int q;
    cin >> q;
    while(q --){
        int n;
        cin >> n;
        for(int i=0;i<n;i++)cin >> a[i];
        vector<pii> ans(30 * n);
        int size = 0;
        bool h = true;
        while(true){
            bool f = false, have1 = false;
            int pre = -1, mn = 0;
            for(int i=0;i<n;i++){
                if(pre == -1) pre = a[i];
                if(pre != a[i]) f = true;
                if(a[i] == 1) have1 = true;
                if(a[mn] > a[i]) mn = i;
            }
            if(!f) break;
            if(have1){
                cout << -1 << '\n';
                h = false;
                break;
            }
            for(int i=0;i<n;i++){
                while(a[i] != a[mn]){
                    if(a[i] > a[mn]){
                        ans[size ++] = {i, mn};
                        a[i] = ceil((double) a[i] / (double) a[mn]);
                    }else{
                        ans[size ++] = {mn, i};
                        a[mn] = ceil((double) a[mn] / (double) a[i]);
                    }
                }
            }
        }
        if(h) {
            cout << size << '\n';
            for (int i = 0; i < size; i++) {
                auto e = ans[i];
                cout << e.first + 1 << ' ' << e.second + 1 << '\n';
            }
        }
    }
}

想到了一半，没想到这么暴力（（

C. Double Lexicographically Minimum

待补充

D1. Hot Start Up (easy version)

题意

给定两个 ，以及 个程序的热启动和冷启动时间，当同一种程序连续运行的时候，第二次启动称为热启动，热启动时间低于冷启动。找出一种方案，使最后运行结束每个程序所用时间总和最短，并输出最短时间。

思路

首先，考虑到递推关系，我们不妨考虑用 的方式。

最朴素的做法

我们不妨建立一个二维 ， 表示最后一次操作后第一个 运行了程序 ，第二个 运行了程序 。

那么显然，最后的答案就是 或者 。

如何递推呢？对于一个新元素 ，以及任意一个 （如第一块），它可以由两种情况推得：

1. 上一个数和它不同，那么它将成为冷启动，我们遍历所有 和 ，将 更新为 。
2. 上一个数和它相同，他么它将成为热启动，我们遍历所有 ，将 更新为 。

时间复杂度：

对应TLE代码

#include <bits/stdc++.h>

using namespace std;

#define int long long
#define pii pair<int, int>

const int N = 5e3 + 10, inf = 0x3f3f3f3f3f3f, mod = 998244353;

int a[N], h[N], c[N];

signed main() {
    ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
    int q;
    cin >> q;
    while(q --){
        int n, k;
        cin >> n >> k;
        for(int i=1;i<=n;i++) cin >> a[i];
        for(int i=1;i<=k;i++) cin >> c[i];
        for(int i=1;i<=k;i++) cin >> h[i];
        vector<vector<int>> dp(k + 1, vector<int>(k + 1));
        for(int i=0;i<=k;i++)
            for(int j=0;j<=k;j++)
                dp[i][j] = inf;
        dp[0][0] = 0;
        for(int x=1;x<=n;x++){
            vector<vector<int>> tmp(k + 1, vector<int>(k + 1, inf));
            for(int i=0;i<=k;i++){
                if(i == a[x]) continue;
                for(int j=0;j<=k;j++) tmp[a[x]][j] = min(tmp[a[x]][j], dp[i][j] + c[a[x]]);
            }
            for(int j=0;j<=k;j++) tmp[a[x]][j] = min(tmp[a[x]][j], dp[a[x]][j] + h[a[x]]);
            for(int j=0;j<=k;j++){
                if(j == a[x]) continue;
                for(int i=0;i<=k;i++) tmp[i][a[x]] = min(tmp[i][a[x]], dp[i][j] + c[a[x]]);
            }
            for(int i=0;i<=k;i++) tmp[i][a[x]] = min(tmp[i][a[x]], dp[i][a[x]] + h[a[x]]);
            dp = tmp;
        }
        int ans = inf;
        for(int j=0;j<=k;j++){
            if(j == a[n]) continue;
            ans = min(ans, dp[j][a[n]]);
        }
        cout << ans << '\n';
    }
}

Time limit exceed on test 3.

对朴素的优化

显然，上述复杂度过高，我们希望能找出一种 的递推方法。

对于上述操作，我们并没有考虑哪个元素一定要放到哪个 上去，也就是说它和 并不绑定。

那么，我们不妨用下标记录一个 的情况，另一个用 来递推。

更具体地说，我们可以记录一下上一次上个 放了什么 ()，然后对于新加入的数 ，它可以由下面两种情况推算：

1. ，那么作为冷启动，它的状态可以由所有 推得，当然，我们需要顺便更新 的值，这和朴素的做法一致。考虑到可以放置在不同的 上，所以热启动依然可行，我们将 更新为其与 的最小值。最后，我们将 改为 。
2. ，那么和上述相同的是，依然存在冷热启动，只是在更新 的时候，它可以热启动罢了。

时间复杂度：

对应AC代码

#include <bits/stdc++.h>

using namespace std;

#define int long long
#define pii pair<int, int>

const int N = 5e3 + 10, inf = 0x3f3f3f3f3f3f, mod = 998244353;

int a[N], h[N], c[N];

signed main() {
    ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
    int q;
    cin >> q;
    while(q --){
        int n, k;
        cin >> n >> k;
        for(int i=1;i<=n;i++) cin >> a[i];
        for(int i=1;i<=k;i++) cin >> c[i];
        for(int i=1;i<=k;i++) cin >> h[i];
        vector<int> dp(k + 1);
        for(int i=1;i<=k;i++) dp[i] = inf;
        int pre = 0;
        for(int p=1;p<=n;p++){
            int x = a[p];
            vector<int> tmp(k + 1, inf);
            if(x == pre){
                for(int i=0;i<=k;i++){
                    tmp[i] = min(tmp[i], dp[i] + h[x]);
                    if(i != x) tmp[x] = min(tmp[x], dp[i] + c[x]);
                }
                tmp[x] = min(tmp[x], dp[x] + h[x]);
            }else{
                for(int i=0;i<=k;i++){
                    tmp[i] = min(tmp[i], dp[i] + c[x]);
                    if(i != x) tmp[pre] = min(tmp[pre], dp[i] + c[x]);
                }
                tmp[pre] = min(tmp[pre], dp[x] + h[x]);
                pre = x;
            }
            dp = tmp;
        }
        int ans = inf;
        for(int i=0;i<=k;i++) ans = min(ans, dp[i]);
        cout << ans << '\n';
    }
}

好难解释….