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

1、看题

第一次组队打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多个队伍

2、签到

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

• 给出一个字符串
• 统计有多少组连着的w，计算个数
  因为题意看错了，字符串可以随机，WA了两次才过掉

然后jyf跟我说I题暴力超时了，然后开始做I题
他看了D和E，F没看
【I-Walking】

• 给出一个矩阵，每个点只能向特定方向走一步
• 求多少个点能走出矩阵
  很简单就是一个剪枝，从边界开始向内枚举，每次打标记O（mn）就行了
  但是开始constCE了一次，后来stringRE了一次。

3、爆零

【D-Router】

• 给出n个点m条边的无向图，求每次删除点i后剩余的图分为几个联通块。n<3e5
  第一个想法是并查集，每次除了有i的边都合并，但是很明显TLE了。
  然后发现可以最开始统计有几个集合，然后每次删除与i相连的边，判断哪些点在环上就不增加，否则增加一个强连通分量。然而tarjan打不来，没写出来。

【J-Matrix】

• 给出一个nm的矩阵，每次选一个ab的子矩阵减1，判断能否让原矩阵全部为0，nm<1e6
  二维差分可以O(1)计算子矩阵的和，然后去枚举就行了？

【F-Design】

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

4、爆零

快结束的时候，才看到的A题
【A-Intelligent】

• 给出一个序列，选出一个无序子集，让里面的数互为倍数，求最大的子集，n的范围2e5
  就还是用dp 数组排序之后dp[i]=max(dp[i的因数]+1，dp[i / i的因数]+1）因数枚举到根号i

【B-Robot】

• 没看题

【E-Network】

• 没看题

【K-Sqrt】

• 没看题

5、复盘

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

文章来源: gwj1314.blog.csdn.net，作者：小哈里，版权归原作者所有，如需转载，请联系作者。

原文链接：gwj1314.blog.csdn.net/article/details/109280156