Contestant(alt). Rank 4431. Rating -40 (+310 -350).
A. Recent Actions
题意
给定一个整数 \(n\)，以及 \(n\) 的排列，给定 \(m\) 个大于 \(n\) 的数，若这个数不在序列里，那么将整个序列右移一位，删去多出的元素，并将第一个空位放入该数。输出原排列的每一个数在第几个数放入的时候被移除。
思路
直接用 \(map\) 或者数组存一下是否在序列里即可，然后统计即可。
时间复杂度：\(O(n)\)
对应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
题意
给定一个数组 \(a\)，所有数均为正数，定义操作为选择两个不同的下标 \(i, j\)，将 \(a_i\) 改为 \(\lceil \frac{a_i}{a_j} \rceil\)。输出一种方案，使所有数相等。若无方案输出无解。
思路
首先，我们不可能将所有数都变为 \(1\)，除非原来就全是 \(1\)。所以我们不妨先特判是否所有数都相等，若都相等那么无需操作，否则，若数组中含有 \(1\)，就为无解。
否则，我们只需避免产生 \(1\) 即可，也就是用当前序列的最小值将所有数除到比最小值小或者等于为止。
上述做法可以保证最后的答案一定是有解的，若第一次操作可以构建出一个 \([\min, \min, ..., \min]\) 的数组，那么就无需操作，否则最后的结果一定是 \([2, 2, ..., 2]\)。
时间复杂度：有点复杂
对应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)
题意
给定两个 \(CPU\)，以及 \(n\) 个程序的热启动和冷启动时间，当同一种程序连续运行的时候，第二次启动称为热启动，热启动时间低于冷启动。找出一种方案，使最后运行结束每个程序所用时间总和最短，并输出最短时间。
思路
首先，考虑到递推关系，我们不妨考虑用 \(dp\) 的方式。
最朴素的做法
我们不妨建立一个二维 \(dp\)，\(dp[i][j]\) 表示最后一次操作后第一个 \(CPU\) 运行了程序 \(i\)，第二个 \(CPU\) 运行了程序 \(j\)。
那么显然，最后的答案就是 \(\min(dp[i][a[n]])\) 或者 \(\min(dp[a[n]][j])\)。
如何递推呢？对于一个新元素 \(x\)，以及任意一个 \(CPU\)（如第一块），它可以由两种情况推得：
- 上一个数和它不同，那么它将成为冷启动，我们遍历所有 \(i \neq x\) 和 \(j\)，将 \(dp[x][j]\) 更新为 \(\min(dp[i][j] + c[x])\)。
- 上一个数和它相同，他么它将成为热启动，我们遍历所有 \(j\)，将 \(dp[x][j]\) 更新为 \(\min(dp[x][j] + h[x])\)。
时间复杂度：\(O(n k ^ 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.
对朴素的优化
显然，上述复杂度过高，我们希望能找出一种 \(O(n)\) 的递推方法。
对于上述操作，我们并没有考虑哪个元素一定要放到哪个 \(CPU\) 上去，也就是说它和 \(CPU\) 并不绑定。
那么，我们不妨用下标记录一个 \(CPU\) 的情况，另一个用 \(dp\) 来递推。
更具体地说，我们可以记录一下上一次上个 \(CPU\) 放了什么 (\(pre\))，然后对于新加入的数 \(x\)，它可以由下面两种情况推算：
- \(pre \neq x\)，那么作为冷启动，它的状态可以由所有 \(i \neq x, dp[i] + c[x]\) 推得，当然，我们需要顺便更新 \(dp[i]\) 的值，这和朴素的做法一致。考虑到可以放置在不同的 \(CPU\) 上，所以热启动依然可行，我们将 \(dp[pre]\) 更新为其与 \(dp[x] + h[x]\) 的最小值。最后，我们将 \(pre\) 改为 \(x\)。
- \(pre = x\)，那么和上述相同的是，依然存在冷热启动，只是在更新 \(dp[i]\) 的时候，它可以热启动罢了。
时间复杂度：\(O(nk)\)
对应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';
}
}好难解释....