51nod 部分题解
HJWJBSR
posted @ 2016年3月18日 14:01
in 题解
, 2034 阅读
最近十分颓废。。然后准备开TC。。
TC英文狗哔题面+Arena下下来死都打不开+网页版的Arena十分艹蛋于是转而开坑51nod
1676:随便hash。。（正解是迭代+hash。。get新姿势 （Solved
1299:感觉像是按照黑点的位置把树拆成若干森林然后变成了全是叶子的问题，然后直接树形DP？ （然而爆栈还wa了也是懒得改了。弃坑。
1450:感觉可以直接DP，但是具体细节看ZTY课件。。
1446:感觉像是meet in middle n*2^(n/2)之后感觉dp一下大小为n的子树颜色情况的可能方案数就好？
1620:感觉按照纵坐标加边，然后两种限制分别是当前状态有没有独立出去的连通块，当前的n个点联通的话需要底下的点至少纵坐标多小，后面那个涉及n-1次合并，但是由于是区间问题所以直接在之前预处理出相邻两个点之间的LCA，然后最后合并就是用个set搞一搞。
1389:直接倍增。。细节比较恶心。。 （Solved
1367:直接DP。。 （Solved
1303:悬线法+乱搞前缀和+容斥。。细节要想清楚。。非常恶心。。 （Solved
1576:就是到重心的距离和*2。。脑补一下就出来了TAT （当然卡时所以无爱了 （Solved
1244:杜教筛TAT，卡空间。。而且不预处理多一点时间是会爆炸的。。（Solved
1239:貌似也是杜教筛裸题TAT。。加了个挂链蛤shit（Solved
1203:莫队。。n*sqrt(n)*质因数个数 （Solved
1370:直接设s[i][j][k]为处理到比区间最大值还要大的所有数之后这个区间存活确认时区间一共用过k次的可行序列个数。然后乱推推？
1598:直接线段树维护斜率。很久以前做的所以不想调了=.=（Solved
1626:像是直接状压（弃坑
1348:直接FFT+long double貌似没有精度问题。。非常诡异的是C++没有精度问题但是VC有。。复杂度n log^2 n （Solved
1411:插头DP问题。。（弃坑
1362:反正爆算算就出来了。。 （弃疗
1447:不会。。
1380:显然一个收钱序列是合法的当且仅当这个序列中任意两个人不相邻。然后我觉得应该是维护一下前缀和然后从大到小插入数，如果有冲突就询问当前所在的黑白相间的区间里面的翻转之后所获得的收益最大值。然后搞到N/3就没了吧。。正解也是用优先队列维护每个位置的值，每次选出最大的然后把两边的删掉，然后再把这个值变成：两边的和减去中间的值加入优先队列。（Solved
1386:这种拿质数的题已经见的多了。。反正都是小于根号n的状压大于根号n的一层一层搞 （Solved
1369:主要是之前被样例4卡住了TAT。实际上疑似水题。。只要按照折线的每个点把对应的角度限制算出来然后合并就可以了TAT
1323:之前作为NOIP模拟题考过。。直接Gauss就好。。（Solved
1297:替罪羊套动态点分治裸题。。LCT当然也资瓷，经典问题。。还要注意的地方就是插在哪里，一个性质就是当前二叉树中值相邻的两个必定有祖先关系。所以就只要用个set维护一下看左右哪个在下面就哪边有空位。（Solved
1312:线性基水题？不会证所以还是看了题解TAT。反正就是消出线性基然后最大的出现n次其余出现n-1次。这个可以构造。（Solved
1304:口胡失败。。这个真不是SA裸题。。
1743:边排序，然后加边的时候如果存在环就缩掉。询问可以二分+可持久化并查集【手动斜眼】，但是同样也可以直接建树最后询问就求LCA。缩环找环部分就不会了TAT。。后来翻题解突然发现要先建出最小生成树，忽略了这个性质TAT。。然后他说要并查集来搞合并，感觉真是很有道理，本来还准备写个LCT维护每一块的情况。 TAT。树剖爆栈了也是2333。改了之后常数又大了。。51nod不给DFS做人的机会真是很不良心。。（弃疗
1302:首先如果只有一组肯定是全都竖着放更优。然后感觉枚举宽度大的那一组的宽度分成两组再把多出来的放过去。这个时候面积只和高度有关了。所以直接分两种情况讨论一下就好了。（Solved
1306:感觉大概像是第i个棋子的跳跃范围为n^(S-i/S)。细节懒得想了TAT。（弃坑
1440:为毛感觉就是建出SAMfail树然后套个主席树。。不知道放640分什么心态。。
1332:花式乱搞吧这个。。明显从根要到一个点就应该不断把这棵子树里面的点移到外面去。所以si代表到达i的时候i的子树里面已经少了多少节点，而且在进去之前这里面的点都是没有区别的所以这si个点是还可以贪心的。
1325:为毛没想到最大权闭合子图。。智商下线。。反正枚举根然后限制条件都出来了。。 （Solved
1327:感觉像是设dpi,j,k代表第i列左边来的已经放了j个，右边来的已经放了k个。转移右边的比较好转移。直接乘就好。左边来的直接乘以组合数。因为左边来的列在之前是没有任何区别的，所以方案也是直接乘以一个分式就好。
1195:结论题，详见ACdreamer的blog（弃坑
1160:NOIP模拟题出现过。。不过貌似是n^2的吧。。然后这东西相当于每次将一个01序列通过一个固定的置换变成另外一个序列由i列到i+1列。。把置换画出来走n步就是第一行的n个数。不知道为什么这是640分题。。（Solved
1339:感觉按照r排序？还没试过。。然后试了之后是对的。。 （Solved
1321:把味道当成边形状当成点，然后就变成一堆的环要求最小点权覆盖集（因为同一形状的要不取要不不取只有两种状态）然后就可以直接dp了。。不知道为什么会wa。。
1634:死也推不出。。然后翻开题解发现有结论是联通二分图计数，于是直接n^4DP即可。。（Solved
1470:很明显如果出现了环就只要把环上所有边按照同一方向排就好了。。同理边双也是一样。。所以边双之后直接建树然后从下往上上传一下标记就好了的样子。。因为还涉及并查集和求LCA。。复杂度应该还是一个log的。。当然用tarjan就是α。垃圾网站卡我树剖毁我青春，明明树剖又好写常数又小，卡栈实在sxbk。。一开始还脑残写个Tarjan的强连通分量。。写完之后才发现不对劲。。然后不会边双这题就变成了double 倍增 double 标记。蜜汁细节挂的真爽。。 （Solved
[UPD 4.21] 因为感觉不是很想继续填这个坑了所以就放出来好了。
2021年10月02日 17:54
How much cash you have the ability to make is usually at your decision on the figures on you must grow your internet business and the quantity of time you desire to put through, just like each and every business. If you want to make a little bit of extra privately just choose one or two clients for the purpose of pocket profit or should you wish to make very much then you really have to work it again and put all his time in, originally.