2021.3.31 校内模拟赛游记

极其糟糕的比赛体验，中文题面比 CF 的英文题面还要难以读懂。

赛后一直搞 T4 的瞎搞哈希做法，用了一整个晚自修。

A

题面有些迷，样例又出锅。

看懂题面后就好做了。

就是要求一个最长不上升子序列，要求字典序最大。

字典序最大的问题只需要反过来跑最长不下降子序列，更新的时候不把等号取上，然后正着找，等号也取上就行了。

B

简单的数学题。

给出由 abc? 四个字符组成的字符串， ? 可变为任意字符，问在所有的情况中子序列 abc 出现了几次。

没有 ? 的做法就左右记一下 a 和 c 的个数然后乘起来就可以了。

有 ? 的就考虑定下一些 ? 的字母，然后其它随便排就可以了。具体地，在找到 b 的时候把左边 a 的个数和右边 ? 的个数乘起来再乘上 $3^{k-1}$ 就是以当前这个为中间，左边的 a 为左边，右边使用 ? 在所有序列中出现的次数。

C

前两题都是签到题，现在开始略有难度(主要在读题)，原题是 CF980D。

其实不怪搬题人，洛谷的翻译过于糟糕了。分成的序列是可以不连续的，赛时按照连续的来做了。

两数相乘是平方数其实是由传递性的，很容易证明。

设 $A = \prod a_i^{k_i}, B = \prod b_i ^ {m_i}, C = \prod c_i ^ {n_i}$ , 若 $A \times B$ 是平方数，那么一定有 $\forall i, k_i+m_i \equiv 0 \pmod 2$ , 同理 $\forall i, n_i+m_i \equiv 0 \pmod 2$ , 所以 $\forall i, n_i \equiv k_i\pmod 2$ 可以得到 $A \times C$ 也是平方数。

那么就可以用并查集维护了，看一段子串中有几个不同集合就好了。

注意 $0$ 不能参与上面运算，它可以放入任意集合，所以单独考虑。

代码。

#include <algorithm>
#include <cstdio>
#include <cmath>
#include <cstring>
#define int long long
const int N = 5005;
int n, a[N], fa[N], ans[N], map[N];
int find(int x) { return fa[x] == x ? x : fa[x] = find(fa[x]); }
bool check(int x, int y) {
	if(x * y <= 0) return false;
	int an = sqrt(x*y);
	if(an * an == x * y) return true;
	else return false;
}
signed main() {
    scanf("%lld", &n);
    for(int i = 1; i <= n; i++) fa[i] = i;
    for(int i = 1; i <= n; i++) {
        scanf("%lld", &a[i]);
        for(int j = 1; j < i; j++)
            if(check(a[i], a[j]))  fa[find(i)] = find(j);
    }
    for(int i = 1; i <= n; i++) {
        memset(map, 0, sizeof(map));
        int an = 0;
        for (int j = i; j <= n; j++)
            if(a[j] == 0) ans[std::max(an, 1ll)]++;
            else {
                if(!map[fa[j]]) an++;
                map[fa[j]] = 1;
                ans[an]++;
            }
    }
    for(int i = 1; i <= n; i++) printf("%lld ", ans[i]);
    return 0;
}

D

原题是 [SDOI2008]Sandy的卡片。

题面可以转化为(作差以后)。

求 $n$ 个串的最长相同子串

赛场上以为是要最长相同的相同子串，样例太水，还让我过了，居然有 $20$ 。

因为 $n, m$ 非常小，所以不用啥后缀自动机了，直接 dp 就好。

$f[i][j]$ 是前 $i$ 串前 $j$ 个且以 $j$ 结尾的最长相同子串， $g[i][i]$ 是相邻的两行前一行以 $i$ 结尾，后一行以 $j$ 结尾的前面的最长相同子串。利用辅助的 $g[i][j]$ 可以方便转移。

其实挺妙的，想不到用两个来维护转移。

#include <cstdio>
#include <algorithm>
#include <vector>
#include <cstring>
#define int long long
const int N = 1005, INF = 0x3f3f3f3f3f3f3f3f;
int n, m, x, ans, g[N][N], f[N][N];
std::vector<int> a[N];
signed main() {
	scanf("%lld", &n);
	for(int i = 1; i <= n; i++) {
		scanf("%lld", &m);
		for(int j = 1; j <= m; j++) {
			scanf("%lld", &x);
			a[i].push_back(x);
		}
		for(int j = (signed)a[i].size()-1; j >= 1; j--) a[i][j] -= a[i][j-1]; 
	}
	for(int i = 1; i < (signed)a[1].size(); i++) f[1][i] = INF;
	for(int i = 2; i <= n; i++) {
		memset(g, 0, sizeof g);
		for(int j = 1; j < (signed)a[i].size(); j++)
			for(int k =  1; k < (signed)a[i-1].size(); k++)
				if(a[i][j] == a[i-1][k]) 
					g[j][k] = std::min(f[i-1][k], g[j-1][k-1] + 1),
					f[i][j] = std::max(f[i][j], g[j][k]);
	}
	for(int j = 1; j < (signed)a[n].size(); j++)
		ans = std::max(ans, f[n][j]);
	printf("%lld", ans+1);
	return 0;
}

好，正戏收场，开始乱搞。

赛时我按照错误的理解写了一个 map 做法，然后挂掉了，所以赛后我不甘心，一定要使用 map 来做。

如果把所有的子串直接用 map 来映射到它的长度，那肯定是要超时的，因为枚举所有子串用的总复杂度就是 $nm^2$ 有 $10^7$ 了，再乘上 $\log$ 再乘上移动串所需要的 $m$ 的复杂度，显然超时。

注意： erase 的时候不能直接 erase 因为 map 的迭代器不会自动跳到下一个，所以要写作 erase(j++) 先传进去，没删掉就到下一个，不然会 RE。

提交记录

氧气也救不了

吸氧的记录

代码如下。

#include <cstdio>
#include <algorithm>
#include <vector>
#include <cstring>
#include <map>
#define int long long
const int N = 1005;
int n, m, x, ans;
typedef std::vector<int> twt;
twt a[N], hash;
std::map<twt, int> anst, t;
signed main() {
	scanf("%lld", &n);
	for(int i = 1; i <= n; i++) {
		scanf("%lld", &m);
		for(int j = 1; j <= m; j++) {
			scanf("%lld", &x);
			a[i].push_back(x);
		}
		for(int j = (signed)a[i].size()-1; j >= 1; j--) a[i][j] -= a[i][j-1]; 
		t.clear();
		for(int j = 1; j < (signed)a[i].size(); j++) {
			hash.clear();
			for(int k = j; k < (signed)a[i].size(); k++) {
				hash.push_back(a[i][k]);
				t[hash] = std::max(t[hash], k-j+1);
			}
		}  
		for(std::map<twt, int>::iterator j = anst.begin(); j != anst.end();)
			if(t[j -> first] != 0) j -> second = std::min(j -> second, t[j -> first]), j++;
			else anst.erase(j++);			
		if(i == 1) 
			for(std::map<twt, int>::iterator j = t.begin(); j != t.end(); j++) 
				anst[j -> first] = j -> second;
	}
	for(std::map<twt, int>::iterator j = anst.begin(); j != anst.end(); j++)
		ans = std::max(ans, j -> second);
	printf("%lld", ans+1);
	return 0;
}

那么怎么办呢？我们难道要放弃这个伟大的做法吗？

不，上面的程序复杂度大主要在于要把整个串给存进去，那么我们先哈希一下再存进去不就可以避免这个问题了吗。

但在这题中似乎特别容易冲突，毕竟全是数，值域大，然而单哈希过了......

为了追求严谨，还是使用三哈希。

代码如下，其实就是重写了上面的 twt.

重写成这样:

struct twt {
	int h[T];
	void clear() {
		for(int i = 0; i < T; i++) h[i] = 0;
	}
	void insert(int x) {
		for(int i = 0; i < T; i++) h[i] = h[i] * ti[i] + x % mod[i];
	}
	bool operator < (twt b) const {
		return h[0] < b.h[0];
	}
} hash;

就好了，注意必须要重载严格弱序的 <, 因为在红黑树中需要用到。

交了发现 TLE on #5

吸口氧就过了。

我们知道主要复杂度在于 map (?), 所以使用传说中的 unordered_map 是不是就可以过了呢？

对于单哈希的那玩意儿，直接把 map 替换为 unoredered_map 就可以了，确实快了很多，但本地测试最慢的点仍然要 1.64s 还是过不了，在洛谷上不开 O2 就 TLE，开了需要 545ms, ~~比暴力程序还要慢~~。

那么对于三哈希的 twt, 如果你直接使用 unordered_map ，恭喜，会收到一大坨 CE, 因为 unordered_map 不知道该如何哈希 twt，所以我们需要自定义哈希函数，并重载等号的运算，哈希函数需要写成伪函数的形式，最后就是这个样子的。

struct twt {
	int h[T];
	void clear()  {for(int i = 0; i < T; i++) h[i] = 0; }
	void insert(int x) { for(int i = 0; i < T; i++) h[i] = h[i] * ti[i] + x % mod[i]; }
	bool operator == (twt b) const {	return h[0] == b.h[0] && h[1] == b.h[1] && h[2] == b.h[2]; }
} hash;
struct hashf{
	size_t operator() (twt a) const {
		return (unsigned) a.h[0] + a.h[1] + a.h[2];
	} 
};
std::unordered_map<twt, int, hashf> anst, t;

~~hash 到最后又合成了一个，这三哈希了个寂寞。~~

其实说了那么多，就是想普及一下 unordered_map 的用法。

但遗憾的是 unordered_map 不是 $\mathcal O(1)$ 的，仍然过不了，开了 O2 也一样........

这场主要难度在于读题的比赛其实对我的帮助在于普及了 unordered_map 和 map.erase()的用法......

2021.3.31 校内模拟赛游记

A

B

C

D

题解 [CF -1172D]Nauuo and Binary Tree

题解 [2019 ICPC 上海网络赛] Lighting Routing I