description： n个数 有两种操作 1. 将a[x]的值改成y 2.查询区间l,r中的最大值 以及 最大值出现的次数 solution： 线段树维护最大值的同时，再维护一个出现次数。对于出现次数的修改需要注意：1.初始值为1 2.更新操作时 当结点值改变 出现次数变成 -> 只有当父节点最大值 等于左儿子或者右儿子的最大值时 才能加上次数3.查询时所有与最大值相同区间出现次数都需要相加 code: #include <bits/stdc++.h> using namespace std; #define LL long long #define lson v &...

Jokewithpermutation description 给定一个不含空格的字符串 问字符串能否构成一个1~n全排列 solution： n只有50 说明只有1位数或者两位数 如果字符串长度小于9 说明只有一位数 输出全部就好 算是一个剪枝 其次可以根据字符串长度 计算出全排列最大的数是多少 假设字符串长度为n 则最大数为 (n - 9) / 2 + 9 减去9代表减去个位数 算两位数的个数之后就是dfs ， 先找一位数 ，因为一位数比较灵活可以先构成 ， 用数组标记一下是否出现过，判断的时候 有全排列最大数跑看看每次是否出现过即可 ，存答案用vector方便更新 code： #inc...

装货物 description： n个物品 x个可容纳体积为w的箱子 问n个物品是否能全部装进箱子内 物品不可拆分 solution： n只有21 可以状压dp或者dfs 这里直接采用dfs 先预处理x个箱子的体积为w 然后从第一个物品开始搜加上一些剪枝 从大的开始放 你大的肯定没有小的更加灵活 所以大的先存 code： #include <bits/stdc++.h> using namespace std; #define LL long long #define ULL unsigned long long #define mes(x, a) memset(x, a, ...

打Boss description： 题目说的很明显了 solution： 对于这种回合制问题 一般都采用让最后一回合来计算。首先特判一些特殊情况 ：1.玩家一下就可把Boss打死 输出Yes2.Boss一下就可把玩家打死 输出No3.玩家的攻击力还没回血高 输出No 然后我们计算一下玩家能挺过多少轮 很明显是除一下 取模一下采用刚刚提到的让最后一回合 其余的回合都是ak1 - m 攻击减去回血 最后一回合除去回血 因为如果你已经打死Boss就不能回血了否则下一步你就已经死了 如果造成的伤害大于血量就代表成功 否则失败 code： #include <bits/stdc++.h&gt...

link: https://ac.nowcoder.com/acm/contest/5961/B description: n个序列 每个序列有m个数 他们都是k的整数次幂 n个序列中所有数相乘乘积最大的值是多少 取模后输出 solution: n和m范围不大 可以接受n * m 如果暴力计算的话 会因为取模操作而导致 大的数取模后变的比原来小的数更小 所以没法直接暴力关键点在于他们都是k次幂 我们可以计算每个序列的指数之和 即 a[i][j] = k ^ pw 计算每个序列pw之和 取最大的 最后快速幂一下就可以得到答案了如何快速得到指数pw 并且判断是否和a[i][j] 是本题关键 a[i...

link https://ac.nowcoder.com/acm/contest/6112/C description： 有个n个数 希望求一个x 使得每个数 +x 的gcd 值最大 ，求出gcd值 和 最小的x solution： gcd的性质： gcd(x,y) = gcd(x,y - x) 三个数也是一样从这个式子可以看出所有数+x之后 他们之间的差值不变 并且 gcd的值也不会变所以求出他们的差分数组 将差分数组gcd就是最大的gcd值求的x 就是要在数组中一个最小的数 使得它变成gcd的倍数 对于每个数 如果本身就可以被整除 答案就是0否则 分成负数和正数 两种情况 处理%gcd的值...

Touch description: 题意有点难读 具体化的讲就是有n个点，每个点有点权。用这n个点来构造q个无向图，对于每个无向图Ei来说规定属于Ei的点x,y. 满足Valx ^ Valy = k 就会有一条权值为1的边，问点x到点y的最短距离 solution: 首先是异或的一个性质 a ^ b = c <-> a ^ c = b <-> b ^ c = a 这三个是等价的1.当a[x] ^ a[y] == k 时 他们之间有条边 输出1即可2.当a[x] == a[y] 的时候 通过一个中间点来到达 即 k ^ c 判断是否存在 走了2步3. 无法到达code:...

https://ac.nowcoder.com/acm/contest/1085/F description： 一个球浮在水面上，给出R,m，代表球的半径和质量，求浮在水面上的高度 solution： 有浮力定律可得 pgV = mg ,p = 1 所以V = m我们设圆的方程为我们通过横截面圆 根据体积公式底面积 * 高 把横截面圆作为底面积 二分这个高度h就可以得到答案圆形面积公式是 pi * r * r 这个r是会变的 对此我们可以直接对他积分根据圆的方程 r就是圆方程里的x 所以移项一下积分的上下限分别为2R-h,0 设定z = 2R-h最后得到积分出来的公式是 最后的体积还要乘上p...

https://ac.nowcoder.com/acm/contest/1085/G description： n个数m个询问 l,r 问 num(ai)为ai出现的次数 solution： 这题区间问题可以很好的用莫队维护，设定一个vis[i]数组代表出现的次数，关于add操作，每出现一个新的次数 使得之前出现的数对答案的贡献得加上vis[a[x] * a[x] 那么当前这个数对答案贡献为(vis[a[x]] + 1)*a[x] 关于del操作，区间去掉一个数，这个数的出现次数先减去1，那么前面所有与这个数相等的都要减上这个数，然后再减去这个数再乘此时的出现次数 code： #in...

https://ac.nowcoder.com/acm/contest/1085/A description： 一共有n天m个安排，每个安排从l~r天，问最长的休息时间是多少 solution： 一开始想着各种数组标记，mapset乱搞，线段树，由于天数到了1e9，所以计算区间大小肯定要O1得到，正解是我们以左边界为第一关键字，右边界为第二关键字进行排序，遍历所有选项计算区间取最大值。难点就在于如何正确得到区间长度，假设当前存在一个区间l,r是有工作的，我们就有n - r （右端点到右边界） 和 l 左边界和左端点距离。排序后设定初始的边界我们每次只计算靠左边的距离，当所有靠左边的计算完后，就...

https://ac.nowcoder.com/acm/contest/6871/A description： 给出两个数n和k 求是否存在三个数 a,b,c 他们之间两两gcd的值为k 且 a + b + c = n 输出这三个数不存在则输出 -1 -1 -1 solution： n k的范围有1e18 暴力不可取。首先由gcd的性质得到 a,b,c都是k的倍数 所有n%k != 0的话肯定是没办法构成的对于这个k 因为a,b,c都是k的倍数 所以n也是由x个k构成的 显然他们的总倍数是 n/k 我们直接枚举倍数i,j 剩下的倍数就是 n/k - i - j,当他们之间互质时，乘上k后他们之...

题目链接 description： 有n个妹子 分别有a,b值 只有a,b值均大于其他人才能设定为一个阶级的重要程度（具体看题目样例） 列出所有妹子的重要程度 solution： 二维点数问题.想到树状数组，我们只关心他们之间的相对大小，对于维度x采用离散化，然后对维度y降序排序，用树状数组维护当前重要程度最大值，对于每个人按照维度x更新和查询，查询出来的值 +1 是用来区分不同重要程度，选择对应下标存入res数组最后输出 code： #include <bits/stdc++.h> using namespace std; struct node{ int x,y; ...

description： 给出字符串s 将s中的子串a代替成b输出 solution： 所有字符串长度都有1e6 一开始采用O(n) substr寻找子串替换输出 T了一发后面用 find 寻找子串a位置 删除a 插入b O(1)输出更新后的串即可 code： #include <bits/stdc++.h> using namespace std; #define LL long long int main() { ios::sync_with_stdio(0); cin.tie(0),cout.tie(0); string s,a,b; ...

description： 有n个水果 每个水果有个喜爱度ai 求连续最大长度水果喜爱值之和大于0 solution： 首先想到一个双指针 但是无法保证指针的移动就是对于答案有利的1.维护一个后缀max前缀和 判断当前r指针往下走 是否对答案有利 如果sum[l] 也就是l的前缀和< last[r] 也就是r位置的后缀位置max前缀和 就可以保证l~r位置是 >0的 符合条件 继续伸展 反之的话 直接跳过 2.二分 二分的话其实和双指针的思路类似 我们维护一个前缀和sum 正向维护一个ai保存当前最小的前缀和 即ai = min(a[i - 1],sum) 设定二分上界为i+1 下...