首页 > 其他 > 详细

退役前的做题计划2.0

时间:2018-10-18 23:43:53      阅读:92      评论:0      收藏:0      [点我收藏+]

标签:最小割   插入   省选   http   直接   顺序   ali   质数   ...   

最近在刷省选题......大致上是按照省份刷的。
不过上面的题目顺序是按照写题的顺序排列的,所以可能会有点乱哈。

[BZOJ2823][AHOI2012]信号塔

最小圆覆盖,随机增量法,期望复杂度\(O(n)\)

[Luogu4899][IOI2018] werewolf 狼人

\(\mbox{Kruskal}\)重构树+二维数点。

[Luogu4900]食堂

\(\sum_{i=1}^n\sum_{j=1}^i\frac ij-\sum_{i=1}^n\sum_{j=1}^i\lfloor\frac ij\rfloor\)
前半部分随便弄弄就好了。
后半部分,\(\sum_{j=1}^i\lfloor\frac ij\rfloor\)实质上等于\(\sum_{j=1}^id(j)\)
所以前缀和一下就好了。

[Luogu4902]乘积

\(\frac{\prod_{i=1}^ni^{\sum_{j=1}^i\lfloor\frac ij\rfloor}}{\prod_{i=1}^n\prod_{j=1}^ij^{\lfloor\frac ij\rfloor}}\)
上半部分就是\(\sum_{i=1}^ni^{\sum_{j=1}^id(j)}\)
下半部分,\(\prod_{j=1}^ij^{\lfloor\frac ij\rfloor}\)实质上是\(i\)的各约数的乘积,也就是\(i^{\frac{d(i)}2}\)
所以前缀积一下就好了。

[BZOJ2178]圆的面积并

辛普森积分,虽然是假的。

[BZOJ4913][SDOI2017]遗忘的集合

多项式求\(\ln+\mbox{MTT}\)。谁说莫比乌斯反演的来着?

[BZOJ4911][SDOI2017]切树游戏

丢猫锟题解就跑

[LuoguT46780]ZJL的妹子序列

很显然是要求\(\prod_{i=1}^n\frac{1-x^i}{1-x}\)\(x^m\)次项系数。
一种做法是求\(\ln\)之后大力开式子,然后可以\(O(n\ln n)\)调和级数求得一多项式然后再\(\exp\)回去。
还有一种做法是拆成前后两部分,\((\frac1{1-x})^n=(\sum_{i=0}^{\infty}x^i)^n\),相当于\(n\)个盒子每个盒子可以无限放球的生成函数,所以\(x^m\)次项系数是\(\binom{n+m-1}{m}\)\(\prod_{i=1}^n(1-x^i)\)可以看做一个带符号的\(01\)背包计数,其中第\(i\)个物品的重量恰好为\(i\)。考虑到至多选\(O(\sqrt m)\)个物品,所以可以做\(O(n\sqrt m)\)\(dp\)

[Luogu4921]情侣?给我烧了!

\(f_{i,j}\)表示前\(i\)对情侣已经入座,有\(j\)对情侣是挨着的的方案数。考虑插入第\(i+1\)对情侣。
\(f_{i,j}\)可以转移到\(f_{i+1,j-2},f_{i+1,j-1},f_{i+1,j},f_{i+1,j+1}\),分别表示第\(i+1\)对情侣分别拆散了两对情侣、只拆散了一对情侣、没有拆散情侣以及他俩坐在一起。注意两人分开座时可能会导致某对情侣复合,转移的时候要额外算一下贡献。

[BZOJ3307]雨天的尾巴

线段树合并模板题。树上差分的时候,对\(lca\)\(fa_{lca}\)打标记而不是做线段树单点插入,即可把空间减小到一半。

[BZOJ1227][SDOI2009]虔诚的墓主人

坐标离散,横坐标从左往右扫,维护每个纵坐标已存在的点数,组合数算一下,再用树状数组区间求和即可。

[BZOJ4870][SHOI2017]组合数问题

矩阵快速幂模板题。

[BZOJ3434][WC2014]时空穿梭

枚举\(n\)维中每一维坐标的极差\(\Delta x_i\),有
\[\sum_{\Delta x_1=1}^{m_1}\sum_{\Delta x_2=1}^{m_2}...\sum_{\Delta x_n=1}^{m_n}\binom{\gcd(\Delta x_1,\Delta x_2...\Delta x_n)-1}{c-2}\prod_{i=1}^n(m_i-\Delta x_i)\]
枚举\(\gcd(\Delta x_1,\Delta x_2...\Delta x_n)\),有
\[\sum_{d=1}^{\min(m)}\binom{d-1}{c-2}\sum_{\Delta x_1=1}^{m_1/d}\sum_{\Delta x_2=1}^{m_2/d}...\sum_{\Delta x_n=1}^{m_n/d}[\gcd(\Delta x_1,\Delta x_2...\Delta x_n)=1]\prod_{i=1}^n(m_i-\Delta x_id)\]
反个演
\[\sum_{d=1}^{\min(m)}\binom{d-1}{c-2}\sum_{t=1}^{\min(m)/d}\mu(t)\sum_{\Delta x_1=1}^{m_1/dt}\sum_{\Delta x_2=1}^{m_2/dt}...\sum_{\Delta x_n=1}^{m_n/dt}\prod_{i=1}^n(m_i-\Delta x_idt)\]
换个写法
\[\sum_{d=1}^{\min(m)}\binom{d-1}{c-2}\sum_{t=1}^{\min(m)/d}\mu(t)\prod_{i=1}^n\sum_{\Delta x_i=1}^{m_i/dt}(m_i-\Delta x_idt)\]
\(T=dt\),改变枚举顺序
\[\sum_{T=1}^{\min(m)}(\prod_{i=1}^n\sum_{\Delta x_i=1}^{m_i/T}(m_i-\Delta x_iT))\sum_{d|T}\binom{d-1}{c-2}\mu(\frac Td)\]
\(F(T)=\prod_{i=1}^n\sum_{\Delta x_i=1}^{m_i/T}(m_i-\Delta x_iT)\)\(G(T)=\sum_{d|T}\binom{d-1}{c-2}\mu(\frac Td)\)
首先\(G(T)\)在给定\(c\)的前提下可以\(O(n\ln n)\)预处理出来。
观察\(F(T)\),将其划开
\[F(T)=\prod_{i=1}^nm_i\lfloor\frac{m_i}T\rfloor-\frac{T\lfloor\frac{m_i}T\rfloor(\lfloor\frac{m_i}T\rfloor+1)}2\]
如果\(\lfloor\frac{m_i}T\rfloor\)确定的话,那么\(F(T)\)就是一个关于\(T\)\(n+1\)次多项式。所以可以预处理\(G(T)T^i\)的前缀和,然后对于每个\(\lfloor\frac{m_i}T\rfloor\)相同的连续段暴力求\(F(T)\)
总体复杂度\(O(n\ln nc+nmc+Tn^3\sqrt m)\)有点爆炸啊。

[BZOJ3629][JLOI2014]聪明的燕姿

直接爆搜质因子,特判最后一个大于根号的质因子即可。

[BZOJ5157][TJOI2014]上升子序列

对于前面的相同元素,直接强制从最后一个这种元素转移即可。

[BZOJ3628][JLOI2014]天天酷跑

先枚举跳跃高度和连跳次数,然后直接记搜转移即可。

[BZOJ3505][CQOI2014]数三角形

正难则反,求三点共线的方案数。枚举相隔较远的两点的横纵坐标之差,然后第三个点就有\(\gcd-1\)种选法。注意特殊处理横纵坐标差为\(0\)

[BZOJ4001][TJOI2015]概率论

\(f_n\)表示\(n\)点二叉树的数量,\(g_n\)表示\(f_n\)棵二叉树的总叶子节点个数。
最近做初赛题发现\(f_n\)就是卡特兰数。
\(g_n\)是啥?考虑\(f_n\)中的一棵\(n\)点二叉树,设其有\(m\)个叶子,那么删掉这\(m\)个叶子后就能得到\(m\)棵不同的\(n-1\)点二叉树;而每棵\(n-1\)点二叉树有\(n\)个位置可以挂叶子,也就是说在上述过程中被计算了\(n\)次。所以\(g_n=nf_{n-1}\)
\(ans=\frac{g_n}{f_n}=\frac{nf_{n-1}}{f_n}=\frac{n(n+1)}{4n-2}\)

[BZOJ3999][TJOI2015]旅游

树剖+线段树两只\(\log\),用\(\mbox{LCT}\)写可以做到一个\(\log\)
每个点维护区间最大值,最小值,后面最大值减前面最小值的最大值,前面最大值减后面最小值的最大值。

[BZOJ4000][TJOI2015]棋盘

其实棋子是放在中间那一行的。
所以直接按行\(dp\)就行了。处理一下相邻两行的两个状态是否可以转移,因为转移都是一样的所以可以矩乘优化,复杂度\(O(2^{3m}\log n)\)

[BZOJ5156][TJOI2014]拼图

据说这玩意儿叫精确覆盖?直接状压完事了。

[BZOJ5158][TJOI2014]Alice and Bob

因为保证\(a\)可以由一个排列得到,所以\(x\)就一定会是排列,否则不更优。贪心,尽量把数值大的放在前面,把数值小的放在后面。对于\(a_i\)值相差为\(1\)的点对建立拓扑关系,然后依次填数,最后统计一遍答案就行了。

[BZOJ5155][TJOI2014]电源插排

正解是动态开点线段树,但是感觉比较难写,就换了一种写法。
开个\(\mbox{std::set}\)维护未放置的区间,平衡树维护已放置的位置集合,支持插入删除,找前驱后继,统计区间点数即可。(如果迭代器支持相减的话就可以直接开两个\(\mbox{std::set}\)做了)

[BZOJ3173][TJOI2013]最长上升子序列

其实只要能够得到最终生成的序列就很好办了。考虑从大到小确定每个数在最终序列里的位置,相当于查找当前的第\(k\)大元素。\(BIT\)可做。

[BZOJ3174][TJOI2013]拯救小矮人

对于所有要出去的小矮人,一定是按照\(a+b\)权值从小到大出去最优。
排序,然后设\(f_i\)表示出去了\(i\)个小矮人时人梯的最高高度。如果\(f_j+b_i\ge h\)就可以用\(f_j-a_i\)更新\(f_{j+1}\)

[BZOJ3175][TJOI2013]攻击装置

黑白染色然后跑最小割。

[BZOJ3167][HEOI2013]Sao

一条链是考过的原题。
如果是树的话同样可以设\(f_{u,i}\)表示\(u\)点子树内,\(u\)点排在第\(i\)个的方案数,每次转移就是合并两个序列,枚举\(f_{u,i}\)以及在\(u\)的前面放\(j\)个元素,根据大小限制决定是从\(f_{v,1...j}\)转移过来还是从\(f_{v,j+1...sz_v}\)转移过来,同样可以用前缀和优化转移,同时要乘上前后隔板插入的方案数\(\binom{i+j-1}{j}\times\binom{sz_u-i+sz_v-j}{sz_v-j}\),复杂度\(O(n^2)\)

[BZOJ4824][CQOI2017]老C的键盘

上一题弱化版。双倍经验。

[BZOJ5019][SNOI2017]遗失的答案

论一个辣鸡出题人是如何被吊打的

[BZOJ3163][HEOI2013]Eden的新背包问题

预处理多重背包的前后缀\(dp\),每组询问\(O(m)\)回答。

[BZOJ3164][HEOI2013]Eden的博弈问题

\(f_u\)表示\(u\)点子树内最少要选多少个叶子才能必胜,如果\(u\)点是自己控制的那么\(f_u=\min\{f_v\}\),否则\(f_u=\sum f_v\)。找出所有可能是最优转移点的叶子即可。

[BZOJ2742][HEOI2012]Akai的数学作业

找到最高和最低的非零系数\(a_m,a_n\),因为答案是有理数所以一定是\(\frac pq\)的形式,更具体的\(p\)一定是\(a_m\)的约数\(q\)一定是\(a_n\)的约数。所以暴力枚举一下然后\(\mbox{check}\)\(\mbox{check}\)的话,\(x\)是浮点数不好做,可以选几个大质数做模意义下的运算判断结果是不是\(0\)即可。

退役前的做题计划2.0

标签:最小割   插入   省选   http   直接   顺序   ali   质数   ...   

原文:https://www.cnblogs.com/zhoushuyu/p/9813323.html

(0)
(0)
   
举报
评论 一句话评论(0
0条  
登录后才能评论!
© 2014 bubuko.com 版权所有 鲁ICP备09046678号-4
打开技术之扣,分享程序人生!
             

鲁公网安备 37021202000002号