ICPC2020小米网络选拔赛第一场复盘

第一次组队打ICPC，可能任务分配上还有待优化

但是有个团队，感觉安心好多。

我们有三个人，开始是分开来，每人看三题

djn看ABC，jyf看DEF，我看GHI，JK没人看

我开始只来得及看了GH，但是发现都不太可做

【G - Tree】

给出两个长为n的序列

构造一颗无根树，满足第一个序列为树的拓扑序，第二个序列为树的先中后序遍历。

输出一种可能的建树方案，无法构造输出NO

序列n长度<2e5

【H-Grouping】

给出一个数字n，2n个整数。

将其随机分为n组，每组两个数。将两个数作差得到n个权重，求n个权重的方差得到一个w值。

不同分组方式的w值取平均对998244353取模得到答案.

大约过了半小时

好多队伍ak了，签到题出来了

CI，DJK都是过了500多个队伍的

甚至ABF都过了200多个队伍

先是djn跟我说C很简单，我开始调C（她看了A和C,B没看完）

【C-Smart】

给出一个字符串

统计有多少组连着的w，计算个数

因为题意看错了，字符串可以随机，WA了两次才过掉

然后jyf跟我说I题暴力超时了，然后开始做I题

他看了D和E，F没看

【I-Walking】

给出一个矩阵，每个点只能向特定方向走一步

求多少个点能走出矩阵

很简单就是一个剪枝，从边界开始向内枚举，每次打标记O（mn）就行了

但是开始constCE了一次，后来stringRE了一次。

【D-Router】

给出n个点m条边的无向图，求每次删除点i后剩余的图分为几个联通块。n<3e5

第一个想法是并查集，每次除了有i的边都合并，但是很明显TLE了。

然后发现可以最开始统计有几个集合，然后每次删除与i相连的边，判断哪些点在环上就不增加，否则增加一个强连通分量。然而tarjan打不来，没写出来。

【J-Matrix】

给出一个nm的矩阵，每次选一个ab的子矩阵减1，判断能否让原矩阵全部为0，nm<1e6

二维差分可以O(1)计算子矩阵的和，然后去枚举就行了？

【F-Design】

一直没看到题面，但是好像A了好多人

快结束的时候，才看到的A题

【A-Intelligent】

给出一个序列，选出一个无序子集，让里面的数互为倍数，求最大的子集，n的范围2e5

就还是用dp 数组排序之后dp[i]=max(dp[i的因数]+1，dp[i / i的因数]+1）因数枚举到根号i

【B-Robot】

没看题

【E-Network】

没看题

【K-Sqrt】

没看题

一共11题，4题没看，2题看了个寂寞，看的5题里面过了4题样例，2个AC。

网络

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。