zhangxixi的博客

本文搬运自本人初中博客园博客，若图片加载不出来，可到原文查看：https://www.cnblogs.com/zhangtingxi/p/15621588.html 题目链接 首先如果一个点满足答案，则这个点一定是割点。 然后我们可以从 aaa 点开始搜，对于每一个点，如果 bbb 点在它的儿子内，说明这个点分离了 aaa 和 bbb。 如何判断 bbb 是否在它的儿子内，只需要在搜索这个儿子前后判断一下即可。 Code 1234567891011121314151617181920212223242526272829303132333435363738394041424344454...

本文搬运自本人初中博客园博客，若图片加载不出来，可到原文查看：https://www.cnblogs.com/zhangtingxi/p/15620690.html 题目链接 题目就是给出一幅图，求其割点个数。 由于 n⩽100n\leqslant 100n⩽100，所以可以暴力删点。 当然也可以跑割点。 (感谢crx老师教我割点模板) 暴力Code 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636...

本文搬运自本人初中博客园博客，若图片加载不出来，可到原文查看：https://www.cnblogs.com/zhangtingxi/p/15615609.html 题目链接 首先，环内的节点必然可以至少存在两条路径到达，所以我们不用考虑环内的节点，可以先对无向图缩点。 剩下的节点必然构成一棵树，我们只需要将叶子节点两两配对。因为这样其上面的所有父亲节点都可以通过它下面的叶子节点形成环。 Code 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515...

本文搬运自本人初中博客园博客，若图片加载不出来，可到原文查看：https://www.cnblogs.com/zhangtingxi/p/15612746.html 题目链接 看题，发现是一个缩点。 缩完点后，对于每一个强连通分量，取其汽油费的最小值，最小值的和就是答案。 方案就是每个强连通分量最小值个数相乘。 Code 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071...

本文搬运自本人初中博客园博客，若图片加载不出来，可到原文查看：https://www.cnblogs.com/zhangtingxi/p/15600574.html 题目链接 典型的树形dp。 设 dp(x,i)dp(x, i)dp(x,i) 表示 xxx 的子树内逗留 iii 秒的作品最大值。 dp(x,i)=max⁡y∈xmax⁡i=0smax⁡j=2×zidp(y,j−2×z)−dp(x,j−i)dp(x, i)=\max_{y\in x}\max_{i=0}^s\max_{j=2\times z}^i dp(y,j-2\times z)-dp(x,j-i) dp(x,i)=y...

本文搬运自本人初中博客园博客，若图片加载不出来，可到原文查看：https://www.cnblogs.com/zhangtingxi/p/15600134.html 我太弱了，改不出T4，就把T1-3题解码了。 T1 报数 题目链接 想着T2，T3的题解都写了，就补一下T1的吧。 典型的筛法。 假如一个数含有7，则把它的倍数全筛走。 这里可以加一个小优化，假如这个数已经被筛过，就不需要再筛它的倍数了。 最后再倒着预处理每个数的下一个没被筛的是什么。 如果不预处理，不断6999999就可以卡死你。 Code 123456789101112131415161718192021222324...

本文搬运自本人初中博客园博客，若图片加载不出来，可到原文查看：https://www.cnblogs.com/zhangtingxi/p/15600119.html 题目链接 想着T2，T3的题解都写了，就补一下T1的吧。 典型的筛法。 假如一个数含有7，则把它的倍数全筛走。 这里可以加一个小优化，假如这个数已经被筛过，就不需要再筛它的倍数了。 最后再倒着预处理每个数的下一个没被筛的是什么。 如果不预处理，不断6999999就可以卡死你。 Code 12345678910111213141516171819202122232425262728293031323334353637383...

本文搬运自本人初中博客园博客，若图片加载不出来，可到原文查看：https://www.cnblogs.com/zhangtingxi/p/15598937.html 题目链接 Part A 式子化简 首先题目要求的式子就是 n2n^2n2 乘上 1n∑i=1n(ai−aˉ)2\frac{1}{n}\sum_{i=1}^n(a_i-\bar a)^2n1​∑i=1n​(ai​−aˉ)2，其中 aˉ=1n∑i=1nai\bar a=\frac{1}{n}\sum_{i=1}^n a_iaˉ=n1​∑i=1n​ai​。 我们把这三合在一起也就是： n2×1n∑i=1n(ai−1n∑j=1n...

本文搬运自本人初中博客园博客，若图片加载不出来，可到原文查看：https://www.cnblogs.com/zhangtingxi/p/15590387.html 题目链接 首先dp得从低位向高位枚举，因为高位无论如果使用 2ai2^{a_i}2ai​ 都对低位二进制1的个数无影响，满足dp的无后效性。 设 dp(k,i,x,y)dp(k, i, x, y)dp(k,i,x,y) 为 SSS 从低的高二进制的前 kkk 位中，用了数列 aaa 的前 iii 项，且此时 SSS 中共有 xxx 个二进制位为1，第 i+1i+1i+1 位进了 yyy 过去。 则： dp(k,i,x,y...

本文搬运自本人初中博客园博客，若图片加载不出来，可到原文查看：https://www.cnblogs.com/zhangtingxi/p/15585466.html 题目链接 首先第一问很好求，就是求最长下降子序列，n⩽5000n\leqslant 5000n⩽5000，O(n2)O(n^2)O(n2) 暴力转移就行。 而这道题的难点就在于去重。 对于 iii 和 jjj（i>ji>ji>j），如果 ai=aja_i=a_jai​=aj​ 且 dpi=dpjdp_i=dp_jdpi​=dpj​，说明他们是相同的，iii 的方案要清0，但是这里不能break！ 因为对...