2022-10-18总结

取石子

Description

有 $n$ 堆石子，第 $i$ 堆石子有 $x_i$ 个。 Alice 和 Bob 轮流取石子， Alice 先手。每人每次从一堆石子中取 $a\sim b$ 个。无法操作的人失败。

此外，当一个人取完一堆石子时他会立即获胜。求谁会获胜。有多组数据。

Input

第一行一个整数 $t$ 表示数据组数。接下来每组数据两行：第一行三个整数 $n,a,b$ ，第二行 $n$ 个整数 $x_1,x_2,...,x_n$ 。

Output

每组数据输出一行一个字符串表示答案。

solution

考虑 SG 定理，先只看一堆石子的情况，石子个数为 $1 \sim a-1$ 时，那么先手无法操作，后手必胜，所以 SG 值为 $0$，对于 $a \sim b$ 的情况，因为这是必胜态的终止局面，所以没有 SG 值，可以看作 $-1$ 或者 $+ \infin$ (我也不确定是不是没有 SG 值，但是这么算就是对的，我也不太会博弈论（逃)。因为每次取的石子数的限制是固定的，所以 SG 值肯定会出现循环节，暴力算 SG 打个表找规律就很容易发现 SG 值的循环节是 $a+b$ 了。

整个游戏的 SG 值是所有子游戏 SG 值的异或和。

#include <cstdio>
#include <iostream>
using namespace std;
typedef long long ll;

int n, a, b;

void solve();
int SG(int x);

int main()
{
    int t; cin >> t;
    while(t --> 0) solve();
}

void solve()
{
    cin >> n >> a >> b;
    int sum = 0;
    bool flag = false;
    for(int i = 1; i <= n; i++)
    {
        int x; cin >> x;
        sum ^= SG(x);
        flag |= (a <= x and x <= b);
    }
    if(flag or sum != 0) cout << "Alice\n";
    else cout << "Bob\n";
}

int SG(int x)
{
    if(x < a) return 0;
    if(a <= x and x <= b) return -1;
    if(a == 1) return x%(a+b);
    
    x = (x-b)%(a+b);
    if(x/a > 1) return x/a;
    else return (x/a)^1;
}

Visibility Sequence

Description

给一个长度为 $N$ 的数列 $H_{1..N}$，第 $i$ 项在 $[1,H_i]$ 中选一个数，得到数列 $X_{1..N}$。

再构造一个数列 $P_{1..N}$，$P_i=\max j(j<i,X_j>X_i)$，若不存在这样的 $j$，$P_i=-1$

求能够造出多少种 $P$

Input

$N$

$H_1,H_2,\dots,H_N$

Output

答案，对 $10^9+7$ 取模

HINT

$1 \le n \le 100$

$1 \le H_i \le 10^5$

solution

将 $P_i$ 看成 $i$ 的父节点，那么整个 $P_i$ 可以对应一棵树，而且是一一对应。

显然子树内的编号连续，而且子树内根的编号最小。

对于树上一个节点 $i$ ，$X_i$ 至少要大于所有儿子节点的 $X$, 至少要大于等于比它编号小的兄弟节点的 $X$ 。

设 $t(l,r,v)$ 为编号从 $l$ 到 $r$， $X_i$ 最小值的最大值为 $v$ 的树的方案数，设 $f(l,r,v)$ 是相同条件下森林的方案数。

转移方程:

$$t(l,r,v) = f(l+1,r,v-1)[v \le H_l] \\ f(l,r,v) = t(l,r,v) + \sum_{k=l}^{r-1} \sum_{w=1}^v f(l,k,w)t(k+1,r,v) + \sum_{k=l}^{r-1}[v \le H_{k+1}] \sum_{w=1}^{v-1}f(l,k,v)t(k+1,r,w)$$

其中第一行 $t$ 的转移为强制让 $l$ 成为 $l+1 \sim r$ 中所有树的树根，第二行则是分别由一棵树、一段森林添加一棵树、一段森林下面接上一棵子树转移过来，这样每次添加一棵树可以保证不重不漏。

然后前缀优化一下可以做到 $O(n^4)$。

#include <algorithm>
#include <cstdio>
#include <iostream>
using namespace std;

typedef long long ll;
const int N = 105;
const int P = 1e9+7;

int n;
int a[N];
ll f[N][N][N], t[N][N][N];
ll sf[N][N][N], st[N][N][N];

int main()
{
    cin >> n;
    for(int i = 1; i <= n; i++)
        cin >> a[i], a[i] = min(a[i], n);
    for(int i = 1; i <= n; i++)
    {
        f[i][i][1] = t[i][i][1] = 1;
        for(int j = 1; j <= n; j++)
            sf[i][i][j] = st[i][i][j] = 1;
    }
    for(int len = 2; len <= n; len++)
    {
        for(int l = 1, r; (r = l+len-1) <= n; l++)
        {
            for(int i = 1; i <= a[l]; i++)
            {
                t[l][r][i] = f[l+1][r][i-1];
                f[l][r][i] += t[l][r][i];
            }
            for(int k = l; k <= r; k++)
            {
                for(int v = 1; v <= a[k+1]; v++)
                {
                    (f[l][r][v] += sf[l][k][v]*t[k+1][r][v]%P) %= P;
                    (f[l][r][v] += f[l][k][v]*st[k+1][r][v-1]%P) %= P;
                }
            }
            for(int i = 1; i <= n; i++)
            {
                sf[l][r][i] = (sf[l][r][i-1]+f[l][r][i])%P;
                st[l][r][i] = (st[l][r][i-1]+t[l][r][i])%P;
            }
        }
    }
    cout << sf[1][n][n];
}

Extending Set of Points

Description

对于一个二维点的集合 $S$，对其不断进行以下操作得到的集合称为 $S$ 的扩展集合 $E(S)$：一开始 $E(S)$ 为 $S$。不断取四个数 $x_1,y_1,x_2,y_2$，使得 $E(S)$ 中包含点 $(x_1,y_1),(x_1,y_2),(x_2,y_1)$ 但不包含点 $(x_2,y_2)$，然后将点 $(x_2,y_2)$ 加入 E(S)E(S)。重复这样的操作直到不能继续操作（即不存在符合要求的 $x_1,y_1,x_2,y_2$）为止。

一开始 $S$ 为空，依次给出 $q$ 个点 $p_{1 \dots q}$，依次对于 $1 \le i \le q$，如果 $p_i$ 不存在于 $S$ 中，那么将 p_ip**i 加入 $S$，否则将 $p_i$ 从 $S$ 中删除。

请在每次加入或删除操作后，求出 $E(S)$ 的大小。注意答案可能会超出 $32$ 位有符号整数的存储范围。

Input

输入第一行包含一个数 $q$，含义如上。

接下来 $q$ 行，其中其 $i$ 行包含两个数 $x_i,y_i$，表示点 $p_i$ 为 $(x_i,y_i)$。

Output

输出一行，包含 $q$ 个数，第 $i$ 个表示在第 $i$ 次加入或删除操作（即处理完 $p_i$）后，你求出的 $E(S)$ 的大小。

HINT

$1 \le q \le 3 \times 10^5$，对于 $1 \le i \le q$ 有 $1 \le x_i,y_i \le q$，输入的所有数为正整数。

solution

这个操作会将每个缺一个角的矩形添上那个角，如果我们将 $x$ 相同或 $y$ 相同的点连在一起，那么这个操作会将每个连通块补成一张网格，每个联通块点的贡献即为 $x$ 坐标的个数乘以 $y$ 坐标的个数。

这可以启示我们用并查集维护 $x,y$ 坐标，我们可以记录每个集合中 $x,y$ 坐标的个数，将一个坐标为 $(x,y)$ 的点看成合并 $x,y$ 这两个集合。

然后题目要求求出所有时间的答案，直接线段树分治即可。

#include <cassert>
#include <cstdio>
#include <iostream>
#include <map>
#include <utility>
#include <vector>
using namespace std;

const int N = 3e5+10;
typedef long long ll;
typedef pair<int,int> pir;
namespace dsu {
    ll ans;
    int fa[N*2], siz[N*2];
    int xtot[N*2], ytot[N*2];
    vector<pir> opt;
    void init(int n);
    int find(int x);
    bool merge(int x, int y);
    bool check(int x, int y);
    void rollback();
}
namespace tr {
    vector<pir> opt[N*4]; int lim;
    void add(int ql, int qr, pir val, int i = 1, int l = 1, int r = lim);
    void solve(int i = 1, int l = 1, int r = lim);
}

int q;
ll ans[N];
map<pir, int> mp;

int main()
{
    cin >> q;
    tr::lim = q;
    dsu::init(q);
    for(int i = 1; i <= q; i++)
    {
        pir x; cin >> x.first >> x.second;
        x.second += q;
        if(mp.count(x))
        {
            tr::add(mp[x], i-1, x);
            mp.erase(x);
        }
        else
            mp[x] = i;
    }
    for(auto i : mp)
        tr::add(i.second, q, i.first);
    
    tr::solve();
    
    for(int i = 1; i <= q; i++)
        cout << ans[i] << " ";
}

namespace tr {
    #define ls (i<<1)
    #define rs (i<<1|1)
    #define lmid ((l+r)>>1)
    #define rmid ((l+r+2)>>1)
    void add(int ql, int qr, pir val, int i, int l, int r)
    {
        if(ql <= l and r <= qr)
            return opt[i].push_back(val);
        if(ql <= lmid) add(ql, qr, val, ls, l, lmid);
        if(qr >= rmid) add(ql, qr, val, rs, rmid, r);
    }
    void solve(int i, int l, int r)
    {
        int cnt = 0;
        for(auto x : opt[i])
            cnt += dsu::merge(x.first, x.second);
        
        if(l == r)
            ans[l] = dsu::ans;
        else
        {
            solve(ls, l, lmid);
            solve(rs, rmid, r);
        }
        
        while(cnt--)
            dsu::rollback();
    }
}

namespace dsu {
    void init(int n)
    {
        for(int i = 1; i <= n*2; i++)
        {
            fa[i] = i, siz[i] = 1;
            xtot[i] = (i <= n);
            ytot[i] = (i > n);
        }
    }
    int find(int x)
    {
        return fa[x] == x ? x : find(fa[x]);
    }
    ll f(int x)
    {
        return (ll)xtot[x]*ytot[x];
    }
    bool merge(int x, int y)
    {
        x = find(x), y = find(y);
        if(x == y) return false;
        if(siz[x] < siz[y]) swap(x, y);
        opt.push_back({x, y});
        ans -= f(x)+f(y);
        siz[x] += siz[y];
        xtot[x] += xtot[y];
        ytot[x] += ytot[y];
        fa[y] = x;
        ans += f(x);
        return true;
    }
    bool check(int x, int y)
    {
        return find(x) == find(y);
    }
    void rollback()
    {
        int x = opt.back().first;
        int y = opt.back().second;
        opt.pop_back();
        ans -= f(x);
        siz[x] -= siz[y];
        xtot[x] -= xtot[y];
        ytot[x] -= ytot[y];
        fa[y] = y;
        ans += f(x)+f(y);
    }
}