histcat

暴力合并每个数和另一个数，算一下要加上多少才能符合。 看着时间复杂度很迷惑，实际上模板题跑的还是很快的。 不过可能又被卡的风险，据 zhx 说 n 越小越容易卡，不过顶多卡一个点（ Copy #include<bits/stdc++.h> #define int long…

在一个圆形操场的四周摆放 $N$ 堆石子，现要将石子有次序地合并成一堆，规定每次只能选相邻的 $2$ 堆合并成新的一堆，并将新的一堆的石子数，记为该次合并的得分。 试设计出一个算法，计算出将 $N$ 堆石子合并成 $1$ 堆的最小得分和最大得分。 $1\leq N\leq…

首先说一些写本文时的悲惨经历，一开始我是使用 Gridea，编辑也是用它的编辑器，但是，在一次写作中，电脑无征兆地蓝屏了。我重启之后发现 md 文件打不开了，查看了一下二进制全是 0 emmm（编写过程中保存了！！）。自此我换成了 hexo emmm。 符号定义 首先我们定义一些…

题目背景 NOIP2015 普及组 T3 题目描述 一条狭长的纸带被均匀划分出了 $n$ 个格子，格子编号从 $1$ 到 $n$。每个格子上都染了一种颜色 $color_i$ 用 $[1,m]$ 当中的一个整数表示），并且写了一个数字 $number_i$。 定义一种特殊的…

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

给定一个长度为 $n$ 的序列，第 $i$ 个元素的下标为 $i$，值为 $a_i$ 现有 $q$ 次操作，每次给定一个区间 $[l,r]$，求该区间的元素和，并将区间内的所有元素值修改为 $0$ 需要你输出所有操作答案的异或和 由于 $n, q$ 很大…

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

小葱同学喜欢吃糖，小葱买了很多糖。但是小葱买的糖太多了，小葱记不清具体数字了，小葱只记得自己的总糖数是自己记录在笔记本上的 $N$ 个数 $a_1,a_2,\cdots,a_N$ 的最小公倍数。请你帮帮小葱，算算小葱买了多少糖。 对于 $100%$ 的数据，$1\leq N…

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

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 看到这个题，很像 dp 但是它可能有环，所以不能 dp。又因为都是正数，可以考虑用 dijkstra 的形式来做 “dp” dijkstra 需要注意的是，做 dijkstra 的时候需要注意一条边x->y只有在x和y都确定了最小值的前提下才能够更新其他点…

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

首先，结论与证明来自http://oeis.org/A005732/a005732.pdf，这里给出简单翻译和加工 结论 给出结论，在一个圆上取 $n$ 个点相连，构成的三角形个数为 $C_{n+3}^6+C_{n+1}^5+C_n^5$ 证明 如何证明呢，我们不妨从圆上 n…