牛客春招刷题训练营 - 2025.5.1 题解
活动地址：牛客春招刷题训练营 - 编程打卡活动
Easy 小欧的奇数
简要题意
给一个成为 的数组，判断能否选出三个数，使得它们相加为奇数。
Solution
要么选两偶一奇，要么选三奇，要么无解，判断一下奇偶数个数是否满足条件即可。
Code
void R()
{
int n,a=0,b=0;
cin>>n;
while (n--)
{
int x;
cin>>x;
if (x&1) a++;
else b++;
}
cout<<((a>2||(a&&b>1))?"YES":"NO");
return;
}
Medium 拦截导弹
简要题意
给一个长为 的数组
，求
的最长不升子序列长度，以及至少多少个不升子序列可以覆盖整个
。
Solution
设 代表最后一位为
的最长不升子序列长度，朴素地动态规划可以在
时间复杂度内解决该问题。
下面介绍 时间复杂度的做法。
对于第一问，考虑什么时候最长不升子序列会发生变化：
-
新增的数小于等于序列尾的数。
-
前面一段长度为
不升子序列+新增的数可以替换掉原先最长不升子序列的后
第一种情况很好理解，对第二种情况给出下面一个例子：
给定数组 为
3 4 1 2 1。
随着数依次插入，最长不升子序列发生如下变化：
注意蓝色到红色部分的变化，就是上面说的第二种情况。
其实在第 步时，最长不升子序列就有四种情况：
虽然最早完整出现的是 ，但是最容易插入新数的序列其实是
。
可以想到我们应该维护的是既满足最长，又使靠后的数尽量大的不升子序列。
但这并不容易维护。
但是如果我们不要求我们维护的序列总是 的子序列，只要求当发生第二种情况时它是
的子序列，事情就变得简单了。
我们只要在每次新增一个不能直接插入序列的数时，用它替换掉序列里第一个比它大的数即可（通过二分找到替换的位置）。
如果发生了第二种情况，在我们维护的序列中将表现为：一段后缀依次都发生了替换，不失合法性。
对于第二问，根据 Dirworth 定理，答案即为最长上升子序列长度，仿照上面做法即可。
Code
void R()
{
int n;
cin>>n;
vector<int> a(n),now;
for (int &x:a) cin>>x;
for (int x:a)
{
if (now.empty()||x<=now.back())
now.push_back(x);
else *upper_bound(now.begin(),now.end(),x,greater<int>())=x;
}
cout<<now.size()<<'\n';
now.clear();
for (int x:a)
{
if (now.empty()||x>now.back())
now.push_back(x);
else *lower_bound(now.begin(),now.end(),x)=x;
}
cout<<now.size();
return;
}
Hard 红和蓝
简要题意
给定一棵 点的树，构造一个红蓝染色方案，使得每个点相邻有且仅有一个与它同色的点，或报告无解。
Solution
根的选取不影响可解性，我们随便取一个点做根，考虑它的每个儿子。
如果其子树大小为偶数，其要么无解，要么内部可以完成染色配对。
如果其子树大小为奇数，则它需要与根共色。
随便给根赋一个颜色，就可以递归染色及判断有解性。
Code
void R()
{
int n;
cin>>n;
vector<int> col(n),siz(n);
vector<vector<int>> adj(n);
for (int i=1;i<n;i++)
{
int u,v;
cin>>u>>v;
u--,v--;
adj[u].push_back(v);
adj[v].push_back(u);
}
auto dfs1=[&](auto &self,int u,int f)->void
{
siz[u]=1;
if (u!=f)
adj[u].erase(find(adj[u].begin(),adj[u].end(),f));
for (int v:adj[u])
{
self(self,v,u);
siz[u]^=siz[v];
}
};
auto dfs2=[&](auto &self,int u,int f)->bool
{
int odd=0;
for (int v:adj[u])
{
col[v]=(!col[u])^siz[v];
odd+=siz[v];
}
if (odd>1) return 0;
for (int v:adj[u])
if (!self(self,v,u))
return 0;
return 1;
};
dfs1(dfs1,0,0);
if (n&1||!dfs2(dfs2,0,0)) cout<<-1;
else for (int x:col) cout<<(x?'R':'B');
return;
}
