人有多大胆,暴力多大产

【杂题选做】[Chapter 9]

Codeforces163D Large Refrigerator

题目大意

给出$V\leq 10^{18}$求$a*b*c=V$使得这个$a*b*c$的立方体表面积尽量小。

数据组数$T\leq 10^5$

简单题解

搜索,输入已经给出了分解,直接枚举因数分别考虑三个因数的上界从大到小枚举即可

$a\leq V^{\frac{1}{3}}$

$b\leq \frac{V}{a}^{\frac{1}{2}}$

然后考虑一个剪枝,发现$a$确定的情况下表面积是一个$a\cdot x+\frac{b}{x}$的函数,然后可以直接计算最小值,然后判断是否可行。

代码

Codeforces167E Wizards and Bets

题目大意

没有入度的点叫做L点,没有出度的点叫做R点,保证这是一个拓扑图,每一个L点都必须匹配一个R点,然后如果$i,j$都是L点,并且这两个点匹配的点满足$i<j$且$match[i]>match[j]$

那么我们考虑这样的$(i,j)$的数量,如果是奇数,那么计数器+1,如果是偶数,那么答案减一。

并且匹配的路径不能相交,$n\leq 600$

简单题解

观察可以发现路径不能相交其实没有什么卵用,因为相交之后总是会使得计数器+1-1=0。

所以我们剩下的观察可以发现和行列式的定义相同。

拓扑排序,计算一下路径方案数量,然后计算矩阵的行列式值即可。

代码

Codeforces232D Fence

题目大意

给出$n$个数,$m$个询问,每次询问$l,r$,求有多少个长度和$[l,r]$相同的区间且不和$[l,r]$相交使得对应位置的和相同。

$n,m\leq 10^5,$

简单题解

显然需要差分一下,然后正着的后面接一个反着的,然后求后缀数组,然后维护一下前缀和,每次二分位置即可。

关键是不能相交,所以我们还要按照编号位置用主席树维护一下。

代码

Codeforces175E Power Defence

题目大意

有两种类型的攻击塔楼,和一种类型的减速塔楼,给出三种塔楼的波及范围,和两种攻击塔楼的攻击力,如果一段区间被$k$个塔楼覆盖,那么移动速度将会变成$\frac{1}{k+1}$,求最大总的伤害值,塔楼只能放在$(x,1),(x,-1)$的位置上,$x\in Z$,人从$(-\infty, 0)$移动到$(\infty, 0)$

简单题解

首先我们需要看出这样一个性质,当塔楼挨得很近的时候是最优秀的。

然后我们枚举哪些位置放减速,然后剩下的空位计算一下收到的伤害就行了,可以计算两个伤害的差然后排序求前缀和来起到替换的作用。

代码

Codeforces176D Hyper string

题目大意

给出一些基本串,然后A串是由这些串组合起来的,组合已经给出,保证所有的字符串的长度的和不会超过$10^6$但是不保证组合后在这个范围内。

然后给出一个串B,长度不超过2000,求A和B的最长公共子序列。

简单题解

两次预处理,计算出当前串的第$i$个第下一个j字符。

第二次预处理出$A$串中的第$i$个串后的第一个j字符。

然后我们$dp(i,j)$表示$B$串到了第$j$个位置最长上升子序列的长度为$i$的最前面的位置。

然后转移很显然了,贪心的转移即可。

代码

Codeforces178F2 Representative

题目大意

$f(x,y)$表示第$x$个串和第$y$个串的最长公共前缀,然后求选出$k$个串之后两两之间的$f$的和的最大值

简单题解

首先我们可以考虑到按照字典序排序,然后类似后缀数组求height数组,然后我们就转化成了分治问题,求区间最小值,然后枚举左右区间选多少个。

最差情况下的复杂度大致为$O(f(n))$,$f(n)=max\{f(x)+f(n-x)+x*(n-x)\}$

考虑另一种计算复杂度的方法,我们将两边统计的看作点,然后一个点对会被统计到当且仅当分割点在他们中间,且这个分割点是最后一个,那么我们有$O(n^2)$个点对,复杂度就是$O(n^2)$的了。。。。

无话可说,这个和那个什么诡异的树上$dp$的分析复杂度方法好像,失去了语言。

代码

Codeforces178E3 The Beaver’s Problem II

题目大意

给出一张图,求上面有多少个圆,多少个正方形,每个点有0.2的概率反色。

简单题解

SolutionA

对图进行若干次模糊,然后求一个块到其中心最远点和最近点的比例

SolutionB

对图求联通块,理论上有很大的概率还是四联通的,然后求最远点对作为正方形的对角线,然后求一个容错率大致在1.2左右,因为大概有20%的黑色点变成了白色。

代码

Codeforces185D Visit of the Great

题目大意

求$Lcm(k^{2^l}+1,k^{2^{l+1}}+1,k^{2^{l+2}}+1,\cdots,k^{2^r}+1)$

数据保证$k\leq 10^6, l,r\leq 10^18$,最后取模$p\leq 10^9$

简单题解

出题人太神啦,我最多想到前一个是后一个的减一的平方加一,完全没有想过展开化简。。。。

设$k^{2^l}+1=x$那么$k^{2^{l+1}}+1=(x-1)^2+1=x^2-2x+2$

那么我们考虑$Lcm(x,x^2-2x+2)=\frac{x*(x^2-2x+2)}{Gcd(x,x^2-2x+2)=Gcd(x,2)}$

所以我们只需要考虑$k^{2^l}+1$的奇偶性也就是$k$的奇偶性即可。

然后我们考虑如何计算$\prod_{i=l}^r (k^{2^i}+1)$

首先我们不难发现左边的指数总是一个二进制数并且bit=1,并且对于每一项1的位置都不同成绩在指数上表现出来是相加,那么展开之后就是

$\sum_{i=0}^{2^{r-l+1}-1}k^{2^l*i}=(k^{2^l})^i$

显然是一个等比数列求和,那么我们直接等比数列求和即可,同时处理特殊情况即

  1. $%$后公比($q$)=1
  2. $k%mod=0$
  3. $mod|(q-1)$其实和第一条是一样的,就是$q=1$,因为$q\leq\ mod$

代码

Codeforces187D BRT Contract

题目大意

有$n$个红绿灯,一共$n+1$段公路,给出公路长度,每次询问当我从零点出发的时间是$x$的时候到达终点的时间。

经过$g$的时间绿灯变成红灯,经过$r$的时间红灯变成绿灯,$n\leq 10^5, r+g\leq 10^9$,速度总是1

简单题解

首先我们不难发现对于出发时间关于$r+g$同余的都是相同的状态,如果被某个红绿灯拦下之后,后面的移动都和前面的移动无关了。

所以我们考虑计算$dp(i)$表示从第$i$个红绿灯出发能够到达的终点还要多久。

然后我们用$dis(i)$表示第$i$个红绿灯的距离起点的位置,那么我们考虑到出发时间是s,到达被拦住的时间是$t$,那么显然有$t-s=dis(t)-dis(s)$

那么我们就是要找到$i$后面的一个最前面的点使得$dis(t)-dis(i)\mod (r+g) \in [dis(i)+g,dis(i)-1]$,当然是模意义下的。

然后我们用线段树维护即可,询问也用类似的方法在线段树上查询即可。

代码

Codeforces180B Divisibility Rules

题目大意

给出两个数$b$和$d$分别表示在$b$进制下的除数为$d$

求判断$d$的倍数的条件。

如果是形如需要知道一个数的末尾几位的判断的为2-type

如果是形如需要知道所有位数的和的为2-type

如果是形如需要知道奇数位数和偶数位数的差的为11-type

如果是可以用上述三种方法组合起来判断的为6-type

否则输出7-type

$d,b\leq 100$

简单题解

首先判断2-type,显然如果$b^k$是$d$的倍数,那么可以判断。

然后判断3-type,如果$b%d=1$那么可以判断。

然后判断11-type,如果$b%d=d-1$那么可以判断,这是为什么呢?

显然如果仅仅在个位增加不进位,那么显然满足,如果发生了进位,那么必然有进的位数是1,并且当前位置增加的也是1,相当于差值为0。

然后6只需要考虑因数然后暴力DP一下就行了。

代码

 

加入讨论

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