博客题解原地址：https://zhuanlan.zhihu.com/p/686259654
A
直接字符串截取即可
#include <bits/stdc++.h>
using namespace std;
#define debug(x) cerr << #x << ": " << x << '\n';
#define bd cerr << "----------------------" << el;
#define el '\n'
#define rep(i, a, b) for (int i = (a); i <= (b); i++)
#define lop(i, a, b) for (int i = (a); i < (b); i++)
#define dwn(i, a, b) for (int i = (a); i >= (b); i--)
#define cmax(a, b) a = max(a, b)
#define cmin(a, b) a = min(a, b)
#define x first
#define y second
#define db double
typedef long long LL;
typedef pair<int, int> PII;
constexpr int N = 2e6 + 10, md = 1e9 + 7;
constexpr int INF = 0x3f3f3f3f;
int n, m;
void solve()
{
string s;
cin >> s;
cout << s.substr(0, s.size() - 3);
}
int main()
{
cin.tie(0)->sync_with_stdio(false);
cout.tie(0);
solve();
}
B
模拟题意即可
#include <bits/stdc++.h>
using namespace std;
#define debug(x) cerr << #x << ": " << x << '\n';
#define bd cerr << "----------------------" << el;
#define el '\n'
#define rep(i, a, b) for (int i = (a); i <= (b); i++)
#define lop(i, a, b) for (int i = (a); i < (b); i++)
#define dwn(i, a, b) for (int i = (a); i >= (b); i--)
#define cmax(a, b) a = max(a, b)
#define cmin(a, b) a = min(a, b)
#define x first
#define y second
#define db double
typedef long long LL;
typedef pair<int, int> PII;
constexpr int N = 110, md = 1e9 + 7;
constexpr int INF = 0x3f3f3f3f;
int n, m;
int a[N][N];
void no()
{
cout << "wrong answer";
exit(0);
}
void yes()
{
cout << "accepted";
exit(0);
}
void solve()
{
int x;
cin >> n >> m >> x;
LL tmp = 0;
rep(i, 1, n)
{
rep(j, 1, m)
{
cin >> a[i][j];
tmp += a[i][j];
}
}
if(tmp != x)
{
no();
}
tmp = 0;
rep(i, 1, m)
{
tmp ^= a[1][i];
}
rep(i, 1, n)
{
LL t = 0;
rep(j, 1, m)
{
t ^= a[i][j];
}
if(t != tmp)
{
no();
}
}
rep(i, 1, m)
{
LL t = 0;
rep(j, 1, n)
{
t ^= a[j][i];
}
if(t != tmp)
{
no();
}
}
yes();
}
int main()
{
cin.tie(0)->sync_with_stdio(false);
cout.tie(0);
solve();
}
C
从前往后贪心即可，看看能否续到上一个单词后面，不能的话，就变成空白。
变成空白之后，就必然重头开始一个单词。
#include <bits/stdc++.h>
using namespace std;
#define debug(x) cerr << #x << ": " << x << '\n';
#define bd cerr << "----------------------" << el;
#define el '\n'
#define rep(i, a, b) for (int i = (a); i <= (b); i++)
#define lop(i, a, b) for (int i = (a); i < (b); i++)
#define dwn(i, a, b) for (int i = (a); i >= (b); i--)
#define cmax(a, b) a = max(a, b)
#define cmin(a, b) a = min(a, b)
#define x first
#define y second
#define db double
typedef long long LL;
typedef pair<int, int> PII;
constexpr int N = 2e6 + 10, md = 1e9 + 7;
constexpr int INF = 0x3f3f3f3f;
int n, m;
void solve()
{
string s;
cin >> s;
bool f = true;
int ans = 0;
lop(i, 1, s.size())
{
if(isupper(s[i]))
{
if(f)
{
ans ++;
f = false;
}
else {
f = true;
}
}
else {
if(!f)
{
f = true;
}
else {
}
}
}
cout << ans;
}
int main()
{
cin.tie(0)->sync_with_stdio(false);
cout.tie(0);
solve();
}
D
使用bfs 搜索即可
（可以将E题的输出丢到这题里面，来检验自己的路径长度答案是否合法）
#include <bits/stdc++.h>
using namespace std;
#define debug(x) cerr << #x << ": " << x << '\n';
#define bd cerr << "----------------------" << el;
#define el '\n'
#define rep(i, a, b) for (int i = (a); i <= (b); i++)
#define lop(i, a, b) for (int i = (a); i < (b); i++)
#define dwn(i, a, b) for (int i = (a); i >= (b); i--)
#define cmax(a, b) a = max(a, b)
#define cmin(a, b) a = min(a, b)
#define x first
#define y second
#define db double
typedef long long LL;
typedef pair<int, int> PII;
constexpr int N = 1010, md = 1e9 + 7;
constexpr int INF = 0x3f3f3f3f;
int n, m;
string s[1002];
int dis[N][N];
bool vis[N][N];
int dx[] = {-1, 1, 0, 0};
int dy[] = {0, 0, 1, -1};
bool check(int x, int y)
{
return 0 <= x && x < n && 0 <= y && y < m;
}
void solve()
{
cin >> n >> m;
lop(i, 0, n)
{
cin >> s[i];
lop(j, 0, m)
{
dis[i][j] = INF;
}
}
queue<array<int, 3>> q;
q.push({0, 0, 0});
dis[0][0] = 0;
while(q.size())
{
auto [x, y, d] = q.front();
cerr << x << ' ' << y << ' ' << d << el;
q.pop();
lop(k, 0, 4)
{
int vx = x + dx[k];
int vy = y + dy[k];
if(check(vx, vy) && s[x][y] != s[vx][vy] && d + 1 < dis[vx][vy])
{
dis[vx][vy] = d + 1;
q.push({vx, vy, d + 1});
}
}
}
if(dis[n - 1][m - 1] != INF)
cout << dis[n - 1][m - 1];
else
cout << -1;
}
int main()
{
cin.tie(0)->sync_with_stdio(false);
cout.tie(0);
solve();
}
E
很灵活的构造题，随便造基本都能过。
我们圈定出一条路径（就像圈猪圈那样），跟样例解释一模一样。最开头的地方拐弯一下，最末尾的地方拐弯一下即可。
然后其余部分，跟路径相邻的，赋值为跟路径相同的值，这样就没法往这边拐弯。
#include <bits/stdc++.h>
using namespace std;
#define debug(x) cerr << #x << ": " << x << '\n';
#define bd cerr << "----------------------" << el;
#define el '\n'
#define rep(i, a, b) for (int i = (a); i <= (b); i++)
#define lop(i, a, b) for (int i = (a); i < (b); i++)
#define dwn(i, a, b) for (int i = (a); i >= (b); i--)
#define cmax(a, b) a = max(a, b)
#define cmin(a, b) a = min(a, b)
#define x first
#define y second
#define db double
typedef long long LL;
typedef pair<int, int> PII;
constexpr int N = 1010, md = 1e9 + 7;
constexpr int INF = 0x3f3f3f3f;
int n, m;
char s[N][N];
bool vis[N][N];
void nxt(int &now)
{
now++;
if (now == 26)
now = 0;
}
void solve()
{
cin >> n >> m;
if(n == 3 && m == 4)
{
cout << "abbc" << el;
cout << "accd" << el;
cout << "bcee" <&l***it(0);
}
if(n == 3 && m == 3)
{
cout << "abb" << el;
cout << "acc" << el;
cout << "bce" <&l***it(0);
}
if(n == 4 && m == 3)
{
cout << "aab" << el;
cout << "bcc" << el;
cout << "bce" << el;
cout << "cde" <&l***it(0);
}
int now = 0;
s[n][1] = now;
vis[n][1] = true;
nxt(now);
int t = 1;
dwn(i, n - 1, 1)
{
s[i][1] = s[i][2] = t;
vis[i][1] = vis[i][2] = true;
nxt(t);
}
t = 1;
rep(i, 2, m)
{
vis[n - 1][i] = vis[n][i] = true;
s[n - 1][i] = s[n][i] = t;
nxt(t);
}
s[1][1] = s[2][1];
t = s[1][1];
nxt(t);
s[1][2] = t;
nxt(t);
s[2][2] = t;
s[n][m] = s[n][m - 1];
t = s[n][m];
nxt(t);
s[n - 1][m - 1] = t;
nxt(t);
s[n - 1][m] = t;
// rep(i, 1, n)
// {
// rep(j, 1, m)
// {
// if (vis[i][j])
// {
// char c = 'a' + s[i][j];
// cout << c;
// }
// else
// {
// cout << " ";
// }
// }
// cout << el;
// }
// cout << el;
t = max(n, m) - 1;
t %= 26;
nxt(t);
rep(i, 1, n - 2)
{
rep(j, 3, m)
{
vis[i][j] = true;
s[i][j] = t;
nxt(t);
}
}
s[2][3] = s[3][2] = s[2][2];
s[1][3] = s[1][2];
rep(i, 1, n)
{
rep(j, 1, m)
{
// if (vis[i][j])
// {
char c = 'a' + s[i][j];
cout << c;
// }
// else
// {
// cout << " ";
// }
}
cout << el;
}
}
int main()
{
cin.tie(0)->sync_with_stdio(false);
cout.tie(0);
solve();
}
F
本场最有价值做的题目。
有一个性质，对于区间内是否存在回文子串，只需要判断长度为 的即可。因为其余长度更长的也是在这个的基础上的。
接下来我们将red分别看成012，因为不能存在长度为 的回文子串，也就相当于：两个相邻同类数字，其距离必须大于等于
。
三类数字都需要满足这个特性，故只能构造出类似 这类循环。
同理，全排列一共有六类：
- 012
- 021
- 102
- 120
- 201
- 210
我们用线段树来维护信息，维护每个区间，012循环 与 原区间对应位置相同的数量。同理对于另外五类。得到一个数组int a[6]
那么如何merge信息呢？（也就是合并两个区间，可以不准确的理解为pushUp操作）
左区间 L 和右区间 R，我们考虑合并后的012 循环的数量：
- 当左区间长度
L.len % 3 == 0时，此时可以无缝衔接L.a[0] + R.a[0]。 - 当左区间长度
L.len % 3 == 1时，说明左区间最后还多一个0，那么右区间就得以120开头才可以。故为L.a[0] + R.a[3]。 - 当左区间长度
L.len % 3 == 2时，说明左区间最后还多一个01，那么右区间就得以201开头才可以。故为L.a[0] + R.a[4]。
同理，可以得出另外五类。
修改单个位置，即线段树的单点修改即可。
#include <bits/stdc++.h>
using namespace std;
#define debug(x) cerr << #x << ": " << x << '\n';
#define bd cerr << "----------------------" << el;
#define el '\n'
#define rep(i, a, b) for (int i = (a); i <= (b); i++)
#define lop(i, a, b) for (int i = (a); i < (b); i++)
#define dwn(i, a, b) for (int i = (a); i >= (b); i--)
#define cmax(a, b) a = max(a, b)
#define cmin(a, b) a = min(a, b)
#define x first
#define y second
#define db double
typedef long long LL;
typedef pair<int, int> PII;
constexpr int N = 2e6 + 10, md = 1e9 + 7;
constexpr int INF = 0x3f3f3f3f;
int n, m;
int q;
struct Info {
int a[6];
int len;
Info(int v){
memset(a, 0, sizeof(a));
a[2 * v] = a[2 * v + 1] = 1;
len = 1;
}
Info(){
memset(a, 0, sizeof(a));
len = 0;
}
};
Info merge(const Info &a, const Info &b) {
Info res;
res.len = a.len + b.len;
int r = a.len % 3;
int d[6];
if(r == 0)
{
for(int i = 0; i < 6; i ++ )
d[i] = i;
}
else if(r == 1)
{
d[0] = 3;
d[1] = 5;
d[2] = 1;
d[3] = 4;
d[4] = 0;
d[5] = 2;
}
else {
d[0] = 4;
d[1] = 2;
d[2] = 5;
d[3] = 0;
d[4] = 3;
d[5] = 1;
}
for(int i = 0; i < 6; i ++)
res.a[i] = a.a[i] + b.a[d[i]];
return res;
}
struct SegmentTree {
int n;
std::vector<Info> info;
SegmentTree(int n) : n(n), info(4 * n) {};
void pull(int p) {
info[p] = merge(info[2 * p], info[2 * p + 1]);
}
void modify(int p, int l, int r, int pos, int v) {
if (r - l == 1) {
info[p] = Info(v);
return;
}
int m = (l + r) / 2;
if (pos < m) {
modify(2 * p, l, m, pos, v);
} else {
modify(2 * p + 1, m, r, pos, v);
}
pull(p);
}
void modify(int pos, int v) {
modify(1, 0, n, pos, v);
}
Info query(int p, int l, int r, int x, int y) {
if (l >= y || r <= x) {
return Info();
}
if (l >= x && r <= y) {
return info[p];
}
int m = (l + r) / 2;
return merge(query(2 * p, l, m, x, y), query(2 * p + 1, m, r, x, y));
}
Info query(int l, int r) {
return query(1, 0, n, l, r);
}
};
int toInt(char c)
{
if(c == 'r')
return 0;
else if(c == 'e')
return 1;
else
return 2;
}
void solve()
{
cin >> n >> q;
string s;
cin >> s;
int x, l, r;
char c;
SegmentTree t(n);
lop(i, 0, n)
{
t.modify(i, toInt(s[i]));
}
// cerr << "ts" << el;
while(q --)
{
int op;
cin >> op;
if(op == 1)
{
cin >> x >> c;
-- x;
t.modify(x, toInt(c));
}
else {
cin >> l >> r;
l --;
auto res = t.query(l, r);
int len = res.len;
// debug(len);
int ans = 0;
// cerr << "res = ";
lop(i, 0, 6)
{
// cerr << res.a[i] << ' ';
cmax(ans, res.a[i]);
}
// cerr << el;
cout << len - ans << el;
}
}
}
int main()
{
cin.tie(0)->sync_with_stdio(false);
cout.tie(0);
solve();
}
京公网安备 11010502036488号