链接：https://atcoder.jp/contests/abc427
A – ABC -> AC
算法：
模拟。
思路：
无。
关键代码：
void miyan()
{
string s;
cin >> s;
for (int i = 0; i < s.size(); ++i)
{
if (i == s.size() / 2)
continue;
cout << s[i];
}
cout << endl;
}B – Sum of Digits Sequence
算法：
模拟。
思路：
无。
关键代码：
void miyan()
{
ll n;
cin >> n;
vector<int> a(100);
a[0] = 1;
ll sum = 0;
for (int i = 1; i <= n; ++i)
{
ll cur = 0;
int x = a[i - 1];
while (x)
cur += x % 10, x /= 10;
sum += cur;
a[i] = sum;
}
cout << a[n] << endl;
}C – Bipartize
算法：
暴搜，状态压缩。
思路：
由于 \(n\) 只有 \(10\)，考虑直接暴搜每个点的颜色。
使用状态压缩，对于 \(u\) 点 \(1\) 代表黑，\(0\) 代表白。
对于每种状态，枚举图上的所有边，累加所有相连且不相等的边，并更新全局最大答案，此时答案存储最大成立边数，最后答案就为 \(m – ans\)。
关键代码：
void miyan()
{
int n, m;
cin >> n >> m;
vector<pii> g(m);
for (int i = 0; i < m; ++i)
{
int u, v;
cin >> u >> v;
--u, --v;
g[i] = {u, v};
}
int ans = 0;
for (int mask = 0; mask < (1 << n); ++mask)
{
int cnt = 0;
for (auto [u, v] : g)
{
if ((mask >> u & 1) ^ (mask >> v & 1))
++cnt;
}
ans = max(ans, cnt);
}
cout << m - ans << endl;
}D – The Simple Game
算法：
\(dp\)，记忆化搜索。
思路：
当前操作的人想赢等价于下一个人怎么操作都是输。
使用记忆化搜索。
\(dp[u][now]\): 当前在 \(u\) 节点，前面已经走了 \(now\) 步，\(Alice\) 是否可以保证必赢。
状态转移：
- 边界情况，当前已经走了 \(k + k\) 步，判断最后棋子落在
'A'则 \(Alice\) 胜利，否则 \(Bob\) 胜利。 - 对于所有与点 \(u\) 想连的点 \(v\)：
- 如果当前是 \(Alice\) 执行：
- 他如果想赢就需要走一个后续节点可以赢的节点，只要有一个 \(v\) 能赢就走这个节点，既递归判断 \((v, now + 1)\) 的状态是否为 \(true\)。
- 如果后续节点都返回 \(false\) 就说明只能返回 \(false\)。
- 如果当前是 \(Bob\) 执行：
- 他如果想赢就需要走一个后续节点可以让 \(Alice\) 输的节点，只要有一个 \(v\) 可以让 \(Alice\) 输，就走这个节点，既递归判断 \((v, now + 1)\) 的状态是否为 \(false\)。
- 如果所有后继状态都 \(true\)，说明无论 \(Bob\) 怎么选，\(Alice\) 都能赢。
- 如果当前是 \(Alice\) 执行：
关键代码：
void miyan()
{
int n, m, k;
string s;
cin >> n >> m >> k >> s;
vector<vector<int>> g(n + 1);
while (m--)
{
int u, v;
cin >> u >> v;
g[u].push_back(v);
}
s = ' ' + s;
vector dp(n + 1, vector<int>(k + k + 1, -1));
auto dfs = [&](auto &&self, int u, int now) -> bool
{
auto &cur = dp[u][now];
if (cur != -1)
return cur;
if (now == k + k)
return (cur = (s[u] == 'A'));
for (auto v : g[u])
{
if (now % 2)
{
if (!self(self, v, now + 1))
return cur = 0;
}
else
{
if (self(self, v, now + 1))
return cur = 1;
}
}
return cur = now % 2;
};
cout << (dfs(dfs, 1, 0) ? "Alice" : "Bob") << endl;
}E – Wind Cleaning
算法：
\(bfs\)，最短路。
思路：
观察到 \(n\) 和 \(m\) 都很小，直接使用 \(bfs\) 跑最短路，队列存储当前地图和步数。
关键代码：
void miyan()
{
int n, m;
cin >> n >> m;
vector<string> s(n);
for (auto &x : s)
cin >> x;
auto bfs = [&]() -> int
{
queue<pair<vector<string>, int>> q;
set<vector<string>> hash;
q.push({s, 0});
hash.insert(s);
while (q.size())
{
auto [t, cnt] = q.front();
q.pop();
ll sum = 0;
for (int i = 0; i < n; ++i)
for (int j = 0; j < m; ++j)
sum += (t[i][j] == '#');
if (!sum)
return cnt;
for (int d = 0; d < 4; ++d)
{
vector<string> v(n, string(m, '.'));
for (int i = 0; i < n; ++i)
{
for (int j = 0; j < m; ++j)
{
if (t[i][j] == '#')
{
int a = i + dx[d], b = j + dy[d];
if (a < 0 || a >= n || b < 0 || b >= m)
continue;
if (t[a][b] == 'T')
goto NEXt;
v[a][b] = '#';
}
else if (t[i][j] == 'T')
v[i][j] = 'T';
}
}
if (hash.count(v))
continue;
hash.insert(v);
q.push({v, cnt + 1});
NEXt:;
}
}
return -1;
};
cout << bfs() << endl;
}F – Not Adjacent
折半搜索以后再补。
