kzoacn's Blog

刷题

50

【6.16】完结撒花

【BZOJ3283】见课件

【BZOJ2219】见上面的课件……里面有一点问题,“新方程”的解和原方程的解不是一一对应的，看这里

【BZOJ4105】这些模数的特点是循环节及其lcm都非常小……在线段树中的每个结点记录循环节中的所有元素以及当前元素位置就可以了

【BZOJ4103】这个……可持久化Trie暴力……

【BZOJ4104】BWT 强烈建议自行yy代码……

【BZOJ4106】实在是太水了……纯粹是练习英语……

【BZOJ4066&&BZOJ2683】恭喜kdtree加入乱搞全明星……改了改重构参数总算进了40s……

【BZOJ2850】kdtree乱搞

【BZOJ3489】以为自己被卡常数了，结果是自己估价写错了……

【BZOJ2480】exBSGS裸题

【BZOJ1587】\(f[i][j]\)表示前j个合并为i堆的代价,\(f[i][j]=min~f[i-1][l-1]+cost(l,j)\),cost(i,j)表示将[i,j]合并到i的代价

【BZOJ4127】校内互测开脑洞原创出了两道原题，我的做法:首先通过整体二分求出每个点由负数变为非负数的时刻,考虑修改对答案的影响,若前后均为负数则答案减少,若前后均非负则答案增加,对于一次修改操作先进行一次,然后在将在此时刻由负数变为非负数的点重构一遍。

然而我的学妹现场用更简单的方法水过了= =

直接链剖线段树,线段树每个节点内记录区域内负数的min和max,若某次修改会导致负数变为非负数,递归子树,否则打标记,考虑到每个数只会变化一次,这样做显然没有问题= =

【BZOJ4128】求个逆然后BSGS= =,求逆的方法是,在A后连接一个单位矩阵E,对AE进行高斯消元消成EB的形式,B即为A^{-1}

然而GTY大爷用2396的方法水过了……就是枚举答案,每次乘一个A,用2396的方法判断相等

【BZOJ4010】倒过来字典序最大的……

【BZOJ4001】大力打表出奇迹！

【BZOJ1278】将向量极角排序后很显然每次会选择一个"半圆"

【BZOJ3091】裸LCT,维护信息稍烦

【BZOJ4129】堆乱搞对着数据改程序即可

【BZOJ1139】状压最短路,这么水的题居然一年没有人做了……

【BZOJ1076】\(f[i][S]\)表示第i次当前状态为S,向后所能获得的最大期望得分,转移显然

【BZOJ3450】OOXX的序列 = =,题解很多,我不多说

【BZOJ3566】为什么不看题解我就不会做题T_T

【BZOJ3323】大裸题……mulx操作可以视为把r+1的值加在r上,将r+1设为0,把r+1移动到l前

【BZOJ1861】裸题……尝试写了一下带父亲的fhqTreap

【BZOJ1187】第一次写插头DP

【BZOJ1398】最小表示法裸题

【BZOJ1210】果然东西会了就觉得简单……插头dp水题,注意n=1 or m=1的时候答案是1……

【BZOJ3647】2795的双倍经验,唯一不同的地方在于它卡自然溢出……

【BZOJ3867】每个结点需要记录区间max,区间是否相同和懒标记,gcd的修改暴力修到全部都一样的区间\

【BZOJ2916】经典题,同色三角形=C(n,3)-异色三角形,异色三角形=\(\frac{\sum_i r_i \times b_i}{2}\),r,b分别表示每个点红色和黑色出边的个数

【BZOJ2331】插头dp果然没学到家= =,仰慕了题解

【BZOJ2929】做远古水题总能深刻地感受到OI题目难度增长的速度……

【BZOJ3876】有源汇下界费用流,暴力spfaT了……popoqqq大爷凭啥你的就不T……

【BZOJ2055】上下界费用流……

【BZOJ2502】怎么都说是下界最小流……最大费用流就可以了……对于原图(u,v),连u->v cap=1 cost=1,cap=inf cost=0对于每一个点S'->i->T cap=inf cost=0,枚举S->S'的cap,增广,cost=\sum m的时候即为答案……

【BZOJ3698】如果第n行和第n列固定就是一个裸的最大流,不固定就变成了上下界= =,于是就可以用奇怪的费用流做……按行列建边s连行t连列,连cap=inf cost=0,如果某行列可以上取整,增加一条cap=1 cost=1,对于点(i,j),若能上取整,i->j+n连cap=1 cost=1的边,接着跑最小费用流，这样就可以保证某行列只有在原有已满的情况下选择上取整

【BZOJ3270】直接列方程消元,20^6居然300ms+就过了……

【BZOJ3931】考你开long long……

【BZOJ4069】当时连这种dp都不会我可以去死了

【BZOJ2134】水……推一推就知道是\(\sum_{i=1}^n \frac{min(a_i,a_{i\%n+1})}{a_ia_{i\%n+1}}\)

【BZOJ3029】f[i][j][k]表示前i场比赛获得j次胜利背包剩余k的概率,注意到k超过n是没有意义的于是就是\(O(n^3)\)

【BZOJ2600】枚举右端点,左端点有单调性,扫一遍就行了

【BZOJ2995】2480双倍经验……

【BZOJ3438】好裸的最小割……

【BZOJ2660】\(f[i][0/1]\)表示拆分后原来为1的第i位是否为1,手算一下若两位之间0的个数为x那么有x/2种方案,dp即可

【BZOJ2939】裸网络流……刷水真不好意思……

【BZOJ2408】BWT 见4104

【BZOJ2891】我是听说直接随机能过才去写的……结果刷屏了……不得已要了数据

【BZOJ1430】完全图生成树个数为\(n^{n-2}\),再乘上\((n-1)!\)