牛客周赛 Round 63（bfs洪水填充，行列式，推式子，前缀和上前缀和）

比赛链接

牛客周赛 Round 63

A题

代码

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 2e5 + 5;
const int inf = 0x3f3f3f3f3f3f3f3f;
string s;
void solve()
{cin >> s;if (s.size() == 2 && s[0] == s[1]){cout << "Yes" << endl;}else cout << "No" << endl;
}signed main()
{ios::sync_with_stdio(false);cin.tie(0), cout.tie(0);int test = 1;// cin >> test;for (int i = 1; i <= test; i++){solve();}return 0;
}

B题

思路

$n$只有1e3，可以$n^2$暴力做。

代码

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 1e3 + 5;
const int inf = 0x3f3f3f3f3f3f3f3f;int n, k;
int a[N];
void solve()
{cin >> n >> k;for (int i = 1; i <= n; i++){cin >> a[i];}int ans = 0;for (int i = k; i <= n; i++){int cnt = 0;for (int low = i - k + 1, high = i; low < high; low++, high--){if (a[low] != a[high]) cnt++;}if (cnt == 1) ans++;}cout << ans << endl;
}signed main()
{ios::sync_with_stdio(false);cin.tie(0), cout.tie(0);int test = 1;// cin >> test;for (int i = 1; i <= test; i++){solve();}return 0;
}

C题

思路

做一遍bfs洪水填充即可。

代码

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 1e2 + 5;
const int inf = 0x3f3f3f3f3f3f3f3f;int n, m;
int a[N][N];
int dx[2] = {0, 1}, dy[2] = {1, 0};
void solve()
{cin >> n >> m;for (int i = 1; i <= n; i++){for (int j = 1; j <= m; j++){cin >> a[i][j];}}queue<pair<int, int>>q;q.push({1, 1});while (q.size()){int cx = q.front().first;int cy = q.front().second;if (cx == n && cy == m){cout << "Yes" << endl;return;}q.pop();for (int i = 0; i < 2; i++){int tx = cx + dx[i];int ty = cy + dy[i];if (tx < 1 || tx > n || ty < 1 || ty > m) continue;if (a[tx][ty] != a[1][1]) continue;q.push({tx, ty});}}cout << "No" << endl;
}signed main()
{ios::sync_with_stdio(false);cin.tie(0), cout.tie(0);int test = 1;cin >> test;for (int i = 1; i <= test; i++){solve();}return 0;
}

D题

思路

众所周知，行列式$\left|\begin{array}{ccc}1& 1& 1\\ 1& 2& 3\\ 1& 1& 2\end{array}\right|$的值为$1$。根据行列式的性质，对其中的任意一行的元素同时乘以$x$，则行列式的值变为$1\ast x$。

代码

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 1e2 + 5;
const int inf = 0x3f3f3f3f3f3f3f3f;int x;
int a[3][3] = {{1, 1, 1}, {1, 2, 3}, {1, 1, 2}};
void solve()
{cin >> x;if (x == 0){for (int i = 0; i < 3; i++){for (int j = 0; j < 3; j++){cout << 1 << " ";}cout << endl;}}else{for (int i = 0; i < 3; i++){for (int j = 0; j < 3; j++){if (i == 0)cout << x << " ";else cout << a[i][j] << " ";}cout << endl;}}
}signed main()
{ios::sync_with_stdio(false);cin.tie(0), cout.tie(0);int test = 1;// cin >> test;for (int i = 1; i <= test; i++){solve();}return 0;
}

E题

思路

对于字符串redreeddeer，假设我们翻转加粗的这个区间，我们将这个区间命名为$L$。

对于$L$左边的$r$的数量，我们定义为$lr$，$L$右边$d$的数量我们定义为$hd$。

对于$L$内的每一个$e$，我们选择分开进行讨论。

假设$L$其中一个$e$左边的$d$的数量为$opd$，右边$r$的数量定义为$opr$（仅限于区间$L$内）。

则反转区间$L$之后新增的子序列$red$的数量为：$(opr+lr)\times (opd+hd)$。

我们定义$pre[]$为原始序列字符$r$的前缀和，$nxt[]$为原始序列字符$d$的后缀和。

假设当前考虑的区间$L$中的元素$e$的下标为$idx$。

则：$opr=pre[r]-pre[idx]$，$lr=pre[l-1]$，$opd=nxt[l]-nxt[idx]$，$hd=nxt[r+1]$。

则$(opr+lr)\times (opd+hd)=(pre[r]-pre[idx]+pre[l-1])\times (nxt[l]-nxt[idx]+nxt[r+1])$。

我们令$lowr=pre[r]+pre[l-1]$，$highd=nxt[l]+nxt[r+1]$。

对$(pre[r]-pre[idx]+pre[l-1])\times (nxt[l]-nxt[idx]+nxt[r+1])$进行拆解得到：$lowr\times highd-pre[idx]\times highd-lowr\times nxt[idx]+pre[idx]\times nxt[idx]$。

对于区间$L$内所有$e$的$lowr$和$highd$都是固定不变的，所以我们可以通过预处理得到。而对于所有的$e$的$pre[idx]$的和与$nxt[idx]$的和，我们可以分别在前缀和数组上再做一次前缀和来实现快速计算。

代码

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 1e5 + 5;
const int inf = 0x3f3f3f3f3f3f3f3f;int n, q;
int R[N], D[N], SR[N], SD[N];
int RD[N];
int sum[N], num[N];
char s[N];
void solve()
{cin >> n >> q;for (int i = 1; i <= n; i++){cin >> s[i];}for (int i = 1, j = n; i <= n; i++, j--){R[i] = R[i - 1], D[j] = D[j + 1];if (s[i] == 'r') R[i]++;if (s[j] == 'd') D[j]++;}for (int i = 1, j = n; i <= n; i++, j--){if (s[i] == 'e') SR[i] = R[i];if (s[j] == 'e') SD[j] = D[j];SR[i] += SR[i - 1], SD[j] += SD[j + 1];}for (int i = 1; i <= n; i++){if (s[i] == 'e'){RD[i] = R[i] * D[i];}RD[i] += RD[i - 1];}int ans = 0;for (int i = 1; i <= n; i++){if (s[i] == 'e'){num[i]++;sum[i]	= (R[i - 1] * D[i + 1]);}num[i] += num[i - 1];sum[i] += sum[i - 1];}ans = sum[n];while (q--){int l, r;cin >> l >> r;int cnt = num[r] - num[l - 1];int res = ans - (sum[r] - sum[l - 1]);int lowr = R[r] + R[l - 1], highd = D[l] + D[r + 1];int op = cnt * lowr * highd - (SR[r] - SR[l - 1]) * highd - lowr * (SD[l] - SD[r + 1]) + (RD[r] - RD[l - 1]);cout << res + op << endl;}
}signed main()
{ios::sync_with_stdio(false);cin.tie(0), cout.tie(0);int test = 1;// cin >> test;for (int i = 1; i <= test; i++){solve();}return 0;
}

F题

思路

没做出来，过两天补上…

代码