A 题 简单的贪心，不妨令 和 分别表示 V 和数量和 I 的数量。 的时候就直接先输出所有的 V 然后再输出所有的 I 即可。 否则就尝试先用 V 填满前面的尽可能多的数字位，然后考虑将 I 先用来占没有填满的位，如果还有富余的 I 就尽量往前面的数字位 就完事了。 #include <bits/stdc++.h> using namespace std; inline int read() { int x = 0, flag = 1; char ch = getchar(); for( ; ch > '9' || ch < '...

题目并不难，没有人AK我觉得主要是因为 T3 的题意不清晰，非常抱歉。 先说声对不起！因为出题人的语言描述能力不强，导致T3的题意出现大锅，深感抱歉！相比之下T4的数据范围问题倒是小锅了(小声bb。 A:二进制？十进制！ 按照题意模拟即可,签到题。 前 是给没有开 童鞋的。 满分和 分只差一个 满分代码：运行时间:2ms，内存占用：424kb (牛客网评测机评测结果，下面的不再赘述) #include <iostream> int main() { long long A,B,c = 0,d = 0,flag = 1; std::cin >> ...

题目并不难，没有人AK我觉得主要是因为 T3 的题意不清晰，非常抱歉。 先说声对不起！因为出题人的语言描述能力不强，导致T3的题意出现大锅，深感抱歉！相比之下T4的数据范围问题倒是小锅了(小声bb。 A:二进制？十进制！ 按照题意模拟即可,签到题。 前 是给没有开 童鞋的。 满分和 分只差一个 满分代码：运行时间:2ms，内存占用：424kb (牛客网评测机评测结果，下面的不再赘述) #include <iostream> int main() { long long A,B,c = 0,d = 0,flag = 1; std::cin >> ...

题目并不难，没有人AK我觉得主要是因为 T3 的题意不清晰，非常抱歉。 先说声对不起！因为出题人的语言描述能力不强，导致T3的题意出现大锅，深感抱歉！相比之下T4的数据范围问题倒是小锅了(小声bb。 A:二进制？十进制！ 按照题意模拟即可,签到题。 前 是给没有开 童鞋的。 满分和 分只差一个 满分代码：运行时间:2ms，内存占用：424kb (牛客网评测机评测结果，下面的不再赘述) #include <iostream> int main() { long long A,B,c = 0,d = 0,flag = 1; std::cin >> ...

做法 关于树链剖分我也不知道该怎么讲了，有许多博客比我讲得好，如果你是还没有学习树链剖分的同学的话，在这里安利博客： OIWIKI 神佬的博客 （这里指的是轻重链剖分） 这里总结一下： 适用情况 对于一条路径上的值进行修改 查询一条路径上的一些具有可以进行区间维护的性质的东西(比如求和，最大值) 额外的例子: 查询一条路径中的元素种类总数 查询一条路径中大于一个给定的值的数的个数(树链剖分后套权值线段树 or 主席树) 查询路径中第大的数 对于一棵子树中的值进行修改 查询一棵子树中的一些具有可以进行区间维护的性质的东西(比如求和，最大值) 上面四种是最裸的树链剖分。直接上树链剖...

[HAOI2011]Problem b 题意 组询问，给定 , 求 并且 = 的数对数量。 () 解题思路 定义 表示 并且 满足 的数对数量。 容斥易得，本题的答案即是： 那么现在我们的目标是在 的时间内快速求出 考虑对于原式进行化简，原式即： 首先是把原式里面的 提出来： 下一步则是 转化为 : 又因为 : 等价于 && 然后我们可以知道， 内的所有数中 的倍数一共有 个。所以式子进一步化简： 现在就可以整一个整除分块乱搞哩！1 #include <bits/stdc++.h> usin...

前言 这个数据结构(或许不是数据结构?)比较冷门，网上也没找到什么博客。我尽量讲得详细。 做一道CF的题目的时候就遇到了"操作树"。 这东西蛮简单的，但是有些时候却挺有用的。 一般可以用操作树的题目： 允许离线（这是最重要的） 需要查询历史版本 当前操作受到之前操作的影响。 需要维护的状态不是那么复杂 操作树的定义： 对于操作树上的节点 就存储操作 完成之后的状态。 操作树该怎么建? 以这道题目为例： CF707D Persistent Bookcase 题意搬运： 维护一个二维零一矩阵（），支持四种操作（不超过次）: 将 置 将 置 将第 ...

前言 不难的线段树题，散发着一股浓浓的套路的味道。 题目分析 首先可以知道 ”我们小学二年级就学过的“ 等差序列求和公式（这个真的是小学二年级的 (doge 然后对于本题的操作一进行分析： 不妨假设修改的区间为: 倘若这个区间包含了一个线段树节点 , 这个节点的区间左端点为 , 区间右端点为 , 那么节点 的区间和就是 (首项 加 末项) * 项数 / 2 这个公式我们耳熟能详 这里的 首项 就是 , 末项 就是 ，项数 就是 。 整理一下就是 : 那么很明显，我们需要记录每次修改的区间左端点 以及给定的 , 于是我们在线段树的懒标记中开两个数组分别记录每...

解题思路 数据结构优化 前置知识：线段树区间修改 / 区间求最小值 + 看到本题，我们首先要想最暴力的状态设置以及转移方程式。令 表示在第 个村庄建设第 个基站同时 只考虑 前 个村庄的最小费用。 ps.这里的"只考虑"指的是只计算前 个村庄的补偿款或者建设基站的费用。 不难想到状态转移方程： 表示的是第 个村庄到第 个村庄都不修建基站的补偿费用。 这样子的空间复杂度是:O的，时间复杂度是 o() 的，显然通过不了本题。 我们可以优化这个 过程。 首先最简单的就是优化空间（其实优化不优化都能通过本题。不过作为一名Oier，这你能忍？ 考虑到我们用的只有...

[CF597C Subsequences] 前言 这是一道数据结构优化 的入门题，但是也很有意思。 前置知识：线段树维护前缀和（区间加法，单点求值） 题解正文 题目大意： 给定一个长度为 的序列 以及一个数 ，求其长度为 的上升子序列的数量。 思路: 首先我们看到本题，不难想到经典问题：最长上升子序列。（但是其实关系不大） 在解最长上升子序列的时候我们一般用的是 的算法，但是实际上还存在一种被不屑的 求最长上升子序列的方法。 对于 的方法稍加魔改变形就可以得到本题的 做法。 : 设置状态: 表示前 个数中，以 结尾的长度为 的上升子序列的数量。 转移方程: ...

不错的背包题。 题解正文 首先我们最朴素的想法是什么？ 枚举每一个美味值以及每一个卡路里值，用 bool 数组存下来判断是否可达，这样子的空间复杂度是 O() 的，时间复杂度是: O()的。 首先上面的做法肯定是不行的，那么怎么办呢？ 想到要满足最后的 ，就不难想到将 作为 背包的重量，然后 作为价值，最后 即是答案。我们可以正负分开处理，对于 的 按照正常的 背包转移，将 的将 视为 开另外的背包来跑，这两个 数组代表的意义分别为：质量为 的时候的最大价值以及质量为 的时候的最大价值。 那么 表示的就是最终的答案，遍历整个 数组取 即可。 #include ...

CF1183H Subsequences (hard version) 题意： 给定一个长度为 () 的字符串 以及 一个数字 ()，规定串的每个子序列的价值为 ，现在要求你求出 个本质不同的子序列使得价值最小。 ps.本质不同 指的是：子序列的内容不同，而不是单纯的子序列的位置不同。 具体做法 这是一道不难的 。 不难发现题目的意思实际上就是让我们求长度为前 长的本质不同的子序列，找出每个长度对应有多少个本质不同的子序列即可。 所以问题就在于找本质不同的子序列。 怎么找呢？遇事不决， 来解。 考虑设置状态如下: 表示的是原串的前 个字符中长度为 的本质不同的子序列数量。 接下...

CF519E 【A and B and Lecture Rooms】 前言: 你可能需要用到的前置知识点: 倍增求 (或者说是树上倍增？) 正文 题目大意: 给定一棵树，以及 个询问，每次询问的形式是给定两个点 ，求有多少个点 满足 题目不难 ，但是要分类讨论清楚也不是那么容易。 无根树，我们假定 号点为根即可。 下面约定概念: 表示 点的深度。 表示 为根的子树的大小。 然后我们开始分类讨论(下面假定 ): . 输出点的个数即可。所有点均满足条件。 . 意味着 是 的祖先节点。 不难发现，倘若 到 中间有偶数个点的话，是没有答案的，输出 倘若 , 中间...

题目并不难，没有人AK我觉得主要是因为T3 的题意不清晰，非常抱歉。 先说声对不起！因为出题人的语言描述能力不强，导致T3的题意出现大锅，深感抱歉！相比之下T4的数据范围问题倒是小锅了(小声bb。 A:二进制？十进制！ 按照题意模拟即可,签到题。 前 是给没有开 童鞋的。 满分和 分只差一个 满分代码：运行时间:2ms，内存占用：424kb (牛客网评测机评测结果，下面的不再赘述) #include <iostream> int main() { long long A,B,c = 0,d = 0,flag = 1; std::cin >> A...