Educational Codeforces Round 114 部分题解
A. Regular Bracket Sequences
题意：
给定整数 \(n\)，要求构造恰好 \(n\) 个不同的合法括号序列，每个序列的长度为 \(2n\)。
思路：
对于每个 \(i\) 从 \(1\) 到 \(n\)，构造序列：\(i\) 个左括号，\(i\) 个右括号，接着 \(n-i\) 个左括号，\(n-i\) 个右括号。这样得到的序列都是合法的，且彼此不同。
代码
点击查看代码
void solve() {
int n;
cin >> n;
for(int j=1;j<=n;j++){
for (int i = 1; i <= j; i++) {
cout<<"(";
}
for (int i = 1; i <= j; i++) {
cout<<")";
}
for (int i = 1; i <= n-j; i++) {
cout<<"(";
}
for (int i = 1; i <= n-j; i++) {
cout<<")";
}
cout<<endl;
}
}
B. Combinatorics Homework
题意：
给定三个正整数 \(a\), \(b\), \(c\) 和一个非负整数 \(m\)。判断是否存在一个字符串，恰好包含 \(a\) 个 'A'，\(b\) 个 'B'，\(c\) 个 'C'，且其中相邻相等字母的对数恰好为 \(m\)。
思路：
将 \(a\), \(b\), \(c\) 排序为 \(a \le b \le c\)。相邻相等对数的最大值为 \(a+b+c-3\)（即所有相同字母连续放置）。若 \(m\) 大于该值则直接输出 "NO"。
否则，考虑通过拆分连续段减少对数。每次拆分需要消耗一个其他字母作为分隔。
每构造一个相邻可以看作减少一个字母，我们构造完 \(m\) 个相邻，使得剩余字母相邻两两不同即为合法。
影响合法性的关键在于最大值，所以我们只对 \(c\) 减少个数。
设排序后 \(a \le b \le c\)，若 \(m \ge c - b\)，则可以将 \(c\) 拆分为与 \(b\) 相等的段数，消耗 \(c-b\) 次操作；否则仅拆分 \(m\) 次。操作后判断剩余字母能否构成无相邻相等对的字符串（即 \(a+b \ge c'-1\)，其中 \(c'\) 为操作后的 \(c\)）。若能则说明存在恰好 \(m\) 对相邻相等字母的字符串。
代码
点击查看代码
void solve() {
int a,b,c,m;
cin>>a>>b>>c>>m;
if(a>b)swap(a,b);
if(a>c)swap(a,c);
if(b>c)swap(b,c);
if(m>a-1+b-1+c-1){
cout<<"NO"<<endl;
}else{
if(m>=c-max(1ll,b)){
m-=c-max(1ll,b);
c=max(1ll,b);
}else{
c-=m;
}
if(a+b>=c-1){
cout<<"YES"<<endl;
}else{
cout<<"NO"<<endl;
}
}
}
C. Slay the Dragon
题意：
给定 \(n\) 个英雄，每个英雄的力量为 \(a_i\)。有 \(m\) 条龙，每条龙的防御为 \(x\)，攻击为 \(y\)。你需要选择恰好一个英雄去杀龙（其力量至少为 \(x\)），其余英雄防守城堡（他们的力量之和至少为 \(y\)）。每次操作可以花费 1 金币将任意英雄的力量增加 1。对于每条龙独立计算最少需要花费多少金币。
思路：
设所有英雄的总力量为 S。对于一条龙 (x, y)，我们有两种选择：
- 选择一个力量不小于 x 的英雄去杀龙，然后计算防守力量是否足够。
- 选择一个力量小于 x 的英雄，将他提升到 x，再计算防守力量。
将英雄力量排序后，找到第一个力量 \(\ge x\) 的英雄位置 p。若 p 存在，则考虑使用该英雄（花费只需补足防守），以及使用前一个英雄 p-1（需要先提升到 x 再补防守）。若 p 不存在（即所有英雄力量都小于 x），则只能使用最大的英雄，将他提升到 x 再补防守。取所有情况的最小值。
代码
点击查看代码
void solve() {
int n;
cin>>n;
int s=0;
for(int i=1;i<=n;i++){
cin>>a[i];
s+=a[i];
}
sort(a+1,a+1+n);
int m;
cin>>m;
for(int i=1;i<=m;i++){
int x,y;
cin>>x>>y;
int p=lower_bound(a+1,a+1+n,x)-a;
int ans=0;
if(p>n){
ans=x-a[n]+max(0ll,y-(s-a[n]));
}else{
ans=max(0ll,y-(s-a[p]));
if(p>1){
ans=min(ans,x-a[p-1]+max(0ll,y-(s-a[p-1])));
}
}
cout<<ans<<endl;
}
}
D. The Strongest Build
题意：
有 \(n\) 个装备槽，每个槽 \(i\) 有 \(c_i\) 个物品，第 \(j\) 个物品提供力量值 \(a_{i,j}\)，且严格递增。每个槽必须选一个物品，构建是选择物品的索引序列 \([b_1,b_2,...,b_n]\)，其力量值为各物品力量值之和。给出 \(m\) 个被禁止的构建（保证至少有一个不被禁止），求不被禁止的最大力量构建，若有多个输出任意一个。
思路：
最大力量构建显然是每个槽选择最后一个物品（索引\(c_i\)）。若该构建不被禁止，直接输出。否则，用优先队列按力量值降序搜索所有可能的构建。从最大构建出发，每次将某个槽的索引减1得到新构建（力量值变小），若新构建未被访问则入堆。这样按力量值从大到小检查，直到找到第一个不被禁止的构建即为答案。
代码
点击查看代码
#define PIII pair<int,vector<int>>
int a[N], c[N], p[N], b[N], f[N];
int b0[N];
vector<int>g[N];
int cnt[N];
void solve() {
int n;
cin >> n;
for (int i = 0; i < n; i++) {
cin >> c[i];
g[i].clear();
for (int j = 0; j < c[i]; j++) {
int x;
cin>>x;
g[i].push_back(x);
}
}
int m;
cin >> m;
set<vector<int>> ban;
for (int i = 0; i < m; i++) {
vector<int> b(n);
for (int j = 0; j < n; j++) {
cin >> b[j];
}
ban.insert(b);
}
vector<int> q(n);
int sum = 0;
for (int i = 0; i < n; i++) {
q[i] = c[i];
sum += g[i][c[i] - 1];
}
priority_queue<PIII, vector<PIII>, less<PIII>> p;
set<vector<int>> vis;
p.push({sum, q});
vis.insert(q);
while (!p.empty()) {
auto [s, v] = p.top();
p.pop();
if (ban.count(v) == 0) {
// cout << s << ':';
for (int i = 0; i < n; i++) {
cout << v[i] << " ";
}
cout << endl;
return;
}
for (int i = 0; i < n; i++) {
if (v[i] > 1) {
vector<int> nxt = v;
nxt[i]--;
if (vis.count(nxt) == 0) {
int ns = s - (g[i][v[i] - 1] - g[i][v[i] - 2]);
p.push({ns, nxt});
vis.insert(nxt);
}
}
}
}
}
浙公网安备 33010602011771号