histcat

大师 ljt12138 首先建了 $n$ 个特斯拉电磁塔，这些电塔排成一排，从左到右依次标号为 $1$ 到 $n$，第 $i$ 个电塔的高度为 $h [i]$。 建筑大师需要从中选出一些电塔，然后这些电塔就会缩到地下去。这时候，如果留在地上的电塔的高度…

link 悬线法 正方形最大面积可以统计最大变成的平方 最大边长等于min(r[i][j] - l[i][j] + 1, h[i][j]) 当i==1时候 l 与 r 数组不要更新。。。。。 Copy #include<bits/stdc++.h> using…

给定若干个自然数 $a_{1\sim n}$。 你需要选出其中一些数，然后将你选出的数划分为若干个集合。 你需要最大化每个集合 $\tt mex$ 的异或和，输出这个值。 一个集合的 ${\tt mex}$ 是指最小的不在这个集合中的自然数，例如 ${0,1,2,4,5}$ 的…

link 首先，看到数据范围这么大，答案还与值域有关，考虑离散化 按照长度（离散前）排序以后肯定一段一段取 所以，考虑双指针，维护两个指针l,r, 意义是从l到r恰好是有m个区间包裹一个点 每次r++，如果包含同一个点的数量大于m了，就l++，知道不大于m 当然…

某一村庄在一条路线上安装了 $n$ 盏路灯，每盏灯的功率有大有小（即同一段时间内消耗的电量有多有少）。老张就住在这条路中间某一路灯旁，他有一项工作就是每天早上天亮时一盏一盏地关掉这些路灯。 为了给村里节省电费，老张记录下了每盏路灯的位置和功率，他每次关灯时也都是尽快地去关…

你有一个大小为 $n\times n$ 的矩阵，矩阵每个格子有一个颜色 $a_{i,j}\le n$。 你喜欢大正方形，但你不喜欢丰富的颜色，具体的，给定讨厌值 $k \le n$，你需要对于所有格子，计算出以这个格子为左上角的最大正方形，满足内部颜色种数不超过 $k$。 你需…

为了在即将到来的晚会上有更好的演出效果，作为 AAA 合唱队负责人的小 A 需要将合唱队的人根据他们的身高排出一个队形。假定合唱队一共 $n$ 个人，第 $i$ 个人的身高为 $h_i$ 米（$1000 \le h_i \le 2000$），并已知任何两个人的身高都不同…

link 考虑 dp 设f[i]表示使序列由全是 1 到满足集合 $P$ 条件所需的最少代价 然后想一想，f[i]怎么推 首先，我们可以把p[i]之前的全部推平，都变成 $0$，然后一个一个变成 1 其次，我们也可以把f[i - 1]搞出来，然后把p[i - 1] + 1到p…

link 由于每头奶牛只会和牛栏起关系，而让我们求最多能分配到多少牛栏，所以我们可以建立二分图 Copy //二分图最大匹配 #include<bits/stdc++.h> using namespace std; const int N = 510; int…

link 比较简单的做法 访问到每一个节点的时候，在儿子节点中求和，找最大值，次大值来维护答案即可 1. 维护 sum 的时候也要判断if(v == fa) continue 2. 不开 long long 见祖宗 Copy #include<bits/stdc++.h>…

货车运输 A 国有 $n$ 座城市，编号从 $1$ 到 $n$，城市之间有 $m$ 条双向道路。每一条道路对车辆都有重量限制，简称限重。 现在有 $q$ 辆货车在运输货物， 司机们想知道每辆车在不超过车辆限重的情况下，最多能运多重的货物。 输入格式 第一行有两个用一个空格隔开的…

[NOI2001] 炮兵阵地 司令部的将军们打算在 $N\times M$ 的网格地图上部署他们的炮兵部队。 一个 $N\times M$ 的地图由 $N$ 行 $M$ 列组成，地图的每一格可能是山地（用 $\texttt {H}$ 表示），也可能是平原（用 $\texttt…

分块含义 分块是一种思想，而不是一种数据结构。 分块的基本思想是，通过对原数据的适当划分，并在划分后的每一个块上预处理部分信息，从而较一般的暴力算法取得更优的时间复杂度。 时间复杂度 分块的时间复杂度主要取决于分块的块长，一般可以通过均值不等式求出某个问题下的最优块长…

某大学有 $n$ 个职员，编号为 $1\ldots n$。 他们之间有从属关系，也就是说他们的关系就像一棵以校长为根的树，父结点就是子结点的直接上司。 现在有个周年庆宴会，宴会每邀请来一个职员都会增加一定的快乐指数 $r_i$，但是呢，如果某个职员的直接上司来参加舞会了…

跑路 小 A 的工作不仅繁琐，更有苛刻的规定，要求小 A 每天早上在 $6:00$ 之前到达公司，否则这个月工资清零。可是小 A 偏偏又有赖床的坏毛病。于是为了保住自己的工资，小 A 买了一个空间跑路器，每秒钟可以跑 $2^k$ 千米（$k$ 是任意自然数）。当然，这个机器是用…

link 对于每个第一行的点进行 bfs，算出它能够到达第 n 行的区间 这个区间一定连续，因为如果不连续那么第一行就会输出 0 而不是 1 了 然后卡卡常数 （好吧我是针对数据编程） （开 O2 不 tle 但是 wa 了，一看判断哪些点走不到写错了） Copy #inc…

link 线段树 考虑两个 tag，mul 与 add 表示[l, mid] [mid + 1, r]这两个区间分别需要* mul + tag 下传标记的时候[l, mid] [mid + 1, r]这两个子区间的 tag，mul tag 直接*mul[u]，add…

题目描述 在大学里每个学生，为了达到一定的学分，必须从很多课程里选择一些课程来学习，在课程里有些课程必须在某些课程之前学习，如高等数学总是在其它课程之前学习。现在有 $N$ 门功课，每门课有个学分，每门课有一门或没有直接先修课（若课程 a 是课程 b 的先修课即只有学完了课程…