人有多大胆,暴力多大产

【杂题选做】[Chapter 8]

Codeforces 193E Fibonacci Number

题目大意

给出一个整数$x$,求$x$在斐波那契数列中最早的出现位置,这个斐波那契数列是这样定义的
$$Fib_0=0\\Fib_1=1\\Fib_i=(Fib_{i-1}+Fib_{i-2})\mod 10^{13}$$

简单题解

这题我完全不会做,根据题解。
我们可以发现,对于$\mod 10^i,3\leq i$满足斐波那契数列的循环节长度为$1.5\cdot 10^i$无话可说。
然后我们可以根据同余的方法,首先处理出1500以内的$x$同余的位置,然后10倍10倍扩展可以得到答案。
根据出题人所说,这样的$x$的位置是很少的。。。。

代码

Codeforces 145D Lucky Pair

题目大意

定义幸运的数为由4和7构成的数。

给出一个长度为$n\leq 2\cdot 10^5$的数列(保证幸运的数的数量不会超过1000),求满足以下条件的$(l_1, r_1, l_2, r_2)$的数量

$$l_1\leq r_1<l_2\leq r_2$$

同时不存在一个幸运的数同时出现在$[l_1,r_1]$和$[l_r,r_2]$中。

简单题解

出题人表示枚举$r_1$然后枚举$r_2$然后右边单调队列可以轻松解决,然而我个菜B不会。。。

所以我采取了左边扫描的过程中,右边用并查集维护。。。

这样的时间复杂度是$O(n^2\cdot \alpha)$的,所以我们需要将所有不是幸运的数的数压缩成一个就行了。

代码

Codeforces 132E England

题目大意

你有最多$m\leq 26$个变量,每次你可以给变量赋值,或者输出某个变量,赋值的代价是这个数二进制下的1的位数。

给出输出序列,求最小代价。

简单题解

费用流,首先我们拆点,每个要输出的数拆成两个点,为了限制点之间的流量至少为$1$,我们可以采取如下的姿势:

  1. 写上下界费用流
  2. 将中间的边的边权设置成负的无穷,然后最后答案加上$n*$负无穷

代码

Codeforces 138D World of Darkraft

题目大意

给出一个网格图,$n,m\leq 20$,网格图上的每个点可以是$L,R,X$

两个人轮流操作,选择一个没有被切到过的点。

如果这个点是$L$,那么从当前点发出一条向左下和向右上的射线直到遇到边界或者遇到一个被切过的格子为止。

如果是$R$则是右下和左上

如果是$X$则综合$L$和$R$

简单题解

首先我们发现对于$(i+j)$奇偶性不同的点是不能互相影响的,然后我们就可以直接$O(n^4)$表示状态,

将当前图翻转45°,然后就变成切割矩形的问题了。分奇偶性计算SG函数即可。

代码

Codeforces 140F Snowflake

题目大意

如果一个点集是中心对称的,那么存在一个点使得点集中的每个点关于这个点的对称点都存在。

现在给出$n\leq 2*10^5$个点,你可以添加$k\leq 10$个点,求不同的中心点的位置。

简单题解

首先我们将一个存在中心点的数组排序,我们可以发现第$i$个总是和第$n-i+1$个关于中点对称

根据$k\leq 10$,假设点$i,j$互相对称,那么这两个点的位置必然相差不超过$k$

那么我们又根据鸽笼原理,我们的$k$个点,最多使得$k$对有匹配,于是我们考虑枚举这第$k+1$对,这第$k+1$对,必然存在于两端的$k+1$个两两组合其一,枚举,然后$O(n)$检验即可。

代码

Codeforces 147B Smile House

题目大意

给出一个有向图$n\leq 300$,没有重边,没有自环,求一个点数最少的正权环。

简单题解

对于不存在的点之间连边为$-INF$,当然也可以直接不联通,

自己对自己连边权值为0

然后我们求$dp(k,i,j)$表示走了$2^k$步从$i$到$j$的最大权值的和。

然后我们二分步数,由于我们存在自环所以存在单调性。

然后我们只需要用LCA的方法合并一下答案检验$f(i,i)$是否存在大于0就行了。

代码

Codeforces  217E Alien DNA

题目大意

给出一个串,每次有一个操作$[L_i,R_i]$,求操作结束之后的前$k\leq 3*10^6$个是什么。

对于一个操作$[L,R]$首先将$[L,R]$中的串复制出来,然后奇数项放后面,然后接在$R+1$的位置上。

简单题解

服了。。。

考虑到我们已经知道最后的长度了,我们就可以倒着考虑那些部分的串是有用的,然后我们就可以知道一开始要保留的串的长度。

然后我们只要按照两次操作之间有效的长度来添加即可,用线段树$O(klog^k)$但是有点卡常数。

用Splay据说很快

替罪羊要TLE。。。。

代码

Codeforces 152D Frames

题目大意

给出一个$n*m$的网格图,满足$n\leq 1000$,求是否能用两个矩形框覆盖这个矩形图。

简单题解

首先将所有的某一行存在连续的大于三个点的行列的次大值,最大值,次小值,最小值处理出来然后枚举。

我的做法。。。

首先将所有的存在两个相邻方向存在连续大于等于3个的叫做A点,

如果一个A点存在两个方向相对并且都存在大于等于4个连续A点,或者这个点周围有$7$个以上A点我们叫做$B$点。

这样的点不会超过30个,然后枚举拐点。。。。

代码

Codeforces 135E Subsequence

题目大意

给出一个数值$k$表示字符集的大小,求满足最长次连续子串的长度为$w$的串有多少个

次连续子串即对于字符串$s$的一个子串$s_{l,r}$还存在$s_{l,r}$为$s$的非连续子序列。

简单题解

首先我们需要看出一个性质:对于一个串的最长次连续子串一定是这个串的前缀或者后缀。

Proof.

一定存在$s_{l,r}=s_{l_1,r_1}s_{l_2,r_2}$满足$l_1<l$或者$r_1>r$。

然后我们将反方向可以延长到串的开头或者结束位置。

 

假设串的长度为$w+L$我们如何才能使得其成立,显然,我们只需要$L$个中存在一个字符和第$w$个字符相同即可。且不能存在两个相同的字符,否则就可以延长到第一个字符那里。

即串的前$L$个和倒数第$w$个存在一个相同,或者后$L$个存在一个和$w$相同,且前$L$个互不相同,后$L$个互不相同。

我们考虑分类讨论$L$的大小,首先$L\leq k$否则必然存在$L$中有一个字符和第$w+1$个相同此时次长串的长度变大。

我们可以枚举$L$,考虑到$w$的长度是不变的,所以我们考虑区间的相交情况进行分类讨论

如果前面$w$和后面$w$个相离,那么$w\leq L$满足此时的情况应该是这样子的。

圈出来的部分互不相同,短的是$w$,那么我们可以先考虑任意情况,然后考虑不合法的。考虑圈出来的部分互不相同$A_k^{L-w}*(A_{k-(L-w)}^w)^2$

再考虑无解的情况$A_k^{L-w+2}*(A_{k-(L-w+2)}^k)^2$

同理考虑$L<w$的情况$w$的区域会相交,考虑相交部分可以任意填,然后考虑无解的情况即可,同时考虑以下当$w-L=1$的时候,第$w$个和倒数第$w$个是同一个即可。

代码

Codeforces 183D T-shirt

题目大意

给出$n\leq 3000$个人$m \leq 300$种物品然后每个人有一定概率喜欢的某种物品,现在请你选择初始每个物品要多少个使得期望的物品被喜欢的数量尽量多,一个物品只能被一个人喜欢。

简单题解

看到这个题就有一种贪心选择的感觉,首先贪心的处理出当前选择之后的增量最多的。关键是增量如何计算。。。。这里我一直算错还有被卡精度。。。看了题解。。。

首先令$f(i,j)$表示第$i$个人前有$j$个人喜欢的概率,

$f(i,j)=f(i-1,j)*(1-p_i)+f(i-1,j-1)*p_i$

然后考虑计算$g(i)$表示运了$i$个物品来之后的期望。

$g(x)=\sum_{i=0}^x f(n,i)*i + \sum_{i=x+1}^n f(n,i)*x$

然后$g(x+1)-g(x)=\sum_{i=x+1}^n f(n,i)=1-\sum_{i=0}^x f(n,i)$

发现这是个凸函数,所以我们就可以证明前面的贪心猜想是正确的。

然后我们只需要通过上述等式发现其实计算$g(x)$只需要知道$f(n,x)$即可,所以此时$f(i,j),j>x$都不需要被计算,所以选择一个物品之后重新进行计算的复杂度是$O(n)$的,所以总的时间复杂度为$O(n^2)$可以通过。

代码

 

加入讨论

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