闲言
好几天没打cf且没有打vp了qwq
这次个人感觉AB两题过得比之前快，C WA了一发，过了；D WA两发，没过。就润去睡觉了。
后续题解先咕一会儿。
代码附在后面
A
容易分析出题中的情况有1~4个字母（不同的）
- 1个，答案显然为0。
- 2个，一次最多能涂两个相同颜色的，所以答案显然为1。
- 3个，此时有一种字母有两个，分为两个相邻与两个相隔的情况，可以发现都只需要一步可以变为有三个相邻的状态，答案为2。
- 4个，只能一个一个变，答案为3。
我在实现代码稍微麻烦了点，jls就是直接set，SSRS_是分类了，但不是完全无脑分类，通过第一个和第二个的cnt来分类。（对于stl还是不熟练QnQ）
B
题意：求十字移动，有一片障碍的前提，从(1, 1)到(n, m)的最小步数。
因为求的是最小步数，我们只先考虑向下或向右的走法。
因为它只有一片是障碍，我们不难分析出，障碍只会严重影响一边的通行（靠左下的路线与靠右上的路线）。
容易发现，若靠左下的路线可以过的话，贴着左下边缘过的方式是绝对可以过得。同理可得靠右上的路线可过的话，贴着右上边缘过的方式亦可以过。
因为，障碍是以一个点为中心的范围。如果，边缘的走法可以过，那最小步数就为 n m-2，否则若两边都不能过，容易想象出这是终点与起点被隔断的情况，即无解，也没有必要去分析其他的走法。
C
题意：有a,b,d两个序列，通过ai di的方式得到bi，再 将bi排序得到我们输入的bi序列，求每个 个体 di的 可能的最大和最小值。
简单分析题意后，得知，我们需要找到每个ai可能匹配上（加上di后相等）的bj，di的最大最小值就是bj-ai的最大最小值。
- bj >= ai
- bj要是ai可以选择的。这里的可以选择是指，它没有被某一个ai，或者某一块a(l~r)绑定。（我WA1发交在这里了QnQ）
关于第二点，我举一个例子
代码语言：javascript复制10 25 30 40
22 33 33 55我们不难发现，a40只能和b55匹配，如果前面的某个数和b55匹配，a40将无法匹配，是不合法的。
所以，a30只能与两个b33匹配，而a25只能和另一个b33匹配。
所以这一块就绑定死了，a10无法尝试与这些绑定一起的匹配。
（因为题中样例只能看出一个会绑定，而一堆会绑定我把原题样例的a20改成a25。）
在代码实现上，因为a，b都是非递减序列，我们需要统计的大于ai的bj就是连续的，可以采用多指针的方式，线性求解。
补充jls的做法，最大值最小值分开处理。
- 最小值就是能匹配的最小的值。
- 最大值就是在满足a[j 1] <= b[j]前的bj与ai的最大值。（这个条件就概括掉我前面这个绑定起来的问题，tql）因为a[j 1]>b[j]的话，a[j 1]就只能在j 1之后的b中匹配。
D
找到D和我思路相似的题解（但我实现能力有点弱）
题意：给出a, b两个序列, c序列为a, b两个序列的某种排列方式的 ci = ai^bi,求所以ci与的最大结果.
易得，想让某一位的与的结果为 1，某一位要全是 1才行。
然后为了结果最大，要从高位到低位进行，且再check低位的时候，要满足高位的限制，即，低位的ab的01匹配，要在之前高位的01匹配的基础上进行，即，一组和一组内匹配。
不难发现，每次的匹配要进行的操作都是一样的，只需要把分出来的组加进去，后面的低位匹配时也需要满足它即可。
jls的思路，check ans，按位下来尝试ans，如果这个ans是存在的，
ans & a的结果应该是与ans & b的结果取反相同的！
jls tql
E
学习的文章
题意：先给你s字符串，后面有q个询问。询问的内容为，把t接在s后面，那么对于接在里面的t的每一位来说，把它作为后缀的字符串，出现在前面的离它最近的地方在哪里，即kmp算法中next[i]。
直接进行前面s的预处理 后面的添加部分的t的kmp会TLE。
分析原因，发现在寻找到真正的ne的时候，跳了重复的多次。
因此，想到要快速查询，不妨设数组chi-1为，当为i-1上的字符时，下一个为j（小写）的位置。(如果i不是所需的字符，则变成前一个满足的位置)
此时，next数组的找寻就变成，next[i] = ch[next[i-1]][s[i]-'a']了。
CODE
A
代码语言：javascript复制#pragma GCC optimize(2)
#include <bits/stdc .h>
#define all(x) (x).begin(), (x).end()
using namespace std;
typedef long long LL;
typedef pair<int, int> PII;
const int N = 200;
bool vis[N];
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
// freopen("i.txt", "r", stdin);
// freopen("o.txt", "w", stdout);
int T;
cin >> T; // scanf("%d", &T);
while (T--)
{
memset(vis, 0, sizeof vis);
int cnt = 0;
char ch[3];
cin >> ch;
for (int i = 0; i < 2; i )
if (!vis[ch[i]])
{
vis[ch[i]] = true;
cnt ;
}
cin >> ch;
for (int i = 0; i < 2; i )
if (!vis[ch[i]])
{
vis[ch[i]] = true;
cnt ;
}
cout << cnt - 1 << 'n';
}
return 0;
}B
代码语言：javascript复制#pragma GCC optimize(2)
#include <bits/stdc .h>
#define all(x) (x).begin(), (x).end()
using namespace std;
typedef long long LL;
typedef pair<int, int> PII;
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
// freopen("i.txt", "r", stdin);
// freopen("o.txt", "w", stdout);
int T;
cin >> T; // scanf("%d", &T);
while (T--)
{
int n, m, sx, sy, d;
cin >> n >> m >> sx >> sy >> d;
if (sx d < n && sy - d > 1 || sx - d > 1 && sy d < m)
cout << n m - 2 << 'n';
else
cout << -1 << 'n';
}
return 0;
}C
代码语言：javascript复制#pragma GCC optimize(2)
#include <bits/stdc .h>
#define all(x) (x).begin(), (x).end()
using namespace std;
typedef long long LL;
typedef pair<int, int> PII;
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
// freopen("i.txt", "r", stdin);
// freopen("o.txt", "w", stdout);
int T;
cin >> T; // scanf("%d", &T);
while (T--)
{
int n;
cin >> n;
vector<int> a(n 1), b(n 1), d1(n 1), d2(n 1);
for (int i = 1; i <= n; i )
cin >> a[i];
for (int i = 1; i <= n; i )
cin >> b[i];
for (int i = n, l = n - 1, r = n; i > 0; i--)
{
while (l && b[l] >= a[i])
l--;
d1[i] = b[l 1] - a[i], d2[i] = b[r] - a[i];
if (l 1 == i)
r = l;
}
for (int i = 1; i <= n; i )
cout << d1[i] << " n"[i == n];
for (int i = 1; i <= n; i )
cout << d2[i] << " n"[i == n];
}
return 0;
}D-1
代码语言：javascript复制#pragma GCC optimize(2)
#include <bits/stdc .h>
#define all(x) (x).begin(), (x).end()
using namespace std;
typedef long long LL;
typedef pair<int, int> PII;
const int N = 1e5 10;
vector<int> ga[N], gb[N];
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
// freopen("i.txt", "r", stdin);
// freopen("o.txt", "w", stdout);
int T;
cin >> T; // scanf("%d", &T);
while (T--)
{
int n;
cin >> n;
vector<int> a(n), b(n);
ga[0].clear(), gb[0].clear();
for (int &x : a)
cin >> x, ga[0].emplace_back(x);
for (int &x : b)
cin >> x, gb[0].emplace_back(x);
int res = 0, g_cnt = 1;
for (int i = 29; i >= 0; i--) // bit
{
bool is_legal = true;
for (int j = 0; j < g_cnt; j )
{
int a0 = 0, b1 = 0;
for (int &x : ga[j])
if (!(x >> i & 1))
a0 ;
for (int &x : gb[j])
if (x >> i & 1)
b1 ;
if (a0 != b1)
{
is_legal = false;
break;
}
}
if (!is_legal)
continue;
// update answer
res = 1 << i;
// divide into new group
int ng_cnt = g_cnt;
for (int j = 0; j < g_cnt; j )
{
int a0 = 0, a1 = 0;
for (int &x : ga[j])
if (x >> i & 1)
a1 ;
else
a0 ;
if (!a0 || !a1) // no need for divide
continue;
vector<int> t_ga = ga[j], t_gb = gb[j];
ga[j].clear(), gb[j].clear(), ga[ng_cnt].clear(), gb[ng_cnt].clear();
for (int &x : t_ga)
if (x >> i & 1)
ga[j].emplace_back(x);
else
ga[ng_cnt].emplace_back(x);
for (int &x : t_gb)
if (x >> i & 1)
gb[ng_cnt].emplace_back(x);
else
gb[j].emplace_back(x);
ng_cnt ;
}
g_cnt = ng_cnt;
}
cout << res << 'n';
}
return 0;
}
/*
观看wangxueyi的题解
思路很像
死于代码实现（（
*/D-2
代码语言：javascript复制#pragma GCC optimize(2)
#include <bits/stdc .h>
#define all(x) (x).begin(), (x).end()
using namespace std;
typedef long long LL;
typedef pair<int, int> PII;
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
// freopen("i.txt", "r", stdin);
// freopen("o.txt", "w", stdout);
int T;
cin >> T; // scanf("%d", &T);
while (T--)
{
int n;
cin >> n;
vector<int> a(n), b(n);
for (int &x : a)
cin >> x;
for (int &x : b)
cin >> x;
auto check = [&](int x)
{
// 这边选用vector判等
vector<int> ta(n), tb(n);
for (int i = 0; i < n; i )
{
ta[i] = a[i] & x;
tb[i] = ~b[i] & x;
}
sort(all(ta));
sort(all(tb));
return ta == tb;
};
int ans = 0;
for (int i = 29; i >= 0; i--)
if (check(ans | (1 << i)))
ans |= 1 << i;
cout << ans << 'n';
}
return 0;
}
/*
jls YYDS
*/E
代码语言：javascript复制#pragma GCC optimize(2)
#include <bits/stdc .h>
#define all(x) (x).begin(), (x).end()
using namespace std;
typedef long long LL;
typedef pair<int, int> PII;
const int N = 1e6 20;
int ne[N], ch[N][26];
char str[N];
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
// freopen("i.txt", "r", stdin);
// freopen("o.txt", "w", stdout);
cin >> str 1;
int slen = strlen(str 1);
ne[1] = 0, ch[0][str[1] - 'a'] = 1;
for (int i = 2; i <= slen; i )
{
ne[i] = ch[ne[i - 1]][str[i] - 'a'];
ch[i - 1][str[i] - 'a'] = i;
for (int j = 'a'; j <= 'z'; j )
{
if (j == str[i])
continue;
ch[i - 1][j - 'a'] = ch[ne[i - 1]][j - 'a'];
}
}
int q;
cin >> q;
while (q--)
{
cin >> str slen 1;
int tlen = strlen(str slen 1);
for (int i = slen 1; i <= slen tlen; i )
{
ne[i] = ch[ne[i - 1]][str[i] - 'a'];
ch[i - 1][str[i] - 'a'] = i;
for (int j = 'a'; j <= 'z'; j )
{
if (j == str[i])
continue;
ch[i - 1][j - 'a'] = ch[ne[i - 1]][j - 'a'];
}
}
for (int i = slen 1, j = slen - 1; i <= slen tlen; i )
cout << ne[i] << " n"[i == slen tlen];
}
return 0;
}
/*
kmp优化
*/
