C
题意
有两个由 或 组成的矩阵 和 ,并给出矩阵 , 判断是否有一种方式，有两个分别来自 和 的子矩阵，同时满足以下情况:
- 其中包含了 和 的所有
- 在某种排列方式下，二者的所有 可以恰好放在 的每一个 上，注意，两个子矩阵可以重叠，但 的每一个 上必须有来自子矩阵的 覆盖
思路
这一题的数据范围较小，故我们只需对其进行暴力枚举即可，本人的枚举思路为：
固定矩阵 不动，并使 与之重合
然后枚举 的平移距离（包括上下和左右）。由于一张图的大小不超过 , 故容易证得 的平移距离一定不大于 , 可能还能更小，但笔者未进行严谨证明，相信各位看官一定有更好的想法。
接下来的难点就在于如何判断平移距离是否合法，笔者便简述一下
首先，我们现对 和平移过后的 进行重合操作，由于平移可能向上向左，故需对其进行偏移以避免越界，如下
void merge(int x, int y) {
memset(b, 0, sizeof(b));
for (int i = 1; i <= n[1] + n[2]; i++) {
for (int j = 1; j <= m[1] + m[2]; j++) {
if (a[1][i][j]) b[i + p][j + p] = 1;
if (a[2][i][j]) b[i + x + p][j + y + p] = 1;
}
}
}
然后我们便通过不断调整 的位置，一一比对，判断其是否与 完全重合，注意在判断时，也要判断该放置方式是否包含了全部的 #， 为方便操作，笔者将其转换为 二进制储存
bool check(int x, int y){
merge(x, y);
int cnt = 0;
for (int i = 0; i <= 100; i++)
for (int j = 0; j <= 100; j++)
if (b[i][j]) {
cnt ++;
for (int i = 1; i <= n[1] + 20; i++)
for (int j = 1; j <= m[1] + 20; j++) {
int flag = 0, tot = 1, t = 0;
for (int xx = 1; xx <= n[3] + 10; xx++) {
for (int yy = 1; yy <= m[3] + 10; yy++) {
if (a[3][xx][yy]) t++;
if (a[3][xx][yy] != b[i + xx - 1][j + yy - 1]) {
flag = 1;
break;
}
}
if (flag) break;
}
if (!flag && cnt == t) {
return 1;
}
}
return 0;
}
总代码
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 200, p = 20;
int n[4], m[4];
int a[4][N][N];
int b[N][N];
void merge(int x, int y) {
memset(b, 0, sizeof(b));
for (int i = 1; i <= n[1] + n[2]; i++) {
for (int j = 1; j <= m[1] + m[2]; j++) {
if (a[1][i][j]) b[i + p][j + p] = 1;
if (a[2][i][j]) b[i + x + p][j + y + p] = 1;
}
}
}
bool check(int x, int y){
merge(x, y);
int cnt = 0;
for (int i = 0; i <= 100; i++)
for (int j = 0; j <= 100; j++)
if (b[i][j]) {
cnt ++;
for (int i = 1; i <= n[1] + 20; i++)
for (int j = 1; j <= m[1] + 20; j++) {
int flag = 0, tot = 1, t = 0;
for (int xx = 1; xx <= n[3] + 10; xx++) {
for (int yy = 1; yy <= m[3] + 10; yy++) {
if (a[3][xx][yy]) t++;
if (a[3][xx][yy] != b[i + xx - 1][j + yy - 1]) {
flag = 1;
break;
}
}
if (flag) break;
}
if (!flag && cnt == t) {
return 1;
}
}
return 0;
}
signed main(){
for (int p = 1; p <= 3; p++) {
cin >> n[p] >> m[p];
for (int i = 1; i <= n[p]; i++)
for (int j = 1; j <= m[p]; j++) {
char c;
cin >> c;
if (c == '#') a[p][i][j] = 1;
}
}
// cout << check(0, 0) << endl;
for (int x = -20; x <= 20; x++) {
for (int y = -20; y <= 20; y++) {
if (check(x, y)) {
cout << "Yes" << endl;
return 0;
}
}
}
cout << "No" << endl;
return 0;
}
总结
这一题实际上是对选手的代码能力，并不包含过多的高级算法，是一道不错的枚举题
D
前置知识
- 栈的概念
- STL 中的栈操作
思路
看到括号的配对，我们不难想到栈，同时，许多题解中也选用了栈，但为什么呢，这里我们进行一个分析
因为在这道题中，每碰到一个右括号，我们都需要需找到距离这一括号最近的左括号，而离其最近的左括号必然是在此之前最后输出的括号，由此，我们发现其满足后进先出的特点，故我们果断选用栈，同时，在 C++ 中，STL 有着天然的栈，我们又多了一个选栈的理由，因此，我们选用栈进行操作
代码实现
我们只需在读到一个右括号时，用栈找到最近的左括号，并将在此之后的字符一一弹出即可，代码如下：
#include<bits/stdc++.h>
#define int long long
using namespace std;
string s;
int n;
int tot = 0;
stack <char> sta;
signed main(){
cin >> n;
cin >> s;
s = ' ' + s;
for (int i = 1; i <= n; i++) {
if (s[i] == '(') {
tot++;
else if (s[i] == ')')
if (tot) {
while(sta.top() != '(') sta.pop();
sta.pop();
tot--;
continue;
}
sta.push(s[i]);
}
string s = "";
while (!sta.empty()) {
s = sta.top() + s;
sta.pop();
}
cout << s << endl;
return 0;
}
E
题意
给定一个长度为 的环，每个位置可以填 ，求有多少种方案，满足相邻位置颜色不相同。
思路
无疑这是一道递推，故我们只需找到递推式即可，首先，对于 ， 我们将其定义为，在长度为 的环中的填色方案总数，则对于 我们即可以从前面所得的 的方案数中递推得到，递推式分为两部分：
1.将一个首尾颜色相同的环的末端加入一个与首尾不同的色块，但我们知道，我们只有首尾颜色不同的方案数，故首尾相同的 可由 得到，因为若要首尾相同，只需在末尾加上一个与首位相同的数即可，故第一个式子得到了：
2.将一个本身合法的环加入一个与首尾均不同的色块，即:
故总递推式为：
注意
长度为 的 需预处理，因为在这一情况会存在越界现象，同时，也会影响答案合法性
代码
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 1e6 + 10, mod = 998244353;
int n, m;
int f[N];
signed main(){
cin >> n >> m;
f[1] = m % mod;
f[2] = m * (m - 1) % mod;
f[3] = m * (m - 1) % mod * (m - 2) % mod;
for (int i = 4; i <= n; i++)
f[i] = (f[i - 1] * (m - 2) + f[i - 2] * (m - 1)) % mod;
cout << f[n] << endl;
return 0;
}