链接：https://atcoder.jp/contests/abc403
A – Odd Position Sum
算法：
模拟。
思路：
无。
关键代码：
void miyan()
{
int n;
cin >> n;
ll ans = 0;
for (int i = 0; i < n; ++i)
{
int x;
cin >> x;
if (i % 2 == 0)
ans += x;
}
cout << ans << endl;
}B – Four Hidden
算法：
模拟。
思路：
无。
关键代码：
void miyan()
{
string t, u;
cin >> t >> u;
int n = t.size(), m = u.size();
if (m > n)
{
cout << "No" << endl;
return;
}
for (int i = 0; i < n - m + 1; ++i)
{
if (t[i] == '?' || t[i] == u[0])
{
bool ok = 1;
for (int j = 0; j < m; ++j)
{
if (t[i + j] != u[j] && t[i + j] != '?')
{
ok = 0;
break;
}
}
if (ok)
{
cout << "Yes" << endl;
return;
}
}
}
cout << "No" << endl;
}C – 403 Forbidden
算法：
模拟，\(stl\)。
思路：
无。
关键代码：
void miyan()
{
int n, m, q;
cin >> n >> m >> q;
vector<int> st(n + 1, 0);
vector<set<int>> hash(n + 1);
while (q--)
{
int op, x, y;
cin >> op;
if (op == 1)
{
cin >> x >> y;
if (!st[x])
hash[x].insert(y);
}
else if (op == 2)
{
cin >> x;
hash[x].clear();
st[x] = 1;
}
else
{
cin >> x >> y;
if (st[x] || hash[x].find(y) != hash[x].end())
cout << "Yes" << endl;
else
cout << "No" << endl;
}
}
}D – Forbidden Difference
算法：
\(dp\)。
思路：
先将所有元素都存入到桶中，然后将桶中的所有元素进行分组，分组规则如下：
- \(x\) 为序列中先前为分组的元素，将其以及 \(x + k/cotsd\) 加入到数组中。
此时这个数组中的元素需要删掉一些，既使得剩下的元素不相邻，使用 \(dp\) 解。
定义 \(dp[i]\) 为删除数组中第 \(i\) 个元素，前 \(i\) 个元素需要删掉的最小元素个数。
初始化定义 \(dp[0] = 0\)。
状态转移：
- 对于 \(dp[i]\) 其可以通过删除上上个元素或者上一个元素转移而来，状态转移方程为：
- \(dp[i] = min({dp[i], dp[i – 1] + m[v[i – 1]], dp[i – 2] + m[v[i – 1]]})\)
\(m[v[i]]\) 为原始序列中值为 \(v[i]\) 的元素个数。
关键代码：
void miyan()
{
int n, d;
cin >> n >> d;
vector<int> a(n);
for (int i = 0; i < n; ++i)
cin >> a[i];
map<int, int> m;
for (auto x : a)
++m[x];
if (d == 0)
{
cout << n - m.size() << endl;
return;
}
ll maxx = ranges::max(a);
ll ans = 0;
vector<int> st(maxx + 10, 0);
vector<int> v;
v.reserve(n);
for (auto [x, y] : m)
{
if (!st[x])
{
for (int i = x; i < maxx + 5; i += d)
{
if (!st[i] && m.count(i))
{
st[i] = 1;
v.push_back(i);
}
else
break;
}
vector<ll> dp(v.size() + 1, INT_MAX);
dp[0] = 0;
for (int i = 1; i <= v.size(); ++i)
{
if (i == 1)
dp[i] = min(dp[i], dp[i - 1] + m[v[i - 1]]);
else
dp[i] = min({dp[i], dp[i - 1] + m[v[i - 1]], dp[i - 2] + m[v[i - 1]]});
}
ans += min(dp[v.size()], dp[v.size() - 1]);
v.clear();
}
}
cout << ans << endl;
}E – Forbidden Prefix
算法：
字典树。
思路：
使用字典树维护：
- 在字典树中插入 \(x\) 的字符串时，如果某个节点为字符串结尾，就将其打上 \(flag\)。
- 在字典树中插入 \(y\) 的字符串时，如果其走的路上碰到了已经打上标记的节点时，就说明他的前缀在 \(x\) 中出现。
在当前插入 \(x\) 一个字符串时会将其结尾节点打上标记，但是无法快速的知道先前的 \(y\) 里的某个字符串的前缀是否包含当前插入的字符串，可以使用一个 \(pos\) 数组，存储经过某个节点的 \(y\) 里的字符串编号，此时在 \(x\) 插入字符串时，就可快速判断其结尾节点在 \(pos\) 里有几个 \(y\) 里的字符串的前缀。
关键代码：
void miyan()
{
int q;
cin >> q;
ll ans = 0;
ll idx = 0, id = 0;
vector tr(N, vector<int>(26, 0));
vector<int> st(N, 0);
vector<int> flag(N, 0);
vector<vector<int>> pos(N);
auto insert1 = [&](string s) -> void
{
int p = 0;
for (int i = 0; s[i]; ++i)
{
int c = s[i] - 'a';
if (!tr[p][c])
tr[p][c] = ++idx;
p = tr[p][c];
}
flag[p] = 1;
for (auto x : pos[p])
if (!st[x])
st[x] = 1, --ans;
pos[p].clear();
};
auto insert2 = [&](string s) -> void
{
++ans;
++id;
int p = 0;
for (int i = 0; s[i]; ++i)
{
int c = s[i] - 'a';
if (!tr[p][c])
tr[p][c] = ++idx;
p = tr[p][c];
pos[p].push_back(id);
if (!st[id] && flag[p])
st[id] = 1, --ans;
}
};
while (q--)
{
int op;
string s;
cin >> op >> s;
if (op == 1)
insert1(s);
else
insert2(s);
cout << ans << endl;
}
}F – Shortest One Formula
还没补。
