CF 1627C-Not Assigning, 1400 / 树的构造与遍历 / 构造一棵树,使得每条边和任意相邻两条边之和都是素数

发布时间 2023-04-21 20:36:40作者: 妃即

CF 1627C-Not Assigning

这个东西坑了我两三个小时:

入度和出度。不能在线判断入度或出度从而决定哪个点是起始点,因为可能现在决定为起点的点接下来的输入中还有点与他连边,且可以作为起点的点被这个点替换掉了,那么即 BUG 了。

收获:

  1. 如果两个素数之和仍为素数,那么其中一个素数必为 2, 比如会出现两个大于 2 的素数相加,而大于 2 的素数都是奇数,相加会得到大于 2 的偶数 X,易知 X 必为合数。
  2. 即使空间没有爆炸数组大小也不要开两倍,能少开就少开,不然可能会因为每次输入 memset 而 TLE,对,两倍也会 TLE