CodeTON Round 6 (Div. 1 + Div. 2, Rated, Prizes!)
A. MEXanized Array
解题思路：
- 如果\(k > (x + 1) || k > n\)那么我们\(MEX\)都一定无法得到\(k\).
- 若\(k > (x + 1)\)，则我们取不到\(k-1\).
- 若\(k > n\)，我们同样取不到\(k-1\).
- 否则，我们选取\(0 \sim (k - 1)\)各一次，后选取不等于\(k\)的最大数即可。
代码:
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 1e6 + 10;
const int M = 2 * M;
typedef pair<int, int> pii;
#define fi first
#define se second
void solve()
{
int n, k, x;
scanf("%d %d %d", &n, &k, &x);
if (k > (x + 1) || k > n)
{
puts("-1");
return;
}
ll cnt = 0;
ll ans = 0;
for (int i = 0; i < n; i++)
{
ans += cnt;
if (cnt < k - 1)
{
cnt++;
}
else if (x > k)
{
cnt = x;
}
}
printf("%lld\n", ans);
}
int main()
{
int t = 1;
scanf("%d", &t);
while (t--)
{
solve();
}
return 0;
}
B. Friendly Arrays
解题思路:
对于全体或运算：
- 如果\(n\)是奇数，对于异或和，若我们原数位上有奇数个\(1\)那么或上这一位不会有影响。反之，或上这一位\(1\)能使答案多出这一位的贡献，所以我们的操作只会使得异或和增大，不会使其减小：
- 对于最小异或和，不用进行任何操作
- 对于最大异或和，在原异或和基础上，添加上\(b_i\)中存在的所有位的贡献。
- 如果\(n\)是偶数，对于异或和，若我们原数位上有偶数个\(1\)那么或上这一位不会有影响。反之，或上这一位\(1\)能使答案减去这一位的贡献，所以我们的操作只会使得异或和减小，不会使其增大：
- 对于最小异或和，在原异或和的基础上，减去\(b_i\)中存在的所有位的贡献。
- 对于最大异或和，不用进行任何操作。
代码:
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 1e6 + 10;
const int M = 2 * M;
typedef pair<int, int> pii;
#define fi first
#define se second
int n, m;
void solve()
{
scanf("%d %d", &n, &m);
vector<int> a(n + 1), b(m + 1);
for (int i = 1; i <= n; i++)
{
scanf("%d", &a[i]);
}
for (int i = 1; i <= m; i++)
{
scanf("%d", &b[i]);
}
if (n & 1)
{
vector<int> v(40);
ll res = 0;
for (int i = 1; i <= n; i++)
{
res ^= a[i];
}
for (int i = 1; i <= m; i++)
{
for (int j = 30; j >= 0; j--)
{
if (b[i] >> j & 1)
{
v[j] = 1;
}
}
}
ll ans = res;
for (int i = 30; i >= 0; i--)
{
if (v[i])
{
ans |= (1 << i);
}
}
printf("%lld %lld\n", res, ans);
}
else
{
ll res = 0;
for (int i = 1; i <= n; i++)
{
res ^= a[i];
}
vector<int> v(40);
for (int i = 1; i <= m; i++)
{
for (int j = 30; j >= 0; j--)
{
if (b[i] >> j & 1)
{
v[j] = 1;
}
}
}
ll ans = res;
for (int i = 30; i >= 0; i--)
{
if ((res >> i & 1) && v[i])
{
ans -= (1 << i);
}
}
printf("%lld %lld\n", ans, res);
}
}
int main()
{
int t = 1;
scanf("%d", &t);
while (t--)
{
solve();
}
return 0;
}
C. Colorful Table
解题思路:
\(a_i\)会在第\(i\)行和第\(i\)列被进行比对。若\(a_i 和a_j\)进比对，较小的那个数会占据第\(i \ or\ j\)行和第\(i \ or\ j\)列。这个框柱这个十字的长和宽，就是当前最大空白边框的大小。
所以，我们排个序，从最小值开始遍历，边加上当前最大边框大小，边更新边框大小即可。
比如最开始我们的边框由上下左右四个方向界定，\(u = 1,d = n ,l = 1,r =n\).如果我们最小值是\(a_1\),那么第一行和第一列会被最小值覆盖，长宽贡献为\((d - u) + (r - l)\)。
而之后的值在覆盖时会缺少这一行和这一列,所以\(u ++ ,u = 2.l ++,l = 2\).
代码：
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 1e6 + 10;
const int M = 2 * M;
typedef pair<int, int> pii;
#define fi first
#define se second
int n, m, k;
void solve()
{
scanf("%d %d", &n, &k);
vector<pii> a(n + 1);
for (int i = 1; i <= n; i++)
{
scanf("%d", &a[i].fi);
a[i].se = i;
}
sort(a.begin() + 1, a.end());
vector<bool> row(n + 1), col(n + 1);
vector<ll> ans(k + 1);
ll u = 1;
ll d = n;
ll l = 1;
ll r = n;
for (int i = 1; i <= n; i++)
{
int idx = a[i].se;
int val = a[i].fi;
while (row[u])
{
u++;
}
while (row[d])
{
d--;
}
while (col[l])
{
l++;
}
while (col[r])
{
r--;
}
ll t = (d - u + 1) + (r - l + 1);
if (idx == u)
{
u++;
}
else if (idx == d)
{
d--;
}
row[idx] = true;
if (idx == l)
{
l++;
}
else if (idx == r)
{
r--;
}
col[idx] = true;
ans[val] = max(ans[val], t);
}
for (int i = 1; i <= k; i++)
{
printf("%lld ", ans[i]);
}
puts("");
}
int main()
{
int t = 1;
scanf("%d", &t);
while (t--)
{
solve();
}
return 0;
}
D. Prefix Purchase
解题思路:
如果\(i < j\),并且\(c_i >= c_j\),那么我们一定选\(c_j\)。
由此可知，如果答案中出现\(c_k >= c_j\)的情况，那么一定是\(k > j\).
所以,答案选择序列的\(c_i\)序列一定是一个单调递增序列。我们这里可以用单调栈处理。
然后我们就可以遍历栈内元素，我们后选取的\(c_j\)一定大于之前选的\(c_i\)。要求最大字典序，那么我们可以计算在选取\(c\)的最大次数不变的情况下，我们能将多少\(c_i\)转变为\(c_j\).
假设我们现在\(res = \lfloor \frac k {c_i} \rfloor ,k = k \% c_i\)。最大转变数即为\(cnt = min(\lfloor \frac {k} {c_{i + 1} - c_i} \rfloor,res)\)，这说明，此时我们能用\(cnt\)个\(c_i\)换取同等数量的\(c_{i + 1}\),由于我们此时是在上述处理好后的单调栈中进行的遍历，所以同等数量下，一定是选越后面的越优，所以我们换。换的操作记得减去前面的加上后面的。
依次遍历完即可。
时间复杂度\(O(n)\).
代码：
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 1e6 + 10;
const int M = 2 * M;
typedef pair<int, int> pii;
#define fi first
#define se second
int n, m, k;
// 次数优先
// 其次越远越好
bool cmp(pii a, pii b)
{
if (a.fi != b.fi)
{
return a.fi < b.fi;
}
else
{
return a.se > b.se;
}
}
void solve()
{
scanf("%d", &n);
vector<int> a(n + 1), ans(n + 1);
for (int i = 1; i <= n; i++)
{
scanf("%d", &a[i]);
}
scanf("%d", &k);
vector<int> q(n + 1);
int hh = 1;
int tt = 0;
for (int i = 1; i <= n; i++)
{
while (hh <= tt && a[q[tt]] >= a[i])
{
tt--;
}
q[++tt] = i;
}
ll lst = 1e9;
ll idx = 0;
for (int i = 1; i <= tt; i++)
{
ll cnt = k / (a[q[i]] - a[q[i - 1]]);
lst = min(cnt, lst);
k -= (a[q[i]] - a[q[i - 1]]) * lst;
for (int j = idx + 1; j <= q[i]; j++)
{
ans[j] = lst;
}
idx = q[i];
}
for (int i = 1; i <= n; i++)
{
printf("%d ", ans[i]);
}
puts("");
}
int main()
{
int t = 1;
scanf("%d", &t);
while (t--)
{
solve();
}
return 0;
}