Codeforces Round 899 (Div. 2)
A. Increasing Sequence
解题思路：
从左往右一个个看，从1开始，如果当前位相同\(+2\)，否则\(+1\)。
代码:
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 1e6 + 10;
const int M = 2 * M;
const int mod = 1e9 + 7;
typedef pair<int, int> pii;
#define fi first
#define se second
int n, m, k;
void solve()
{
scanf("%d", &n);
vector<int> a(n + 1);
int cur = 0;
for (int i = 1; i <= n; i++)
{
scanf("%d", &a[i]);
if (cur + 1 == a[i])
{
cur += 2;
}
else
{
cur++;
}
}
printf("%d\n", cur);
}
int main()
{
int t = 1;
scanf("%d", &t);
while (t--)
{
solve();
}
return 0;
}
B. Sets and Union
解题思路:
数据范围很小，可直接暴力枚举。
由于最多有50中不同的元素，我们可以枚举删去每一种元素会导致起码要连带走多少其他种类的元素，其中带走最少的就是答案。
分别记录每一个集合中有哪些元素，同时记录每个元素存在于哪些集合中，遍历即可。
代码：
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 1e6 + 10;
const int M = 2 * M;
const int mod = 1e9 + 7;
typedef pair<int, int> pii;
#define fi first
#define se second
int n, m, k;
void solve()
{
scanf("%d", &n);
vector<vector<int>> v(60, vector<int>(60));
vector<vector<int>> f(60, vector<int>(60));
unordered_map<int, int> cnt;
for (int i = 1; i <= n; i++)
{
scanf("%d", &k);
for (int j = 1; j <= k; j++)
{
int x;
scanf("%d", &x);
f[x].push_back(i);
v[i].push_back(x);
cnt[x]++;
}
}
int ans = 0;
int num = cnt.size();
// cout << cnt.size() << endl;
for (int i = 1; i <= 50; i++)
{
if (cnt[i] == 0)
{
continue;
}
vector<int> t(60);
int res = 0;
for (auto u : f[i])
{
for (auto j : v[u])
{
t[j]++;
}
}
for (int j = 1; j <= 50; j++)
{
if (t[j] && t[j] == cnt[j])
{
res++;
}
}
// cout << i << ' ' << res << endl;
ans = max(ans, num - res);
}
printf("%d\n", ans);
}
int main()
{
int t = 1;
scanf("%d", &t);
while (t--)
{
solve();
}
return 0;
}
C. Card Game
解题思路:
不难发现，如果我们要取了第\(i\)位，那么第\(i\)位往后的所有正数一定都能取到。
对于奇数位的正数，如果我们取了，那么后面的偶数位的正数全部都变到奇数位上，从后往前取即可。
如果从第\(i\)位往后的第一个正数是奇数位，那么我们先将第\(i\)位往后的正数全取了，再取\(a_i\)即可。
如果从第\(i\)位往后的第一个正数是偶数位，那么我们先将\(a_i\)取了，第一个正数就是奇数位了，按上述方法即可将后面的正数取完。
所以，我们从后往前枚举选取\(a_i\)，然后取\(min(suffix_i)\)即可。
答案下界为0.
代码:
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 1e6 + 10;
const int M = 2 * M;
const int mod = 1e9 + 7;
typedef pair<int, int> pii;
#define fi first
#define se second
int n, m, k;
void solve()
{
scanf("%d", &n);
vector<ll> a(n + 1);
for (int i = 1; i <= n; i++)
{
scanf("%lld", &a[i]);
}
ll ans = 0;
ll s = 0;
for (int i = n; i; i--)
{
if (i & 1)
{
ans = max(ans, s + a[i]);
}
else
{
ans = max(ans, s);
}
s += max(0ll, a[i]);
}
printf("%lld\n", ans);
}
int main()
{
int t = 1;
scanf("%d", &t);
while (t--)
{
solve();
}
return 0;
}
D. Tree XOR
解题思路:
求解每一个结点作为根节点，或者求解选一个结点作为根节点的最优情况，一般来说换根DP.
\(siz[u]:以结点u为根的子树的结点个数\)。
\(ans[u]:以u结点为根节点的子树上，所有结点权值变为相同数，所需要的花费值\)。
使得父节点\(u\)和子节点\(v\)权值相同的花费为\(siz[v] * (a[u] \oplus a[v])\),我们递归操作即可。
\(siz[u] = \sum siz[v] + 1,其中v是u的子节点\)。
\(ans[u] = \sum ans[v] + (a[u] \oplus a[v]) * siz[v]\)。
第一次算出以\(结点1\)为根节点时，所有结点的\(siz[i]和ans[i]\)。第一次\(dfs\)完后，\(ans[1]就是答案m_1\)。
接下来我们考虑以其他节点为根应当如何计算。
从结点1出发，父节点一定会比子节点先更新到答案。
\[\begin{align*} ans[u] &= (n - siz[u]) * (a[u] \oplus a[p])\\ ans[u] &= ans[u] + (ans[p] - siz[u] * (a[u] \oplus a[p])) \end{align*} \]代码:
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
void solve()
{
int n;
scanf("%d",&n);
vector<int> a(n + 1);
for(int i = 1;i<=n;i++)
{
scanf("%d",&a[i]);
}
vector<vector<int>> adj(n + 1);
for(int i = 1;i<n;i++)
{
int a,b;
scanf("%d %d",&a,&b);
adj[a].push_back(b);
adj[b].push_back(a);
}
vector<ll> ans(n + 1);
vector<int> siz(n + 1);
auto dfs1 = [&](auto self,int u,int p) -> void
{
siz[u] = 1;
for(auto v : adj[u])
{
if(v == p)
{
continue;
}
self(self,v,u);
siz[u] += siz[v];
ans[u] += 1ll * siz[v] * (a[u] ^ a[v]) + ans[v];
}
};
dfs1(dfs1,1,-1);
// cout<<ans[1]<<endl;
auto dfs2 = [&](auto self,int u,int p) -> void
{
if(u != 1)
{
ans[u] = 1ll * (n - siz[u]) * (a[u] ^ a[p]);
ans[u] += 1ll * ans[p] - (1ll * siz[u] * (a[u] ^ a[p]));
}
for(auto v : adj[u])
{
if(v == p)
{
continue;
}
self(self,v,u);
}
};
dfs2(dfs2,1,-1);
for(int i = 1;i<=n;i++)
{
printf("%lld ",ans[i]);
}
puts("");
}
int main()
{
int t = 1;
scanf("%d",&t);
while(t--)
{
solve();
}
}