DP\text{DP}DP ：（今天做的这两道都没啥 DP 相关来着

D. Match & Catch

题意：

给定两个字符串 1≤∣s1∣,∣s2∣≤50001\leq |s_1|,|s_2|\leq 50001≤∣s1​∣,∣s2​∣≤5000 ，求最短的满足各只出现一次的连续公共字串。

思路：写了个哈希超时了，哈希表常数还是太大，时限紧最好别用库内哈希表。

后缀数组解法：见 题解 。

AC代码：https://codeforces.com/contest/427/submission/181166321

D. New Year Letter

题意：

构造长度为 n,mn,mn,m 的两个字符串 s1,s2s_1,s_2s1​,s2​ ，使得 sks_ksk​ 含有 xxx 个子串 AC\text{AC}AC 。字符串递推式 si=si−2+si−1s_i=s_{i-2}+s_{i-1}si​=si−2​+si−1​ 。

3≤k≤50,0≤x≤109,1≤n,m≤1003 \le k \le 50,0 \le x \le 10^9, 1 \le n, m \le 1003 ≤k ≤ 50,0 ≤ x ≤ 109,1 ≤ n, m ≤ 100

思路：首先，递推出来 sks_ksk​ 有多少个 s1,s2s_1,s_2s1​,s2​ ，以及有多少个 s1s2,s2s2,s2s1(s1,s1是没有的)s_1s_2,s_2s_2,s_2s_1(s_1,s_1是没有的)s1​s2​,s2​s2​,s2​s1​(s1​,s1​是没有的) 的连接个数。

然后就是暴力枚举 + 暴力讨论了。枚举两个字符串的首字符，尾字符，有多少个 AC\text{AC}AC 暴力讨论即可。

AC代码：https://codeforces.com/contest/379/submission/181171146

构造题 ∗1700∼∗2000^*1700\sim ^*2000∗1700∼∗2000 ：

A. GCD Table

题意：

有一个长度为n(1≤n≤500)n(1\leq n\leq 500)n(1≤n≤500)的数列aaa，它可以生成一个n∗nn*nn∗n的数表，数表的第iii行第jjj列存放的数字是gcd⁡(a[i],a[j])\gcd(a[i],a[j])gcd(a[i],a[j]) （即a[i]a[i]a[i]和a[j]a[j]a[j]的最大公因数）。

举个例子，上面那个表，就是由数列a[]={4,3,6,2}a[]=\{4,3,6,2\}a[]={4,3,6,2}生成的。

现在我们要做这样一件事情：将这个数表中的这n∗nn*nn∗n 个数打乱，得到一个长度为n∗nn*nn∗n的序列(可参考样例1)。在已知这个序列的情况下，请还原出数列aaa。

题解：CF582A GCD Table 题解

思路：需要注意到

1. gcd⁡(x,y)≤min⁡(x,y)\gcd(x,y)\leq \min(x, y)gcd(x,y)≤min(x,y) ，也就是两个数字产生的影响是小于两个数字的。

2. 乱序序列的最大次大值一定是原序列的最大次大值。

这样的话，每次从乱序序列拿出最大值，然后和已拿出的数字计算一下，抵消掉乱序序列的影响，划归为子问题。

AC代码：https://codeforces.com/contest/582/submission/181179199

C. Primitive Primes

题意：

• 给定两个序列 aaa 和 bbb，其中序列 aaa 的长度为 nnn，序列 bbb 的长度为 mmm。
• 分别保证序列中所有数字的最大公约数为 111。即 gcd⁡(a0,a1…an−1)=1\gcd(a_0, a_1 \dots a_{n - 1}) = 1gcd(a0​,a1​…an−1​)=1，gcd⁡(b0,b1,…bm−1)=1\gcd(b_0, b_1, \dots b_{m - 1}) = 1gcd(b0​,b1​,…bm−1​)=1。
• 设 aaa 与 bbb 卷积的结果为序列 ccc。即 ck=∑0≤i≤k∧i
• 给出一个 质数 ppp，请你求出一个下标 ttt，满足 ctc_tct​ 不能被 ppp 整除。如果有多个满足要求的 ttt，请任意输出一个。
• 1≤n,m≤1061 \leq n, m \leq 10^61≤n,m≤106，1≤p,ai,bi≤1091 \leq p, a_i, b_i \leq 10^91≤p,ai​,bi​≤109。

思路：注意到，卷积的话，两个指针的方向是相反的。如果 aaa 的一段前缀的元素都是 ppp 的倍数，那么这个数不管和哪个 bbb 的元素卷一起，都还是 ppp 的倍数。于是答案就是各找到第一个非 ppp 的倍数，即为答案。

AC代码：https://codeforces.com/contest/1316/submission/181184451

B. Monopole Magnets

题意：

单极磁铁，顾名思义，就是只有一个磁极（N 或 S）的磁铁，他们在实际生活中是不存在的，不过……不要在意那些细节。

我们有一个 nnn 行 mmm 列的方格图，要在里面放一些单极磁铁，你可以随便放置，甚至把多个磁铁放在同一个格子里。

单极磁铁的吸引是这么定义的：任选一个 N 极磁铁和一个 S 极磁铁，如果它们两个恰好处于同一行或同一列中，那 N 极磁铁会向靠近 S 极磁铁的方向前进一格。当然，如果它们两个处于同一个格子，什么也不会发生。注意 S 极磁铁的位置是永远不会变化的。

这个方格图里的每一个格子都涂成了黑色或白色。磁铁的放置必须要遵守以下规则：

1. 每行每列都必须至少有一个 S 极磁铁。
2. 对于每个黑色格子，必须有某个 N 极磁铁通过一系列的吸引操作经过它。
3. 对于每个白色格子，无论 N 极磁铁的位置怎样变化，都不能经过它。

现在我们想知道：要满足以上三条规则，至少要放几个 N 极磁铁。如果无论怎么放都不能满足规则，请输出 −1-1−1。

(1≤n,m≤1000)(1\le n,m\le 1000)(1≤n,m≤1000)

思路：注意到，一行或一列上，如果有连续两段或两段以上的黑色块，那么一定无解。这样的话，每一个连通块一定是凸集，而且可以视作它的最小包围矩阵。我们移动这些矩阵挤到一起，那么有若干个空行或空列，设为 rw,lcrw,lcrw,lc 。

如果这两个数一个为 000 一个非 000 ，一定无解，因为这样一定没法放 SSS 。否则容易构造方案使得这些空行或空列放置了 SSS 。

AC代码：https://codeforces.com/contest/1344/submission/181194214