Description 筱玛是一个热爱线段树的好筱玛。筱玛的爷爷马爷在游戏中被筱玛吊打了，于是他恼羞成怒，决定给筱玛出这样一道数据结构题：给定一个长度为nn的数组AA，刚开始每一项的值均为00。支持以下两种操作，操作共mm次 mm次操作结束后，你要告诉马爷AA数组变成什么样子了。由于答案可能会很大，你只需要输出数组AA中的每个数在模意义下的值。 Solution 首先要知道差分是什么（其实我之前也不是很懂）构造数组 那么 即 的前缀和 随后对于原数组 的区间修改可以通过差分实现区间加1就是 这样区间[l, r]内的数字在通过前缀和计算的时候都是原来的数字+1，从而实现区间加的操作 有了这个...

Description 一句话翻译：找到 [0, n] 上符合k进制和-k进制下表示相同的数字个数 Solution 思路：思维、二进制模拟显然，对于k和-k进制下相同表示的数字，在偶数位上必须为0(不妨打个表自己看看)所以只需分析奇数位的排列组合情况，先对n进行k进制下的转换，长度为 , 然后分情况讨论： 当位数是偶数时，只需考虑每个奇位数，有k种情况(0, 1, 2.... k - 1)，所以最终答案是 当位数是奇数时，从高位开始，找每个偶数位中是否存在大于0，如果存在，该位后面的奇数位都是k种情况,否则就是当前奇数位对应数字种情况。当然，这样计算我们会多次计算到000000这种情况，...

Description 《梦三国2》是一款3D MOBA类网游。游戏继承《梦三国》的三国文化背景和基础玩法，并加入许多全新地图和全新竞技玩法。由于人气高，游戏在线人数与日俱增，我们知道当在线人数不断增长的时候，会给服务器带来巨大的压力。已知该游戏***有n名用户，编号从1到n，服务器共有m条服务线，每个用户最多只能登陆一条线，第i条线最多可以容纳v[i]名用户同时在线，且只能给编号在[l[i],r[i]]范围内的用户提供服务。现在希望找出一种合理的资源分配方案，使得同时在线人数最大化，请输出这个最大人数。 Solution 思路:贪心以r坐标为第一关键字，l坐标为第二关键字，val为第三关键字...

Description Abu runs a delivery service where he deliver items from one city to another. As with any business, Abu wants to decrease his cost as much as possible. The further he travel, the more fuel he will use.In any particular day, Abu have k items to deliver. Each item needs to be delivered from...

前情摘要：退役选手，一个人不想读英文题，只做签到题0.0 A. ABB Solution 题意:可以在后面添加字符，使得原串变成回文串，问需要添加的最少字符数。思路：Manacher里的p[i]数组指以某个点为中心的回文半径，利用这个数组就可以做这道题，模板是网上随手复制的。时间复杂度 #include <cstdio> #include <cstring> #include <algorithm> #include <iostream> using namespace std; typedef long long ll; const int ...

Description The company Chris Ltd. is preparing a new sorting hardware called Maximizer. Maximizer has n inputs numbered from 1 to n. Each input represents one integer. Maximizer has one output which represents the maximum value present on Maximizer's inputs. Maximizer is implemented as a pipeline o...

Description windy有一块矩形土地，被分为 N*M 块 1*1 的小格子。 有的格子含有障碍物。如果从格子A可以走到格子B，那么两个格子的距离就为两个格子中心的欧几里德距离。如果从格子A不可以走到格子B，就没有距离。如果格子X和格子Y有公共边，并且X和Y均不含有障碍物，就可以从X走到Y。如果windy可以移走T块障碍物，求所有格子间的最大距离。 保证移走T块障碍物以后，至少有一个格子不含有障碍物。 Solution 数据范围很小，考虑在矩阵上进行搜索。对于每个点，找到所有可达且合法的位置(途中障碍物需要 <= T)的位置，对距离逐一验证即可。难点在于如何将矩阵上的点映射到一...

Description Solution 基础太差了，没想出这题。对于 其实是二进制的不进位运算， 因此有公式。该公式表示 二进制位上均为 1 的相加会进位。那么 其中需要满足 且 与 二进制位上不能有相同的，否则输出-1. Code #include<bits/stdc++.h> using namespace std; typedef long long ll; int main() { ll x, y, t; cin >> t; while(t--) { cin >> x >> y; // a + ...

Description 牛牛考完了四六级，准备分享一下自己的英语学习方法。 牛牛：学习英语最重要的就是背单词，如果你能把所有的单词都记住，那么你的英语就能变成天下第一。 然而牛牛的记忆方法就是把单词的每个字母转换成数字，把A看成1，B看成2，C看成3{}A看成1，B看成2，C看成3，依次类推，然后计算出来这个单词每个字母的和。从此每次想到这个单词，就要先想到这个单词的和，然后想办法凑出这个和。 不久后，牛牛又对自己的记忆方法进行了更新，可以把重复的连续字母进行合并， 比如把ABCABC写成(ABC)2，HHHH写成(H2)2或者H4，这样计算和的时候只需要用里面的和乘个数就可以了，更加方便。（...

Description Little beaver is a beginner programmer, so informatics is his favorite subject. Soon his informatics teacher is going to have a birthday and the beaver has decided to prepare a present for her. He planted n flowers in a row on his windowsill and started waiting for them to grow. However,...

Description 给定一棵n个点的带权树，求树上最长的异或和路径。 Solution 由异或的性质得到 即根据题目要求，只需要找到一个根节点，然后贪心找跟当前二进制位不同的点即可。于是先dfs预处理出根节点到每个节点的异或值，同时建立起字典树然后每次枚举节点 ，在字典树上找最大的匹配结果。 Code #include<bits/stdc++.h> using namespace std; typedef long long ll; const int N = 1e5 + 5; vector<pair<int, int> > G[N]; int ...

Description 小 Z 是 ZRP（Zombies’ Republic of Poetry，僵尸诗歌共和国）的一名诗歌爱好者，最近他研究起了诗词音律的问题。在过去，诗词是需要编成曲子唱出来的，比如下面这首《菩萨蛮》，唱出来的话其对应的音符就是这样的：南 园 满 地 堆 轻 絮， 愁 闻 一 霎 清 明 雨1 1 5 5 6 6 5 4 4 3 3 2 2 1因而可以发现，“1 1 5 5 6 6 5 4 4 3 3 2 2 1”这串音符就成为了研究音律的关键。小Z翻阅了众多史料发现，过去的一首曲子的音调是不下降的小Z想要知道对于一首给定的曲子，如何通过提高音调或者降低音调，...

测试方法 等价类划分法 边界值分析法 错误推测法 常见的有超长混合字符串，全角字符串，数字0以及单引号。 正交分析法 可以有效减少测试点 因果判定法 测试环境 主流的浏览器(包含一些插件)：IE、Chrome、Firefox、360浏览器、QQ浏览器、搜狗浏览器操作系统：Windows系列，Linux，Unix分辨率的兼容性 HTTP接口测试 测试内容 接口——API(Application Programming Interface)URL：htttps://api.douban.com/v2/music/search分别是采用协议htttps + 服务器地址//api.douban.co...

Description Solution 难点在于题目太长了，输出也很麻烦。需要注意到 , 用优先队列每次找最大值显然是不可行的，需要寻找 的做法。对于一个数字 ，如果按照题目将它分成 和 , 如果 , 那么满足 和 基于以上性质，可以开三个队列，分别有： 原来的蚯蚓 分割出来的蚯蚓 分割出来的蚯蚓 那么只要原来的蚯蚓具有单调性，每次只需要找这三个队列的最大值即可至于每次都要增加的长度，我们可以先不加上，等到取出来的时候在加 , 放回去的时候注意要减去 Code #pragma GCC optimize(3) #include<bits/stdc++.h> t...