【JZOJ 5451】【NOIP2017提高A组冲刺11.4】Genocide
Description Solution 显然的斜率优化， 如果只有一个询问的话直接做即可， 多个询问的话，考虑预处理3个数组： fi,gi,hi 分别表示：从前向后做到i，最大的答案；从后向前做到i，最大的答案；i一定选的最大答案。 f,g好做，主要是h，这个用分治来...
【JZOJ 5442】【NOIP2017提高A组冲刺11.1】荒诞
Description 我的灵魂与我之间的距离如此遥远，而我的存在却如此真实。 ——加缪《局外人》 我醒来的时候，发现满天星斗照在我的脸上。田野上的声音一直传到我的耳畔。夜的气味，土地的气味，海盐的气味，使我的两鬓感到清凉。这沉睡的夏夜的奇妙安静，像潮水一般浸透我的全身。这时，长夜将尽，汽...
JZOJ 100036【NOIP2017提高A组模拟7.10】随机
8.28 模拟题 T3 随机 对应题目 : JZOJ 100036【NOIP2017提高A组模拟7.10】随机 这道题题目的意思不难理解，主要是理解了之后自己的一个想法。 题目是说一个序列有一个规定的特征值：一个序列中任意两元素差的绝对值的最小值和区间长度两者之间的较大者。（表达能力棒棒哒） 然后...
JZOJ 100035【NOIP2017提高A组模拟7.10】区间
题目大意：1<=k<=n<= 2∗107 1<=t,p<= 109 time limits:2s题解：我们注意到这是没有办法用逆元的。 但就就是这就是分块啊（为毛比赛没有一个人想到）。 把n个序列分成长度为k的若干段，当然最后一段不一定是k。 然...
JZOJ5441. 【NOIP2017提高A组冲刺11.1】序列
Description 给定一个1~n的排列x，每次你可以将x1~xi翻转。你需要求出将序列变为升序的最小操作次数。有多组数据。 Input 第一行一个整数t表示数据组数。 每组数据第一行一个整数n，第二行n个整数x1~xn。 Output 每组数据输出一行一个整数表示答案。 Sam...
JZOJ 100036 【NOIP2017提高A组模拟7.10】随机
题目大意：1<=n<= 106 题解： Ans=min(max(|ai−aj|,j−i+1)) 假设我们现在的区间长度是m，最小值是min，将右端点右移，m++，min将可能会减小。 我们确定一个左端点l，假设右端点是r，那么一定当r位于m>=min的临界点...
JZOJ.5335【NOIP2017模拟8.24】早苗
Description Input Output Sample Input 3 3 Sample Output 21 Data Constraint Hint 考虑D...
jzoj5441【NOIP2017提高A组冲刺11.1】序列
题目 Description 给定一个1~n的排列x，每次你可以将x1~xi翻转。你需要求出将序列变为升序的最小操作次数。有多组数据。 Input 第一行一个整数t表示数据组数。 每组数据第一行一个整数n，第二行n个整数x1~xn。 Output 每组数据输出一行一个整数表示答案。 ...
jzoj5336 【NOIP2017提高A组模拟8.24】提米树 （dfs序dp，奇异姿势dp）
题面 分析 剪枝的意思就是你可以任意选点作为叶子。（前提是他子树不选） 比赛的时候有一种60分的n^2 log n做法，就是在dfs序上直接dp. 但是正解比较奇怪，先画颗树出来看看，就会发现根到真·叶子的路径上有且只有一个被选为叶子。于是我们考虑设一种玄学的dp。 令 f[i] ...
【jzoj5334】【NOIP2017提高A组模拟8.24】【空】【扫描线】【set】
descriptionsolution考虑用扫描线，可以发现有相交和内含两种情况，相交就是l+r的差，内含就是r-l的差，可以分别两次用set维护。code#include<set>#include<cstdio>#include<cmath>#include&l...
【JZOJ5335】【NOIP2017提高组模拟】早苗（DP、矩阵乘法）
DescriptionSolution这题的DP其实很显然。 首先显然有一个状态是f[i][j]表示做到第i个，向前最多连续j个不同的方案数。 我们既然不能有m个不同的，那么我们只要不向m转移就好了。 转移也是比较的显然首先可以新加一个颜色f[i][j]–>f[i+1][j+1]*(m-j) ...
JZOJ5397. 【NOIP2017提高A组模拟10.6】Biology trie+LCA/哈希
题意：求一些指定串的最长公共后缀，动态加入。 傻逼题，被题意坑了，以为要求最长公共LCS。 hash入门题，二分长度以后判断一下是否所有串都相同。 trie+LCA也可以，不过麻烦一点。 trie+LCA： #include<cstdio>#include<algorith...
JZOJ5373. 【NOIP2017提高A组模拟9.17】信仰是为了虚无之人 并查集+启发式合并
题意：构造一个长度为n数列，给出m个要求，保证第一个满足，每个要求具体描述为li,ri,ki，表示l到r的异或和为k。对于每一个操作，如果能和前i-1个要求不冲突（能构造出一个合法序列），输出1，否则输出0，最后输出合法序列（不合法的要求忽略），要求字典序最小。大爷好像很喜欢启发式合并= =。被虐了...
[JZOJ4438] K小数查询（经典分块）
Description 给你 N 个数组成的序列，需要支持两种操作 1 L R x 将 L 到 R 加上 x 2 L ...
2018/7/9-纪中某B组题【jzoj1503,jzoj1158,jzoj1161】
正题 T1：jzoj1503-体育场【带权并查集】 博客链接：https://blog.csdn.net/mr_wuyongcong/article/details/80969720 T2：jzoj1158-荒岛野人【扩欧,gcd,同余方程】 博客链接：https://blog.csdn.net/m...
[规律]JZOJ 4213 对你的爱深不见底
Description 出乎意料的是，幸运E 的小R 居然赢了那个游戏。现在欣喜万分的小R 想要写一张明信片给小Y，但是因为小R 非常羞涩，所以他打算采用一些比较神奇的方式来表达。 他定义了一些字符串，s1 = a,s2 = b,si =s_i-1 + s_i-2 (i ...
[dfs] Jzoj P4252 QYQ的图
Description 给你一个n个点，m条边的无向图，每个点有一个非负的权值ci，现在你需要选择一些点，使得每一个点都满足： 如果这个点没有被选择，则与它有边相连的所有点都必须被选择。 问：满足上述条件的点集中，所有选择的点的权值和最小是多少？ QYQ很快就解决了...
[JSOI2008][BZOJ1014][JZOJ1716]火星人
题目大意 给定一个初始字符串 S ，要求支持下列操作： ∙ Q x y ：询问 suffix(x) 和 suffix(y) 的 LCP ∙ R x d ：将字符串第 x 个字符修改为字符 d ...
jzoj 5230_队伍统计_dp
题目描述 现在有n个人要排成一列，编号为1->n 。但由于一些不明原因的关系，人与人之间可能存在一些矛盾关系，具体有m条矛盾关系(u,v),表示编号为u的人想要排在编号为v的人前面。要使得队伍和谐，最多不能违背k条矛盾关系（即不能有超过k条矛盾关系(u,v),满足最后v排在了u前面）。问有多少...
JZOJ 5230. 【NOIP2017模拟A组模拟8.5】队伍统计
Description现在有n个人要排成一列，编号为1->n 。但由于一些不明原因的关系，人与人之间可能存在一些矛盾关系，具体有m条矛盾关系(u,v),表示编号为u的人想要排在编号为v的人前面。要使得队伍和谐，最多不能违背k条矛盾关系（即不能有超过k条矛盾关系(u,v),满足最后v排在了u前面...