链接：https://www.matiji.net/exam/oj-questionbank
MC0455四大名著-西游签到
算法：
模拟。
思路：
无。
关键代码：
void solve()
{
string s, t;
cin >> s >> t;
int n = s.size();
int l = 0, r = n - 1;
while (l < n && s[l] == t[l])
++l;
while (r >= 0 && s[r] == t[r])
--r;
if (l == n)
{
cout << "Y" << endl;
return;
}
for (int i = l, j = r; i < j; i++, j--)
swap(s[i], s[j]);
if (s == t)
cout << "Y" << endl;
else
cout << "N" << endl;
}MC0456斩断灵藤
算法：
图论，树，贪心。
思路：
定义：
- 节点 \(1\) 为根节点。
- \(size[u]\) 为以 \(u\) 为根的子树大小。
- \(son\) 存储当前节点的各个子树的大小。
贪心策略：
本题从节点 \(1\) 开始进行 \(DFS\) 遍历，在回溯过程中统计每个节点的子树大小。对于每个节点，先将所有子节点对应的子树大小升序排序，再依次尝试将这些子树合并到当前节点上。合并时，如果当前总大小不超过限制 \(m\)，则将其并入；否则，说明无法继续合并，需要将当前及剩余子树“斩断”，并将分割次数累加。这个过程通过贪心策略尽可能合并较小的子树，从而最小化最终连通块的数量。
关键代码：
void solve()
{
int n, m;
cin >> n >> m;
vector<int> g[n + 10];
for (int i = 0; i < n - 1; ++i)
{
int u, v;
cin >> u >> v;
g[u].push_back(v);
g[v].push_back(u);
}
ll ans = 0;
vector<int> size(n + 10, 1);
function<void(int, int)> dfs = [&](int u, int f) -> void
{
vector<int> son;
for (auto v : g[u])
{
if (v == f)
continue;
dfs(v, u);
son.push_back(size[v]);
}
sort(all(son));
for (int i = 0; i < son.size(); ++i)
{
if (size[u] + son[i] <= m)
size[u] += son[i];
else
{
ans += son.size() - i;
break;
}
}
};
dfs(1, -1);
cout << ans + 1 << endl;
}MC0457符咒封印
算法：
推公式，前缀和。
思路：
每次暴力查询每个区间必然超时，所以考虑使用前缀和优化，再推到出一个公式，每次查询仅需 \(O(1)\) 即可。
公式推导：\(\sum_{i=l}^{r} (i – l + 1) \cdot a_i = \sum_{i=l}^{r} i \cdot a_i – (l – 1) \cdot \sum_{i=l}^{r} a_i\)
因此我们可以提前预处理出这两个前缀和数组：
- \(ss[i] = 1 \cdot a_1 + 2 \cdot a_2 + \cdots + i \cdot a_i\)
- \(s[i] = a_1 + a_2 + \cdots + a_i\)
那么对于每次查询 \([l, r]\)，我们就可以直接快速计算出答案：
\(\text{ans} = (ss[r] – ss[l-1]) – (l-1) \cdot (s[r] – s[l-1])\)
注意还要取模，每次计算取模加同余处理一下即可。
关键代码：
void solve()
{
ll n, q;
cin >> n >> q;
vector<ll> a(n + 10);
for (int i = 1; i <= n; ++i)
{
cin >> a[i];
a[i] %= MOD;
}
vector<ll> s(n + 10, 0);
vector<ll> ss(n + 10, 0);
for (int i = 1; i <= n; ++i)
{
s[i] = (s[i - 1] + a[i]) % MOD;
ss[i] = (ss[i - 1] + (i * a[i] % MOD)) % MOD;
}
while (q--)
{
ll l, r;
cin >> l >> r;
cout << ((ss[r] - ss[l - 1] + MOD) % MOD - (l - 1) * (s[r] - s[l - 1]) % MOD + MOD) % MOD << endl;
}
}MC0461排队
算法：
贪心，区间选点不重合问题。
思路：
题目中给出的三种操作可转换成：
- 操作1：可选区间 \([x + 1, n]\)。
- 操作2：可选区间 \([1, x + 1]\)。
- 操作3：可选区间 \([x + 1, y + 1]\)。
进行以上转换后不难想到这是一个区间选点不重合问题。
对区间左端点排序，枚举\(1 \text{ ~ } n\)上的所有点，每次将区间内有该点的加入到堆中，右端点最小的区间选择该点，如果无法选择就说明不成立。
关键代码：
void solve()
{
int n;
cin >> n;
bool flag = 0;
vector<pii> range;
for (int i = 0; i < n; ++i)
{
int op, x, y;
cin >> op;
if (op == 1)
{
cin >> x;
range.push_back({x + 1, n});
}
else if (op == 2)
{
cin >> x;
range.push_back({1, x + 1});
}
else
{
cin >> x >> y;
if (x > y)
flag = 1;
range.push_back({x + 1, y + 1});
}
}
if (flag)
{
cout << "N" << endl;
return;
}
sort(all(range));
priority_queue<int, vector<int>, greater<int>> q;
for (int i = 1, j = 0; i <= n; ++i)
{
while (j < n && range[j].first <= i)
q.push(range[j++].second);
if (q.size())
{
if (q.top() >= i)
q.pop();
else
{
cout << "N" << endl;
return;
}
}
}
if (q.size())
cout << "N" << endl;
else
cout << "Y" << endl;
}MC0462最后一难
算法：
模拟。
思路：
无。
关键代码：
void solve()
{
string s;
cin >> s;
ll ans = 0;
for (int i = 0; i < s.size(); ++i)
if (s[i] == 'm')
ans += (s.substr(i, 6) == "matiji");
cout << ans << endl;
}