ABC425D - Ulam-Warburton Automaton

#include <bits/stdc++.h>
using namespace std;
int n, m;
// 存每个位置是第几轮被改成的黑色，从 1 开始，0表示白色
vector<int> s[300000 + 5];
queue<pair<int, int>> q;
int dx[] = {0, 0, 1, -1};
int dy[] = {1, -1, 0, 0};
// 检查要不要变
int tim; // 当前在处理第几轮
bool check(int x, int y)
{
    if (s[x][y])
        return false;
    int cnt = 0;
    for (int i = 0; i < 4; i++)
    {
        int nx = x + dx[i];
        int ny = y + dy[i];
        if (nx < 0 || nx > n - 1 || ny < 0 || ny > m - 1)
            continue;
        if (s[nx][ny] != 0 && s[nx][ny] < tim)
            cnt++;
    }
    return cnt == 1;
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> m;
    for (int i = 0; i <= n - 1; i++)
    {
        for (int j = 0; j <= m - 1; j++)
        {
            char x;
            cin >> x;
            if (x == '#')
            {
                s[i].push_back(1);
                q.push({i, j}); // 起点入队
            }
            else
                s[i].push_back(0);
        }
    }
    tim = 1;
    while (!q.empty())
    {
        // 一个有趣的写法，每次循环都处理完当前层
        int siz = q.size();
        tim++;
        while (siz--)
        {
            pair<int, int> now = q.front();
            q.pop();
            for (int i = 0; i < 4; i++)
            {
                int nx = now.first + dx[i];
                int ny = now.second + dy[i];
                if (nx < 0 || nx > n - 1 ||
                    ny < 0 || ny > m - 1 ||
                    !check(nx, ny))
                    continue;
                s[nx][ny] = tim;
                q.push({nx, ny});
            }
        }
    }
    int ans = 0;
    for (int i = 0; i <= n - 1; i++)
        for (int j = 0; j <= m - 1; j++)
            if (s[i][j] != 0)
                ans++;
    cout << ans << "\n";
    return 0;
}

ABC426D - Pop and Insert

#include <bits/stdc++.h>
using namespace std;

int n, cnt0, cnt1;
string s;
void work()
{
    cin >> n;
    cin >> s;
    cnt0 = cnt1 = 0;
    for (int i = 0; i < s.size(); i++)
    {
        cnt1 += s[i] == '1';
        cnt0 += s[i] == '0';
    }
    int ans = cnt0 * 1 + cnt1 * 2;
    // 初始化为 s[0] 这一个数字一段
    int nowLen = 1;
    int now = (s[0] == '1');
    int max0 = 0, max1 = 0;
    for (int i = 1; i < s.size(); i++)
    {
        if (s[i] == s[i - 1])
            nowLen++;
        else
        {
            if (now == 0)
                max0 = max(max0, nowLen);
            if (now == 1)
                max1 = max(max1, nowLen);
            now = (s[i] == '1');
            nowLen = 1;
        }
    }
    // 最后一段连续的也处理一下
    if (now == 0)
        max0 = max(max0, nowLen);
    if (now == 1)
        max1 = max(max1, nowLen);
    // 算答案
    // 要么全变0、要么全变 1
    // 保留最长的一段连续的，剩下的相同的要改两次，不同的要改一次
    cout << min(cnt1 * 1 + (cnt0 - max0) * 2,
                cnt0 * 1 + (cnt1 - max1) * 2)
         << "\n";
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    int T;
    cin >> T;
    while (T--)
        work();
    return 0;
}

ABC427E - Wind Cleaning

因为挪动后必然是原始矩阵的一个子矩阵，放到了某个位置，所以状态数量最多不超过 $O((nm)^3)$，是一个非常小的数，可以很随意地广搜。

#include <bits/stdc++.h>
using namespace std;
int n, m, Tx, Ty;
vector<pair<int, int>> a;
// 存所有广搜过程中的状态
queue<vector<pair<int, int>>> q;
// 存每个状态几步到达 <状态,几步>
map<vector<pair<int, int>>, int> dis;
// 方向数组
int dx[] = {0, 0, 1, -1};
int dy[] = {1, -1, 0, 0};
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin >> n >> m;
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= m; j++)
		{
			char c;
			cin >> c;
			if (c == 'T')
				Tx = i, Ty = j;
			if (c == '#')
				a.push_back({i, j});
		}
	// 纯暴力广搜，初始状态入队
	q.push(a);
	dis[a] = 0;
	while (!q.empty())
	{
		// 取出队头状态
		vector<pair<int, int>> now = q.front();
		q.pop();
		// 是否达成目标
		if (now.empty())
		{
			cout << dis[now] << "\n";
			return 0;
		}
		// 枚举后续状态
		for (int i = 0; i < 4; i++)
		{
			vector<pair<int, int>> nxt;
			bool flag = true;
			for (int j = 0; j < now.size(); j++)
			{
				// now[j] 这个垃圾移动到的位置
				int x = now[j].first + dx[i];
				int y = now[j].second + dy[i];
				// 检查这个方向能不能挪
				if (x == Tx && y == Ty)
				{
					flag = false;
					break;
				}
				// 检查挪完之后还在不在范围内
				if (x < 1 || x > n || y < 1 || y > m)
					continue;
				// 合法且还在范围内就加入后续状态
				nxt.push_back({x, y});
			}
			if (flag && dis.find(nxt) == dis.end())
			{
				dis[nxt] = dis[now] + 1;
				q.push(nxt);
			}
		}
	}
	cout << "-1";
	return 0;
}

ABC427D - The Simple Game

记忆化搜索

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 200000;
int n, m, k;
string s;
vector<int> e[MAXN + 5];
int book[25][MAXN + 5];
// 现在是第 now 轮，当前位置在 pos，最终胜利的人是谁
int dfs(int now, int pos)
{
    // 2*k 轮做完了，停哪儿就是谁赢
    if (now == 2 * k + 1)
        return s[pos - 1] == 'A';
    // 记忆化
    if (book[now][pos] != -1)
        return book[now][pos];
    // 当前的操作人 1 Alice 0 Bob
    int ab = now % 2;
    // 后续可以移动到 u，可以让操作人自己必胜，那就是自己
    for (int u : e[pos])
        if (dfs(now + 1, u) == ab)
            return book[now][pos] = ab;
    return book[now][pos] = 1 - ab;
}
void work()
{
    cin >> n >> m >> k;
    cin >> s;
    for (int i = 1; i <= n; i++)
        e[i].clear();
    for (int i = 1; i <= 2 * k + 1; i++)
        for (int j = 1; j <= n; j++)
            book[i][j] = -1;
    for (int i = 1; i <= m; i++)
    {
        int u, v;
        cin >> u >> v;
        e[u].push_back(v);
    }
    if (dfs(1, 1) == 1)
        cout << "Alice\n";
    else // ==0
        cout << "Bob\n";
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    int T;
    cin >> T;
    while (T--)
        work();
    return 0;
}