20240922字节跳动笔试第二题

#字节求职进展汇总#1. 给一个树，若存在边(u,w)和(w,v)，则可以添加一条边(u,v)，求最多可以添加多少边针对每个节点u，计算与其相连的边数sz，则可以添加 sz*(sz-1)/2，O(n)2. 有一个长为n的数组ai，每次询问[l, r]，求所有长度大于等于l小于等于r的子数组之和最大值（注意快读）首先暴力求解所有长为x的子数组之和的最大值，然后维护mx[i][j]表示长度大于等于i小于等于j的子数组之和最大值，后续O(1)查找。总的时间复杂度O(n^2+q)3. 有一个长为n的字符串s，每次可以将si按照字母表的顺序循环右移一位（即a->b, z->a）求使字符串相邻字符都不相等的最小操作数考虑dp。dp[i][j]表示前i个字符满足条件且第i个字符为j时的最小操作次数，对于第i+1个字符遍历a-z（k=0-26），计算操作次数（v=(k+26-s[i+1]+'a')%26）并进行状态更新dp[i+1][k]。时间复杂度O(26*26n)优化：对于dp[i]在计算dp[i+1][k]时，只需要记录dp[i]内最小值及对应字符和次小值即可，若k=最小值对应字符，则用次小值更新dp[i+1][k]，否则直接用最小值更新；同时，k也可以只考虑dp[i]内最小值对应字符，以及除此之外s[i+1]右移操作最少的字符，可以将复杂度降到O(2n)4. 有一个长为n的数组ai，求有多少个严格单调递减的子序列，对10^9+7取余经典的离散化+树状数组问题。将每个ai按大小映射到1-m（记作bi），用树状数组维护以j结尾的子序列个数的前缀和，总的减掉就是以大于j结尾的子序列个数，类似lc315

🍭 大家好这里是 春秋招笔试突围，一起备战大厂笔试 💻 ACM金牌团队🏅️ | 多次AK大厂笔试 ｜ 大厂实习经历 ✨ 本系列打算持续跟新 春秋招笔试题 👏 感谢大家的订阅➕ 和 喜欢💗 和 手里的小花花🌸 ✨ 笔试合集传送们 -> 🧷春秋招笔试合集 🍒 本专栏已收集 100+ 套笔试题，笔试真题 会在第一时间跟新 🍄 题面描述等均已改编，如果和你笔试题看到的题面描述不一样请理解，做法和题目本质基本不变。 🍹 感谢各位朋友们的订阅，你们的支持是我们创作的最大动力 💞 🌈 字节跳动秋招笔试，来啦！！！ 🍥 本次考察的知识点非常全面，树相关/前缀和/动态规...

第二题线段树20%，第四题dp16%，求大佬给点思路。

第4题，离散化后权值线段树。 #define IO std::ios::sync_with_stdio(0),cin.tie(0),cout.tie(0) #define bug(x) cout<<#x<<" is "<<x<<endl #include<bits/stdc++.h> typedef long long ll; using namespace std; #define rs o * 2 + 1 #define ls o * 2 const int N = 2e5 + 5; const int mod...