(题解由比赛出题人提供，点击右侧“本文相关内容”的题目即可开始做题） T1 最大乘积最优解一定是拆分成若干个3+一或两个2的形式，直接计算即可。 T2 简单多边形因为保证面积不为0，所以通过相邻两两点的叉积之和的正负性就可以判断逆时针还是顺时针。 T3 因式分解这题是G的一个子问题，详见G。 T4 矩阵  T5 Pocky游戏  T6 Alice收集玩偶设一共获得了t个小猫玩偶，那么答案就是 。这是两个单调函数取min。两个单调函数取min之后是不超过两段的分段单调函数。这样就可以分类讨论出最大值。 T7 因式分解2  其他疑问可加以下交流群（加入一个即可啦~）牛客多校算法训练营1：45379...

(题解由比赛出题人提供，点击右侧“本文相关内容”的题目即可开始做题） T1 长方体设三条边长度为a,b,c设ac围成的面积是x,bc围成的面积是y,ab围成的面积是z,则则答案为4*(a+b+c). T2 好位置  T3 操作数  T4 经纬度先将两个点的经纬度转化为直角坐标系系中的坐标,球心为原点,然后直线距离可以直接算出 球面距离,可以通过原点到 个点的向量算出夹角,然后便能算出球面距离. T5 求长度  T6 玩游戏  其他疑问可加以下交流群（加入一个即可啦~）牛客多校算法训练营1：453799454牛客全国算法训练营2：330766563牛客多校算法训练营3：934889305

(题解由比赛出题人提供，点击右侧“本文相关内容”的题目即可开始做题） T1 字典序最大的子序列我们让循环一开始的起始位置为0 。然后做26次循环，从'Z'到'A'。若当前循环的字符为k，我们从起始位置开始找所 有出现的字符k，每出现一次就加到答案字符串末尾，然后更新起始位置为当前位置。这样构造出的一定是字典序 最大的字符串。 T2 漂亮的树我们先考虑前 的数字，由于 ，所以必须调成递增的差值为1的递增序列。我们最朴素的想法是先确定的值，对于不同的 我们算有多少个 ，找最大的那个。这样就把 分成了几个集合。但是这样枚举想想会超时。但是这时你会惊奇的发现，对于在一个集合里的元素 是相同的~。因此我...

(题解由比赛出题人提供，点击右侧“本文相关内容”的题目即可开始做题） T1 吉姆的运算式出这题的目的，主要是想要告诉大家，逗号也是个运算符。 有办法证明，对于一个只含逗号，括号，数字的合法算式，其结果就是就是算式里最右边的数字（可以用数学归纳法证）。由于本题保证测试资料一定是合法算式，所以我们不用真的去解析算式的括号结构，而是直接去找字串中出现在最 右边的数字就行了。如使用的程序语言是C++，我们可以把字串读入后，把括号和逗号都变成空白字元，最后再利用stringstream把新字 串再用数字读入，读到最后一个数字就是答案啦〜 T2 沃老师学生的成绩由于「分数」这个词有歧义，题解内的作文分数都...

(题解由比赛出题人提供，点击右侧“本文相关内容”的题目即可开始做题）   T1 n的约数 发现询问次数较少，考虑搜索 一个数的约数个数即分解质因数后，每个质因数出现次数+1的乘积 搜索的时候f(i,j,k)表示搜索了前i个质因数，现在乘积为j，上一个质因数出现次数为k 贪心的考虑，可以发现用越小的质因数越好，于是k不增 这样就可以搜出来了   T2 区间的连续段 首先发现可以贪心，这样是O( nm )的 由于k固定，考虑数组中每个位置i向最大的j+1使得a[i..j]的和<=k连边 这个连边的结构是个森林 每次查询即查询树的一条链 可以倍增维护 O( nlogn + mlogn )   ...

(题解由比赛出题人提供，点击右侧“本文相关内容”的题目即可开始做题）   T1 幸运数字I 无解的情况非常好判断。 否则答案必然是4或者7。 为什么呢？ 因为比4和7还长的子串出现的次数必然不会比4或7出现的次数的较大值还多，而 这样子的子串在字典序上是不占优势的。   T2 幸运数字II 1到1,000,000,000中的幸运数字最多有 29个。 对于每个幸运数字 x，我们都想知道有多少个 i满足next[i]=x；这样的i其实就是前一 个幸运数字y的后一个数y+1到x的那些，再把边界情况考虑进来即可。   T3 幸运数字III 考虑每次操作x的移动情况。 对于某次操作来说，如果xi为奇数，...

(题解由比赛出题人提供，点击右侧“本文相关内容”的题目即可开始做题）   T1 圆圆 这题就是个数学题，基本上需要具备一些数学上的基础知识，对于sin、cos、单位圆及至少要有基础的理解。如果对于以上的名词陌生的话，建议可以先去浏览对应的wiki页面。 对于任意的实数 的询问，答案会跟 的询问一样         T2 迷宫          T3 文化节              T4 图图        T5 排列    T6 四联通      其他疑问可加以下交流群（加入一个即可啦~） 牛客多校算法训练营1：453799454 牛客全国算法训练营2：330766563 牛客多校算法训练营...

(题解由比赛出题人提供，点击右侧“本文相关内容”的题目即可开始做题）   T1 假的线段树 暴力   T2 假的字符串 每一个串如果有一个串是它的前缀，则肯定不行 否则每次从这个字母向同一个父亲的其他字母连边，表示这个大小关系必须存在 如果出现环，就出现矛盾了 可以通过拓扑排序找环 O( n + |s| )   T3 真的字符串 考虑用后缀平衡树维护这个序列即可 有两种写法 O( qlog^2n + |s1|logn ) O( qlogn + (|s1|+|s2)logn )   T4 求距离 暴力   T5 求最值 可以转换为平面最近点对 O( nlogn ) 由于平面最近点对有1w种乱搞做...

(题解由比赛出题人提供，点击右侧“本文相关内容”的题目即可开始做题）   T1 旅游观光 输出(n-1)/2 构造和样例解释类似   T2 栈和排序 维护一个后缀max,f[i]表示[i..n]的max的位置 每次push(i)时，如果a[f[i]] > a[i]，就把[i+1..f[i]]都push进去 否则pop(i) 可以证明这样是最优的   T3 最长回文 对a、b各做一次manacher。 枚举一个串的回文中心p作为最后拼出来的串的回文中心 有个结论是我们只需要考虑以p为中心的极长回文串 然后二分答案，hash来check在另一个串里面最多选多长的串 O( nlogn )   ...

(题解由比赛出题人提供，点击右侧“本文相关内容”的题目即可开始做题）   T1 珂朵莉的假动态仙人掌 1 2 1 2 1 2 1 2地送即可   T2 珂朵莉的值域连续段 一个子树值域连续当且仅当其子树max-min+1=size DFS一下即可   T3 珂朵莉的二分图 二分图即不能有奇环的无向图，要使得所有的奇环消失，即要删去所有奇环的交上的边。 但是如果删去奇环和偶环的交上的边，奇环和偶环就会重新组成一个新的奇环，所以在偶环上的边是不能删的。 先随便搞个生成树出来，然后对于每个非树边在树上打标记，最后DFS一次即可以实现O( n + m )   T4 珂朵莉的假toptree 暴力   ...

(题解由比赛出题人提供，点击右侧“本文相关内容”的题目即可开始做题）   T1 约数个数的和 答案就是 for( register int i = 1 ; i <= n ; i++ ) ans += n / i; 相当于枚举那个约数，查一下有多少个数有那个约数可以O( n )求也可以O( sqrt( n ) )求   T2 储物点的距离 维护几个前缀和，算算贡献就可以了 大家可以自己推推式子吧 O( n + m )   T3 回文串的交集 考虑容斥一下，求两个不相交的回文子串很好求 枚举一下分割线，然后严格属于两边的回文子串就可以产生贡献 大力差分一下，维护两个前缀和，算算贡献就可以了 ...

(题解由比赛出题人提供，点击右侧“本文相关内容”的题目即可开始做题）   T1 骰子的游戏   T2 购物    T3 随机树    T4 珂朵莉的无向图 30分做法：暴力 60分做法：随便给的部分分，感觉可以根号分治什么什么的吧 100分做法：每次把一堆点加进去BFS即可 复杂度O( a + mq )   T5 珂朵莉的数列 10分做法：puts( “0” ); 30分做法：直接暴力 60分做法：优化暴力 70分做法： 考虑计算贡献，如果有i a[j]的点对( i , j )则会在1 <= l <= i , j <= r <= n的子区间[l,r]中出现，则对答案的贡...

(题解由比赛出题人提供，点击右侧“本文相关内容”的题目即可开始做题）   T1 猴子吃香蕉 二分一下次数，然后用简单数学推导一下就知道这个猴子吃了多久了 注意的事项： 二分的时候两个2e9加起来会爆掉int的如果二分上界设成2e9，那么中间运算有可能爆炸 发现如果这个猴子吃的时间会增长，那么二分的上界是O( sqrt( t ) )级别的 于是特判这里就可以了~   T2 点权和 考虑每次修改的贡献  考虑这次操作x造成的影响： x对自己的贡献： x的节点值会加上deg[x]+1，deg为度数 x对上方的贡献： x的父亲节点的值会加上2 x的父亲的父亲节点的值会加上1 x的父亲节点的儿子值会加上...

(题解由比赛出题人提供，点击右侧“本文相关内容”的题目即可开始做题）   T1 Laptop 可以先按Mi排成降序后，可以保证左侧的M一定比右侧的大。 对于每个j，如果有一个i，使得i<j且Si>Sj那么j就被“完虐”了。 所以我们只要排序后依次判断前面的最大的S是否比Si大就行了。 复杂度O（nlog2n）   T2 Distance 其实搞来搞去还是Manhattan距离，于是是经典问题。 我们可以设Xi=i2 Yi=Ai2 那么就是求Manhattan距离最远的两个点。 由于Xi=i2，所以我们其实可以直接用i来比较X的大小，那么按Y排序后，用2个线段树/树状数组维护Ai2-...