昨晚 CF A-D 题解
2026-07-07 14:16:07
发布于：广东
13阅读
0回复
0点赞
坏消息：EF 十分困难，我完全不会做。
好消息：EF 过于困难，别人也不会做。
这下知道哪道题更难了吧。
A
Difficulty：3- / Easy
Tag：-
显然，只有两种可能：
...ab...ab...，满足存在至少两个 满足 。...aaa...，满足存在 满足 。
判断一下即可。
namespace cjdst{
void solve(){
int n;
std::cin >> n;
std::vector <int> a(n + 5);
for(int i = 1; i <= n; i++){
std::cin >> a[i];
}
std::sort(a.begin() + 1, a.begin() + n + 1);
for(int i = 1; i <= n; i++){
if(a[i] >= 3 || (i > 1 && a[i] == 2 && a[i - 1] == 2)){
std::cout << "YES\n";
return;
}
}
std::cout << "NO\n";
}
}
时间复杂度：。
B
Difficulty：3.7 / Easy
Tag：-
是不是我想复杂了，但感觉确实难吧。
首先根据题意，第三个区间只需要非空就行，删掉最后一个数就成可空了，不管它。
显然第一个区间只有 种情况。我们可以枚举所有第一个区间的情况。
现在假设第一个区间已经确定好了，应当如何求出第二个区间是否存在。
也就是说要看第一个区间右端点后一个数为左端点，是否存在一个右端点满足区间内 的数量不超过一半。
令 ，显然满足 才合法。定义 ，则只需要判断 即可。
namespace cjdst{
void solve(){
int n;
std::cin >> n;
std::vector <int> a(n + 5);
std::vector <int> pre(n + 5), pre2(n + 5, -0x3f3f3f3f);
for(int i = 1; i <= n; i++){
std::cin >> a[i];
}
for(int i = 1; i <= n; i++){
pre[i] = pre[i - 1] + (a[i] == 3 ? -1 : 1);
}
for(int i = n - 1; i; i--){
pre2[i] = std::max(pre2[i + 1], pre[i]);
}
int cur = 0;
for(int i = 1; i < n - 1; i++){
if(a[i] == 1) cur++;
if(cur * 2 >= i){
if(pre2[i + 1] - pre[i] >= 0){
std::cout << "YES\n";
return;
}
}
}
std::cout << "NO\n";
}
}
时间复杂度：。
C
Difficulty：3- / Easy
Tag：-
这和 B 真的是一个难度的吗。
用桶记录每一个颜色段的长度。
然后会发现操作就是把所有颜色段长度整体 或 ，到 了删除这个颜色。
所以只会保留最长的几个颜色段，而且它们之间的差一定不变。
枚举会保留哪些颜色段，直接判断即可。
namespace cjdst{
void solve(){
int n, m;
std::cin >> n >> m;
std::vector <int> a(n + 5);
std::map <int, int, std::greater <int>> mp;
int l = 1;
for(int i = 1; i <= n; i++){
std::cin >> a[i];
}
for(int i = 2; i <= n; i++){
if(a[i] != a[i - 1]){
mp[i - l]++;
l = i;
}
}
mp[n - l + 1]++;
int cur = 0, cur2 = 0, ans = 0;
for(auto it:mp){
cur += it.first * it.second;
cur2 += it.second;
if((m - cur) % cur2 == 0 && -(m - cur) / cur2 < it.first) ans++;
}
std::cout << ans << '\n';
}
}
时间复杂度：。
D
Difficulty：3.3 / Easy
Tag：-
显然可以转化成任意子段合并。
假设 合并。然后我们看向前缀和。
发现前缀和删掉了 的部分，其它不变。
而最后的两个的前缀和相等。
所以原问题就转化成了前缀和的 LCS。
namespace cjdst{
void solve(){
std::string a, b;
std::cin >> a >> b;
int n = a.size(), m = b.size();
std::vector <int> pre1(n + 5), pre2(m + 5);
a = " " + a + " ";
b = " " + b + " ";
for(int i = 1; i <= n; i++){
pre1[i] = (pre1[i - 1] + a[i] - '0') % 10;
}
for(int i = 1; i <= m; i++){
pre2[i] = (pre2[i - 1] + b[i] - '0') % 10;
}
if(pre1[n] != pre2[m]){
std::cout << "-1\n";
return;
}
std::vector <std::vector <int>> dp(n + 5, std::vector <int>(m + 5, -0x3f3f3f3f));
dp[0][0] = 0;
for(int i = 0; i <= n; i++){
for(int j = 0; j <= m; j++){
if(i) dp[i][j] = std::max(dp[i][j], dp[i - 1][j]);
if(j) dp[i][j] = std::max(dp[i][j], dp[i][j - 1]);
if(i && j && pre1[i] == pre2[j]) dp[i][j] = std::max(dp[i][j], dp[i - 1][j - 1] + 1);
}
}
std::cout << dp[n][m] << '\n';
}
}
时间复杂度：。
有帮助，赞一个