人有多大胆,暴力多大产

【杂题选做】[Chapter 10]

Codeforces198E Gripping Story

题目大意

平面上有$n$个磁铁,人在一个点上手里有一块磁铁,令一个磁铁能被吸过来当且仅当距离小于等于吸引距离,并且质量小于等于引力。

$n\leq 10^5$

简单题解

首先不难发现我们要按照dis进行搞,然后考虑我们每次只是求一个前缀内的所有质量小于等于引力的东东,不妨直接对线段树上每个点建立平衡树然后按照质量排序,然后询问貌似就可以了,当然也可以每个点维护一个vector,然后统计区间内的质量最小值,然后每次取一个,不难发现最多取$n$次,这样的复杂度也是$O(n\log n)$

代码

Codeforces176E Archaeology

虚树模板题,不想多说

Codeforces196D Good String

题目大意

给出一个字符串S,求另一个字符串S1使得S1是字典序大于S的最小的字符串且不存在长度大于等于$m$的回文子串。

简单题解

首先我们知道一个性质,如果存在长度为$m$的回文串,那么一定存在长度为$m-2$的,如果存在长度为$m+1$的回文串,那么一定存在长度为$m-1$的,

那么我们只需要一次一次的尝试即可,考虑到由于存在两个字符所以可能存在2个字符被限制,如果被卡死,那么就要倒回去进行调整,然后后面每个位置就有26个选择就不会被卡死了。

代码

Codeforces200E Tractor College

题目大意

已知$c_3, c_4, c_5$满足$c_3*a_3+c_4*a_4+c_5*a_5=V(0\leq a_3\leq a_4\leq a_5)$

求合法的$a_3,a_4,a_5$

使得$|c_4*a_4-c_3*a_3|+|c_5*a_5-c_4*a_4|$尽量小。

简单题解

首先枚举$a_4$然后分类讨论各种极限情况即可。(难道这种求绝对值的东西都是枚举公共的项比较方便?)

代码

Codeforces200A Cinema

题目大意

给出一个$n*m$的棋盘大小,然后$m$次询问,每次找最近的没有被标记过的曼哈顿距离距离$(x,y)$最小的点将其标记。

简单题解

败了,居然是这样。。。

首先我们考虑暴力枚举行,然后找这一行的这一个位置的前一个和后一个,用并查集维护。

考虑到如果连续$k$次还招不到答案,那么有$k^2$个点已经被标记,但是$k^2\leq m$,所以复杂度是$k^{\frac{3}{2}}$

完败。

代码

Codeforces201D Brand

题目大意

给出两个序列一个长度为$n\leq 15$另一个长度为$m$,求相对位置错误的数量。

简单题解

我败了,这么简单的题我居然想不出来。。。思维僵化

首先$n$很小可以考虑状态压缩,然后我们就用$f(S,p)$表示当前已经出现了$S$中的数了,当前位置在$p$,。。。但是显然$p$太大了。。。过不了。

所我们考虑替换定义$f(S,p)=n$转换成$f(S,n)=p$表示当前的错误的对数为$n$能够出现的最早位置为$p$。。。。

败了。

代码

Codeforces201E Organization

题目大意

一个伪交互题,首先是这样的每次给出一组询问的个数不超过m个,返回一个集合表示询问的数的位置。

给出$n$和$m$求询问最少多少次才能分辨出$n$原来的样子。

简单题解

我完败,完全想不出来。。。

首先考虑到如果次数为$k$,那么我们相当于要构造$n$个数每个数都在$k$位二进制以内,并且每一位上为1的个数不超过$m$个。

这是非常不好计算的,所以我们计算1的个数的总数小于等于$m*k$的有多少个。

这是等价的吗?

答案是肯定的,首先我们假设,某一行多于$m$个,那么必然有某一行少于$m$个,然后我们考虑到假设$x$为多余那一行的那一行是1,少于是0的个数。

$y$是少于那一行的多于是0,少于是1的个数,然后考虑$x>y$,然后我们可以得到如下的结论,肯定存在一个数交换$1$到$0$上后不和$y$个重叠,然后这样的操作可以使得多于的那一行-1,然后重复调整可以得到最优解。

。。。。失去了语言。。。。

代码

Codeforces204E Little Elephant

题目大意

求每个字符串有多少个子串出现在至少$K$个串中。

保证所有的串的长度的和小于等于$10^5$

简单题解

首先我们考虑这样一个问题:首先我们考虑用后缀数组解决这个题目,首先接在一起后缀数组,然后我们考虑每个后缀的最长的前缀使得这个这一段的height大于等于长度并且覆盖了至少K个种类的串,很显然存在单调性,然后我们考虑用并查集合并height从大到小,如果存在一个合并后的区间存在至少K种,那么这个height就是这个区间的最小的height,我们对区间取最大值,然后最后扫一遍进行询问即可。

貌似很多针对子串的问题都可以转换成用后缀数组的height上进行维护某些东西解决。看来我后缀数组还没有学好,满脑子的AC自动机,后缀自动机。。。完全想多了。

代码

Codeforces207B Military Trainings

题目大意

给出$n$辆坦克,第$i$辆坦克只能接受范围在$[i-a_i,i]$的坦克的信息

然后对这$n$辆坦克的循环串求从$1$到$n$传递信息的最少传递次数。

简单题解

又又又忘记了,正难则反,考虑到一个点如果要从前面转移到他,那么反过来也可以看作从他转移到别人,求从n到1转移的最少次数,然后我们考虑将串扩展成$2n$的然后我们就可以计算经过倍增次跳跃后的能够走到的最远的距离的前一个点,然后我们就可以通过类似二分合并的方法解决这个题目,找到使得无法跳到1的最多行走步数+1就是答案,我的代码有点鬼畜。请勿模仿。

代码

TLE

Codeforces207A Beaver’s Calculator

题目大意

如果$j=i+1$并且$a_j<a_i$那么这称为一个坏对,

然后我们将$n$个串归并求最少的坏对数量并输出方案。

简单题解

首先我们发现坏对如果在某个串中出现,那么这个坏对就势必无法消除,那么最终的坏对数量就是坏对数量最多的那个串,然后我们按照坏对进行分组然后贪心进行归并即可。

代码

 

加入讨论

电子邮件地址不会被公开。 必填项已用*标注