zhangxixi的博客

本文搬运自本人初中博客园博客，若图片加载不出来，可到原文查看：https://www.cnblogs.com/zhangtingxi/p/15640116.html 题目链接 我要是在noip前做这道题就好了。 这道题的本质就是noip2021方差中的一个性质，对于每个数进行修改，就是把它左右的差进行交换。 注意的是首项一定要一样。 Code 123456789101112131415161718192021222324252627282930313233343536373839// Problem: CF1110E Magic Stones// Contest: Luogu// U...

本文搬运自本人初中博客园博客，若图片加载不出来，可到原文查看：https://www.cnblogs.com/zhangtingxi/p/15634024.html 题目链接 暴力是肯定可以的。所以这里讲 O(1)O(1)O(1)。 首先不考虑重复，则有 (∣s∣+1)×26(|s|+1)\times 26(∣s∣+1)×26 种可行方案。 然后重复的就是在一个字母的左右放和这个字母相同的字母，有 ∣s∣|s|∣s∣ 种可能。 所以总共有 (∣s∣+1)×26−∣s∣(|s|+1)\times 26-|s|(∣s∣+1)×26−∣s∣ 种可能。 Code 12345678910111...

本文搬运自本人初中博客园博客，若图片加载不出来，可到原文查看：https://www.cnblogs.com/zhangtingxi/p/15633892.html 题目链接 由于 n⩽15n\leqslant 15n⩽15，所以我们可以直接枚举每条题目选或不选，最后判断是否合法即可。 时间复杂度：O(2n)O(2^n)O(2n)。 Code 1234567891011121314151617181920212223242526272829303132333435363738394041424344// Problem: CF550B Preparing Olympiad// Con...

本文搬运自本人初中博客园博客，若图片加载不出来，可到原文查看：https://www.cnblogs.com/zhangtingxi/p/15633812.html 题目链接 对于最小的点，与它相连的没填的点中，都赋值为这个点点权+1。 这样子贪心就算旁边的点必然会比这个点大，所以+1是没错的。 最后再遍历所有边检验答案合法性。 Code 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666...

本文搬运自本人初中博客园博客，若图片加载不出来，可到原文查看：https://www.cnblogs.com/zhangtingxi/p/15633178.html 题目链接 从1开始从小到大考虑，用set维护每个数左右的扩散范围，然后答案为这个数的区间就是左端点个数 ×\times× 右端点个数。 Code 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859// Problem: AT2060 [AGC005B] M...

本文搬运自本人初中博客园博客，若图片加载不出来，可到原文查看：https://www.cnblogs.com/zhangtingxi/p/15631062.html 桥 定义 无向连通图中如果一条边断开后能使图不连通则条边就是桥。 方法 dfs+并查集 每条边只能走一次。如果搜到一个点还在访问中说明他们是双连通分量，用并查集合并。 Code 1234567891011121314151617181920void dfs(int x){ for(int g=h[x]; g; g=d[g].n) { if(c[g]) continue; ...

本文搬运自本人初中博客园博客，若图片加载不出来，可到原文查看：https://www.cnblogs.com/zhangtingxi/p/15630249.html 题目链接 我们先对于有向图缩点，变成一棵树。 然后我们对于每个树上且在原图中的分割点节点所对应原图中的连通块考虑。 假设这里没有割点，很明显，只需要放2个出口即可。 如果有一个割点，说明这个点是树上的叶子节点，需要放1个出口。 如果有两个或以上的割点，无论哪个割点被割，都可以往另一个方向逃，所以这个连通块不用放。 Code 1234567891011121314151617181920212223242526272829...

本文搬运自本人初中博客园博客，若图片加载不出来，可到原文查看：https://www.cnblogs.com/zhangtingxi/p/15629936.html 题目链接 首先这个点删去之后必然与剩下 n−1n-1n−1 个点失去相连。 如果这个点能使其它点失去相连，说明这个点为割点。 然后统计一下每个儿子与父亲的影响即可。 Code 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666...

本文搬运自本人初中博客园博客，若图片加载不出来，可到原文查看：https://www.cnblogs.com/zhangtingxi/p/15625582.html 题目链接 首先考虑删走一个点后能增加联通块数量，则这个点一定是割点。 然后就完了啊 tarjan完（虽然我没有打tarjan）我们就分别判断每个点是不是割点。如果是看一下是否有父。统计一下即可。 要注意题目一定要割，所以如果有 nnn 个联通块要输出 n−1n-1n−1。 Code 1234567891011121314151617181920212223242526272829303132333435363738394...

本文搬运自本人初中博客园博客，若图片加载不出来，可到原文查看：https://www.cnblogs.com/zhangtingxi/p/15621787.html 题目链接 题目中对主要航道定义是这样的： 如果某一条航道的删除使得一些星球不能到达，那么这条航道是不能删除的，称之为「主要航道」。 这说明了什么？ 说明了主要航道就是桥。 然后题目就是求桥的个数。 模板题。 Code 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455...