histcat

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

题目描述 在 $N \times N$ 的棋盘里面放 $K$ 个国王，使他们互不攻击，共有多少种摆放方案。国王能攻击到它上下左右，以及左上左下右上右下八个方向上附近的各一个格子，共 $8$ 个格子。 对于全部数据，$1 \le N \le 9$，$0 \le K \le N…

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

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

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

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

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

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

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

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

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

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

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

link 简单的一个筛法 一个数不能取到，那么它的倍数一定不能取到 看一个数能不能取到，暴力求解就行 不过，要对于每个数预处理出答案 具体看代码 Copy #include<bits/stdc++.h> using namespace std; const int N…

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

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

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

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