zhangxixi的博客

矩阵树定理 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/132152078 启蒙： http://zhengruioi.com/contest/1416 T1，T2的10分暴力（后面是论文科技，不搞了） https://www.luogu.com.cn/problem/P6178 O(n3)O(n^3)O(n3) 解决无向图生成树计数问题。 行列式 交换两行，行列式变号 一行整体加上 kkk 倍另一行，行列式符号不变 行列式如果只有其中对角线非...

不完全考虑构造+dp与构造：1107T2 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/134274865 http://cplusoj.com/d/senior/p/SS231107B 发现reverse操作会对一堆数进行修改，但如果我们只关注其中一些数呢？ 假设我们已经构造好 [1,i−1][1,i-1][1,i−1] ，我们现在尝试构造 [i,n][i,n][i,n] ，我们可操作的范围是在 [i−1,n][i-1,n][i−1,n] 假设 iii 在...

模拟网络流之dp类：1107T3 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/134275008 http://cplusoj.com/d/senior/p/SS231107C 可以发现是求第 iii 层到第 jjj 层的最大流。 同样先转成最小割，显然割点比个边优。然后我们可以利用状压dp来求。 f(i,j,s)f(i,j,s)f(i,j,s) 表示在第 iii 层，还可以割 jjj 条边，这层还存活的点集为 sss ，最快在哪里就流不动了。 我们先假设...

耳分解与双极定向 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/132112802 耳分解 对于无向图中的任意边双和有向图中的任意强联通都可以按照此方法构造： S={u}S=\{u\}S={u} 每次找 SSS 的两个元素 u,vu,vu,v （可相同），找一条 不经过 SSS 的路径 ，并把路劲上的所有点加入 SSS 可以拿来dp，来构造某种条件的边双。 常用的状态设计 f(S)f(S)f(S) ，然后枚举 TTT 为 SSS 补集的子集。再...

上下界网络流小结 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/132093889 正式请看：https://oi-wiki.org/graph/flow/bound/ 无源汇上下界可行流 新建源汇 S,TS,TS,T ，若 a→ba\to ba→b 有 [c,d][c,d][c,d] 。网络流中上界肯定满足。 我们变成： S→b,cS\to b,cS→b,c a→T,ca\to T,ca→T,c a→b,c−da\to b,c-da→b,c−...

偏序关系用分治优化建图：ARC165F 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/134253598 https://atcoder.jp/contests/arc165/tasks/arc165_f 首先可以建图，然后变成求字典序最小的的拓扑排序 然后发现这样复杂度会炸，观察连边的条件是什么： li<ljl_i<l_jli​<lj​ ri<rjr_i<r_jri​<rj​ 这是个二维偏序问题，我们考虑用分...

珂朵莉树转化区间（对于多区间类问题）+扫描线线段树维护：1031T3 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/134249552 http://cplusoj.com/d/senior/p/SS231031C 珂朵莉树有个很好的性质： 任意时刻，所有区间都是不交的 所以我们可以把所有区间先拿珂朵莉树变成一堆小区间，每个区间有个存活时间 [t1,t2][t_1,t_2][t1​,t2​] 考虑这个区间意义。他会在 l∈[1,t1],r∈[t1,t2]...

排列与置换换+容斥+多项式生成函数启发式合并：[Gym-103446B] 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/134243178 https://vjudge.net/contest/591700#problem/G 看到排列，先考虑置换换，题意转化为置换环相邻的不能再最终序列上相邻 而这个过程看起来很容斥，所以我们容斥：至少要 xxx 个相邻 我们发现每个置换环的所有边不能全部同时被选，所以我们每个置换环要分开考虑，最后再乘起来 然而这样的复杂度...

用Python舞动数据的魔力：探索数据分析的艺术之路 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/134241814 用Python舞动数据的魔力：探索数据分析的艺术之路 [TOC] 前言 打开招聘网站，我们会发现数据分析越来越普遍应用到各个职能岗位，也就是说，不论你在哪个行业，都会需要数据分析技能。所以作为程序员的你，会吗~ 什么是Python数据分析 Python数据分析是使用Python语言对数据进行处理、清洗和分析的过程，通过利用Python的各种...

轮廓线dp：GYM103446C 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/134241273 https://vjudge.net/contest/591700#problem/H 考虑轮廓线dp，当我们枚举到蓝色格子的时候，我们记录红色格子的状态 每个格子有4种状态 0有向下 1需要向上 2不用管 3需向右 每次枚举的时候，我们需要考虑这个格子的三种状态： 1 0+不放 0+放 他们会对所有3和同列的值造成影响 ...