淘天笔试

考虑换根DP，先随便找个点做根，每个点只统计这个有根树下它的子树对它的贡献，也就是if(color[u] != color[v]) color[u] += color[v];这样我们只能统计出子树的贡献，我们还需要父亲的贡献，父亲的贡献我们考虑扩展并查集，在dfs过程中顺便合并一下就能够得到每个点所在并查集的size，如果一个点和它的父亲不同颜色，那么就是相同并查集，直接用并查集size减去dp求出的子树贡献就是父亲的贡献，然后第二遍dfs，把每个点任意一种颜色都试一下，我们提前知道子树的贡献是多少，可以根据现在我们变的颜色统计一下现在的子树和，看看父亲跟他现在是不是一个颜色，是的话不加贡献，不然加上贡献，和ans取最大值即可。代码如下：#include# include#include# include#include# include#include# include#include# include#include# include#includeusing ll = long long;using ull = unsigned long long;const int maxn = 1e6 + 5;int fa[maxn],sum[maxn],siz[maxn];std::string color;char col[] = {'R','G','B'};int ans  = 0;int find(int x){return x == fa[x] ? x : find(fa[x]);}void merge(int x,int y){x = find(x), y = find(y);if(x == y) return;siz[x] += siz[y];fa[y] = x;}std::vector g[maxn];void dfs(int u,int fa){sum[u] = 1;for(int i = 0;i < g[u].size();i++){int v = g[u][i];if(v == fa) continue;dfs(v,u);if(color[u] == color[v]){sum[u] += sum[v];merge(u,v);}}}void dfs2(int u,int fa){int sfa = (find(u) == find(fa)) ? siz[find(u)] - sum[u] : siz[find(fa)];for(int i = 0;i < 3;i++){char c = col[i];int s = 1;for(auto& v : g[u]){if(v == fa) continue;if(c != color[v]) s += sum[v];}if(c != color[fa]) s += sfa;ans = std::max(ans,s);}for(auto& v: g[u]){if(v == fa) continue;dfs2(v,u);}}void solve(){int n;std::cin >> n;std::cin >> color;for(int i = 1;i <= n;i++){siz[i] = 1;fa[i] = i;}for(int i = 0;i < n - 1;i++){int u,v;std::cin >> u >> v;g[u].push_back(v);g[v].push_back(u);}dfs(1,0);dfs2(1,0);std::cout << ans << '\n';}int main() {int T;T = 1;while(T--) solve();return 0;}

第一次笔阿里系惨遭零封…想看下各位佬都过了多少…是我太菜了吗

15道选择一题三分，三道编程15+15+25。编程挺难的没有签到题。第一道用类似筛法的方法做的。第二道双指针。第三道树形dp嵌套一个类似背包dp的东西。楼主因为背包dp的数组开成了全局变量，卡了20min总共1h30min交卷

第一题：我猜是贪心，分别统计每个数字的最大值，然后统计每个频次出现的数字数目，然后分别从最大值开始贪心，最后写的，没时间了当前值的频次a  小于等于频次a的所有的数字总数为 m  频次大于a的数字个数（不是总数）为b 如果 a + m + b*a >=k ，那么当前数就是最大的众数 import java.util.*; public class Main {     public static void main(String[] args) {         Scanner in = new Scanner(System.in);         int t = in.nextIn...

第二题用并查集为啥只过了20%，剩下的wa。这题不能用并查集做吗？还是有什么坑的地方？第三题没时间看，分模块提交第一题花的时间太长了

第一题打卡题不说了第二题考虑了三种情况过了48%，应该dp的，做到最后想起来但是时间不够了第三题哈希表超时过了10%，看别人的做法树状数组可解决，但是俺不会。。能进面吗家人们

笔试时间：2025年9月6日往年笔试合集：2023春招秋招笔试合集2024春招秋招笔试合集第一题：构造二次函数给定一个正整数s，请构造一个二次函数：f(x) = ax² + bx + c，使得该函数的顶点处的数值等于s。要求a, b, c ∈ [-100, 100]。输入描述第一行一个整数T (1 ≤ T ≤ 100)，表示数据组数。 接下来T行，每行一个正整数s (1 ≤ s ≤ 10⁴)。输出描述对于每组数据，输出一行，包含三个整数a, b, c，表示所构造的二次函数。要求：-100 ≤ a, b, c ≤ 100，且a ≠ 0。样例输入2110样例输出1 0 11 0 10参考题解二次函...

有没有大佬讲讲思路，第一题是最小回文和，比较简单；第二题，讨厌鬼和俩朋友赛马，感觉特殊情况a=0, a<0都考虑了，但是还是只过了1/3；第三题，树的结点染色，找包含3种不同颜色的长度为2的路径有几条，虽然知道是dfs，但是不擅长，没写出来，o(╥﹏╥)o

技术通用卷，不分测开、开发，进去后可以选择你的方向（前端、Java、C++、OS等），我选的Java。单选7*3'多选8*3'编程题3道，我a了一道，一道暴力手撕通过10%，还有一道没做出来，1.1/3。总体感受：偏难，一个是题量大时间少，1小时40分钟。另外选择题的知识点考的也挺深，不是那种一眼就能想出答案的，我在选择题上耽误的时间有点久。

T3题面：给一个3e5数组,每次询问长度为len的子数组乘积的和，如果子数组乘积>1e9，则视为0.赛后一分钟想出来了，比赛时打了个暴力+线段树注意到1e9大约是2^30， 因此len长度如果>30就直接输出0,30以内做一个记忆化就行，复杂度O(30*n)感觉是以前比赛做过的题，忘了怎么做了。。。---upd: 忘了数据范围了，如果有0,1的话那这样也不行

笔试时间：2025年8月16日往年笔试合集：2023春招秋招笔试合集2024春招秋招笔试合集第一题：混乱的数字给定一个长度为 ( n ) 的数组 ({a_1, a_2, \ldots, a_n})，数组中的元素互不相同。我们希望最后能够按严格从大到小的顺序将所有元素输出。为此，我们决定使用若干个队列来对元素进行整理，每一个队列都是先进先出（FIFO）的结构。整个过程分为两个阶段：分配阶段：按照数组的原始顺序（从 ( i = 1 ) 到 ( n )），选择任意一个队列将 ( a_i ) 放入。然而，如果队列中已经存在元素，则只能将 ( a_i ) 放入与队列中已有元素相同奇偶性的队列中。输出阶段...

笔试时间：2024年04月03日 历史笔试传送门：2023秋招笔试合集第一题题目：小红的数组访问小红有一个长度为 n 的数组 a ，她每次会询问区间 [l,r] 中所有数字拼接起来是否是 3 的倍数。输入描述第一行输入两个整数 n,q(1<=n,q<=10^5) 表示数组长度和询问次数。第二行输入 n 个整数表示数组 a(1<=ai<=10^9) 。接下来的q行，每行输入2个整数，表示询问的 [l,r] 区间。1<=l<=r<=n。输出描述对于每个询问输出一行，若区间所有数字拼接起来是 3 的倍数，则输出 "YES" ，否则输出 &...

里面好多套题，Java，Android，IOS前端都有，任选其一。时间只有100分钟，量大题难，不愧是阿里。总共15道单选，5道多选，3道编程。选择题类型还是数据结构，Linux，数据库，设计模式，计算机网络，以及编程语言，有的不确定的也跳了，怕后面时间来不及。编程题，难度大概是middle middle+ hard，最后一题是真的有点难，耽误了很久。第一题计算异或结果，核心在于找到两个字符串中长度最大的，利用StringBuilder构建即可，在最后比较的时候，从后往前比较，相同补0，不同补1。第二题，小有难度，找数类的题，需要注意的点是，构建二进制数，模拟二进制加法，删除多余的0以及边界特殊条件（我也没处理好）。最后过了90%，怕时间不够，继续做了。最后时间也不多了，也没改进成，感觉是数据范围问题。第三题，难度更高，光读题都好久，好在前两天笔试遇到过类似的，思路有一点点像，当时没写出来，后面复盘的时候看博主解析，知道思路了。所以这次在理解题意上快了很多。这题要不是遇到过类似的，我肯定想不到，用到了快速幂和逆元，都是ACM里的概念，平时leetcode不咋遇到过。剩下需要注意的就是，分类讨论，从0-5一次分解问题，最后debug一会ac。时间所剩无几。总的来说，不愧是阿里，量大题难，感觉得给两个小时才算正常，100分钟真的太赶了。另外也感受到笔试复盘的意义，不会的题，下去再看看别人的解法和解析，不一定啥时候又碰到了。

第一题：（100）（1e5次查询，问n（1e18）是不是立方数和平方数。两次二分或者立方数先打表，平方数二分、(第一题跟2、3题分开的，做完2、3后没法复制到粘贴板了)第二题：（100）求[0,10^r]中各个数位和为y的总数（1<=r,y<=1000）简单的数位dp #include "bits/stdc++.h" using namespace std; const int mod = 1e9 + 7; int main() { int r, y; cin >> r >> y; vector<vector<int> ...

第一题题意 8×8国际象棋棋盘 有一个马和一个象，问再摆放一个旗子放在哪里不会被吃题解模拟即可第二题题意一个王国有n个城堡，n-1条边构成一棵树，树的根是1号节点。树中有m个节点损坏，需要全部修理好。每次选择一个节点修理，会修好从该节点到树根整条路径上的全部节点。问最少需要修理几次。题解dp[i]表示修理好子树i需要的次数。如果子树i的儿子节点有需要修理的，则在修理好每个儿子节点的时候就会自动修理节点i，dp[i]为其子树修理次数求和；如果所有儿子节点都不需要修理，则要判断i节点自身是否需要修理。第三题题意平面整数坐标系上有n个节点。每个节点可以移动到横坐标或纵坐标相同的其他节点上。问需要新增...

笔试时间：2023年9月2日 秋招第一题题目给一个长度为n的数组a，请计算出有多少个四元组(i,j,k,l)满足ai+aj=ak@al(i<j<k<l)?(@表示按位异或)答案可能太大，请对10^9+7取模后再输出。输入描述第一行一个正整数n。第二行n个正整数ai。1<=n<=10^41<=ai<=100输出描述一个整数，表示答案对10^9+7取模。样例输入52 3 1 5 4样例输出1说明满足要求的四元组有(1,2,3,5)。参考题解Java：[此代码未进行大量数据的测试，仅供参考] import java.util.Scanner; public ...

1, 2 纯水题。  判断问号做加法  [n, m] = map(int, input().split()) b = [] k = 0 for i in range(n): s = input() for elem in s: if elem == '?': k += 1 b.append(s) matrixs = [0, 0, 0, 0, 0] for i in range(n - 1): for j in range(m - 1): tt = 0 t = [b[i][j], b[i + 1][j], b[i][j + 1], b[i + 1][j + 1]] for elem in t: ...