2022-11-3总结

正方形

Description

给定一个 $n*m$ 的棋盘，其中有些格子是障碍，有 $q$ 次询问，每次询问给出 $x1,y1,x2,y2,w$，问能否将以 $(x1,y1)$ 为右下角的边长为 $w$ 的正方形通过平移使得右下角移动到 $x2,y1$，期间不穿过障碍且不能超出棋盘。

Input

第一行三个整数 $n,m,q$。

接下来 $n$ 行，每行一个长度为 $m$ 的 $01$ 字符串，其中第 $j$ 个字符表示 $(i,j)$ 是否有障碍，$1$ 表示障碍。

接下来 $q$ 行，每行五个整数 $x_1,y_1,x_2,y_2,w$。

Output

输出 $q$ 行 Yes 或 No。

Hint

$n,m \le 10^3, q \le 10^5$

Solution

先 $O(nm)$ 处理出以每个格子为右下角能放下的最大正方形 $siz_{i,j}$，首先小的正方形能走的格子肯定比大的正方形多，所以我们将询问按 $w$ 从大到小排序，每次只加入 $siz_{i,j} \ge w$ 的格子，然后判断 $(x1,y1)$ 与 $(x2,y2)$ 是否联通，这个可以并查集维护，注意特判起点终点相同的情况。

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

typedef pair<int,int> pir;
const int N = 1005;
const int Q = 1e5+10;

const int dx[] = {0, 1, 1};
const int dy[] = {1, 0, 1};

const int dx2[] = {1, -1, 0, 0};
const int dy2[] = {0, 0, 1, -1};

namespace dsu {
    int fa[N*N], siz[N*N];
    void init(int n)
    {
        for(int i = 1; i <= n; i++)
            fa[i] = i, siz[i] = 1;
    }
    int find(int x)
    {
        return fa[x] == x ? x : fa[x] = find(fa[x]);
    }
    void merge(int x, int y)
    {
        x = find(x), y = find(y);
        if(x == y) return void();
        if(siz[x] < siz[y]) swap(x, y);
        siz[x] += siz[y]; fa[y] = x;
    }
    bool check(int x, int y)
    {
        return find(x) == find(y);
    }
}

struct query { int x1, y1, x2, y2, w, id; };

int n, m, q;
int siz[N][N];
char s[N][N];
query qry[Q];
vector<pir> id[N];
bool ans[Q];

void prework();

#define pos(i,j) ((i-1)*m+j)

int main()
{
    cin >> n >> m >> q;
    for(int i = 1; i <= n; i++)
        cin >> (s[i]+1);
    prework();
    for(int i = 1; i <= q; i++)
    {
        cin >> qry[i].x1 >> qry[i].y1;
        cin >> qry[i].x2 >> qry[i].y2;
        cin >> qry[i].w; qry[i].id = i;
    }
    sort(qry+1, qry+q+1, [](query a, query b){
        return a.w > b.w;
    });
    
    dsu::init(n*m);
    for(int i = 1, j = min(n,m); i <= q; i++)
    {
        while(j > 0 and j >= qry[i].w)
        {
            for(auto x : id[j])
            {
                for(int k = 0; k < 4; k++)
                {
                    int nx = dx2[k]+x.first;
                    int ny = dy2[k]+x.second;
                    if(1 <= nx and nx <= n and 1 <= ny and ny <= m and siz[nx][ny] >= j)
                        dsu::merge(pos(x.first,x.second), pos(nx,ny));
                }
            }
            j--;
        }
        if(qry[i].x1 != qry[i].x2 or qry[i].y1 != qry[i].y2)
            ans[qry[i].id] = dsu::check(pos(qry[i].x1,qry[i].y1), pos(qry[i].x2,qry[i].y2));
        else
            ans[qry[i].id] = (siz[qry[i].x1][qry[i].y1] >= qry[i].w);
    }
    
    for(int i = 1; i <= q; i++)
        cout << (ans[i] ? "Yes" : "No") << "\n";
}

void prework()
{
    memset(siz, -1, sizeof(siz));
    queue<pir> q; int x;
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= m; j++)
            if(s[i][j] == '1')
                q.push({i, j}), siz[i][j] = 0;
    for(int i = 1; i <= n; i++)
        q.push({i, 0}), siz[i][0] = 0;
    for(int i = 1; i <= m; i++)
        q.push({0, i}), siz[0][i] = 0;
    while(!q.empty())
    {
        auto a = q.front(); q.pop();
        for(int k = 0; k < 3; k++)
        {
            int nx = dx[k]+a.first;
            int ny = dy[k]+a.second;
            if(nx <= n and ny <= m and siz[nx][ny] == -1)
            {
                siz[nx][ny] = siz[a.first][a.second]+1;
                q.push({nx, ny});
            }
        }
    }
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= m; j++)
            if(siz[i][j] != -1) id[siz[i][j]].push_back({i, j});
}

纳什均衡

Description

给定一个 $n$ 个点的有根树，标号 $0 \sim n-1$ ，根的标号是 $0$ ，每个节点的儿子数只能为 $0$ 或 $2$，将节点分成以下三类：

$E$：到根距离为偶数的所有非叶子节点的集合。

$O$：到根距离为奇数的所有非叶子节点的集合。

$L$：所有叶子节点的集合。

对于所有叶子节点 $x \in L$ ，都会被分配一个二元组 $(c(x), d(x))$。

游戏开始前，Alice 对于 $E$ 中的每个点 $x$，从两个儿子中选择一个作为重儿子，类似地，Bob 对于 $O$ 中的每个点 $x$ ，选择一个儿子作为重儿子。

当策略确定之后，从根开始，不断沿着重儿子走，直到走到某个叶子节点 $x$，此时 Alice 得分 $c(x)$，Bob 得分 $d(x)$。

如果一组策略满足其中一方不改变策略的条件下，另一方无法通过改变自己的策略来获得更高的分数，那么称这一组策略为纳什均衡点。

给定树形态和 $k$，令 $c$ 和 $d$ 的值域都是 ${1,2,\cdots,k}$，那么一共有 $k^{2|L|}$ 组不同的 $(c,d)$，现在要求对每组不同的 $(c,d)$ 都计算纳什均衡点的个数，答案对 $998244353$ 取模。

Input

第一行两个整数 $n, k$。

第二行包括 $n-1$ 个数，第 $i$ 个数为 $fa_i$，即编号为 $i$ 的节点的父亲的编号。

Output

一行一个整数表示答案。

Hint

$n \le 5000, k \le 20$。

Solution

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

typedef long long ll;
const int N = 5005;
const int P = 998244353;


int n; ll k, c, d;
ll f[N], a[N], b[N], all[N];
int ls[N], rs[N];

void dfs(int x, bool t);

int main()
{
    cin >> n >> k;
    for(int i = 2; i <= n; i++)
    {
        int fa; cin >> fa; fa++;
        rs[fa] = ls[fa]; ls[fa] = i;
    }
    ll ans = 0;
    for(c = 1; c <= k; c++)
        for(d = 1; d <= k; d++)
            dfs(1, 0), (ans += f[1]) %= P;
    cout << ans << "\n";
}

void dfs(int x, bool t)
{
    if(!ls[x])
    {
        f[x] = 1;
        a[x] = k*c%P;
        b[x] = k*d%P;
        all[x] = k*k%P;
        return void();
    }
    dfs(ls[x], t^1);
    dfs(rs[x], t^1);
    
    #define l ls[x]
    #define r rs[x]
    
    if(!t)
    {
        f[x] = (f[l]*a[r]%P + f[r]*a[l]%P)%P;
        a[x] = 2*a[l]*a[r]%P;
        b[x] = (b[l]*all[r]%P + b[r]*all[l]%P)%P;
    }
    else
    {
        f[x] = (f[l]*b[r]%P + f[r]*b[l]%P)%P;
        a[x] = (a[l]*all[r]%P + a[r]*all[l]%P)%P;
        b[x] = 2*b[l]*b[r]%P;
    }
    all[x] = 2*all[l]*all[r]%P;
}