Contestant. Rank 1335. Rating +80.
A. MEXanized Array
题意
给定三个整数 \(n, k, x\)，构造一个长为 \(n\) 的数组，满足 \(MEX = k\)，最大值不超过 \(x\)。
输出数组总和的最大值。无法构造输出 \(-1\)。
思路
首先，如果 \(MEX\) 大于数组的长度，或者大于数组的最大值 \(+ 1\)，那么就无法构造。
否则，我们就只需对 \(MEX\) 和最大值的大小关系进行特判即可。
我们先依次填入 \(0, 1, 2, \ldots, k - 1\)，然后剩余的都填上最大值。如果最大值是 \(MEX\)，那么我们应该填上 最大值 $ - 1$。
时间复杂度：\(O(1)\)
对应AC代码
#define chatgpt3_5 "bits/stdc++.h"
#define chatgpt4 "bits/extc++.h"
#include chatgpt3_5
using namespace std;
//#define FLOATING_OCEAN
#define int long long
#define pii pair<int, int>
#define pipi pair<pii, pii>
#define tpi tuple<int, int, int>
#define fs first
#define sc second
#define pb emplace_back
#define ep emplace
#define rall(x) x.rbegin(),x.rend()
#define all(x) x.begin(),x.end()
const int N = 1e6 + 10, M = 2e5 + 10, mod = 1e9 + 7, inf = 0x3f3f3f3f3f3f3f3f;
const double eps = 1e-9, PI = acos(-1);
void solve() {
int n, k, x;
cin >> n >> k >> x;
if(k > n || k > x + 1){
cout << -1 << '\n';
return;
}
int sum = 0;
for(int i=0;i<k;i++) sum += i;
sum += (n - k) * (x - (x == k ? 1 : 0));
cout << sum << '\n';
}
signed main() {
# ifdef FLOATING_OCEAN
freopen("1.in","r",stdin);
freopen("1.out","w",stdout);
# endif
ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
// init();
int t = 1;
cin >> t;
while (t--) solve();
}签到签到
B. Friendly Arrays
题意
给定一个长为 \(n\) 的序列 \(a\)，以及一个长为 \(m\) 的序列 \(b\)，定义一次操作为选定任意一个 \(b_j\)，然后对所有 \(i \in [1, n]\)，执行 \(a_i = a_i | b_j\)。
输出任意次操作后，序列 \(a\) 所有数的异或和的最小值和最大值。
思路
首先，如果序列 \(a\) 长为偶数，那么执行一次操作后，\(b_j\) 上所有为 \(1\) 的位置都会因为异或而变成 \(0\)，从而可以发现操作次数越多，异或和越小。
那么这个时候最大值就是操作前的异或和，最小值就是将所有 \(b_j\) 都操作一遍后的异或和。
如果序列 \(a\) 长为奇数，那么执行一次操作后，\(b_j\) 上所有为 \(1\) 的位置都会因为异或而变成 \(1\)，从而可以发现操作次数越多，异或和越大。
那么相反的，此时最小值就是操作前的异或和，最大值就是将所有 \(b_j\) 都操作一遍后的异或和。
那么不妨直接把这两个答案算出来，然后输出最小值和最大值即可。
时间复杂度：\(O(n)\)
对应AC代码
#define chatgpt3_5 "bits/stdc++.h"
#define chatgpt4 "bits/extc++.h"
#include chatgpt3_5
using namespace std;
//#define FLOATING_OCEAN
#define int long long
#define pii pair<int, int>
#define pipi pair<pii, pii>
#define tpi tuple<int, int, int>
#define fs first
#define sc second
#define pb emplace_back
#define ep emplace
#define rall(x) x.rbegin(),x.rend()
#define all(x) x.begin(),x.end()
const int N = 1e6 + 10, M = 2e5 + 10, mod = 1e9 + 7, inf = 0x3f3f3f3f3f3f3f3f;
const double eps = 1e-9, PI = acos(-1);
void solve() {
int n, m;
cin >> n >> m;
vector<int> a(n + 1);
int ans1 = 0, ans2 = 0;
for(int i=1;i<=n;i++) {
cin >> a[i];
ans1 ^= a[i];
}
int w = 0;
for(int i=1;i<=m;i++) {
int x;
cin >> x;
w |= x;
}
for(int i=1;i<=n;i++){
ans2 ^= (a[i] | w);
}
if(ans1 > ans2) swap(ans1, ans2);
cout << ans1 << ' ' << ans2 << '\n';
}
signed main() {
# ifdef FLOATING_OCEAN
freopen("1.in","r",stdin);
freopen("1.out","w",stdout);
# endif
ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
// init();
int t = 1;
cin >> t;
while (t--) solve();
}有意思的思维题
C. Colorful Table
题意
给定一个长为 \(n\) 的序列 \(a, a[i] \leq k\)，对于一个 \(n \times n\) 的矩阵 \(b\)，有 \(b[i][j] = \min(a[i], a[j])\)。
对于 \(x \in [1, k]\)，输出将 \(b[i][j] = x\) 的所有方格包含在里面的最小矩形的长宽之和。
思路
首先，得到的矩阵是对称的，所以最后的答案肯定是一个正方形的边长 \(\times 2\)。
其次，因为有取最小值操作，所以我们不妨从小到大枚举所有颜色，用 \(\mathtt{set}\) 维护值大于等于当前颜色的下标集合。
那么，对于这个颜色，我们需要的答案就是最大的下标和最小的下标的距离 \(\times 2\)。
时间复杂度：\(O(n \log n)\)
对应AC代码
#define chatgpt3_5 "bits/stdc++.h"
#define chatgpt4 "bits/extc++.h"
#include chatgpt3_5
using namespace std;
//#define FLOATING_OCEAN
#define int long long
#define pii pair<int, int>
#define pipi pair<pii, pii>
#define tpi tuple<int, int, int>
#define fs first
#define sc second
#define pb emplace_back
#define ep emplace
#define rall(x) x.rbegin(),x.rend()
#define all(x) x.begin(),x.end()
const int N = 1e6 + 10, M = 2e5 + 10, mod = 1e9 + 7, inf = 0x3f3f3f3f3f3f3f3f;
const double eps = 1e-9, PI = acos(-1);
void solve() {
int n, k;
cin >> n >> k;
vector<int> a(n), ans(k);
vector<vector<int>> pos(k);
set<int> s;
for(int i = 0;i < n;i++){
cin >> a[i];
a[i] --;
pos[a[i]].push_back(i);
s.insert(i);
}
for(int i = 0;i < k;i++) {
if (pos[i].empty()) continue;
int x = *s.rbegin(), y = *s.begin();
ans[i] = x - y + 1;
for (auto it : pos[i]) s.extract(it);
}
for(auto e : ans) cout << e * 2 << ' ';
cout << '\n';
}
signed main() {
# ifdef FLOATING_OCEAN
freopen("1.in","r",stdin);
freopen("1.out","w",stdout);
# endif
ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
// init();
int t = 1;
cin >> t;
while (t--) solve();
}其实很显然，但我也不知道为啥做了好一会儿（x
D. Prefix Purchase
题意
给定长度为 \(n\) 的序列 \(a, c\)，其中序列 \(a\) 的初始值都是 \(0\)。
对于第 \(i\) 种支付，可以通过支付 \(c_i\) 个硬币，来使 \([1, i]\) 内所有 \(a_i\) 都加上 \(1\)。
现在，在硬币最多有 \(k\) 个的条件下，输出字典序最大的 \(a\)。
思路
首先，为了让第一个数尽可能大，我们一定会尽可能多使用价格低的。
那么，我们先全用价格最低的硬币，然后考虑用价格高但范围更大的硬币替换。
显然，我们肯定先用小的替换，这样代价更小，那么我们只需贪心地从小到大枚举所有支付方式，然后只使用能让范围进一步扩大地方式即可。
时间复杂度：\(O(n \log n)\)
对应AC代码
#define chatgpt3_5 "bits/stdc++.h"
#define chatgpt4 "bits/extc++.h"
#include chatgpt3_5
using namespace std;
//#define FLOATING_OCEAN
#define int long long
#define pii pair<int, int>
#define pipi pair<pii, pii>
#define tpi tuple<int, int, int>
#define fs first
#define sc second
#define pb emplace_back
#define ep emplace
#define rall(x) x.rbegin(),x.rend()
#define all(x) x.begin(),x.end()
const int N = 1e6 + 10, M = 2e5 + 10, mod = 1e9 + 7, inf = 0x3f3f3f3f3f3f3f3f;
const double eps = 1e-9, PI = acos(-1);
void solve() {
int n;
cin >> n;
vector<int> a(n + 1), d(n + 2);
map<int, int> mp;
for (int i = 1; i <= n; i++) {
cin >> a[i];
mp[a[i]] = i;
}
int k;
cin >> k;
int v = 0, pos = 0, pcnt = inf;
for (auto [x, y]: mp) {
if (y <= pos) continue;
int cnt = min(pcnt, k / (x - v));
d[pos + 1] += cnt;
d[y + 1] -= cnt;
k -= cnt * (x - v);
pcnt = cnt;
v = x, pos = y;
}
for (int i = 1; i <= n; i++) {
d[i] += d[i - 1];
cout << d[i] << ' ';
}
cout << '\n';
}
signed main() {
# ifdef FLOATING_OCEAN
freopen("1.in","r",stdin);
freopen("1.out","w",stdout);
# endif
ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
// init();
int t = 1;
cin >> t;
while (t--) solve();
}哎，贪心