水题记录(四)

50 / 50

【BZOJ1528】【POI2005】SAM-Toy Cars

贪心,每次选择后继最远的,可以保证这$k$步内最优,然后推下去就最优了,用堆维护。

【BZOJ1831】【AHOI2008】逆序对

考虑到填入的不下降一定最优,设 $f[i][j]$ 表示第$i$个 “-1″选不大于$j$的数最小能得到的答案,然后树状数组求逆序对转移即可。不太会O(nk)的。同1786

【BZOJ1826】【JSOI2010】缓存交换

1528+离散化即可。

【BZOJ1531】【POI2005】Bank notes

多重背包,我不会单调队列,二进制分组可过。如果要求输出方案,因为只有两种转移,拿个bool数组记录即可。

【BZOJ1432】【ZJOI2009】Function

貌似不太可做??那就找规律。
然后做完了..(数据范围真的毒瘤啊….)

【BZOJ3529】【SDOI2014】数表

$$
\sum_{k}f(k)\sum_{i}^{n} \sum_{j}^{m}[gcd(i,j)=k]
$$
$$
\sum_{k}f(k)\sum_{d = 1}^{min(\lfloor \frac{n}{k} \rfloor,\lfloor \frac{m}{k} \rfloor)}\mu(d) \times \lfloor \frac{\lfloor \frac{n}{k} \rfloor}{d} \rfloor \times \lfloor \frac{\lfloor \frac{m}{k} \rfloor}{d} \rfloor
$$
$$
\text{Set T = d * k}
$$
$$
\sum_{T = 1}^{min(n, m)}(\lfloor \frac{n}{T} \rfloor \times \lfloor \frac{m}{T} \rfloor \times \sum_{k | T} f(k) \times \mu(\frac{T}{k}))
$$
$$
\text{Set } ~g(T) = \sum_{k | T} f(k) \times \mu(\frac{T}{k})
$$
$$
\sum_{T = 1}^{min(n, m)}\lfloor \frac{n}{T} \rfloor \times \lfloor \frac{m}{T} \rfloor \times g(T)
$$

注意到要求$f(k) < a$,这里的$a$会对答案产生影响。于是可以按$a$排序然后离线处理,最开始处理好所有$f$的值,拿个堆维护下。

【BZOJ1861】【HH去散步】

因为不能走回头路,考虑把边看做点建立矩阵,把每个边看做两个点,一个正向一个反向然后快速幂。

【BZOJ3555】【CTSC2014】企鹅QQ

哈希,复杂度$O(m*nlogn)$卡过

【BZOJ3504】【CQOI2014】危桥

神奇网络流,正着连一遍反着连一遍,都能跑说明可以

【BZOJ1822】【JSOI2010】冷冻波

计算几何暴力判一判,然后二分网络流搞搞

【BZOJ2659】【Beijing wc2012】算不出的等式

找找规律,特判p=q的情况

【BZOJ3438】小M的作物

最小鸽,同文理分科

【BZOJ2610】【Poi2003】Monkeys

倒过来并查集

【BZOJ2423】【HAOI2010】最长公共子序列

DP,记得减掉重复的方案数,滚动数组

【BZOJ1758】【WC2010】重建计划

二分,求一个树中链的长度在$[L,R]$之间的最长链,点分治,同一个子树中同一深度只用选具体根具体最大的那个,这里可以启发式合并。这样可以把子树搞成一个链,然后就是两条链的合并。用单调队列求长度在$[L,R]$之间的最大连续和,前缀和一下,对于一个点$i$只需要维护$[i-R,i-L]$之间的最小值即可。注意,只需要点分治一次。

【CF990G】GCD Counting

注意到不同的$GCD$其实不多,所以点分治,暴力枚举$GCD$即可,复杂度大概是O$(\log n \lg^2$值域$)$的。

【BZOJ3530】【SDOI2014】数数

建立AC自动机,那么AC自动机中所有被标记状态的都是不能被访问的。设$dp[i][j][0/1/2]$表示字符串第$i$位,现在在自动机的第$j$个状态,前$i$位大于/等于/小于$n$的前$i$位的方案数,注意第一位特判一下$0$。

【BZOJ1880】【SDOI2009】Elaxia的路线

跑四遍最短路,算出每个点到给出的四个点的距离,然后枚举相邻的点对$[u,v]$,判断是否在公共的路径上。然后拓扑排序求一个最长路径即可,考虑到边的方向的问题(如样例),只需要把其中一个起点和终点交换一下计算然后取最大值即可。

【WGSZOJ0026】福斯特

二分+数据结构。我写了个离散化+树状数组,把$b$看成$b-a$,$c$看成$c-b$,然后搞一搞,我写的奇丑无比,调了好久。浪费了一上午,常数还是别人的五倍。

【BZOJ4088】【SDOI2015】立体图

一直不敢做的一题,看到cxy直接A了。虽然是模拟但是还是不会,就只好学习一波cxy的代码。写了一下午+一晚上,一天只写了两题真是菜啊qwq。

首先不考虑颜色的情况就只有一个坐标变换,关于颜色的问题,可以把每个块分为3个面,由四个部分组成,每个部分可以状压颜色。

注意到一束光的性质,可以把光看成很多束很粗的方格构成,表示为 $(i,j,k)$。对于垂直于最上层,$i=j=k$,而左边的$j+k$为定值。对于给出的光的中的一束经过的点满足 二/三 元组的差/和 为一定值。

于是我们可以枚举这一定值,确定一个光束,这一束光撞到一个块就会停止。

考虑到遮挡的问题,可以发现对于同一个位置的光,不同颜色的块最多$6$个(如图)。所以暴力枚举每一块,然后枚举每束光线,特判所有情况,观察是否能覆盖或者被遮挡。

【BZOJ4890】【THOI2017】城市

算法一:暴力枚举删除的边,求出左边的直径和右边的直径,然后求直径中点(半径),中点相连即是答案。复杂度$O(n^2)$,可以AC此题

算法二:把边拆点建立$LCT$动态处理直径,查询半径的时候在直径上二分,用splay维护距离,复杂度$O(nlog^2n)$。

算法三:在$splay$里面二分,复杂度$O(nlogn)$

算法四:注意到直径的两个端点是固定的,每次加入点的时候只需要考虑该树中最深的点即可,而中点一定在直径上且单调,于是$2-pointer$就可以维护了,复杂度$O(n)$,达到理论最低复杂度。

【BZOJ2564】集合的面积

显然新的图的凸包的点一定是由$A$凸包里的一个点+$B$凸包里面的一个点得到的。发现新凸包是$A,B$的凸包极角排序顺次链接的。貌似贪心地连也是可以的,不是很能理解贪心的正确性就背下来了QAQ

【BZOJ1597】【Usaco2008 Mar】土地购买

将近一年没写斜率优化,康复失败,sb题还能浪费一晚上。

【BZOJ3771】Triple

老年选手康复一波FFT…所以这个题貌似是个生成函数?我不会生成函数,但是也是可以做的?

首先可以列一个简单DP(背包),另$F$表示凑出$F$的方案数
$$
Ans(i+j+k) = \sum F(i) F(j) F(k)
$$
这东西明显可以FFT了。然后发现有重复情况没办法处理。

于是只能考虑容斥。设$F(i)G(i)H(i)$表示把$1/2/3$个东西捆绑在一起,体积为$i$的方案数。

选一个自然是$F(i)$,选两个的时候会多算一个$(x,x)$,所以是$F(i)^2-G[i]$,本质不同所以$ (F(i)^2-G[i]) / 2$,三个的时候多算本质不同的(3个)和(2个 + 1个),而$F(i) \times G(i)$多算了(x,y,y)和(y,x,x)和$(x,x,x)$,总之搞一搞得到$ (F(i)^3 – 3 * F(i) * G(i) + 2 * H(i) )/6 $,然后$FFT$的时候算算就好了。

【BZOJ3992】【SCOI2015】序列统计

继续康复NTT…觉得这题很神啊,通过数怎么怎么高QAQ,首先列DP式子
$$
f[i \times j ~ mod ~m] = \sum_{i,j}^{m – 1}f[i] \times f[j]
$$
$n$次循环,发现$n$是$1e9$,但是发现这个东西是$f(x)^n$,然后可以快速幂。结果打完以后发现不会处理乘法,发现题解里面说可以求出$S-i$的离散对数,根据性质有$ind(ab) \equiv ind(a)+ind(b)(mod~m) $。然后就变成加法的形式,搞个最简单的生成函数就做完了。

PS:(怎么算离散对数?)

首先算个原根,如果值域是$[1,n]$,离散对数的值域是$[0,n-1]$,我们对$n-1$分解质因数,然后暴力枚举一个原根$g$,如果$\forall g^k \ne 1 mod~m ~(g | (n – 1))$,那么这个数就是一个原根。

然后从$0$到$n-1$求出原根的某次方,这个某次方在模意义下的值对应的离散对数就是这个次数。

这个水题记录终于过半了…

【BZOJ3451】Normal

根据期望的线性,答案为每个点的贡献。也就是计算
$$
\sum_{j=0}^{n-1}\sum_{i=0}^{n – 1} P(i \in subtree(j))
$$
如果有一个点对$(j,i),i\in subtree(j)$相连的是长度为$Len$的边(其中都没有被删),选中$i$的概率为$\frac{1}{Len+1}$。所以我们计算出长度为$i$的链的对数即可,总答案就是
$$
\sum_{len=0}^{n-1} num[i] * \frac{1}{len+1}
$$
关于计算一棵树里面长度为$Len$的链的对数,可以考虑点分治。搞个紧张刺激的简单生成函数,令$F[i]$表示链长为$i$的方案数,那么$F[i+j]=\sum_{i=0}^{mxdeep}F[i]*F[j]$,然后就可以$FFT$了,总复杂度$O(nlog^2n)$

发现自己常数巨大无比,于是把$NTT$改成了$FFT$,竟然快了四倍多

【BZOJ5018】【SNOI2017】英雄联盟

由于$m$比较大,所以设$f[i][j]$表示前i个英雄花j元能得到的最大成乘积,分组背包直接转移即可。

【BZOJ3513】【MUTC2013】idiots

太菜了,sb题都想不出来QAQ。本来估计20分钟打完结果搞了一个多小时。设$f(i)$表示两条木棍组合为长度为$i$的方案数,$p(i)$表示长度大于等于$i$的木棍数,答案是$\sum_{i}^{mx} f(i) g(i) $,求$f$直接自己和自己卷一下,对于偶数容斥以后除个二就没了。输入巨大无比,尝试搞个读入优化结果越来越慢qwq

【BZOJ4361】isn

太神了不会做..设$f(x)$为长度为$i$的序列的方案,答案为
$$
\sum_{i=1}^{n}f(i)\times (n-i)!-[i\neq n] \times f(i+1) \times (n-i-1)! \times(i+1)
$$
容斥,以$i$结尾的,减去不合法的(在它之间就不减了的),也就是减去$f(i+1)$的收益,组成$f[i+1]$的每个点都可以作为一个转移点,所以要乘上$i+1$

【BZOJ4950】【WF2017】Mission Improbable

可以随意放!!显然每行每列都保留最大值,如果这位置有物品就可以取到1,否则也只能是0。如果行的最大值和列相等,就可以在交界处放最大值,也就是可以省一个,二分图匹配行列。

【BZOJ4956】【WF2017】Secret Chamber at Mount Rushmore

水题,乱搞

【BZOJ4952】【WF2017】Need for Speed

二分,上界写错挂了一次QAQ

【BZOJ4953】【WF2017】Posterize

看不懂题意,翻译有毒。$f[i][j]$表示第$i$个位置用了$j$个分离的最小答案,区间$DP$一下,

$f[i][j]= min_{k<i} f[k-1][j-1] + cost[k][i]$ 。

【BZOJ2456】mode

记录众数和次数,如果众数为当前的$x$,次数就加一,否则减一,小于0就改成这个。

【BZOJ4926】皮皮妖的递推

找规律!前m个是1,后面的$f[i]=f[i – 1] + f[i – m]$,构造出这样的数列以后,找到第一个小于等于$n$的序列,$n$减去这个数,答案加上这个数的前一个。

【BZOJ1061】【Noi2008】志愿者招募

学习了一波单纯形,如果这个志愿者可以工作,这个地方的系数为1,满足限制然后求最小值,求最小值的方法就是把$f[i][j]$变成$f[j][i]$,然后照样跑就行了。

【BZOJ4569】【Scoi2016】萌萌哒

类似$ST$表,建立$log$层,每一层建立一个并查集, 令$f[i][j]$表示从$i$开始长度为$2^j$的区间, 那么每一个限制都可以拆成两个区间分别merge,最后从上往下pushdown,最后的答案就是$9 \cdot 10^{cnt-1}$

【BZOJ3307】雨天的尾巴

对于每一个点建立线段树,差分以后,答案就是字数的线段树合并以后的和。

【BZOJ3653】谈笑风生

答案就是
$$
\sum_{dep[x]\in limit1, pos[x] \in limit2}{size[x]-1}
$$
所以直接用主席树维护$Size$和即可。

【BZOJ3653】OSU!
$$
(x+1)^3-x^3=3x^2+3x+1
$$

$$
(x+1)^2-x=2^x+1
$$

$$
f[x]=f[x-1]+(3 \cdot x[i-1]+3 \cdot x[i-1]+1) \cdot phb[i]
$$

【BZOJ1143】【CTSC2008】祭祀river

对于DAG定义反链:一些点的集合,链中任意两点x, y,一定满足x不能到达y,y也不能到达x

而上题显然就是求出最长反链,根据定理:最长反链 = 最小链覆盖(可重)

DAG的最小链覆盖=floyd传递闭包以后,总点数减去对应二分图的最大匹配。

不会输出方案QAQ。

【BZOJ1143】 水叮当的舞步

迭代加深,根据剩下的颜色和边界的颜色剪枝,估价,求联通块的时候因为联通块不会变小,所以可以带入上一层的联通块放入bfs队列进行优化。

(Ps: bool类型的函数不返回默认值不为0,但是我电脑开了O2以后默认返回0,结果写掉return false直接GG

【BZOJ2946】 公共串

同LCS2,于是又一次复习(预习)一下SAM

【BZOJ1899】【ZJOI2004】Lunch午餐

令$f[i][j][k]$表示前$i$个人,第一队等待了$j$分钟,第二队等待了$k$分钟,总时间的最小值,很好转移。注意到$k=\sum_{i}x[i]-j$,所以可以省去一维,同样第一维也可以省去。

【BZOJ4985】评分

二分答案,把序列转化为01序列,目的是让最后剩下一个1。然后DP一下,$dp[i]$表示让这个位置变为$1$需要多少个$1$,然后用队列模拟。

【BZOJ4472】salesman

树形DP,贪心。

【BZOJ1077】天平

差分约束,可以用Floyd

【BZOJ1027】合金

好题..首先第三个是没有用的,因为a+b+c=1,ab可以合成c就自然是对的。

设合成的为$(a \cdot x.x+ b \cdot y.x, a \cdot x.y + b \cdot y.y)$。因为$a+b=1$,所以抽象成两个点以后可以合成的金属就在两个,点所连的线段上。那么多个点可以合成的金属就在这个点集的凸包上。

现在给出点集A,B,求一个$A$的最小子集$C$,使得$C$的凸包包含$B$的所有点。方法是Floyd,具体实现是:对于$i->j$这个向量,如果所有的$B$都在这个线段上或者在他的左边(或者右边,但是方向要统一),就把$i-j$连边,然后Floyd求一个最小环即可。

【BZOJ1057】棋盘制作

要求是黑白相间,那么把行+列为奇数的反色,求最大0和最大1然后取max即可。同BZOJ3039,注意到有单调行,单调栈维护即可。算正方形可以DP,但是也可以算矩形的时候把长宽取min然后再取max。

【BZOJ2097】奶牛健美操

最大最小考虑二分,问题在于判定。设$f[x]$表示从这个点开始的到其子树中最长链的长度。合并子树的时候则把子树信息Sort一遍,如果$a+b+2>mid$,贪心地把最大子树切除。

50题终于写完了..累死了啊

Leave a Reply

Your email address will not be published. Required fields are marked *

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code class="" title="" data-url=""> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong> <pre class="" title="" data-url=""> <span class="" title="" data-url="">

*