zhangxixi的博客

算法复键——圆方树 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/162103786 干什么的 把点双变成一个点 怎么实现 https://blog.csdn.net/zhangtingxiqwq/article/details/132645934 代码总览： 1234567891011121314151617void dfs(int x) { dfn[x]=low[x]=++tot; z.push(x); for(int y : T[x]) ...

容斥原理+哈夫曼式多项式乘法NTT：ABC462G 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/162099398 https://atcoder.jp/contests/abc462/tasks/abc462_g 首先根据容斥原理，我们相当于求： 我们对颜色进行分类，对于颜色 kkk ，我们假设有 XkX_kXk​ 个球， YkY_kYk​ 个盒子。 我们现在枚举它有 DkD_kDk​ 个球放在相应颜色的盒子里，方案有： 因为颜色间不相互影响，所以这...

一般图的点的三元问题转化为二分图最大独立集：ABC461G 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/162103270 https://atcoder.jp/contests/abc461/tasks/abc461_g 一种错误做法 我刚开始的做法： 首先每个点肯定是0、1013、2026，即0、1、2的。 考虑到每个点双内，它的最大值必然不会超过所有点选1。 于是建立圆方树，然后树上dp。 一个点若为2，则需同一点双内所有点均为0。 12345678...

atcoder Convolution库（NTT）用法 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/162096360 求： ci=∑j=0iajbi−jc_i = \sum_{j = 0}^i a_j b_{i - j} ci​=j=0∑i​aj​bi−j​ 用法： 1vector<T> convolution<int m = 998244353>(vector<T> a, vector<T> b) 其中 ...

语法复键之Lambda排序、priority_queue、multiset / set、动态开二维vector 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/162002963 使用Lambda实现sort排序 1sort(a + 1, a + n + 1, [] (node &x, node &y) {return x.v > y.v; }); Priority_queue 1234priority_queue&...

语法复键之Lambda排序、priority_queue、multiset / set、动态开二维vector 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/162002963 使用Lambda实现sort排序 1sort(a + 1, a + n + 1, [] (node &x, node &y) {return x.v > y.v; }); Priority_queue 1234priority_queue&...

Devc++：MinGW64更新 & atcoder库配置 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/162093442 MinGW64更新 下载 下载地方： https://github.com/niXman/mingw-builds-binaries 选择此版本 解压至D盘根目录 测试 解压后是这样子的： 把bin目录添加到环境变量path里 然后用wt测试： 添加 devc++ > 工具 > 编译选项 黄色按钮添加，红色...

算法复键——AC自动机 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/162074359 什么是AC自动机： 在Trie上跑kmp 核心思想：构建fail树。fail[u]指向一个节点，表示这个节点具有和u所在节点所代表串的最长公共后缀。 核心代码： 12345678910111213141516171819void bfs() { int i, j; q.push(1); fail[1] = 0; fail[0] = 1; // 根节点失配指向...

算法复键——5道ABC F题 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/162058972 ABC 462 F（动态规划） 显然dp 设 dp(i,j,k)dp(i,j,k)dp(i,j,k) 表示前 iii 个字符，目前的贡献为 jjj ，最后两个字母为 kkk 的方案数。 jjj 最大为 KKK ， 但可能为负，但顶多-1. kkk 的话其实本质只需要区分三种状态 ABABAB 、 XAXAXA 、 XXXXXX 。只有这三种状态是必要的 然后转移的...

dp之双dp前后互补加类二进制均摊思想：SS221109D 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/162037356 https://cplusoj.com/d/senior/p/SS221109D 首先可以推一下性质，不难发现，一个数只会进行如此变换： 先除至多 log⁡2(n)\log_2(n)log2​(n) 次 再乘至多 nnn 次 所以一个明显的dp是可以设计的： f(i,x,y)f(i,x,y)f(i,x,y) 表示第 iii...