淘天笔试

#淘天笔试# #淘天# #笔试# 考虑换根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;}

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

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

自上周六做完那个笔试一道题都没A出来心里就有被挂的预期了，刚才看了一眼处理得还挺快，值得给个好评。虽然是第一次面试完之后被流程中止，心里难免有点失落，但是因为有预料到所以还好，甚至还松了一口气。或许对我来说快速处理比流程卡在那儿不动勾人心思要好得多。结束就结束了，专心准备其他已经约好的或者正在到来的面试吧。好像听说阿里系的这些笔试结果还会保留到秋招，不知道是不是这么回事。我阿里系的笔试都做得挺烂的，心凉了#淘天##笔试##淘天笔试##挂#

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

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

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

第一题：我猜是贪心，分别统计每个数字的最大值，然后统计每个频次出现的数字数目，然后分别从最大值开始贪心，最后写的，没时间了当前值的频次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 = ...

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

笔试时间：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" ，否则输出 &...

第一题题意 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...

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

淘天集团春季2025届实习生招聘已经正式开启啦，很多同学也已经进入到了笔试环节！淘小天为你送上一份笔试指南！关于笔试说明、笔试时间安排、注意事项等，往下看，你要的答案这里都有！1、笔试对象：海内外院校2025届毕业生（毕业时间 2024年11月-2025年10月）；2、笔试方向：工程研发、算法、数据研发（需参加笔试的岗位清单详见下文）；3、笔试节点：简历评估通过后，面试完成前，您都有机会完成笔试；场次采用“就近安排，支持顺延”原则，若无法参加最近场次，请切勿登录系统点击【开始答题】，笔试入口会自动顺延至下一场，直至您完成笔试；4、笔试机会：每位同学在单个笔试方向下只有一次笔试机会，请同学们提前...

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 ...

第一题：（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...

笔试时间：2024年05月15日 历史笔试传送门：2023秋招笔试合集第一题题目：小红的子序列排列小红拿到了一个数组，她想知道该数组有多少个子序列是排列。由于答案过大，请对10^9+7取模。排列是一个长度为k的数组，其中1到k都恰好出现一次。例如[2,3,1]是排列，而[1,3,3]、[1,5,2,3]则不是排列。子序列指数组取若干元素（可以不连续）按原数组顺序形成的新数组。输入描述第一行输入一个正整数n，代表小红拿到的数组。第二行输入n个正整数ai，代表数组中的元素。1<=n<=10^51<=ai<=10^9输出描述一个整数，代表子序列是排列的数量。样例输入一31 2...