Contestant. Rank 728. Rating +14.
A. Increasing Sequence
题意
给定一个长度为 \(n\) 的序列 \(a\)，构造一个满足下面条件的序列 \(b\)：
长度为 \(n\)；
严格递增；
\(a_i \neq b_i\)
输出最小的满足条件的 \(b_n\)。
思路
显然，我们模拟一下构造即可。
我们从 \(1\) 开始向后枚举，如果当前位和 \(a_i\) 相等，那么我们就多加一个 \(1\)。
时间复杂度：\(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 = 2e5 + 10, M = 2e5 + 10, mod = 998244353, inf = 0x3f3f3f3f3f3f3f3f;
const double eps = 1e-9, PI = acos(-1);
void solve() {
int n;
cin >> n;
int cur = 1;
for(int i=1;i<=n;i++){
int a;
cin >> a;
if(cur == a) cur ++;
cur ++;
}
cout << cur - 1 << '\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. Sets and Union
题意
给定 \(n\) 个集合 \(S_i\)，定义一个方案为选定若干个集合，并取并集。
输出筛去全选的方案后，元素最多的方案对应的个数。
思路
我们可以反过来考虑，即让被 "删除" 的数尽可能多。
那么，我们肯定是尽可能只删一个数。
但是，删除一个数后，有可能会剔除好几个区间，从而连带着删除好几个数。
那么，我们就需要对每个数，处理出这个数在哪些区间中出现，然后枚举每个数作为需要删除的数字，然后把对应的区间删除后，计算还剩下多少数即可。
时间复杂度：\(O(50 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 = 2e5 + 10, M = 2e5 + 10, mod = 998244353, inf = 0x3f3f3f3f3f3f3f3f;
const double eps = 1e-9, PI = acos(-1);
void solve() {
int n;
cin >> n;
vector<set<int>> a(51);
for(int i=1;i<=50;i++){
for(int j=1;j<=n;j++) a[i].ep(j);
}
vector<vector<int>> p(n + 1);
for(int i=1;i<=n;i++){
int m;
cin >> m;
p[i].resize(m + 1);
for(int j=1;j<=m;j++){
cin >> p[i][j];
a[p[i][j]].erase(i);
}
}
int ans = 0;
for(int x=1;x<=50;x++){
if(a[x].size() == n) continue;
set<int> st;
for(auto e : a[x]){
for(int j=1;j<p[e].size();j++) st.ep(p[e][j]);
}
ans = max(ans, (int) st.size());
}
cout << ans << '\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. Card Game
题意
给定 \(n\) 张牌，以及从顶部往下开始编号的牌的值序列 \(a\)。
定义游戏如下：
选择一个不大于剩余牌数的奇数正整数 \(i\)，取走第 \(i\) 张卡，并将其添加到分数中；
选择一个不大于剩余牌数的偶数正整数 \(i\)，取走第 \(i\) 张卡
取走卡牌后，下标会重新索引。
输出最后分数的最大值。
思路
首先，我们设第一个拿掉的牌为 \(i\)，那么有下面的策略：
拿走奇数索引下的正数卡牌；
拿走偶数索引下的正数卡牌
可以发现，只要我们从底往上拿，就不会影响到索引。
上面的操作显然有一个条件，即当我们选择的第一张牌是奇数，我们就一定得拿，而其他的只需拿正数即可。
我们可以用一个前缀和来完成。
时间复杂度：\(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 = 2e5 + 10, M = 2e5 + 10, mod = 998244353, inf = 0x3f3f3f3f3f3f3f3f;
const double eps = 1e-9, PI = acos(-1);
void solve() {
int n;
cin >> n;
vector<int> a(n + 1);
for(int i=1;i<=n;i++) cin >> a[i];
vector<int> suf(n + 4);
for(int i=n;i>=1;i--) suf[i] = suf[i + 2] + max(0ll, a[i]);
int ans = 0;
for(int i=1;i<=n;i++){
if(i % 2 == 1){
ans = max(ans, a[i] + suf[i + 1] + suf[i + 2]);
}else{
ans = max(ans, suf[1] + suf[i + 2]);
}
}
cout << ans << '\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();
}比较抽象
D. Tree XOR
题意
给定包含 \(n\) 个节点的一棵树，每个点具有权值 \(a_i\)。
假设根为 \(r\)，定义一次操作为选定一个点 \(v\) 以及一个整数 \(c\)，并将点 \(v\) 以及其所有子节点 \(i\) 都执行 \(a_i := a_i \oplus c\)，代价为 \(s \cdot c\)，\(s\) 为被操作的点的个数。
现在，对于所有点，若将其作为树根，输出使所有元素都相等的代价和。
思路
首先，两个元素相等，则其异或值为 \(0\)。
那么，如果根为 \(r\)，某个子节点为 \(p\)，那么 \(p := r \oplus p\)。
因此，我们可以通过一次 \(\mathtt{dfs}\) 得到单根的解。
接下来我们考虑换根：
如果我们将根从 \(r\) 换到某个相邻的节点 \(q\)，那么除了这两个点外，其余的点的父节点和子树都没变。
为什么没变呢？因为就算父节点的值变了，其子树之后的计算得到的代价就是不变的，毕竟 \((a \oplus c) \oplus(b \oplus c) = a \oplus b = (a \oplus c') \oplus(b \oplus c')\)。
因而，我们只需考虑 \(r\) 和 \(q\)。
可以发现，原来 \(q\) 是 \(r\) 的子节点，那么如果 \(q\) 所在子树大小为 \(X\)，当初的代价就是 \(X \cdot (a_r \oplus a_q)\)。
而现在，\(r\) 是 \(q\) 的子节点，那么如果 \(r\) 所在子树大小为 \(Y\)，现在的代价就是 \(Y \cdot (a_r \oplus a_q)\)。
从而，我们 \(\mathtt{dfs}\) 计算一下每个根的值即可。
时间复杂度：\(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 = 2e5 + 10, M = 2e5 + 10, mod = 998244353, inf = 0x3f3f3f3f3f3f3f3f;
const double eps = 1e-9, PI = acos(-1);
void solve() {
int n;
cin >> n;
vector<vector<int>> e(n + 1);
vector<int> a(n + 1), siz(n + 1, 1), dp(n + 1);
for(int i=1;i<=n;i++) cin >> a[i];
for(int i=1;i<n;i++){
int u, v;
cin >> u >> v;
e[u].pb(v), e[v].pb(u);
}
auto dfs = [&](auto dfs, int x, int p) -> void{
for(auto y : e[x]){
if(y == p) continue;
dfs(dfs, y, x);
siz[x] += siz[y];
dp[1] += siz[y] * (a[x] ^ a[y]);
}
};
auto change = [&](auto dfs, int x, int p) -> void {
for (auto y : e[x]) {
if (y == p) continue;
dp[y] = dp[x] + (a[y] ^ a[x]) * (n - 2 * siz[y]);
int pre_x = siz[x], pre_y = siz[y];
siz[x] = n - siz[y], siz[y] = n;
dfs(dfs, y, x);
siz[x] = pre_x, siz[y] = pre_y;
}
};
dfs(dfs, 1, -1);
change(change, 1, 1);
for(int i=1;i<=n;i++) cout << dp[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();
}神奇的换根 \(dp\)