【BZOJ】【1834】【ZJOI2010】Network 网络扩容
网络流/费用流这题……我一开始sb了。第一问简单的最大流……第二问是要建费用流的图的……但是是在第一问的最大流跑完以后的残量网络上建，而不是重建……我们令残量网络上原有的弧的费用全部为0（因为如果还能走就不需要扩容），而新加的弧容量为INF，费用为给定的w[i]。然后跑费用流就好了……这样建的话如果...
ZJOI2018酱油记
ZJOI2018酱油记前言作为\(HN\)高一蒟蒻选手，毕竟去了趟\(ZJOI\)玩泥巴不写点游记还是不太好吧。今天来补一补。Day0星期天，中午，我们一群人滚到了学校门口然后集合，滚去坐地铁连校车都不提供，差评高铁站感觉很久很久很久没有来过了换句话说，我很久很久很久没有离开过长沙了忽然出去一趟，似...
【bzoj1059】 ZJOI2007—矩阵游戏
http://www.lydsy.com/JudgeOnline/problem.php?id=1059 (题目链接)题意一个01矩阵，可以任意交换两行或两列，问能否经过若干次交换后使主对角线全为1。Solutionhzwer：同行同列的点无论经过多少次变换仍然同行或同列，所以题目可转换为能不能找到...
【树链剖分】[BZOJ1036][ZJOI2008]树的统计Count
题目描述一棵树上有n个节点，编号分别为1到n，每个节点都有一个权值w。我们将以下面的形式来要求你对这棵树完成一些操作：I.CHANGEut:把结点u的权值改为tII.QMAXuv:询问从点u到点v的路径上的节点的最大权值III.QSUMuv:询问从点u到点v的路径上的节点的权值和注意：从点u到点v的...
[BZOJ3527][ZJOI2014]力 FFT+数学
题目链接：http://www.lydsy.com/JudgeOnline/problem.php?id=3527首先卷积的形式是$h(i)=\sum_{i=0}^jf(i)g(i-j)$，如果我们可以把式子整理成这个样子再套上FFT就成功了。$$E_i=\sum_{j<i}\frac{q_j...
[BZOJ3527][ZJOI2014]力：FFT
分析整理得下式：\[E_i=\sum_{j<i}{\frac{q_i}{(i-j)^2}}-\sum_{j>i}{\frac{q_i}{(i-j)^2}}\]假设\(n=5\)，考虑这两个数组：\(a:q_1\quadq_2\quadq_3\quadq_4\quadq_5\)\(b:-\...
BZOJ 1835: [ZJOI2010]base 基站选址 [序列DP 线段树]
1835:[ZJOI2010]base基站选址题目描述有N个村庄坐落在一条直线上，第i(i>1)个村庄距离第1个村庄的距离为Di。需要在这些村庄中建立不超过K个通讯基站，在第i个村庄建立基站的费用为Ci。如果在距离第i个村庄不超过Si的范围内建立了一个通讯基站，那么就成它被覆盖了。如果第i个村...
洛谷P4338 [ZJOI2018]历史（LCT，树形DP，树链剖分）
洛谷题目传送门ZJOI的考场上最弱外省选手T210分成功滚粗。。。。。。首先要想到30分的结论说实话Day1前几天刚刚刚掉了SDOI2017的树点涂色，考场上也想到了这一点想到了又有什么用？反正想不到最大的贡献是怎么推出来的然后晚上心中怀着九条CNM看完了Solution.pdf貌似对我这个蒟蒻来说...
BZOJ 3926: [Zjoi2015]诸神眷顾的幻想乡 广义后缀自动机 后缀自动机 字符串
https://www.lydsy.com/JudgeOnline/problem.php?id=3926广义后缀自动机是一种可以处理好多字符串的一种数据结构（不像后缀自动机只有处理一到两种的时候比较方便）。后缀自动机可以说是一种存子串的缩小点数的trie树，广义后缀自动机就是更改了一下塞点的方式让...
【刷题】BZOJ 2816 [ZJOI2012]网络
Descriptionhttp://www.lydsy.com/JudgeOnline/upload/zjoi2012.pdfSolution维护树上联通块的信息，支持动态加边删边LCT总共只有10种颜色，直接建10个LCT，每个LCT维护一种颜色LCT还是差不多只是第二个操作比较麻烦，得一个一个颜...
bzoj 1834: [ZJOI2010]network 网络扩容
#include<cstdio>#include<iostream>#include<cstring>#defineM100000#defineinf2139062143usingnamespacestd;structdata{intl,r,w;}a[M];int...
洛谷.1110.[ZJOI2007]报表统计(Multiset Heap)
题目链接主要思路/*对于询问1，用堆代替multiset/Splay对于询问2，multiset1.注意哨兵元素2.注意multiset中删除时是删除某元素的一个位置，而不是这个元素！这个值会全部都删掉*/#include<set>#include<cstdio>#inclu...
BZOJ_1058_[ZJOI2007]报表统计_STL
BZOJ_1058_[ZJOI2007]报表统计_STLDescription小Q的妈妈是一个出纳，经常需要做一些统计报表的工作。今天是妈妈的生日，小Q希望可以帮妈妈分担一些工作，作为她的生日礼物之一。经过仔细观察，小Q发现统计一张报表实际上是维护一个可能为负数的整数数列，并且进行一些查询操作。在最...
BZOJ 1059: [ZJOI2007]矩阵游戏 匈牙利算法
1059:[ZJOI2007]矩阵游戏TimeLimit:10Sec MemoryLimit:162MBSubmit:2351 Solved:1156题目连接http://www.lydsy.com/JudgeOnline/problem.php?id=1059Description小Q是一个非...
BZOJ 1058: [ZJOI2007]报表统计( 链表 + set )
这种题用数据结构怎么写都能AC吧...按1~N弄个链表然后每次插入时就更新答案,用set维护就可以了...-----------------------------------------------------------------------------------#include<cs...
BZOJ 3527: [ZJOI2014]力（FFT）
题意给出\(n\)个数\(q_i\),给出\(Fj\)的定义如下：\[F_j=\sum\limits_{i<j}\frac{q_iq_j}{(i-j)^2}-\sum\limits_{i>j}\frac{q_iq_j}{(i-j)^2}.\]令\(E_i=F_i/q_i\)，求\(E_i...
[BZOJ 1833] [ZJOI2010] count 数字计数 【数位DP】
题目链接：BZOJ-1833题目分析数位DP..用f[i][j][k]表示第i位是j的i位数共有多少个数码k。然后差分询问...Get()中注意一下，如果固定了第i位，这一位是t，那么数码t的答案是要加一个值的（见代码）。代码#include<iostream>#include<c...
1003. [ZJOI2006]物流运输【区间DP+最短路】
Description物流公司要把一批货物从码头A运到码头B。由于货物量比较大，需要n天才能运完。货物运输过程中一般要转停好几个码头。物流公司通常会设计一条固定的运输路线，以便对整个运输过程实施严格的管理和跟踪。由于各种因素的存在，有的时候某个码头会无法装卸货物。这时候就必须修改运输路线，让货物能够...
【bzoj1036】[ZJOI2008]树的统计Count
树链剖分模板题，嗯看一个不知名的神犇里的博客里的一句话感觉说的很对，树链剖分就是将树hash到数组中然后用线段树或者平衡树来维护的数据结构，剖分出轻重链之后维护就好了，也可以结合欧拉序，DFS序来用。一开始想找着zyf2000的写，发现她的代码又臭又长（不是故意D神犇的，希望神犇看不见），所以结合着...
[ZJOI2006]物流运输 SPFA+DP
题目描述物流公司要把一批货物从码头A运到码头B。由于货物量比较大，需要n天才能运完。货物运输过程中一般要转停好几个码头。物流公司通常会设计一条固定的运输路线，以便对整个运输过程实施严格的管理和跟踪。由于各种因素的存在，有的时候某个码头会无法装卸货物。这时候就必须修改运输路线，让货物能够按时到达目的地...