T4 是什么，我不想做！我开摆了！
A. Substring
http://222.180.160.110:1024/contest/3312/problem/1
没记错的话这应该是一场 ABC 的 T1，总之我们想办法让 T 去匹配 S，也就是说，在 S 中枚举匹配起点，统计从匹配起点开始与 T 不同的字符总数，将所有起点的答案取 min 就行了。
namespace XSC062 {
const int maxn = 1e3 + 5;
const int inf = 0x3f3f3f3f;
int n, m, res;
char s[maxn], t[maxn];
inline int min(int x, int y) {
return x < y ? x : y;
}
int main() {
scanf("%s %s", s + 1, t + 1);
n = strlen(s + 1);
m = strlen(t + 1);
res = inf;
for (int i = 1; i <= n - m + 1; ++i) {
int cnt = 0;
for (int j = 1; j <= m; ++j)
cnt += (s[i + j - 1] != t[j]);
res = min(res, cnt);
}
printf("%d", res);
return 0;
}
} // namespace XSC062
B. 字符串的展开
http://222.180.160.110:1024/contest/3312/problem/2
题目名字好熟悉！我总觉得我在不知道几年前写过 这样一篇题解。当时的文风和码风可谓不堪入目。
不难发现只需要对减号的两端特殊处理，所以我们走一遍整个字符串，遇到减号就看看它两边的东西，然后对应模拟就行了。
namespace XSC062 {
const int maxn = 105;
char s[maxn];
int p1, p2, p3, n;
inline bool isNum(char t) {
return t >= '0' && t <= '9';
}
inline bool isLet(char t) {
return t >= 'a' && t <= 'z';
}
inline void putNum(char l, char r) {
if (p3 == 1) {
for (int i = l + 1; i < r; ++i) {
for (int j = 1; j <= p2; ++j)
putchar(p1 == 3 ? '*' : i);
}
}
else {
for (int i = r - 1; i > l; --i) {
for (int j = 1; j <= p2; ++j)
putchar(p1 == 3 ? '*' : i);
}
}
return;
}
inline void putLet(char l, char r) {
if (p3 == 1) {
for (int i = l + 1; i < r; ++i) {
for (int j = 1; j <= p2; ++j) {
if (p1 == 3)
putchar('*');
else if (p1 == 1)
putchar(i);
else putchar(i + 'A' - 'a');
}
}
}
else {
for (int i = r - 1; i > l; --i) {
for (int j = 1; j <= p2; ++j) {
if (p1 == 3)
putchar('*');
else if (p1 == 1)
putchar(i);
else putchar(i + 'A' - 'a');
}
}
}
return;
}
inline void deal(char l, char r) {
if (isNum(l) && isNum(r) && l < r)
putNum(l, r);
else if (isLet(l) && isLet(r) && l < r)
putLet(l, r);
else putchar('-');
return;
}
int main() {
scanf("%d %d %d", &p1, &p2, &p3);
scanf("%s", s + 1);
n = strlen(s + 1);
for (int i = 1; i <= n; ++i) {
if (s[i] == '-' && i >= 2 && i <= n - 1)
deal(s[i - 1], s[i + 1]);
else putchar(s[i]);
}
return 0;
}
} // namespace XSC062
C. 1-05E. mm逗黑白猫
http://222.180.160.110:1024/contest/3312/problem/3
听 gm 说这道题 A*，双向广搜，朴素广搜都有人过的，总之我写的是双向广搜。
字典序最小这个点确实难了我很久，对于正向，我们只需要保证按照字典序从小往大搜就可以了，因为靠前的部分字典序越小，整体的字典序就越小。
但对于反向就有点麻烦，好像最终从前往后的输出字典序大小并不能由反向搜索顺序决定……
所以我们暴力一点，对于同一层内的反向搜索，我们让最后一次（也就是最靠前）交换字典序最小的排在前面，用一个优先队列实现。这样我们就能保证碰头的时候能用字典序最小的反向碰到字典序最小的正向。
好悬啊，不知道能不能过啊，开摆啦！
namespace XSC062 {
const int inf = 0x3f3f3f3f;
const int maxm = (1 << 16) + 5;
struct _ {
int s, t, d, p, fa;
bool operator< (const _ &q) const {
if (t != q.t)
return t > q.t;
else if (q.d != d)
return d > q.d;
else if (d == 0)
return p > q.p;
else
return (s ^ fa) < (q.s ^ q.fa);
}
};
_ b, e;
int x, now;
int vis[2][maxm];
std::priority_queue<_> q;
inline void print(int x) {
for (int i = 15; ~i; --i) {
if (x & (1 << i))
printf("%d%d", 4 - (i / 4), 4 - (i % 4));
}
putchar('\n');
return;
}
inline void TWBFS(_ &be, _ &en) {
q.push(be), q.push(en);
while (!q.empty()) {
_ f = q.top(), t;
t = f, ++t.t, t.fa = f.s;
q.pop();
if (vis[f.d][f.s] != inf)
continue;
vis[f.d][f.s] = f.fa;
for (int i = 15; ~i; --i) {
for (int j = i - 1; ~j; --j) {
int k = (f.s >> i) & 1;
int l = (f.s >> j) & 1;
t.s = f.s - (k << i) + (l << i)
- (l << j) + (k << j);
if (vis[!t.d][t.s] != inf) {
int cnt = t.t, x = t.s;
while (~vis[!t.d][x])
++cnt, x = vis[!t.d][x];
printf("%d\n", cnt);
x = t.s;
std::stack<int> s;
vis[t.d][t.s] = f.s;
while (~vis[t.d][x]) {
s.push(x);
x = vis[t.d][x];
}
while (!s.empty()) {
x = s.top(), s.pop();
print(x ^ vis[t.d][x]);
}
x = t.s;
while (~vis[!t.d][x]) {
print(x ^ vis[!t.d][x]);
x = vis[!t.d][x];
}
return;
}
if (vis[t.d][t.s] == inf) {
t.p = ++now;
q.push(t);
}
}
}
}
return;
}
int main() {
memset(vis, 0x3f, sizeof (vis));
for (int i = 1; i <= 4; ++i) {
for (int j = 1; j <= 4; ++j) {
scanf("%1d", &x);
b.s = (b.s << 1) + x;
}
}
for (int i = 1; i <= 4; ++i) {
for (int j = 1; j <= 4; ++j) {
scanf("%1d", &x);
e.s = (e.s << 1) + x;
}
}
if (b.s == e.s) {
puts("0");
return 0;
}
e.d = 1, b.fa = e.fa = -1;
TWBFS(b, e);
return 0;
}
} // namespace XSC062
D. zzj & liaoy 想要去摄影
http://222.180.160.110:1024/contest/3312/problem/4
为啥看到 liaoy 这个名字会无端联想到嫂子…… 我不是很认识她，只知道她是一个开放的魁梧女子（试图把伊斯文化传播到 OI）。
这个怎么打啊，我只会爆搜啊，gm 还说这题比 T3 简单来着……
不对，我还是可以双向广搜！
标签：return,230217,记录,int,vis,maxn,const,字典 From： https://www.cnblogs.com/XSC062/p/17131423.html