2 BIT_jzx

尚未进行身份认证

我要认证

暂无相关简介

等级
TA的排名 13w+

TREE(dfs序+树上差分)

题目一棵 N 个节点的树,每个节点有整数值的点权。树上节点标号为 1∼N。 Q 个询问,形式如下: (1) 0 x y:把编号 x 的节点的点权修改为 y。 (2) 1 x y:对于编号 x∼y 路径上的每一种点权,是否都出现偶数次? 数据保证每次询问的路径上最多只有一种点权的出现次数是奇数次。 输入格式: 第一行两个数 N、Q 表示树的节点数和询问个数。(5<=...

2020-02-21 00:20:42

小奇的数列

题目给定一个长度为 N 的数列 A,以及 Q 次询问,每次给出三个数 L,R 和 P,询问 (A[L'] + A[L'+1] + … + A[R']) mod P 的最小值。其中 L <= L' <= R' <= R。 即模意义下的区间子串和的最小值。 输入格式: 第一行包含两个正整数 N 和 Q,表示数列的长度和询问的个数。 第二行为 N 个整数,为 A...

2020-02-14 00:22:19

平衡树(模板)

Splay#include <iostream>#include <cstdio>#include <cstring>#include <algorithm>#include <cmath>using namespace std;const int MAXN = 2e5 + 3;int ch[MAXN][2] , va...

2020-01-26 15:53:23

树的重心

题目题目链接题解:/*这道题要用dp+倍增,也就是倍增dp首先要了解树的重心的基本性质1.重心都是相邻的2.重心都是在树的重边上(不会证明)那么就可以dp了,dp[i][j]表示从i节点开始,向下跳2的j次方条重边所得到的点,转移和LCA是一样的现在要考虑换根,其实可以在线维护,具体看代码*/#include <cstdio>#include &l...

2019-11-28 13:07:56

划分

题目题目描述2048 年,第三十届 CSP 认证的考场上,作为选手的小明打开了第一题。这个题的样例有nn组数据,数据从1 \sim n1∼n编号,ii号数据的规模为a_iai​。小明对该题设计出了一个暴力程序,对于一组规模为uu的数据,该程序的运行时间为u^2u2。然而这个程序运行完一组规模为uu的数据之后,它将在任何一组规模小于uu的数据上运行错误。样例中的...

2019-11-27 13:03:38

Emiya 家今天的饭(CSP 2019 D2 T1)

题目题目描述Emiya 是个擅长做菜的高中生,他共掌握nn种烹饪方法,且会使用mm种主要食材做菜。为了方便叙述,我们对烹饪方法从1 \sim n1∼n编号,对主要食材从1 \sim m1∼m编号。Emiya 做的每道菜都将使用恰好一种烹饪方法与恰好一种主要食材。更具体地,Emiya 会做a_{i,j}ai,j​道不同的使用烹饪方法ii和主要食材jj的菜(1 ...

2019-11-25 00:42:01

括号树(CSP 2019 D1T2)

题目题解首先想到用单调栈将在树上以i结尾的括号串记录下来然后进行分类讨论如果第i个字符是(,则i的答案就是i的父亲的答案,是不变的否则,这个有括号可能会对答案有贡献:如果在这之前,没有其它的未匹配的右括号在(到i为止)最近出现的左括号与i之间,那么贡献就会加1举例子:()() 如果i=4,那么贡献加一否则:()))如果i=4,那么贡献不变但是还要考...

2019-11-22 13:42:43

最长公共子序列[模板]

#include <iostream>#include <cstdio>#include <cstring>#include <cmath>using namespace std;const int MAXN = 100003;int a[MAXN] , b[MAXN];int s[MAXN] , dp[MAXN];int n;i...

2019-11-14 19:23:46

愤怒的小鸟

题目题解由于n<=18,可以想到状压dp然后选择枚举一个抛物线,直接更新如果用填表法,就会有些难度,而时间复杂度是O()且其中cnt表示i的点集减去抛物线的点集代码//可是用了O2才过#pragma GCC optimize(2)#include <iostream>#include <cstdio>#includ...

2019-11-14 15:10:01

Slow Path Finding Algorithm(多校联考)

题目小H 今天学习了「缓慢的路径寻找算法」,下课后便准备找一道题练习一下。题目是这样的:给定一张有向图,每条边上都有一个小写英文字母,小H 需要寻找一条路径使得路径上出现最多的字母的出现次数最大。然而小H 想了很久也只会jV j = 1 的情形,于是他找到了你,请你帮他解决这个问题。Input输入文件包含多组测试数据。第一行一个整数T (1 T 105),表示测试数据的组数。每...

2019-11-12 13:32:35

最大K段和(FZSZ多校模拟)

题目给出N个数,在里面选出不超过K段连续的子序列,使其两两不相交,求总和的最大值(可以一段都不选)数据范围N,K<= 100000对于一个数a满足 -1000000000 <= a <=100000000题解首先看到这道题很容易想到是dp,然后再加上一个优化可是这里的N,K太大O(NK)是会超时的所以换方法,然后用了一种不知道为什么的算法:...

2019-11-06 01:14:30

Star Way To Heaven(LOJ 6322)

题目礼国庆 2017 Day6」Star Way To Heaven内存限制:256 MiB时间限制:1000 ms标准输入输出题目类型:传统评测方式:文本比较上传者: 匿名提交提交记录统计测试数据讨论1题目描述小伤心的走上了 Star way to heaven。到天堂的道路是一个笛卡尔坐标系上一个的长方形通道顶点在和。小从最左边任意一点...

2019-11-04 13:17:30

排列计数

题目题目描述求有多少种长度为 n 的序列 A,满足以下条件:1 ~ n 这 n 个数在序列中各出现了一次若第 i 个数 A[i] 的值为 i,则称 i 是稳定的。序列恰好有 m 个数是稳定的满足条件的序列可能很多,序列数对10^9+7109+7取模。输入格式第一行一个数 T,表示有 T 组数据。接下来 T 行,每行两个整数 n、m。输出格式输出 T 行,...

2019-10-30 13:16:13

小奇探险

题目题目描述小奇去遗迹探险,遗迹里有个宝箱,有的装满了珠宝,有的装着废品。小奇有地图,所以它知道每一个宝箱的价值,但是它不喜欢走回头路,所以要按顺序拿这个宝箱中的若干个。拿宝箱很累的。一开始小奇的体力是,每得到一个宝箱之后,小奇得到的价值是体力宝箱的价值,之后它的体力就会变为原来的倍。小奇不喜欢连续放过很多宝箱,所以任意一段长度为的序列中,小奇一定要取走...

2019-10-30 00:37:51

战争调度(树形DP+BFS)

题目题目描述脸哥最近来到了一个神奇的王国,王国里的公民每个公民有两个下属或者没有下属,这种关系刚好组成一个 n 层的完全二叉树。公民 i 的下属是 2 * i 和 2 * i +1。最下层的公民即叶子节点的公民是平民,平民没有下属,最上层的是国王,中间是各级贵族。现在这个王国爆发了战争,国王需要决定每一个平民是去种地以供应粮食还是参加战争,每一个贵族(包括国王自己)是去管理后勤还是...

2019-10-27 14:53:53

最优贸易(DP)

题目题目描述CC国有nn个大城市和mm条道路,每条道路连接这nn个城市中的某两个城市。任意两个城市之间最多只有一条道路直接相连。这mm条道路中有一部分为单向通行的道路,一部分为双向通行的道路,双向通行的道路在统计条数时也计为11条。CC国幅员辽阔,各地的资源分布情况各不相同,这就导致了同一种商品在不同城市的价格不一定相同。但是,同一种商品在同一个城市的买入价和卖出价始终是相同...

2019-10-24 12:45:13

木棍 Sticks「POI2011 R3 Day2

题目若干彩色的木棍,求是否存在三根互不同色的木棍,能够构成一个非退化的三角形(即面积为正的三角形)。输入格式第一行一个正整数表示颜色种类数。接下来行,每行若干个空格隔开的正整数,描述木棍。第行第一个数为,表示颜色的木棍数。该行接下来个正整数,描述这种颜色的木棍的长度。输出格式若不存在,则输出一行NIE; 否则,输出一行六个空格隔开的数,分别表示第一根木棍的颜色,第一根木棍的...

2019-10-22 00:02:18

积木大赛

题目春春幼儿园举办了一年一度的“积木大赛”。今年比赛的内容是搭建一座宽度为nn的大厦,大厦可以看成由n块宽度为1的积木组成,第i块积木的最终高度需要是h_ihi​。在搭建开始之前,没有任何积木(可以看成nn块高度为00的积木)。接下来每次操作,小朋友们可以选择一段连续区间[l, r][l,r],然后将第第LL块到第RR块之间(含第LL块和第RR块)所有积木的高度分别增加11。小...

2019-10-20 13:45:32

Roadblocks

题目Bessie has moved to a small farm and sometimes enjoys returning to visit one of her best friends. She does not want to get to her old home too quickly, because she likes the scenery along the way....

2019-10-13 08:52:31

CF1215E Marbles

题目有 n(n \le 4 * 10^5)(n≤4∗105)个珠子 , 第ii个珠子颜色是c_i (c_i \le 20)ci​(ci​≤20), 每次操作把相邻的两个珠子交换。现在要把相同颜色的珠子排列在相连的一段,问至少要多少次操作 。输入格式第一行:一个数n第二行:n个数,表示珠子的颜色输出格式一行:至少交换的次数输入输出样例输入 #1 复制73 4 ...

2019-09-26 12:48:13

查看更多

勋章 我的勋章
  • 签到新秀
    签到新秀
    累计签到获取,不积跬步,无以至千里,继续坚持!
  • 持之以恒
    持之以恒
    授予每个自然月内发布4篇或4篇以上原创或翻译IT博文的用户。不积跬步无以至千里,不积小流无以成江海,程序人生的精彩需要坚持不懈地积累!
  • 1024勋章
    1024勋章
    #1024程序员节#活动勋章,当日发布原创博客即可获得
  • 勤写标兵Lv1
    勤写标兵Lv1
    授予每个自然周发布1篇到3篇原创IT博文的用户。本勋章将于次周周三上午根据用户上周的博文发布情况由系统自动颁发。