Codeforces Round #189 (Div. 1 + Div. 2)

2024-08-31 18:46:30

A. Magic Numbers

不能出现连续的3个4，以及1、4以外的数字。

B. Ping-Pong (Easy Version)

暴力。

C. Malek Dance Club

考虑\(x\)二进制每一位1，假设位置为\(p\)，则前\(p-1\)位都需要一样，否则之前就计算了贡献，那么后面的位可以任取。

D. Psychos in a Line

链表模拟。

E. Kalila and Dimna in the Logging Industry

因为\(b_n=0\)，所以用最小代价砍倒第\(n\)棵树即可。
\(dp(i)\)表示砍掉第\(i\)棵树的最小代价。
\[dp(i)=min\{dp(k)+b_k\cdot a_i\}\]
斜率优化。

F. Have You Ever Heard About the Word?

删除次数最多\(\sqrt n\)次。
假设当前的删除长度为\(len\)，每隔\(len\)取一个关键点\(p\)，如果存在可删除串，则\(p\)和\(p+len\)的最长前缀和最长后缀之和大于\(len\)，通过二分+hash可以\(logn\)计算。

G. Ping-Pong

The length of the new interval is guaranteed to be strictly greater than all the previous intervals.

对于\(a<b\)，\(|I_a|<|I_b|\)，区间\(a\)和区间\(b\)要么相互可达，要么区间\(a\)完全被区间\(b\)完全包含。
利用线段树+并查集维护相互可达的区间。
判断\(a\)是否可达\(b\):
1. 相互可达，即属于同一集合。
2. 区间\(a\)的端点是否被\(b\)集合包含。
满足上面其中一点说明\(a\)可达\(b\)，否则不可达。

最新文章

热门文章