洛谷 P1110 [ZJOI2007]报表统计 解题报告
P1110 [ZJOI2007]报表统计题目描述\(Q\)的妈妈是一个出纳，经常需要做一些统计报表的工作。今天是妈妈的生日，小\(Q\)希望可以帮妈妈分担一些工作，作为她的生日礼物之一。经过仔细观察，小\(Q\)发现统计一张报表实际上是维护一个非负整数数列，并且进行一些查询操作。在最开始的时候，有一...
Luogu P1110 [ZJOI2007]报表统计 multiset
沿用了学长的$multiset$然后这道题可以看到我的程序中有两行注释，它在我看来和他们下面的代码没区别，但是我们发现，C++会先调用后面的参数，所以$--it$会被先执行。。。。。。。。。维护两个数组，$a[]$和$b[]$表示每一段开头的元素和结尾的元素。在更新相邻差值的时候，只用考虑新插入的值...
Luogu4338 ZJOI2018 历史 LCT、贪心
传送门题意：在$N$个点的$LCT$中，最开始每条边的虚实不定，给出每一个点的$access$次数，求一种$access$方案使得每条边的虚实变换次数之和最大，需要支持动态增加某个点的$access$次数。$N \leq 4 \times 10^5$ZJOI2018真的都是大火题首先一个小小的转化：...
[ZJOI2018]历史
[ZJOI2018]历史最大化access轻重链的切换次数考虑一个点的贡献，即它交换重儿子的次数发现这个次数只和它自己ai以及每个儿子的子树次数和有关。一个关键的事实是：我们可以自上而下进行贪心！我们最大化fa的贡献，发现，对于操作序列，一个儿子子树的操作是一个子序列，不影响这个儿子子树的贡献！（内...
【BZOJ5212】[ZJOI2018]历史（Link-Cut Tree）
【BZOJ5212】[ZJOI2018]历史（Link-Cut Tree）题面洛谷BZOJ题解显然实际上就是给定了一棵树和每个点被\(access\)的次数，求解轻重链切换的最大次数。先考虑不带修改的答案。如果直接考虑全局的答案会很麻烦。考虑每一个在每一个点处被切换的次数。显然这个子树之和其子树内的...
LOJ2434. 「ZJOI2018」历史 [LCT]
LOJ思路第一眼看似乎没有什么思路，试着套个DP上去：设\(dp_x\)表示只考虑\(x\)子树，能得到的最大答案。合并的时候发现只有\(x\)这个点有可能做出新的贡献，而做出新贡献的时候必然是两个来自不同子树的国家发生战争。于是做法突然就明朗了起来：对于每个点\(x\)，记\(s\)表示子树内的崛...
[ZJOI2013]K大数查询
Description：给定一个序列，支持两种操作1.在[L,R]的每个位置上加上一个数 （注意一个位置上有多个数）2.查询[L,R]上所有数中的第K大Hint:\(n,m<=5e4\)Solution:一道很好的整体二分题，在值域上二分所有询问的答案，并在线段树上维护\(size\)详见代码...
Luogu P2597 [ZJOI2012]灾难
一道非常综合的好题然后就莫名其妙地知道了动态LCA的求法果然是ZJOI的题目，只能说这思路服了首先我们发现每次操作只会灭绝一种动物，然后我们想一下就知道如果有\(n(n>=2)\)个食物的动物就不会灭绝。然后我们YY一个叫灭绝树的东西，在这个树上的点都满足一个性质：当一个节点被割去时，以它为根...
[ZJOI2019]线段树（线段树）
看到这题，首先想到将求和转期望，即每次操作进行概率为1/2，求节点打标记概率。首先对于每次区间修改操作，对节点进行分类：1、这个点和其父亲都和修改区间无交，这种情况可以无视。2、这个点和修改区间无交但父亲和修改区间有交，这样该区间有无标记只和本身及是否存在一个祖先有标记相关。3、这个点被修改区间覆盖...
【ZJOI2010】网络扩容
费用流+最大流 先一遍最大流 再所有边扩容，新加节点限制扩容量k# include <bits/stdc++.h># define IL inline# define RG register# define Fill(a, b) memset(a, b, sizeof(a))# defi...
bzoj 2111: [ZJOI2010]Perm 排列计数 （dp+卢卡斯定理）
bzoj 2111: [ZJOI2010]Perm 排列计数1 ≤ N ≤ 10^6, P≤ 10^9题意：求1~N的排列有多少种小根堆 1: #include<cstdio> 2: using namespace std; 3: const int N = 1e6+5; ...
【BZOJ2111】[ZJOI2010]Perm 排列计数 组合数
【BZOJ2111】[ZJOI2010]Perm 排列计数Description称一个1,2,...,N的排列P1,P2...,Pn是Magic的，当且仅当2<=i<=N时，Pi>Pi/2. 计算1，2，...N的排列中有多少是Magic的，答案可能很大，只能输出模P以后的值Inp...
BZOJ2111: [ZJOI2010]Perm 排列计数
题目：http://www.lydsy.com/JudgeOnline/problem.php?id=2111题意：一个1,2,...,N的排列P1,P2...,Pn是Magic的，当且仅当2<=i<=N时，Pi>Pi/2. 计算1，2，...N的排列中有多少是Magic的，答案可...
「ZJOI 2010」 排列计数
题目链接戳我\(Solution\)其实我们可以发现这题等价于让你求：用\(1\)~\(n\)的数组成一个完全二叉树使之满足小根堆性质的方案数于是我们可以考虑\(dp\)假设我们现在在\(i\)点,\(i\)的子节点个数为\(s[i]\)(包括自己)则：\(dp[i]=C(s[i]-1,s[i*2]...
【BZOJ】2111: [ZJOI2010]Perm 排列计数 计数DP+排列组合+lucas
【题目】BZOJ 2111【题意】求有多少1~n的排列，满足\(A_i>A_{\frac{i}{2}}\)，输出对p取模的结果。\(n \leq 10^6,p \leq 10^9\)，p是素数。【算法】计数DP+排列组合+lucas【题解】令i的父亲为i/2，转化为要求给一棵n个点的完全二叉树...
2111: [ZJOI2010]Perm 排列计数
2111: [ZJOI2010]Perm 排列计数链接题意：称一个1,2,...,N的排列$P_1,P_2...,P_n$是Magic的，当且仅当$2<=i<=N$时，$P_i>P_{i/2}$. 计算1，2，...N的排列中有多少是Magic的，答案可能很大，只能输出模P以后的值...
BZOJ 2111: [ZJOI2010]Perm 排列计数 [Lucas定理]
2111: [ZJOI2010]Perm 排列计数Time Limit: 10 Sec Memory Limit: 259 MBSubmit: 1936 Solved: 477[Submit][Status][Discuss]Description称一个1,2,...,N的排列P1,P2...,...
泡泡堂BNB[ZJOI2008]
——BZOJ1034Description第XXXX届NOI期间，为了加强各省选手之间的交流，组委会决定组织一场省际电子竞技大赛，每一个省的代表队由n名选手组成，比赛的项目是老少咸宜的网络游戏泡泡堂。每一场比赛前，对阵双方的教练向组委会提交一份参赛选手的名单，决定了选手上场的顺序，一经确定，不得修改...
洛谷P2055 [ZJOI2009]假期的宿舍 [二分图最大匹配]
题目描述学校放假了 · · · · · · 有些同学回家了，而有些同学则有以前的好朋友来探访，那么住宿就是一个问题。比如 A 和 B 都是学校的学生，A 要回家，而 C 来看B，C 与 A 不认识。我们假设每个人只能睡和自己直接认识的人的床。那么一个解决方案就是 B 睡 A 的床而 C 睡 B 的床...
[bzoj2229][Zjoi2011]最小割_网络流_最小割树
最小割 bzoj-2229 Zjoi-2011题目大意：题目链接。注释：略。想法：在这里给出最小割树的定义。最小割树啊，就是这样一棵树。一个图的最小割树满足这棵树上任意两点之间的最小值就是原图中这两点之间的最小割。这个性质显然是非常优秀的。我们不妨这样假设，我么已经把最小割树求出来了，那么这个题就迎...