当前位置: 首页 > news >正文

Educational Codeforces Round 101 (Rated for Div. 2) 题解

题面

A. Regular Bracket Sequence

【题面】

给定一个长度为 \(n\) 的序列 \(S\),其中有包括 (),和 ?。问如果可以把 ? 变成 ( 或者 ),是否可以把序列 \(S\),变成括号序列。 保证存在一个左括号和一个右括号

【思路】

  1. 首先考虑到如果说字符串的长度为奇数那么这个序列一定不能成为括号序列。
  2. 对于任意数量的括号只要满足第一个不是左括号,最后一个不是右括号即可。
    n比较小可以考虑二进制枚举

【实现】

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
inline int read(){int x = 0, f = 1; char ch = getchar();while(ch < '0' || ch > '9'){ if(ch == '-') f = -1; ch = getchar(); }while(ch >= '0' && ch <= '9'){ x = x * 10 + (ch ^ 48); ch = getchar(); }return x * f;
}
void solve(){string s;cin >> s;int n = s.size();s = " " + s;if(n % 2 == 1 || s[1] == ')' || s[n] == '('){cout << "No\n";return ;}cout << "Yes\n";
}
int main(){int T = read();while(T--){solve();}return 0;
}

B. Red and Blue

【题面】

给定一个长度为 \(n+m\) 的数组 \(a\),把数组 \(a\) 分成两个长度分别为 \(n\)\(m\) 的数组 \(r\)\(b\)。重新组合 \(r\)\(b\) 满足 \(r_i\)\(b_i\) 在原数组中的相对位置不变。
\(f(a)\) 的最大值:

\[f(a) = \max(0, a_1, (a_1 + a_2), (a_1 + a_2 + a_3), \dots, (a_1 + a_2 + a_3 + \dots + a_{n + m})) \]

【思路】

1.首先根据样例,可以发现贪心(每一次取最大值)是错误的。
2.可以发现 \(n\)\(m\) 的大小很小,所以可以考虑一个 \(O(nm)\) 的算法。
3.考虑 \(dp\),定义 \(dp_{i,j}\) 表示在前 \(i\)\(r_i\) 和 前 \(j\)\(b_j\) 中的最大 \(f(a)\),那么
\(dp_{i+1,j} = \max(dp_{i+1,j},dp_{i,j}+r_i)\)
\(dp_{i,j+1} = \max(do_{i,j+1},dp_{i,j}+b_i)\)
\(dp_{0,0}=0\)

【实现】

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
inline int read(){int x = 0, f = 1; char ch = getchar();while(ch < '0' || ch > '9'){ if(ch == '-') f = -1; ch = getchar(); }while(ch >= '0' && ch <= '9'){ x = x * 10 + (ch ^ 48); ch = getchar(); }return x * f;
}
const int N = 105;
ll dp[N][N];
void solve(){int n = read();vector<int>a(n+1);for(int i=1; i<=n; ++i){a[i] = read();}int m = read();vector<int>b(m+1);for(int i=1; i<=m; ++i){b[i] = read();}for(int i=0; i<=n; ++i){for(int j=0; j<=m; ++j){dp[i][j] = INT_MIN;}}dp[0][0] = 0;ll ans = INT_MIN;for(int i=0; i<=n; ++i){for(int j=0; j<=m; ++j){if(i<n)dp[i+1][j] = max(dp[i+1][j], dp[i][j] + a[i+1]);if(j<m)dp[i][j+1] = max(dp[i][j+1], dp[i][j] + b[j+1]);ans = max(ans, dp[i][j]);}}cout << ans << '\n';
}
int main(){int T = read();while(T--){solve();}return 0;
}

C. Building a Fence

【题面】

给定 \(n\) 个栅栏其中每一个栅栏的区间 \([l_i..r_i]\)。其中第 \(i\) 个区间的 \(l_i\) 要求必须 \(\geq h_i\)。如果每一个相邻的栅栏必须有长度至少为 \(1\) 的相交区间,问是否存在这种情况

【思路】

1。发现每一个栅栏的区间 \([l_i..r_i]\) 只跟上一个栅栏和 \(h_i\) 有关。
2.可以用一个线性复杂度的算法去把计算每一个栅栏区间的最低值和最大值,最后取一个交集即可。

【实现】

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
inline int read(){int x = 0, f = 1; char ch = getchar();while(ch < '0' || ch > '9'){ if(ch == '-') f = -1; ch = getchar(); }while(ch >= '0' && ch <= '9'){ x = x * 10 + (ch ^ 48); ch = getchar(); }return x * f;
}
void solve(){ll n = read(), k = read();vector<ll>h(n+1), l(n+1), r(n+1);for(int i=1; i<=n; ++i){h[i] = read();}l[1] = r[1] = h[1];for(int i=2; i<=n; ++i){if(h[i] +k-1< l[i-1] -k+1|| h[i] >= r[i-1] + k){cout << "No\n";return;}l[i] = max(h[i], l[i-1] + 1 - k);r[i] = min(h[i] + k-1, r[i-1] + k - 1);if(l[i] > r[i]){cout << "No\n";}}if(l[n] <= h[n] && h[n] <= r[n]){cout << "Yes\n";}else{cout << "No\n";}
}
int main(){int T = read();while(T--){solve();}return 0;
}

D. Ceil Divisions

【题面】

您有一个数组 \(a_1,a_2,...,a_n\) ,其中 \(a_i=i\)

在一个步骤中,您可以选择两个索引 \(x\)\(y\) ( \(x \neq y\) ),并设置 \(a_x = \left\lceil \frac{a_x}{a_ y} \right\rceil\)
您的目标是在不超过 \(n + 5\) 的步骤中使数组 \(a\)\(n - 1\)\(1\) 组成。注意,您不必最小化步骤数。

【思路】

1.首先可以发现对于任意 \(n\)\(m\),如果 \(n < m\) 那么 \(\lceil \frac{n}{m} \rceil = 1\)
2.可以把构造出把 \(3\)\(n-1\) 都去除以 \(n\) 这样 \(a\) 就变成了 \(1,2,1,1,...,1,n\)那么只用考虑把 \(n\) 变成 1即可。但是发现如果要把 \(n\) 变成 \(1\),此时需要 \(\log n\) 此次,绝对会超时。
3.考虑要让 \(\frac{n}{p_1·p_2·p_3·...·p_k}\) 要让 \(k\) 尽量少。由于考虑到 \(n\) 是从 \(1\)\(n\) 中最大的,所以让 \(k\) 不能是 \(1\),最小只能是 \(2\)。有由于每一次的可以删去 \(p_2..n\)。那么尽量让 \(\lvert p_1 - p_2 \rvert\) 最小,就干脆让 \(p_1 = p_2\) 那么就让 \(n=\frac{n}{\sqrt n}\)

【实现】

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
inline int read(){int x = 0, f = 1; char ch = getchar();while(ch < '0' || ch > '9'){ if(ch == '-') f = -1; ch = getchar(); }while(ch >= '0' && ch <= '9'){ x = x * 10 + (ch ^ 48); ch = getchar(); }return x * f;
}
void solve(){ll n = read();vector<pair<ll, ll> > ans;for(ll i = n; i >=3; --i){ll cnt = ceil(sqrt(i));for(ll j = cnt+1; j<i; ++j){ans.push_back({j, i});}ans.push_back({i, cnt});ans.push_back({i, cnt});i = ++cnt;}cout << ans.size() << '\n';for(auto x : ans){cout << x.first << ' ' << x.second << '\n';}
}
int main(){int T = read();while(T--){solve();}return 0;
}

E. A Bit Similar

http://www.hskmm.com/?act=detail&tid=29436

相关文章:

  • Centos7下docker的jenkins下载并配置jdk与maven
  • The 2024 ICPC Asia Shanghai Regional Contest
  • 英语_阅读_Fireflies_待读
  • 1.基础
  • 深入解析:RoadCLIP 笔记 针对自动驾驶优化的 CLIP 变体 vlm
  • ASP.NET Razor VB 变量 - 实践
  • dos命令和命令提示符
  • 20232401 2025-2026-1 《网络与系统攻防技术》实验一实验报告
  • for 循环 range
  • 在AI技术唾手可得的时代,挖掘新需求成为核心竞争力——某知名离线转录工具需求洞察
  • JavaScript async/await 基础使用
  • 27. 移除元素 暴力+快慢指针+相向双指针
  • ST表学习笔记
  • 谈一类易实现的非四毛子线性 RMQ
  • 我们学会在具体情境中做出恰当判断
  • 编译安装nginx
  • AutoGCL——AutoGCL: automated graph contrastive learning via learnable view generators
  • 【教程】无需第三方应用,Windows自带邮箱如何绑定QQ邮箱等第三方邮箱
  • 2025婚纱摄影影楼权威推荐榜:专业团队与创意拍摄打造梦幻婚礼
  • 为什么40岁后的快乐消失了
  • 分布式结构化存储系统-HBase访问方式
  • 【Azure APIM】自建网关(self-host gateway)收集请求的Header和Body内容到日志中的办法
  • [JAVA]JDK多版本设置
  • Google Veo3生成跳舞视频
  • 【PolarCTF】stackof
  • 新生赛 F,H,J 题解
  • pycharm跑python项目易出错的困难
  • 双端队列的0-1BFS
  • Python psycopg2 类库使用学习总结
  • [GenAI] RAG架构演进