P3166 Pal-Palindromes

简要题意: 给出 $n$ 个不同的回文串 $s_1,s_2,\cdots,s_n$，求满足 $s_i+s_j$ 也为回文串的有序数对 $(i,j)$ 的个数。

数据规模: $\sum |s_i| \le 2\times 10^6$。

题解: 容易发现，若两个回文串 $s_i+s_j$ 还是回文，假设 $|s_i| \le |s_j|$（反过来同理），那么必然有 $s_i$ 是 $s_j$ 的前缀，且将 $s_j$ 除去前缀 $s_i$ 后的剩余部分应当仍是回文串。

那么可以先将所有串 $s_i$ 按照长度从小到大排序，依次插入字典树中，访问在字典树上经过的节点所对应的串，用哈希判断拼接后是否为回文即可。

这道题顶多评蓝吧，为什么洛谷上会是紫？我不理解。代码不放了。

P3435 Okr-Periods of Words

简要题意: 对于字符串 $s$ 的每个前缀，求其最长周期。

数据规模: $|s| \le 10^6$。

题解: 假设 $s$ 的长度为 $n$，其周期长度为 $t$，则必然有 $s[1\sim n-t] = s[t+1\sim n]$。那么只需要找到 $s$ 最短的前缀 $=$ 后缀即可。在 kmp 的 fail 树上维护一下即可。

P3439 Mag-Warehouse

简要题意: 给定二维平面上 $n$ 个点，求一个点到所有点的曼哈顿距离之和最小。

数据规模: $n \le 10^5,\ 1\le x_i,y_i \le 5\times 10^8$。

题解: 套路地，将曼哈顿距离转化为切比雪夫距离，对 $x$ 坐标和 $y$ 坐标分开计算，目标点的坐标即为所有点坐标的带权中位数。最后将坐标转换回去时，由于要除以 $2$，可能会有 $0.5$，可以直接枚举周围 $4$ 个点计算。

P3448 Mis-Teddies

简要题意: 有四种型号的 Teddy Bear $A1,A2,B1,B2$，分别有 $N_1,N_2,N_3,N_4$ 只。问存在多少种方案，将这 $N_1+N_2+N_3+N_4$ 只 Teddy Bear 顺序排列并且保证不存在相邻的 $3$ 只型号字母或数字相同的 Teddy Bear，对 $10^6$ 取模。

数据规模: $1 \le N_i \le 38$。

题解: 设 $dp[i][s1][s2][s3][lst1][lst2]$ 表示已经放了前 $i$ 个位置，$A1,A2,B1$ 几种熊分别用了 $s1,s2,s3$ 只，且最后两个位置放了 $lst1,lst2$ 的方案数，容易发现 $B2$ 熊的数量也能计算出，枚举下一位转移即可。

这道题顶多评绿吧，为什么洛谷上会是黑？我不理解。代码不放了。

P3450 Zos-Sophie

简要题意: 给出一个 $n$ 个点 $m$ 条边的无向图 $G$，问是否存在顶点个数不小于 $k$ 的独立集，如果存在，找出顶点个数最多的独立集。

数据规模: $2 \le n \le 10^6,\ 1 \le m \le 3\times10^6,\ n-10 \le k \le n$。

题解: 图的最大独立集是个 NP 完全问题，但是数据给定了 $n - 10 \le k \le n$，那么首先显然有 $O(n^{10})$ 的多项式复杂度算法，即暴力枚举删去的点。为了表述的方便，下文中令 $l=n-k$，即最多能删去的点数；同时令 $d_u$ 表示点 $u$ 的度数。

考虑图上最大独立集的对偶问题，即图上最小点覆盖（用最少的点覆盖每一条边）。如此以来，问题转化为考虑用哪些点去覆盖所有的边。为了防止意义上的混淆，定义集合 $V'$ 表示最小点覆盖中选出的点集。

算法 $\text{I}$ : 我们先任取一个度数 $> 0$ 的点 $u$，并考察是否 $u \in V'$。假设 $u \in V'$ 成立，则将 $u$ 及其相邻的边删去；否则根据最小点覆盖的性质，与 $u$ 相邻的其他点必有 $v \in V'$，将与 $u$ 相邻的所有点 $v$ 及 $v$ 周围的边删去即可。并递归上述操作 $l$ 次，每次操作后判断边集是否为空。

下面分析上述算法的时间复杂度。注意到每次操作必须删除至少 $1$ 个点，所以递归的总层数不超过 $l$。同时显然每层有 $2$ 种决策，所以递归次数为 $O(2^l)$。而由于判断边集是否为空需要 $O(n+m)$ 判断或维护，所以时间复杂度为 $O((n+m)2^l)$，虽然无法通过此题，但相比 $O(n^{10})$ 的方法有了很高的优化空间。

算法 $\text{II}$ : 考虑度数 $> l$ 的点，显然这些点必须 $\in V'$，否则将无法在 $l$ 次内覆盖其连出的所有边。那么可以在一开始删去这些点，如果这些点的数量 $> l$，直接输出 NIE。考察剩余度数 $> 0$ 的点的数量，观察到：

引理 $\text{I}$ : 如果图 $G$ 的所有点度数均 $\le l$，且最小点覆盖大小 $< l'$，则 $G$ 中的边数不超过 $l \times l'$，度数 $> 0$ 的点数不超过 $2\times l \times l'$。

证明显然，考虑每个点覆盖集合中的点都覆盖了 $l$ 条边，即可确定点数和边数的上界。

因此，在删完度数 $> l$ 的点并忽略孤立点后，若残余图 $G'$ 中的点数仍然 $> 2\times l \times l'$，就直接输出 NIE。这样图 $G'$ 的大小就有了明确的上界，即 $|V_{G'}|, |E_{G'}| \le 2l^2$。若在该图中暴力选择 $l$ 个点判断，复杂度为 $O(\binom{2l^2}{l} \times l^2)$。结合算法 $\text{I}$，便能够在 $O(n+m+l^22^l)$ 的时间复杂度内解决此题。

代码有较多的细节，以及一些地方需要精细实现以保证复杂度。

注：随机化算法也能够通过此题，可以见 Claris 的博客。

代码:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86

using ll = long long;
const int N = 1e6 + 10, M = 3e6 + 10;
int n, m, k, sz, mp[N], deg[N];
bool del[N];
set<int> g[N], rec[N];
vector<int> ans;
pair<int, int> edg[M];
set<pair<int, int>> st;
bool check() {
  vector<int> res;
  for (int i = 1; i <= sz; ++i) {
    if (!g[mp[i]].empty())
      return false;
    if (del[mp[i]])
      res.push_back(mp[i]);
  }
  if (res.size() < ans.size() || (res.size() == ans.size() && res > ans))
    ans = res;
  return true;
}
bool dfs(int p, int cnt) {
  if (cnt > k)
    return false;
  if (check())
    return true;
  while (p <= sz && g[mp[p]].empty())
    ++p;
  if (p > sz)
    return false;
  bool ret = false;
  int u = mp[p];
  set<int> adj = g[u];
  for (auto v : adj)
    g[v].erase(u);
  swap(g[u], rec[u]), del[u] = true;
  ret |= dfs(p + 1, cnt + 1);
  swap(g[u], rec[u]), del[u] = false;
  for (auto v : adj)
    g[v].insert(u);
  for (auto v : adj)
    for (auto w : g[v])
      g[w].erase(v);
  for (auto v : adj)
    swap(g[v], rec[v]), del[v] = true;
  ret |= dfs(p + 1, cnt + adj.size());
  for (auto v : adj)
    swap(g[v], rec[v]), del[v] = false;
  for (auto v : adj)
    for (auto w : g[v])
      g[w].insert(v);
  return ret;
}
signed main() {
  read(n), read(k), read(m), k = n - k;
  for (int i = 1, u, v; i <= m; ++i)
    read(u), read(v), edg[i] = minmax(u, v);
  sort(edg + 1, edg + m + 1);
  m = unique(edg + 1, edg + m + 1) - edg - 1;
  for (int i = 1, u, v; i <= m; ++i)
    tie(u, v) = edg[i], ++deg[u], ++deg[v];
  for (int i = 1; i <= n; ++i)
    if (deg[i] > k)
      --k, del[i] = true;
  fill(deg + 1, deg + n + 1, 0);
  for (int i = 1, u, v; i <= m; ++i) {
    tie(u, v) = edg[i];
    if (!del[u] && !del[v])
      g[u].insert(v), g[v].insert(u);
  }
  for (int i = 1; i <= n; ++i)
    if (!g[i].empty())
      mp[++sz] = i;
  ans.resize(sz);
  if (sz > 2 * k * k || !dfs(1, 0))
    return puts("NIE"), 0;
  for (auto p : ans)
    del[p] = true;
  ans.clear();
  for (int i = 1; i <= n; ++i)
    if (!del[i])
      ans.push_back(i);
  write(ans.size()), putchar('\n');
  for (int i = 0; i < (int)ans.size(); ++i)
    write(ans[i]), putchar(" \n"[i == (int)ans.size() - 1]);
  return 0;
}