Cptraser/ 十月 31, 2018/ 2018.11/ 0 comments

看你们都写这种东西,看起来挺好用的…
BZOJ3944Sum,杜教筛裸题,转化成\phi(n)=\frac{n * (n+1)}{2} * \sum_{i=2}^{n}\phi(\lfloor\frac{n}{i}\rfloor)\S(n)=1 - \sum_{i=2}^{n}\S(\lfloor\frac{n}{i}\rfloor)然后记忆化搜索即可(然而被卡了一早上常)
BZOJ3884上帝与集合的正确用法,扩展欧拉定理,递归求解即可(a^n可以看做a^{a^n},边界为p==1)。

    \[a^n\equiv a^{n \mod \varphi(p) +\varphi(p)}(mod p) (n\geq\varphi(p))\]

啊啊最近数论真的是搞得我头有点痛,还是先放一边准备一下NOIp的题吧。
Luogu3128MaxFlow,树剖裸题,复习一下。
BZOJ3631松鼠的新家,话说我上题怎么过的,线段树写的漏洞百出。
luogu意外的好用呢…
BZOJ1349Squintlong long开根…
CF1051D Bicolorings,给定一个2 * n的方块,求联通块为k的方案数,联通块DP,设f(i,j,0/1,0/1)即可。(额额这题还可以滚存)
CF1051F The Shortest Statement,给定一个n个点m条边的无向连通图,m-n\leq 20,有Q次询问,每次求(u,v)之间的最短路。先预处理最小生成树上的边,剩下的边两端点跑最短路,询问时枚举多余边上的点取min即可。(貌似不用最小生成树)
BZOJ4196软件包管理器,支持区间覆盖和子树查询的树剖。
HDU5634 Rikka with Phi,线段树,考虑怎样区间开\varphi,由于一个数最多开log_2 n次就会变成1,所以记一个当前区间是否全部相等,全部相等就区间整体开\varphi。(乘除太多大常数)。
POJ1275出纳员问题,差分约束经典题,注意细节。Solution
BZOJ1855股票交易,用单调队列维护F(i-w-1,k)+k * AP_i(BP_i)即可。Solution
BZOJ1151动物园,状压DP,记F(i,j)G(i,j)表示答案和当前点的贡献。考虑到环边界问题,枚举前四个点的状态。

    \[F(i,j)=max(F(i - 1,(j\&15)<<1),F(i - 1,(j\&15)<<1|1))+G(i,j);\]

NOIP模拟赛二十六,真的是智障T3 j打成i了。T1单调队列裸题,但我写了尺取法+RMQT2数位DP容斥乱搞找规律;T3 DP,用Map削减状态。
2018.11.03AM模拟赛,T1二分图裸题,T2区间DP裸题,T3大力分块。
2018.11.03PM模拟赛,T1最坑的是可以斜着放,导致大批大批70分,T2倒过来N^2Floyd即可,但我写了个询问分块重构Floyd,类似Gty的妹子树的做法,T3乱搞。
2018.11.04模拟赛,T1莫名CEfreopen真是神仙,T2求后缀K大,我写了个二分加树状数组,其实可以用堆,T3子集DP,容斥。
BZOJ1042硬币购物,完全背包预处理方案数然后容斥。
Luogu2679子串NOIp题,DP,滚存即可。

    \[F(i,j,k,0)=F(i - 1,j,k,0)+F(i - 1,j,k,1);\]

    \[F(i,j,k,1)=F(i - 1,j - 1,k,1)+F(i - 1,j - 1,k - 1,0)+F(i - 1,j - 1,k - 1,1);(A[i]==B[j])\]

    \[F(i,j,k,1)=0;(A[i]!=B[j])\]

Luogu2831愤怒的小鸟,状压DP,预处理暴力DP2^n * n^2 * T 无压力水过
BZOJ1015星球大战,离线,倒着并查集。
Luogu1850换教室,期望好题,Floyd预处理+期望DP
BZOJ1342静音问题,第一眼尺取法,但是好像需要Mutiset维护,其实只要维护两个单调队列即可。
CF906C Party,状压好题,同时学了一波状压BFS姿势。
CC COOK92 Maximum Tree Path,直接用直径做A *的估价,直接就*过去了,正解是枚举gcd,然后按min从大到小建树维护直径。

    \[treediameter1(x,y)+treediameter2(a,b)\Rightarrow treediameter(a|x,b|y)\]

即两树合并,新树直径在原树直径的端点中。
BZOJ4001概率论,证明不会,貌似是生成函数,反正答案是:

    \[\frac{\frac{n * (n+1)}{2}}{2n - 1}\]

CF776B Sherlock and his girlfriend,额,裸的欧拉筛。
BZOJ3505数三角形,补集转化,求出总方案数减去不合法的(在一条线上的,直线、斜线),考虑枚举斜线的点求gcd即可。
BZOJ4806炮DP,设F(i,j,k)表示前i行,有j个一个炮一列的,k个两个炮一列的方案数。
LJNOIP模拟赛一,T1CF906C PartyT2CC COOK92 Maximum Tree PathT3先建一棵树,然后对于树边如果覆盖其的非树边集合相同,则切断其中两条有方案,Hash即可。
LJNOIP模拟赛二,T1贪心,然后我用堆套堆加按秩合并用两个log * 过去了。T2DP,把DP状态打出来发现对称然后就过了(可以压缩状态)。T3补集转化,求出有相同颜色的路径数即可,对于原树建DFS序,然后将其转化为二维平面上的矩形,用扫描线即可。(建矩形要分类讨论)。
LOJ136最小瓶颈路,直接Kruskal建树,LCA即可。
LOJ137最小瓶颈路加强版,询问增加到了10^7,预处理欧拉序,然后STO(1)查询。这题的骚操作是按秩合并可以维护欧拉序。(树剖常数小也可以过)。
BZOJ1477青蛙的约会,exgcd。Solution
CF787A TheMonster,exgcd。Solution
CF7C Line,exgcd。Solution
可能要退役了呢……
BZOJ4552排序,思路很好的二分,二分最终答案,对原序列改为0/1序列,表示大于等于或小于,每次排序直接线段树处理即可。
TJOI2007路标设置,二分直接贪心Check即可。

Share this Post

Leave a Comment

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

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