题目大意

  有一幅 $n$ 个点 $m$ 条边的简单带权无向图，对于每个点 $i$，你要求出一棵生成树，满足：

1. 与 $i$ 相连的边全部在这棵生成树中；
2. 生成树边权和最小。

  $n \leq 10^5,~m \leq 3 \times 10^5,~边权w_i \leq 10^9$
  5s

由来

  2019 年南京 Regional 充分暴露了这个问题，市面上大多数标着 $O(n^3)$ 的 KM 板子实际上是 $O(n^4)$ 的，以致选手如果是用了经典书籍上的板子，或者是网上随便扒的板子，就会 TLE。
  然后最近做题做到了 KM，就想补一个自己的真·$O(n^3)$ 的 KM。网上的 $O(n^3)$ 也都没有教程只能自己啃代码，就想把思路写一下。
  大二了才会 KM 你丢不丢人

题目大意

  有一个长度为 $n$ 的数组 $a_1,\cdots,a_n$，每次选相邻的两个数 $a_i,a_{i+1}$，花费代价 $a_i+a_{i+1}$ 把它们合并成 $\gcd(a_i,a_{i+1})$。求把整个序列合并起来的最小代价。

  $n \leq 2 \times 10^5,~1 \leq a_i \leq 10^{12}$
  2s

题目大意

  你有无限个这种 S 型的牌（一开始都如左上角那样放置），每次你可以选择一张牌，将其 Rotate，或将其 Flip，或将其放入一个 $N \times N$ 的棋盘。棋盘上不能有牌重叠，被操作过的牌最后都必须放入棋盘。

  你有一个计数器，每当执行 Rotate 或 Flip 操作的时候，计数器会加 $1$。
  现在给你最终的棋盘状态（01 矩阵，表示每个格子有没有被覆盖），求计数器的奇偶性。（保证奇偶性唯一）

  $N \leq 50$

题目大意

  平面上有 $n$ 个点，两人轮流博弈。每人每回合画一条线段连接两个点，不能在端点外的地方穿过已画的线段或其他端点。不能操作者输。问先手必胜或必败。

  $n,|x_i|,|y_i| \leq 1000$，可以三点共线，没有重点。
  多测，$T \leq 1000$
  2s

题目大意

  给定一幅 $n$ 个点的二分图。左边的每个点度数至少为 $1$ 至多为 $3$，且左边每个点只会连向右边编号大于等于它的点。
  现在你要选择一些边，限制如下：

• 右边的每一个点都要被覆盖到；
• 有一个 01 矩阵 $A_{n\times n}$，若 $A_{i,j}=1$ 则表示左边第 $i$ 个点和第 $j$ 个点不能同时被覆盖到；
• 对于左边的每一个点，如果它没被覆盖到则代价为 $0$，否则代价为 $M_i^{d_i}$，其中 $d_i$ 表示被它覆盖了多少次。满足上面两条的情况下要使得代价最小。

  求最小代价，或输出无解。

  $n \leq 18,~1 \leq M_i \leq 100$
  多测，$T \leq 10$
  1s

题目大意

  给出两幅 $n$ 个点的无向图 $G_1,G_2$，对于 $G_1$ 的每一棵生成树，贡献是有多少条边在 $G_2$ 中出现。求 $G_1$ 的所有生成树的贡献和。

  $n \leq 400$，4s

新的开始

  11 月沈阳赛区结束，我们莫得出线也莫得 EC，那么 SYSU_FateBlueBird 这支队也 end 了。

题目大意

  一个长为 $n$ 的序列 $a$。
  有 $m$ 个询问，每次询问三个区间，把三个区间中同时出现的数一个一个删掉，问最后三个区间剩下的数的个数和，询问独立。
  注意这里删掉指的是一个一个删，不是把等于这个值的数直接删完，
  比如三个区间是 $[1,2,2,3,3,3,3]$，$[1,2,2,3,3,3,3]$ 与 $[1,1,2,3,3]$，就一起扔掉了 1 个 $1$，1 个 $2$，2 个 $3$。

  $n,m \leq 10^5,~1 \leq a_i \leq 10^9$
  3s，512M

  奋战一星期，造台单周期

从南京回来

  从南京回来，我们就二连银了。
  我们互相说得最多的就是：“求求你做个人吧！”
  做个人，别演了，题要读要沟通，数据范围要看，智商在线一点，我不信我们连金牌队都不是。
  心好累的，不敢奢望什么校排、出线啥的，至少先把金保了，帮队友保个研。

题目大意

  有一个 $6 \times 6$ 的网格图，每个格子上有一根柱子。
  现在有 $n$ 个盘子套在 $(1,1)$ 的柱子上，自底向上分别为 $a_1,a_2,\cdots,a_n$（构成一个大小为 $n$ 的排列）。
  每次操作你可以选择一根柱子，将其最上面的连续若干个盘子拿起，往下走一格或往右走一格。
  请构造一种方案使得盘子最后有序套在 $(6,6)$（自底向上是 $n,n-1,\cdots,1$）。

  $n \leq 40000$

题目大意

  有 $n$ 个布尔变量 $x_1,\cdots,x_n$，在一组约束下恰好有三种赋值方式。
  约束是形如 $x_i \to x_j$ 这样，$x_i$ 可以是 $!x_i$，$x_j$ 可以是 $!x_j$。
  现给出这三种赋值方式，请构造出一组约束。

  $n \leq 50$，你构造的约束数量 $\leq 500$

题目大意

  一个序列是好的，当且仅当，若两个元素相等，则它们之间的所有元素都相等，比如 $[3,3,3,4,1,1]$。
  现在有一个初始序列 $a_1,\cdots,a_n$，你要把它修改成好的。如果你把一个值为 $x$ 的元素改成 $y$，那么所有值为 $x$ 的元素都要改成 $y$。求最少需要修改多少个位置。
  在 hard version 中，还有 $q$ 次单点修改，每次修改都要回答一次。（在 easy version 中，$q=0$）

  $1 \leq n,a_i \leq 2 \times 10^5,~0 \leq q \leq 2 \times 10^5$
  5s

  赛季才刚开始，不能说太多伤心的话，简单写写记记就好了吧