CF932 div2比赛总结

很烂，只做了两道题，感觉晚上好困。C思路是差不多的，主要是中间实现太复杂了，我忘了在遍历区间的右端点的时候，那个值是递减的。还是要注意区间与区间之间的关系。实现的时候还有些sb问题，需要注意。 ## CF932 div2 E. Distance Learning Courses in MAC ### 题意 n个数，每个数为 \([x_i,y_i]\) 内任意一个数，q个询问，每次给一个 \(l, r\)，问从第l个数到第r个数（共r-l+1个数）的最大or和。 ### 题解 - 从最大位开始贪心 - 如果该位（设为第 j 位）有两个数能为1（y_i <= (1<<j)），且至少一个数的 \(x_i\) <= (1<<j)，说明这个数可以进行“降维打击”，变成 (1<<j)-1 直接结束游戏 - 这样就把题目简化了很多，要么使用这个1后面继续考虑此数，要么不使用这个1直接进行降维打击。这个1只要不用就会结束游戏，所以一般情况必须得用。 # Educational Codeforces Round 161 Div.2 D. Berserk Monsters [[优化处理]]

题意

n个二元组 \((a_i,d_i)\) 排成一列，n轮，每一轮对于每一个 i 若 \(d_i<a_{pre_i}+a_{nxt_i}\) 则去掉这个二元组。（pre，nxt就是最近的没有去掉的二元组）。求每一轮去掉的组数。

题解

这道题比赛时想复杂了，想着对于每个联通块的左右端点处理，但其实没那么复杂。

It is important to note that if during the j�-th round the i�-th monster did not die and none of its alive neighbors died, then there is no point in checking this monster in the (j+1)(�+1)-th round. Therefore, we can solve the problem as follows: let's maintain a list of candidates (those who can die) for the current round; if the monster dies in the current round, then add its neighbors to the list of candidates for the next round.

只用每次检查没有被保护的人（list），如果死了就在list中加入它附近的人。注意检查和去掉应该是两个循环。

Educational Codeforces Round 161 Div.2 E - Increasing Subsequences [[构造]]

题意

构造一个子严格上升子序列的数量恰好为x的序列 ## 题解 构造->找到特殊处理方式 在一个序列最后如果加上一个比它们都小的值->t+=1 在一个序列最后如果加上一个比它们都小的值->t=2 t为子严格上升子序列的数量 将序列操作与数的二进制操作联系。 # 把一段染成一个颜色之后可以把这一段看成一个数 # Educational Codeforces Round 163 (Rated for Div. 2)D. Tandem Repeats? [[优化处理]] ## 题意 有一行由小写字母和？组成的字符串，？可以代表任何小写字母。求重复子串的最大长度，重复子串指满足 \(s[l,l+len-1]=s[l+len,l+len*2-1]\) 的连续子串。 \(n<=5e3\) ## 题解 没想到那么简单qwq 就是要找到处理的相同量，这里是判断 \(s[i]==s[i+len]\) ，当len固定时左端点l和l+1只有端点需要处理。在每次记一个cnt，记录满足相等的个数。因为len固定时判断的永远时s[i]和s[i+len]，所以 \(？\) 可以直接贪心处理。 # Educational Codeforces Round 163 (Rated for Div. 2)E. Clique Partition [[构造]] ## 题意 n个点，第i个点序号为i，让你给每个点分配一个 a_i（1~n中互不相同的数）。当 \(|i−j|+|a_i−a_j|≤k\) 时第i个点和第j个点连一条边。求此图的极大强连通子图的个数的最大值。 ## 题解 易得每个强连通子图的点的个数<=k，则构造一种方式使n=k时答案为1。如下： \[m,m-1,m-2,...,1,n,n-1,...,m+1，其中m=k/2向上取整\] 找到边界，构造边界 # Educational Codeforces Round 163 (Rated for Div. 2) F. Rare Coins [[概率]] [[优化处理]] ## 题意 有n个袋子，编号为1到n。第i个袋子里装着 \(b_i\) 个银币。每个银币有50%的概率价值为0，50%的概率价值为1。一个袋子的价值为其银币价值的和。现在问你Q个问题，每次给一个l和一个r和一个a，求 \[编号为l到r的袋子的价值和 - 其他袋子价值和 > a\] 的概率 ## 题解 简化问题：b1个银币贡献是加，b2个银币贡献是减，求 \(res=t+b1-b2>0\) 的可能性。 我们假设这b1个银币默认值是0，有1/2的概率变成1；b2个银币默认值是1，有1/2的概率变成0。则这b1+b2个银币都有1/2的概率使res增加1。我们再求res满足上述条件的概率（或者是方案数）就行。 把“和”变成“变化值”，整体化 # * [[构造]]可以注意一下特殊情况，比如 11111……1111 。还有题目上的限制可能比实际要用到的大，可能是来迷惑你的。

9.30

记得每次都要初始化，特别记住map， vector sqrt(long long) 精度不够，还是两边都平方 并查集卡常 -> 启发式合并

void merge(int x, int y) { x = find(x), y = find(y); if (x == y) return; if (sz[x] > sz[y]) swap(x, y); f[x] = y, sz[y] += sz[x]; }

D. Penchick and Desert Rabbit

一列数，只能跳左边比它大的，和右边比它小的，求以每一个数为起点能跳到的最高处。 突破口：a[i] 如何跳到 a[i+1]，利用 1~i最高 和 i+1~n最矮。然后发现如果跳不到则两边隔离。 why：发现从一个数跳到另一个数要考虑 左中右 三边的数，所以把中间删掉。