ultmaster edited 7 年前
改编自蓝桥杯 2015，但其实跟原题没啥关系，除了用了它的图，因为我懒得画图。。。
这道题可以算是一个趣味题吧。如果说太一脸懵逼倒也不见得。做法当然很多啦，最经典的例如：
int ind = 1;
for (int i = 0; i < m; ++i)
for (int j = 0; j < n; ++j)
a[i][j] = ind++;
行末不要多空格。当然还有很多奇怪的做法。你非要来考验我的 checker 我也不反对。当然 checker 有可能写错了，不过我觉得写错的概率并不大。
肯定有同学会担心会不会 FST (Failed System Test) 啊之类：除非你 CE 了吧？请注意，在这种题上纠结太久会直达 GG。好了，下一题。
类型：adhoc
来自 Greater New York 2016。
本来想会不会有人想用线性的做法的，直接枚举嘛。后来想想这种事情根本不可能，你会枚举还不会用二进制？做法就是把二进制中的每一位（除了最高位的 1）都拿到。然后令 p = q = 1，从最高位（除了最高位的 1）往下走，如果是 0，就向左，如果是 1，就向右，就做完了。复杂度是 (O(\log{N}))。
如果有同学觉得实现有困难的，核心代码如下：
vector<int> f;
while (n > 1) {
f.push_back(n % 2);
n /= 2;
}
int p = 1, q = 1;
for (auto i = f.rbegin(); i != f.rend(); ++i) {
if (*i == 0) {
q = p + q;
} else {
p = p + q;
}
}
什么？还要约分？你没发现是互质的吗？样例还是很良心的，样例过了就过了吧？
类型：数学
来自 Pacific NW 2016，改动了一下背景。
简单动规。不管你是与目标串做 LCS，还是做 LIS（因为目标串是严格递增的），都能获得一个最大可利用的字符串长度，然后用 26 去减它就得到答案。朴素做法复杂度是 (O(|s|^2))，可以优化到 (O(|s|\log{|s|}))，但本题没有优化的必要性。
核心代码如下：
char s2[] = "aabcdefghijklmnopqrstuvwxyz";
for (int i = 1; i <= n; ++i)
for (int j = 1; j <= 26; ++j) {
dp[i][j] = max(dp[i-1][j], dp[i][j-1]);
if (s1[i] == s2[j])
dp[i][j] = max(dp[i-1][j-1]+1, dp[i][j]);
}
PNW 官方还提供了一种（可能）有点巧妙的方法，但不需要使用动规。这里提供整份代码供同学们参考。
#include <iostream>
#include <string>
using namespace std ;
int main() {
string ec, s ;
cin >> s ;
for (char c : s) {
auto it = lower_bound(ec.begin(), ec.end(), c) ;
if (it == ec.end())
ec.push_back(c) ;
else
*it = c ;
}
cout << (26-ec.size()) << endl ;
}
类型：动态规划
来自 COCI 2016/2017。
对于任意航线 A-B，我们可以看出，A-B 航线是否存在仅和城市 A 和城市 B 是否改变了航线有关。同时，城市 A 和城市 B 是否改变了航线是由他们改变次数的奇偶决定的。由此可以看出，改变一个城市两次以上是没有意义的。所以问题就转化为是否存在 (p_1, p_2, \ldots p_N, p_i \in {0,1})，使得表达式：(p_{i} \oplus p_{j} = e(i, j), \forall 1 \leq i, j \leq N, i \neq j) 成立，其中 (e(i, j) = 0) 当且仅当城市 (i) 和 (j) 之间起初就有边相连。这是一个经典的 2-SAT 问题，可以使用强连通分量分解的方法或者（更简单的）并查集的方法在等式数量的线性时间内解决该问题。复杂度是 (O(N^2))。
在这里我们介绍一种更加巧妙的方法。由于目标是完全图，所以其实边是都存在的，实质区别在于边有没有被标记。所以这个 2-SAT 问题的特别之处在于，整个图是强连通的。我们考察两种可能性，一种是选择了城市 (1)，还有一种情况是不选择。我们就可以按顺序推导出 (2) 到 (N) 的选择情况。最后再检查一下是不是满足条件。核心代码如下：
void flip(int x) {
for (int i = 0; i < n; ++i)
a[i][x] = a[x][i] = 1 - a[i][x];
}
bool probaj() {
for (int x = 1; x < n; ++x)
if (a[x][0] == 0)
flip(a, x);
for (int i = 0; i < n; ++i)
for (int j = i + 1; j < n; ++j)
if (a[i][j] == 0)
return false;
return true;
}
COCI 官方还提供了一个结论：有且仅有两个连通分量，并且每个连通分量都是一个完全图时，输出 YES，否则输出 NO。由于 COCI 官方未对该结论做出证明，现在作出不严格的简易证明如下：
充分性是显然的。由于完全图之内的边在所有点切换之后仍完全存在，所以，显然对于两个完全子图的情况，只要切换一个子图内所有的顶点，保持另一个子图不变即满足要求。
必要性采用反证法，分两种情况讨论：第一种是存在两个以上的完全图。由于完全图之内的边切换后不受影响，这个问题实际上就是多个孤立点的情况。那么假设切换第一个点，那么后面任何一个点都不能切换，显然不合要求。第二种是存在一个连通的不完全图。在这样一个图中，如果切换了某一个点，就规定了所有与之相连的点都要切换，所有不连的点都不能切换。所以，相连的点和不相连的点之间一定不存在边，与连通性矛盾。
证毕。希望学过离散数学的 dalao 们轻喷。
可惜的是，NB 的结论不能降低复杂度：复杂度已经卡在了读入的 (O(N^2)) 上。
类型：图论
画风转向蓝桥杯模式（众所周知，蓝桥杯很爱考图论和搜索）。此题翻译自 Greater New York 2016。
谁都知道这是搜索啊，问题是怎么搜啊。在这里介绍几个技巧。
dfs 之前先把空格的位置提出来，用一个 vector 什么的记录一下，然后去填 vector 里面的内容，相对来讲会快一点和简单一点。
注意每个空里面填的数字是有范围的。如果后面一个空已经被填了，那么只能填比较小的数；如果前面一个空被填了同理。实现方法可以是往 vector 里面塞东西的时候多塞一个数的范围，这样方便在 dfs 的时候控制 for 循环的范围。如果两个数都没有范围，可能需要在输出的时候做一个大小的判断。
控制好 rowcount，columncount，blockcount 三个二维数组，来记录一个数字有没有被填过。blockcount 的坐标计算可能有点小技巧（不过推导一下问题不大）。
找到答案之后立即退出，答案的记录类似于回溯法。
还是给出核心代码：
struct Pos {
int x, y, st, en;
};
int rowcount[10][20], columncount[10][20], blockcount[10][20];
vector<Pos> pos;
vector<int> ans[10][10];
void add_pos(int i, int j, char c, int st, int en) {
if (c == '-') {
pos.push_back((Pos){i, j, st, en});
} else {
rowcount[i][c - '0']++;
columncount[j][c - '0']++;
blockcount[(i / 2) * 2 + (j / 3)][c - '0']++;
ans[i][j].push_back(c - '0');
}
}
int dfs(int u) {
if (u >= pos.size())
return 1;
Pos p = pos[u];
for (int i = p.st; i <= p.en; ++i) {
if (!rowcount[p.x][i] && !columncount[p.y][i] && !blockcount[(p.x/2)*2+p.y/3][i]) {
rowcount[p.x][i] = columncount[p.y][i] = blockcount[(p.x/2)*2+p.y/3][i] = 1;
if (dfs(u + 1)) {
ans[p.x][p.y].push_back(i);
return 1;
}
rowcount[p.x][i] = columncount[p.y][i] = blockcount[(p.x/2)*2+p.y/3][i] = 0;
}
}
return 0;
}
读入部分：
for (int i = 0; i < 6; ++i)
for (int j = 0; j < 6; ++j) {
char tmp[10];
scanf("%s", tmp);
if (strlen(tmp) == 3) {
if (tmp[2] >= '1' && tmp[2] <= '9')
add_pos(i, j, tmp[0], 1, tmp[2] - '0' - 1);
else add_pos(i, j, tmp[0], 1, 9);
if (tmp[0] >= '1' && tmp[0] <= '9')
add_pos(i, j, tmp[2], tmp[0] - '0' + 1, 9);
else add_pos(i, j, tmp[2], 1, 9);
} else {
add_pos(i, j, tmp[0], 1, 9);
}
}
dfs(0);
此题复杂度比较难估计。不过实际运行非常快，基本不用担心超时。
类型：搜索
改编自蓝桥杯 2015，但除了「正回文子串」这五个字的字面关系之外，跟原题似乎也没啥关系。
事实上，这是一道传统字符串题。考察后缀家族。无论你是使用后缀数组还是哈希还是后缀自动机，理论上都能解决。这里介绍前两种方法。
后缀数组：知道回文子串可以用后缀数组来解决的同学应该会首先想到这种方法。（事实上你会发现这种方法略坑）公共子串在任意一本介绍后缀数组的书中都有介绍，这里不再赘述。回文子串可以将字符串倒置接在后面，从而运用 height 算出一个字符向前和向后的公共长度，即以其为中心的最长回文子串的长度。这样，用后缀数组就同时解决了寻找公共子串和计算最长回文子串这两个问题。最终二分答案。复杂度是 (O(L \log L))。主要代码如下：
scanf("%d%s", &n, s1);
scanf("%d%s", &m, s2);
nn = n * 2 + 2; mm = m * 2 + 2;
copy(str, s1); str[n] = 'a';
reverse(s1, s1 + n);
copy(str + n + 1, s1); str[n * 2 + 1] = 'b';
copy(str + nn, s2); str[nn + m] = 'c';
reverse(s2, s2 + m);
copy(str + nn + m + 1, s2); str[nn + m * 2 + 1] = 'd';
str[nn+mm+1] = 0;
DA(str, sa, nn+mm+1, 128);
calheight(str, sa, nn+mm);
kk = nn + mm + 1;
for (int i = 1; i < kk; ++i)
a[i] = height[i];
initRMQ(kk);
for (int i = 0; i < kk; ++i) {
if (sa[i] < nn - 1 && sa[i] != n) {
int j = i + 1, k = Rank[nn - 2 - sa[i]];
pal[i] = RMQ(min(j,k), max(j,k));
} else if (sa[i] >= nn && sa[i] < nn + mm - 1 && sa[i] != nn + m) {
int more = sa[i] - nn;
int j = i + 1, k = Rank[nn + mm - 2 - more];
pal[i] = RMQ(min(j,k), max(j,k));
}
}
int l = 0, r = n, mid;
while (l < r) {
mid = (l + r + 1) / 2;
int check = 0, last = -1, self;
for (int i = 1; i < kk; ++i)
if (pal[i] >= mid) {
if (last == -1) last = sa[i];
else {
self = sa[i];
if (((last >= nn && self < nn) || last < nn && self >= nn) &&
RMQ(Rank[last]+1, Rank[self]) >= mid) {
check = 1;
break;
}
last = self;
}
}
if (check) l = mid;
else r = mid - 1;
}
printf("%d\n", max(2 * l - 1, 0));
实际上后缀数组是一种吃力又不容易 AC 的办法。更好写的方法应该是哈希（又宣传一波哈希）。二分答案，遍历判断回文串，判断子串。可以用 Manacher 算法加速回文串判断。理论复杂度是 (O(L \log^2{L}))。实际运行会快得多，甚至能超过常数较大的后缀数组。
int HASH(char *s, unsigned long long *h, int len) {
h[len] = 0;
for (int i = len - 1; i >= 0; --i)
h[i] = h[i+1] * x + (s[i] - 'a');
xp[0] = 1;
for (int i = 1; i <= n; ++i) xp[i] = xp[i-1] * x;
}
int check(int len) {
int L = 2 * len - 1;
if (m < L) return 0;
for (int i = 0; i < m-L+1; ++i)
hh[i] = hb[i] - hb[i+L] * xp[L];
sort(hh, hh + m-L+1);
for (int i = 0; i < n-L+1; ++i) {
unsigned long long k = ha[i] - ha[i+L] * xp[L];
if (p[i+len-1] >= len && binary_search(hh, hh + m-L+1, k))
return 1;
}
return 0;
}
int main() {
scanf("%d%s", &n, a);
scanf("%d%s", &m, b);
{
// manacher
int mx = 0, id = 0;
for (int i = 0; i < n; i++) {
p[i] = mx > i ? min(p[2 * id - i], mx - i) : 1;
while (i >= p[i] && a[i + p[i]] == a[i - p[i]])
p[i]++;
if (i + p[i] > mx) {
mx = i + p[i];
id = i;
}
}
}
HASH(a, ha, n);
HASH(b, hb, m);
if (!check(1)) {
printf("0\n");
} else {
int l = 1, r = (n + 1) / 2, mid;
while (l < r) {
mid = (l + r + 1) / 2;
if (check(mid))
l = mid;
else r = mid - 1;
}
printf("%d\n", 2*l-1);
}
}
另外由于小数据很多，好好写四五十分还是很好拿的。
类型：字符串、数据结构
就酱。祝大家蓝桥杯好运！