about 2 years ago

前言

尽管滚粗了还是可以来刷一刷题目的,把做的CF题目一起放在这里吧。。。
计数器君:不想写了

[662A]:就是给你两个长度为的序列,定义等概率等于,求异或和不为的概率。令,那么问题变成了从中选出若干个数使得其异或和为的概率,经典问题,我们直接求出线性基即可,假设有个线性基,那么答案
[662B]:给你一个无向图,个点条边,每条边有两种颜色,可以选择若干个点,并且翻转与这些点相邻的边的颜色,问最少翻转多少个点可以是所有边颜色相同,无解输出。首先枚举最终颜色,然后我们发现一个联通块只要确定了一个点的状态后所有点的状态都确定了,并且取反所有点的状态影响答案的合法性,因此我们直接确定点的状态,如果需要的点的个数超过一半,直接取反即可。
[662C]:一个矩阵,,可以取反若干行与若干列,求出最少能有多少个枚举行变换,那么对于一个行变换,答案的计算方式为,其中表示列为的列的数量,表示状态为的列最少能有多少个,也就是,直接即可。
[668A]:模拟题
[668B]:计算第一个和第二个的最终位置即可。
[668C]:有两个长度为的概率序列分别表示在两个序列中随机选中的概率。现在每次从两个序列中分别随机选一个数出来,给出出现的概率以及出现的概率,要求复原。对记一个前缀和,然后对着列等式,发现如果知道了就可以推出,而且有,直接倒推就好。
[668D]:离散化后对于每一个值考虑,按排序,然后按询问顺序操作,树状数组维护即可。
[665E]:经典应用。
[660F]:我们假设表示删除前缀和后缀的贡献,那么有,其中:

可以发现是一个关于的一次函数,因此我们可以维护一个凸壳,而且随着的增大,要不断删除一些一次函数。删除不好做,我们可以考虑利用分治将其转化成只有插入的过程,因此就是分治+半平面交,询问的时候二分一下即可,
[639F]:缩点建出一棵树,然后对于询问建出虚树,然后用虚树上的点+加的边里的点直接即可。
[653F]:由于要字符串不相同,考虑建出,对于上的每一个节点,二分出对于一个右端点的最大能向左的范围,然后直接主席树查询即可。
[650E]:首先答案是不相同的边的数目,很显然这是最小的,并且我们可以构造出解。具体的构造方法就是把相同的边连接的两个点缩起来,然后从叶子节点往上开始换边,这样可以保证不出现环。
[666E]:考虑暴力就是我们把个串用分隔符隔开串在一起,建这个的,然后把每次询问的子串放到里面跑一遍,询问一下走到的那个节点的集合中的区间最大值即可。所以问题变成了子串定位,假设是,我们先在里面跑,假设走到了,那么的位置一定是的祖先,倍增一下就好,注意一下无解的判断(我竟然跑了个rank1出来)。
[633H]:莫队+线段树+矩阵。
[626G]:如果没有修改,那么贪心地每次选最大贡献的,一个线段树或堆就可以。观察到每次只增减一个位置,那么对于答案的影响很小,对于每个操作,暴力交换贡献最大的一对即可。
[589C]:首先直接分下去的复杂度似乎是可以保证的,因为类似二分,但是我跑了,发现,对于每个序列预处理前的和就可以过了。
[559E]:Philipsweng的题解
[675E]:简单题没想出来(弱啊),就是我们从右往左,每次选择区间内能拓展到最远的更新答案即可。

← 2016湖南省选经历 TC杂题 →
 
comments powered by Disqus