首页 > 其他分享 >Codeforces Round #947 题解 (A~G)

Codeforces Round #947 题解 (A~G)

时间:2024-05-26 20:44:33浏览次数:37  
标签:匹配 题解 Codeforces Mocha 即可 947 Array 最小

目录

A. Bazoka and Mocha's Array

枚举每个循环移位判断 .

B. 378QAQ and Mocha's Array

首先最小的数肯定得选,删掉最小的数的倍数后再选一个最小的数,看一下能不能删空即可 .

C. Chamo and Mocha's Array

二分答案 \(x\),把 \(\ge x\) 的位置设为 \(1\),\(<x\) 的位置设为 \(-1\),然后就只需要判断是否存在一个长度不小于 2 的区间和 \(>0\),做一个最大子段和即可 .

D. Paint the Tree

注意到最优的策略一定是先在中点会合然后一起遍历所有点 .

对于从根遍历所有点的最小步数可以发现安排深度最大的叶子最后走即可得到答案 \(2(n-1)-\max dep\) .

E. Chain Queries

一个点集是链当且仅当:

  1. 连通 .
  2. 对于每个点父亲组成的可重集合 \(S\),下面两种情况满足其中一种:
    • \(S\) 中没有重复元素 .
    • \(S\) 中只有深度最大的点出现过 2 次,其他的元素没有重复出现过 .

连通可以算点数减边数,在 BFS 序上建树状数组维护即可 . \(S\) 可以直接用一个桶动态维护 .

F. Set

按位枚举每一位的决策,注意到每确定一位实际上会使一些约束合并,可以动态维护所有剩余的约束进行暴搜 .

因为确定 \(x\) 个数后只剩 \(2^{n-x}\) 个约束,所以直接搜的状态数是 \(\Theta(n2^n)\) 级别的,可以通过 .

G. Zimpha Fan Club

如果两个串都没有 *,按位匹配即可 .

如果两个串都有 *,只需匹配 * 隔开的最前面的串和最后面的串即可 .

对于一个串有 *,一个串没有 * 的情况,按 * 划分成若干段,相当于每次对于一段计算到另一段的最早匹配点然后匹配掉这个位置,只需要支持每次快速找匹配点 .

首先两个只带 - 和字母的串进行匹配可以直接用卷积表示,具体见残缺的字符串 . 对于本题考虑倍增进行这个匹配的过程,这样复杂度就是 \(O(n\log n)\) 的了(因为可以注意到 \(\sum i2^i\sim n2^n\)).

标签:匹配,题解,Codeforces,Mocha,即可,947,Array,最小
From: https://www.cnblogs.com/CDOI-24374/p/18214217

相关文章

  • Codeforces Round 947 (Div. 1 + Div. 2) E. Chain Queries
    本来决定开摆养生不打的,但11点半的时候点进去看到这个题是个疑似DS,写题的欲望瞬间高涨,然后就40min写了这个题然而赛中并不能提交,只好等到第二天早上再交一发,没想到还WA了一发才过首先这题如果我们能确定当前黑色点集的链的两个端点\(x,y\)的话,这个题就非常显然了只需要求出\((x......
  • 【leetcode 399 周赛】【题解】
    第一题和第三题一样。就是求约数第二题就是模拟第4题使用线段树1,3题代码实际上发现没有下面代码的负载,比如:a*b=n,枚举a就好,a在[1,sqrt(n)内。importjava.util.*;classSolution{publicintnumberOfPairs(int[]nums1,int[]nums2,intk){......
  • CATIA入门操作——萌新宝宝遇到的奇奇怪怪的问题解决,持续更新中。。。
    目录引出发生肾么事了??鼠标中键旋转不了解决:特征树不显示参数关系我的窗口去哪了?插曲:草图工具的调出插曲:颜色工具栏显示弹窗警告警告:创建约束是临时的操作技巧技巧:快速隐藏不相关元素工具栏怎么变成水平?总结异形弹簧新建几何体草图编辑,画一条样条线进行扫掠,圆心和半......
  • CF1821F Timber 题解
    题意:在\([1,n]\)的区间里放\(m\)棵树,每棵树的高度为\(k\)。求有多少种放置树的方法,满足:每个树都在整点上,且每个点最多只能放一棵树。存在一种砍倒树的方案,使得树倒了之后不会越界,也不会有某个点被超过一棵树占据。你可以自由选择树向左倒(也就是占据区间\([x-k,x]\))......
  • [SHOI2007]书柜的尺寸 题解
    题目链接设\(f_{i,t1,t2}\)表示前\(i\)本书,第一层的宽度为\(t1\),第二层的宽度为\(t2\),所需要的最小高度。第三层宽度\(t3=\sum_{i=1}^{i}t_i-t1-t2\)。但本题还有一个重要限制:每层的高度取决于该层最高的书,如果直接按照顺序加入书本,从\(dp\)的状态来看,无法确定新书本......
  • CCF-GESP 等级考试 2024年3月认证C++一级真题解析
    2024年03月真题1单选题第1题C++表达式(3-2)*3+5的值是()。A.-13B.8C.2D.0正确答案:B.8解析:首先计算括号中的表达式(3-2),得到(1)。接下来进行乘法运算(1*3),得到(3)。最后进行加法运算(3+5),得到(8)。因此,表达式的值是(8)。第2题C++......
  • 24.2.13 ~ 4.13 Codeforces Round 925 & 926 & 934 & 939 (Div.3 / Div.2 * 3)
    925Div.3Solve:A~G(7/7)Rank:95Rating:\(0+706=706\)(\(1400+206=1606\))发挥评价:Normal+本场没什么有价值题目。926Div.2Solve:A~DF(5/6)Rank:72Rating:\(706+575=1281\)(\(1606+225=1831\))发挥评价:Good本场没有什么失误。CF1929E*2300(me*2300)选......
  • Codeforces Round 947 (Div. 1 + Div. 2)
    Solve:A~ERank:425Rating:\(1744+195=1939\)(\(1894+95=1989\))发挥评价:Normal本场问题:E先WAon4,较快找出问题后修改WAon27,就又急了(重现上午),开始怀疑做法正确性未果,结果1h后才发现是代码出现问题。注意先检查代码漏洞而不是先怀疑正确性(尤其是错在后面时候,要是正......
  • 题解:P6880 [JOI 2020 Final] オリンピックバス
    一个比较重要的性质:反转的边要在最短路上才会有贡献。我们可以先跑一遍最短路,记录下整颗最短路树,然后暴力的对每一条边进行判断,反转。我们建正反图各两个,分别以\(1\),\(n\)为起点。\(n\),\(1\)为终点。然后对每个图跑最短路,记录下最短路树。若不反转任何一条边,则答案为\(1\)......
  • 题解:CF1119D Frets On Fire
    大水题。首先,若区间内只有一根弦,不会对答案有贡献。我们思考如何对答案产生贡献。我们知道,对于每一个\(s_i\),都会产生一段\(s_i+r-l\)的连续序列,在对\(s\)数组排序后,若每个\(s_i+r-l\ges_{i+1}\)则答案为\(s_n+r-(s_1+l)+1\)。若够不到下一位呢?我们在\(s_n+r-(s_1+l......