JZOJ 5230. 【NOIP2017模拟A组模拟8.5】队伍统计
Description现在有n个人要排成一列，编号为1->n。但由于一些不明原因的关系，人与人之间可能存在一些矛盾关系，具体有m条矛盾关系(u,v),表示编号为u的人想要排在编号为v的人前面。要使得队伍和谐，最多不能违背k条矛盾关系（即不能有超过k条矛盾关系(u,v),满足最后v排在了u前面）...
【JZOJ 5400】【NOIP2017提高A组模拟10.7】Repulsed
Description小w心里的火焰就要被熄灭了。简便起见，假设小w的内心是一棵n-1条边，n个节点的树。现在你要在每个节点里放一些个灭火器，每个节点可以放任意多个。接下来每个节点都要被分配给一个至多k条边远的灭火器，每个灭火器最多能分配给s个节点。至少要多少个灭火器才能让小w彻底死亡呢？Solut...
[暑假集训] jzoj 2016.7.11 noip模拟赛C 总结
今天空间又没算好,瞬间没100分觉得时间可以就迷之认为空间也可以..不开滚动的后果洪水哦~暴力送分O(n^2)切然而一看哦~n<=50哦哦哦那就n^4好了,这样更好写邦德哦哦哦n<=20压位DP吧时间是2^20*n左右,时限还有2s再切一题餐桌咦好熟悉然后一看数据范围n<=2000...
jzoj5377 开拓
哇好火的dp啊.开始根本想不出这里如果顺着dp肯定是不行的,没办法记录钻头能力值显然能力值的变化会影响后面收入而具体影响就是:全部乘了1-0.01k或1+0.01c.可以倒着dp(orz)设f[i]表示初始能力为1i~n可以搞到的最大收入.然后如果是资源星球就\(f[i]=max(f[i+1],f[...
JZOJ 100035【NOIP2017提高A组模拟7.10】区间
题目大意：1<=k<=n<=2∗1071<=t,p<=109timelimits:2s题解：我们注意到这是没有办法用逆元的。但就就是这就是分块啊（为毛比赛没有一个人想到）。把n个序列分成长度为k的若干段，当然最后一段不一定是k。然后对每一块求一个前缀、后缀乘积和。最后暴...
JZOJ 5195. 【NOIP2017提高组模拟7.3】A
5195.【NOIP2017提高组模拟7.3】A TimeLimits: 1000ms MemoryLimits: 262144KB DetailedLimits GotoProblemSetDescription InputOutput SampleInput73SampleOutput4 ...
【JZOJ5363】【NOIP2017提高A组模拟9.14】生命之树 Trie+启发式合并
题面45在比赛中，我只想到了45分的暴力。对于一个树中点对，相当于在他们的LCA及其祖先加上这个点对的贡献。那么这个可以用dfs序+树状数组来维护。100想法我想到了可能要用trie树来维护这个字符串的公共前缀。然后这就面临了两个很严重的问题。1.我对于每个子树都要建一个trie，所以这是\(O(n...
【jzoj5333】【NOIP2017提高A组模拟8.23】【大新闻】【可持久化线段树】
descriptionsolution可以发现把序列倒过来就是在队末加或删数维护前缀权值线段树即可，这不就是主席树，直接做就可以了。code#include<set>#include<cstdio>#include<cmath>#include<cstrin...
jzoj5336 【NOIP2017提高A组模拟8.24】提米树 （dfs序dp，奇异姿势dp）
题面分析剪枝的意思就是你可以任意选点作为叶子。（前提是他子树不选）比赛的时候有一种60分的n^2logn做法，就是在dfs序上直接dp.但是正解比较奇怪，先画颗树出来看看，就会发现根到真·叶子的路径上有且只有一个被选为叶子。于是我们考虑设一种玄学的dp。令f[i]为在dfs序上，当前最后一个叶子选的...
[solution] JZOJ-5795 词典
【solution】JZOJ-5795词典题面Description小C有$n$个字符串$T_1T_n$，给出$m$个询问第$i$个询问给出一个字符串$S_i$,对于每个询问，我们可以得到一个长度为$n$的$bool$数组$a$，其中$a_i=(S_i$是否为$T_i$的前缀$)$例如，$a=[0,...
jzoj5986. 【WC2019模拟2019.1.4】立体几何题 （权值线段树）
传送门题面题解不难看出每个点的大小为行列限制中较小的那一个（因为数据保证有解）对于行的每个限制，能取到的个数是列里限制大于等于它的数的个数，同理，对于列是行里大于它的个数（这里没有等于，为了避免重复计算）于是可以对于行列分别开权值线段树，修改的时候只要把对应的贡献改一下就好了//minamoto#i...
【JZOJ5231】【NOIP2017模拟A组模拟8.5】序列问题 线段树
题面100在\(O(n^2)\)的基础上，我们可以用线段树来加速。枚举了左端点之后，需要知道以这个左端点为起点的前缀max，前缀min。这里只讨论前缀max，前缀min同理。当我们倒序枚举左端点的时候，这个前缀max就可以用线段树来维护：左端点向左移一位到i——首先我们要预处理出a[i]向右第一个比...
【JZOJ5232】【NOIP2017模拟A组模拟8.5】带权排序
DescriptionDataConstraint对于20%的数据，n<=6,0<=li<=ri<=15对于40%的数据，n<=10,0<=li<=ri<=20对于60%的数据，0<=li<=ri<=1000对于100%的数据，n&l...
【jzoj5231】【NOIP2017模拟A组模拟8.5】【序列问题】 【分治】
题目大意解题思路考虑分治，统计跨国分治中心的区间的答案，从左到右枚举右端点，维护第一个左端点到分治中心max比分治中心到右端点大的位置，同理维护min，同时维护对答案的贡献即可。code#include<cstdio>#include<cmath>#include<cs...
【JZOJ5231】【NOIP2017模拟A组模拟8.5】序列问题
DescriptionDataConstraint对于30%的数据，n<=5000对于60%的数据，n<=50000对于100%的数据，n<=500000,0<=A[i]<=10^9Solution这道题有很多种解法，我这里主要讲讲分治和线段树两种解法。分治：我们对于每...
JZOJ 5232【NOIP2017模拟】带权排序(概率，线段树)
DescriptionSolution我们知道要求的是∑si∗E(pi)，那么我们的目的就是对于每个数求出它的期望排名。一个数排名的期望就是对于前面的数小于等于它的期望和后面的数小于它的期望(题目还有一个要求ai=aj时piCode#include<iostream>#include&l...
[暑假集训] jzoj 2016.7.14 noip模拟赛B 总结
继续做B组总结不要放弃YY贪心和暴力的想法,没准就是正解呢时间也刚好够,还是今天没有码农题和缘故下次要争取缩短读题时间,这次读了一个多小时WildNumber数位跌拍送分题然后机智的打了搜索10^7过了Antimonotonicity一长串看不懂的单词不明觉厉还以为是最长子序列的蜜汁扩展然后惊奇的发...
【JZOJ5231】【NOIP2017模拟A组模拟8.5】序列问题 线段树
题面100在\(O(n^2)\)的基础上，我们可以用线段树来加速。枚举了左端点之后，需要知道以这个左端点为起点的前缀max，前缀min。这里只讨论前缀max，前缀min同理。当我们倒序枚举左端点的时候，这个前缀max就可以用线段树来维护：左端点向左移一位到i——首先我们要预处理出a[i]向右第一个比...
【JZOJ5231】【NOIP2017模拟A组模拟8.5】序列问题
DescriptionDataConstraint对于30%的数据，n<=5000对于60%的数据，n<=50000对于100%的数据，n<=500000,0<=A[i]<=10^9Solution这道题有很多种解法，我这里主要讲讲分治和线段树两种解法。分治：我们对于每...
[jzoj]3875.【NOIP2014八校联考第4场第2试10.20】星球联盟(alliance)
Linkhttps://jzoj.net/senior/#main/show/3875Problem在遥远的S星系中一共有N个星球，编号为1…N。其中的一些星球决定组成联盟，以方便相互间的交流。但是，组成联盟的首要条件就是交通条件。初始时，在这N个星球间有M条太空隧道。每条太空隧道连接两个星球，使得...