E—小苯的数组构造 思路： 首先容易知道 y > x 或者 n=1 && x != y 情况下是 NO 其次如果 x 在二进制下某一位是 0，但是 y 在二进制下这一位是 1，也是 NO 再看 x = y 的情况，还是比较好想的   n 为奇数，那么就先输出 x，再随后输出 n-1 个相同的数，n-1 是偶数，所以它们异或结果为 0，最后异或结果为 x   n 为偶数，先输出 lowbit(x) 以及 x - lowbit(x)，然后又是输出 n-2 个相同的数   x = y 还需要特别注意 x 是 2 的幂且 n 为偶数的情况，这种情况是 NO 如果 x != y，同...

比赛主页：牛客练习赛135 目录  A题 B题 C题  A A题链接 题意： 给定两个数字 x、y，满足 2*x <= y，问 [1, n] 内有多少个数 z，满足 z/x = z/y 思路：  打表发现 cnt = min(x-1,n) 如果 z 小于 x，那么 z/x 以及 z/y 都是 0，如果 z >= x，那么 z/x 相比 z/y 结果就会不同  // https://ac.nowcoder.com/acm/contest/103151/A #include <bits/stdc++.h> using namespace std; #define int l...

E-小苯的水瓶 原题：E-小苯的水瓶 题意： 给定 n 个水瓶，每个水瓶有一些水，这些水瓶可以倒水给其他水瓶，但是转移的总和不能超过 m，可以操作任意次，此外还有 k 的水量可以分配给这些水瓶，最后小红会喝掉水量最少的水瓶里的水，问小红最多可以喝多少水 思路： 如果 小红最多能喝 h 的水，那么 h-1, h-2 .... 比 h 少的水量他肯定可以喝到这么多水，满足单调性，可以二分。 check 函数就是把 < limit 的水瓶需要的水量全部加起来，记为 need，另外把多的加起来记为 res，再加上 k，看 need 与 min(res,m)+k 的大小 // https://ac...

E—全都要！！！！！ 原题：E—全都要！！！！！ 题意： 给定 n 个数，从 0 开始向前移动，每次移动距离为 [1, 6]，移动过程 sum += a[i]，求经过确切的 k 次移动后 sum 最大值是多少？（进入数组需要一次移动） 思路： dp dp[i][j] 表示移动到 i 位置，移动 j 次的最优答案  遍历数组，枚举 j（因为要确切地移动 j 次，所以如果 i<k 那么就不能更新答案） 比较 i 的前 6 个位置，取最大值，注意不能越界  // https://ac.nowcoder.com/acm/contest/102896/E // dp[i][j] 表示前 i 个位置...

比赛主页 目录  B. Perfecto C. Trapmigiano Reggiano D1. Infinite Sequence (Easy Version)  B. Perfecto 原题：B. Perfecto 题意： 构造一个长度为 n 的排列，满足从 1 到 n 的所有位置的前缀和都不是完全平方数。 如果不行，输出 -1. 思路： 如果直接构造 1，2，3，4，......，n，为什么有的位置不满足条件？   首先判断 [1,n] 的累加和是否是完全平方数   否则，遍历序列，不满足条件的位置跟它的下一个位置交换，即 swap ( a[i], a[i+1])  i 一定不会是最后一...

补题链接 1-5届 https://www.nowcoder.com/exam/company 第六届  初赛第一场的补题链接：https://ac.nowcoder.com/acm/contest/71300 初赛第一场题解：https://ac.nowcoder.com/discuss/1241427 初赛第二场，12月10日题解：https://www.nowcoder.com/discuss/563702942105190400 复赛第一场的题解+补题：https://ac.nowcoder.com/discuss/1246063 复赛第二场（2023年12月23日）补题+题解链接：h...

I-小鸡的排列构造的checker 原题：I-小鸡的排列构造的checker 题意： 给定一个长度为 n 的排列以及 m 次询问，每次询问给出 l, r, c，分别表示查询的区间 [l, r]，查询的下标 c，问在区间 [l, r] 内进行从小到大排序，原来下标为 c 的数经过排序后的下标是多少？（下标是对于整个数组来说的，不是对于区间来说；每次查询不会改变原数组的位置） 思路： 树状数组离线查询  查询 [l,r,c] 相当于问 [l,r] 区间有多少个小于等于 p[c] 的数 因为比 p[c] 小的数将要排在 p[c] 前面，再加上左边界 - 1 就是答案 对于样例 [1, 4, 9, 2...

C-小L的位运算 原题：C-小L的位运算 题意： 给定三个二进制数 a, b, c，可以进行以下几种操作：  花费 x，反转 a 或 b 中的任意一个数位 花费 y，交换 a 或 b 中的任意两个数位  要使得 a⊕b=c，最小的花费是多少？ 思路： 对于某个位置，共有 4 种情况：00，01，10，11，通常情况下，这 4 种情况都可以通过一定的交换方法来各取所需，最多剩下 1 个落单的，对于任意一种类型，都可以通过其他 3 种类型来抵消，可以举例子看看；但是可能会存在某个类型的数量 > 其他 3 种类型的总和，那么多出来的就只能单独反转了。  #include <bits/st...

C1. Skibidus and Fanum Tax (easy version) 原题：C1. Skibidus and Fanum Tax (easy version) 题意： 给定一个长度为 n 的数组 a 以及长度为 m 的数组 b，对于数组 a 中的每一个数，最多可以进行一次以下操作：  选择数组 b 中的一个数，将 a[i] 替换为 b[x] - a[i]，即 a[i] = b[x] - a[i]  问数组 a 是否可以经过以上操作，使得数组 a 变成非递减数组，即 a0 <= a1 <= a2 <= a3 ...  easy 版本 m = 1.  思路： 对于每...

C-智乃的Notepad(Easy version) 原题：C-智乃的Notepad(Easy version) 题意： 给定 n 个字符串，问最少敲击多少次键盘，才能使得每个字符串都在屏幕上显示过。  字符串在屏幕上有效显示，当且仅当屏幕上只有该字符串 敲击键盘意思为从键盘上输入 26 个字母以及删除键  思路： 题目明显涉及到字符串前缀，那么就会联想到字典树，可在草稿纸上用样例创建一颗字典树，有利于理解。 最优解是留下最长的字符串，就是屏幕上最终显示最长的字符串； 假设所有的字符串都在屏幕上输入并且被删除，即求和：s[i].size()*2，这就是最原来的结果，计为 sum，通过排序后，可...

比赛主页 E-Tokitsukaze and Dragon's Breath 原题：E-Tokitsukaze and Dragon's Breath 题意： 寻找矩阵中的一个点，使得这个点向左上、右上、左下、右下四个方向延伸出的 "X" 型的权值累加和最大，输出最大值。 思路： 对于 "X" 型，可以分成往左倾斜、往右倾斜。  往左倾斜： i - j 相等 往右倾斜： i + j 相等  分别记录两种对角线的每一条对角线的权值累加和，然后遍历矩阵每一个点，取最大。 #include <bits/stdc++.h> using namespa...

H-一起画很大的圆 原题：H-一起画很大的圆 题意 给定一个矩形区域，在矩形的边界上找到 3 个整数点，使得过这 3 个点画出的圆面积最大，输出这三个点的坐标。 思路 三个不共线的点确定一个圆。 如果这三个点越接近一条直线，这个圆最大。 要使得圆尽可能大，那么这三个点尽量趋近于在一条直线上，就是三个点连成的角尽可能大，越接近 180° 越优。  横着的矩形   (a,d-1), (b-1,d), (b,d)，其他的方位也行   竖着的矩形   (a,c), (a,c+1), (a+1,d)，其他的方位也行  // https://ac.nowcoder.com/acm/contest/9533...

目录  J-硝基甲苯之袭 H-井然有序之窗 M-数值膨胀之美 E-双生双宿之错 C-兢兢业业之移  J-硝基甲苯之袭 原题：J-硝基甲苯之袭 题意： 给定一个数组 a，问存在多少对 (i,j) 满足 a[i] xor a[j] = gcd(a[i], a[j])。 题解：   对于两个数的 gcd，gcd 一定是这两个数的因子，所以去遍历其中一个数的因子，用 x 以及它的因子 p 来表示 y，即 y=x^p，代入到式子，看知否成立   为啥呢？   X xor Y = gcd(X, Y)，令 P 表示 gcd，我们知道，P 一定是 X 的因子，所以 X xor Y = P，又因为异或满足 Y ...

题目：二叉树 题意 已知一颗二叉树有 n 个结点，问能构造出多少种高度不超过 m 的二叉树。 题解  对子树分治，左孩子依次为 0 ~ n-1 个结点，右孩子就是 n-1 ~ 0 这样去分治 n=0，那就是空树，就是 1 种方案 m=0，高度为 0，除了空树，不可能有高度为 0 的树，方案数为0 左右孩子一起分这 n-1 个结点，总数要相乘，乘法原理嘛  记忆化递归 int dp[55][55]; int fun(int n, int m) { if(n==0)return 1; if(m==0)return 0; if(dp[n][m]!=-1)return dp[n][m]; int an...