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

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

题面

A.ABC string

【题面】

给定一个字符串 \(s\),构造一个括号字符串 \(t\) 满足:
1.如果任意 \(s_i=s_j\),那么 \(t_i=t_j\)
2.\(t\) 满足身为一个括号字符串的要求。

【思路】

1.首先可以发现应为 \(s\) 中的元素数量只有 \(3\) 个,所以说可以直接枚举一下每一种不同的 \(s_i\) 可以对应哪些括号即可。
2.时间复杂度就是枚举每一种括号的情况,和判断是否符合一个括号序列。

【实现】

#include <bits/stdc++.h>
using namespace std;
const int N=5e1+10;
char s[N];
int dis[3];
void solve(){memset(dis,0,sizeof(dis));cin>>s;if(strlen(s)%2) { puts("NO"); return; } if(s[0]-'A'==s[strlen(s)-1]-'A') { puts("NO"); return; }dis[s[0]-'A']=1;dis[s[strlen(s)-1]-'A']=-1;bool flag;int zero,sum;for(register int i=0;i<=2;i++) if(!dis[i]) zero=i;dis[zero]=1;sum=0,flag=true;for(register int i=0;i<strlen(s);i++){sum+=dis[s[i]-'A'];if(sum<0) { flag=false; break; }}if(flag&&!sum) { puts("YES"); return; }dis[zero]=-1;sum=0,flag=true;for(register int i=0;i<strlen(s);i++){sum+=dis[s[i]-'A'];if(sum<0) { flag=false; break; }}if(flag&&!sum) { puts("YES"); return; }puts("NO");
}
int main()
{int t;scanf("%d",&t);while(t--){solve();}return 0;
}

B. Berland Crossword

【题面】

给定一个 \(n\times n\) 的矩阵,再给出第一行,最后一行、第一列、和最后一列有多少个黑色的点。判断是否存在。

【思路】

1.首先可以发现对于非第一行,最后一行、第一列、和最后一列的格点是无效的。
2.角落的格子会有重复,所以只有这些格点是需要被特殊考虑的。再发现因为只有4个格子我们可以直接去枚举 \(2^4=16\) 次,去判断是否满足要求。

【实现】

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<int> vi;
const int N = 1e5 + 5;
int n,u,d,l,r;inline bool check(int ul, int ur, int dl, int dr){int um = u - ul - ur;int dm = d - dl - dr;int lm = l - ul - dl;int rm = r - ur - dr;if(um < 0 || um > n - 2) return false;if(dm < 0 || dm > n - 2) return false;if(lm < 0 || lm > n - 2) return false;if(rm < 0 || rm > n - 2) return false;return true;
}
int a[4];
bool flag;
void dfs(int step){if(step == 4){flag |= check(a[0], a[1], a[2], a[3]);return;}a[step] = 0;dfs(step + 1);a[step] = 1;dfs(step + 1);
}
int main(){ios::sync_with_stdio (false);cin.tie(nullptr);int T;cin>>T;while(T --){cin>>n>>u>>r>>d>>l;flag = false;dfs(0);cout<<(flag ? "YES" : "NO")<<endl;}return 0;}

C.1D Sokoban

【题面】

\(n\) 个箱子在一个数轴上,你可以从原点开始走去推箱子(不能拉),箱子可以推动箱子。

【思路】

1.因为不能拉,所以原点左侧和右侧的点不能到另一侧,所以可以分开考虑。
2.人只能推最左侧的箱子(我们简称可推箱子),可推箱子将左侧的若干个箱子压缩在一起,而右侧的箱子保持原状。因此,我们可以将答案的计算分成两个部分:压缩在一起的箱子占据的特殊位置数量,以及保持原状的箱子占据的特殊位置数量
3.因此,我们得到了一种不是很有效率的做法:枚举可推箱子的所在位置,计算有多少个箱子被压缩在一起,进而分别计算这两个部分的箱子占据的特殊位置数量。
4.可以用 lower_bound 去二分,时间复杂度是 \(O(n\log m)\)

【实现】

#include<bits/stdc++.h>
using namespace std;
constexpr size_t N = 2e5 + 5;
int a[N], b[N];
int sum[N], in[N];
void solve(){int n, m;cin >> n >> m;unordered_set<int> s;for (int i = 0; i < m; i++) in[i] = sum[i] = 0;for (int i = 0; i < n; i++)cin >> a[i], s.insert(a[i]);for (int i = 0; i < m; i++)cin >> b[i], in[i] = (s.count(b[i]) >= 1);for (int i = 1; i < m; i++) in[i] += in[i - 1];int ta = lower_bound(a, a + n, 0) - a - 1;int tb = lower_bound(b, b + m, 0) - b - 1;while (tb >= 0) {while (ta >= 0 && a[ta] >= b[tb]) sum[tb]++, ta--;tb--;}ta = lower_bound(a, a + n, 0) - a;tb = lower_bound(b, b + m, 0) - b;while (tb < m) {while (a[ta] <= b[tb] && ta < n) sum[tb]++, ta++;tb++;}int posl = lower_bound(b, b + m, 0) - b - 1, posr = posl + 1;for (int i = posl - 1; i >= 0; i--) sum[i] += sum[i + 1];for (int i = posr + 1; i < m; i++) sum[i] += sum[i - 1];int ansl = 0, ansr = 0;for (int i = posl, mx = posl + 1; i >= 0; i--) {while (mx - 1 >= 0 && b[i] - b[mx - 1] + 1 <= sum[mx - 1]) mx--;if (mx >= 1)ansl = max(ansl, i - mx + 1 + in[mx - 1]);elseansl = max(ansl, i - mx + 1);}for (int i = posr, mx = posr - 1; i < m; i++) {while (mx + 1 < m && b[mx + 1] - b[i] + 1 <= sum[mx + 1]) mx++;ansr = max(ansr, mx - i + 1 + in[m - 1] - in[mx]);}int ans = ansl + ansr;cout << ans << '\n';
}
signed main(){int T;cin >> T;while(T--){solve();}return 0;
}

D.DogeForces

【题面】

一个公司里有上下级关系,每个下级有恰好一个直属上司,立刻想到树形结构
用树形结构翻译题目:每个节点有权值,父节点的权值严格大于子节点,每个父节点有 \(\geq 2\) 个孩子。二维数组 \(a\) 给出了每对节点的最近公共祖先(lca)的权值。

【思路】

1.容易想到最大的权值肯定属于根(记为 \(max\)
2.如果 \(a_i = max\),说明 \(i,j\) 属于不同的树中。
3.因此,我们可以通过 \(a_{i,j}\) 是否等于 \(max\) 来确认有多少个子树,以及每个子树中有哪些节点(最直观的方法是使用并查集,代码中有更为方便快速的解法)。
4.用递归还原每一个树的结构

【实现】

#include<bits/stdc++.h>
#define pb push_back
#define mkp make_pair
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef pair<int, int> pii;
const int N = 1e3 + 5;
int c[N];
int a[N][N];
int n,k;
vector<pii> edges;
void solve(vi vs, int fa){int u = vs[0];if(vs.size() == 1){c[u] = a[u][u];if(fa != -1) edges.pb(mkp(u, fa));return;}int maxa = 0;for(auto v : vs){maxa = max(maxa, a[u][v]);}vector<vi> subs;for(auto v : vs){bool smallest = true;for(auto w : vs){if(a[v][w] != maxa){if(w < v) smallest = false;}}if(smallest){//确保v是所在子树里编号最小的节点,这样能够避免重复计算子树vi sub;for(auto w : vs){if(a[v][w] != maxa) sub.pb(w);}subs.pb(sub);}}k++;int curU = k - 1;c[curU] = maxa;if(fa != -1) edges.pb(mkp(curU, fa));for(auto sub : subs){solve(sub, curU);}}
int main(){ios::sync_with_stdio (false);cin>>n;for(int i = 0; i < n; i ++){for(int j = 0; j < n; j ++)cin>>a[i][j];}k = n;vi vs;for(int i = 0; i < n; i ++) vs.pb(i);solve(vs, -1);cout<<k<<endl;for(int i = 0; i < k; i ++) cout<<c[i]<<" ";cout<<endl<<n + 1<<endl;for(auto e : edges){cout<<e.first + 1<<" "<<e.second + 1<<endl;}return 0;}

E.A-Z Graph

【题面】

维护一个有边权的有向图,支持加边、删边,询问是否存在一个包含 \(k\) 个点的节点序列,正向走和反向走得到的字符串相同。

【思路】

1.观察样例路径 \(1 \to 2 \to 3 \to 2 \to 1\),发现这条路径是合法的,但与回文串没有直接关系。路径 \(1, 2, 3, 2, 1\) 本身是一个回文结构。

2.这个结构还可以进一步简化:\(1 \to 2 \to 1 \to 2 \to 1\) 也是一个合法路径!完全不需要 3 号点的参与。
3. 只要存在 \(u \to v\)\(v \to u\) 这样的双向边,就可以构造 \(u \to v \to u \to v \to u \ldots\) 这样的路径,这可以解决所有的奇数长度路径问题。
4. 假如有路径 \(1 \to 2 \to 3 \to 4\)\(4 \to 3 \to 2 \to 1\) 能够得到相同的字符串,可以发现 \(2 \to 3\)\(3 \to 2\) 必然有一样的字符。\(2 \to 3 \to 2 \to 3 \to \ldots\) 能解决所有偶数长度的路径,但相比奇数路径有额外要求:\(u \to v\)\(v \to u\) 需要具有相同的边权。

【实现】

#include<bits/stdc++.h>
#define pb push_back
#define mkp make_pair
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef pair<int, int> pii;
const int N = 2e5 + 5;
int n,m;
map<pii,char> mp;
int cntO,cntE;
int main(){ios::sync_with_stdio (false);cin>>n>>m;while(m--){char op;int u, v, k;char c;cin>>op;switch(op){case '+':cin>>u>>v>>c;if(mp.find(mkp(v,u)) != mp.end()){cntO++;if(mp[mkp(v,u)] == c) cntE++;}mp[mkp(u,v)] = c;break;case '-':cin>>u>>v;if(mp.find(mkp(v,u)) != mp.end()){cntO--;if(mp[mkp(v,u)] == mp[mkp(u,v)]) cntE--;}mp.erase(mkp(u,v));break;case '?':cin>>k;if(k % 2 == 1) cout<<(cntO > 0 ? "YES" : "NO")<<endl;else cout<<(cntE > 0 ? "YES" : "NO")<<endl;break;default:break;}}return 0;}s
http://www.hskmm.com/?act=detail&tid=28705

相关文章:

  • 基于MATLAB的梯度下降法实现
  • C++练习
  • 2025 年房屋鉴定公司最新推荐权威榜单:涵盖安全评估 / 承载力 / 工程质量 / 危房 / 受损伤等领域,助您精准挑选靠谱机构
  • 当游戏NPC有了“灵魂”,网易伏羲解码游戏智能交互场景新实践
  • 2025最新微信公众号文章数据批量导出excel工具1.0版
  • 磊科N60Pro刷机
  • Mac端查词翻译工作流:基于欧路词典与Raycast
  • m3u8格式在直播场景中的应用
  • C# ProgressBar 进度条控件
  • 随手写的一个子进程
  • 来追梦-D1295 小F过河
  • P3605解题报告
  • P13763 解题报告
  • CF1082E 解题报告
  • 国标GB28181算法算力平台EasyGBS具备哪些核心流媒体技术?
  • 2025 年净化车间源头厂家最新推荐排行榜:精选实力企业,助力企业精准选择优质净化车间服务商无尘/gmp/新能源/锂电池净化车间厂家推荐
  • C语言的“动态数组”
  • 背包 dp 历年真题:做题记录
  • 【触想智能】什么是工业平板电脑以及工业平板电脑对制造业具有什么意义
  • 2025 年国内无尘车间源头厂家最新推荐排行榜:聚焦无菌洁净领域优选企业助力企业精准选型万级/十万级/洁净/食品厂/千级无尘车间厂家推荐
  • 新手小白安装Typroa遇到的问题 - I
  • 怎么能跑得快,怎么突破瓶颈
  • (Sigcomm25) Stellar: 阿里新一代云AI RDMA网络
  • 高效工作,五步工作法
  • 虚树学习笔记
  • 市场营销:
  • Python3开发敏感词过滤程序底层逻辑记录
  • OUC《软件工程原理与实践》- 实验2:深度学习基础 - OUC
  • 类型转化
  • 【IEEE出版】第五届电子信息工程与计算机技术国际学术会议(EIECT 2025)