AtCoder Grand Contest 043 题解

作者: xht37 分类: 题解 发布时间: 2020-04-18 15:16

点击数:198

AtCoder Grand Contest 043

Range Flip Find Route

注意到,最后走的路线一定是黑白交替的。

每一次翻转颜色都一定是在进入黑色的时候,将后面一段黑色的路变成白色。

这与最短路很类似,由于边权只有 $0/1$,因此本题用 deque bfs 即可,时间复杂度 $\mathcal O(nm)$。

const int N = 107, inf = 1e9;
int n, m, d[N][N], v[N][N];
char s[N][N];
deque<pi> q;

int main() {
    rd(n), rd(m);
    for (int i = 1; i <= n; i++) rds(s[i], m);
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            d[i][j] = inf;
    q.pb(mp(1, 1)), d[1][1] = s[1][1] == '#';
    while (q.size()) {
        pi x = q.front();
        q.pop_front();
        if (v[x.fi][x.se]) continue;
        v[x.fi][x.se] = 1;
        if (x.fi < n) {
            if (s[x.fi][x.se] == '.' && s[x.fi+1][x.se] == '#') {
                if (d[x.fi+1][x.se] > d[x.fi][x.se] + 1)
                    q.pb(mp(x.fi + 1, x.se)), d[x.fi+1][x.se] = d[x.fi][x.se] + 1;
            } else {
                if (d[x.fi+1][x.se] > d[x.fi][x.se])
                    q.push_front(mp(x.fi + 1, x.se)), d[x.fi+1][x.se] = d[x.fi][x.se];
            }
        }
        if (x.se < m) {
            if (s[x.fi][x.se] == '.' && s[x.fi][x.se+1] == '#') {
                if (d[x.fi][x.se+1] > d[x.fi][x.se] + 1)
                    q.pb(mp(x.fi, x.se + 1)), d[x.fi][x.se+1] = d[x.fi][x.se] + 1;
            } else {
                if (d[x.fi][x.se+1] > d[x.fi][x.se])
                    q.push_front(mp(x.fi, x.se + 1)), d[x.fi][x.se+1] = d[x.fi][x.se];
            }
        }
    }
    print(d[n][m]);
    return 0;
}

123 Triangle

首先进行一次绝对值差分,让序列中的数都在 $0 \sim 2$ 中,显然无论什么情况后面的每个数只可能为 $0 \sim 2$。

如果此时的序列中存在 $1$,则意味着答案只可能是 $0$ 或 $1$;如果不存在 $1$,则答案只可能是 $0$ 或 $2$。

对于不存在 $1$ 的情况,我们可以将每个数都 $\div 2$,最后再将答案 $\times 2$,这显然是等价的。

于是现在的答案都只可能是 $0$ 或 $1$ 了,于是显然我们只用在模 $2$ 的情况下讨论。

考虑一次绝对值差分在模 $2$ 意义下的影响,可以发现等价于 $\operatorname{xor}$。

现在问题变为,给定一个 $0/1$ 序列,每次将相邻两个数 $\operatorname{xor}$,求最后剩下的数。

那么考虑每个数会被异或几次即可,设序列长度为 $n$,则位置 $i$ 上的数会被异或 $\binom {n-1}{i-1}$ 次。

这时候我们还要求出模 $2$ 意义下的组合数,一个简单的方法是计算每个阶乘的分解中 $2$ 的次数,将计算组合数时的除法改为做减法。则对于一个组合数,最后如果剩下的 $2$ 的次数为 $0$,则说明 $\bmod 2 = 1$,否则 $\bmod 2 = 0$。

对于阶乘的分解,可以先对每个数简单地求出分解中 $2$ 的次数,然后做前缀和即可。

时间复杂度 $\mathcal O(n)$。

const int N = 1e6 + 7;
int n, a[N], c[N];
char s[N];

int main() {
    rd(n), rds(s, n), --n;
    for (int i = 1; i <= n; i++) a[i] = abs(s[i] - s[i+1]);
    bool ok = 0;
    for (int i = 1; i <= n; i++)
        if (a[i] == 1) ok = 1;
    if (!ok) for (int i = 1; i <= n; i++) a[i] >>= 1;
    for (int i = 1; i <= n; i++) {
        int x = i;
        while (!(x & 1)) ++c[i], x >>= 1;
        c[i] += c[i-1];
    }
    int ans = 0;
    for (int i = 1; i <= n; i++)
        ans ^= c[n-1] - c[i-1] - c[n-i] ? 0 : (a[i] & 1);
    if (!ok) ans <<= 1;
    print(ans);
    return 0;
}

Giant Graph

以下设 $n,m$ 同阶。

由于 $10^{18}$ 非常大,因此求最大独立集,相当于贪心地从权值大的往小的选,能选则选。

考虑 dp,设 $f_{x,y,z}$ 表示点 $(x,y,z)$ 是否要被选。

转移方程为 $f_{x,y,z} = \prod_{(x^\prime,y^\prime,z^\prime) \to (x,y,z)} [f_{x^\prime,y^\prime,z^\prime} = 0]$,其中 $(x^\prime,y^\prime,z^\prime) \to (x,y,z)$ 表示 $(x^\prime,y^\prime,z^\prime), (x,y,z)$ 之间有边且 $x^\prime + y^\prime + z^\prime \ge x + y + z$。

时间复杂度 $\mathcal O(n^3)$,显然过不了。

考虑如下这样一个博弈问题:

有三张 $n$ 个点的有向图,每张图在某个点上都有一个标记。

有两个人轮流进行移动,每次移动可以将一个标记从一条出边移动过去。

谁不能移动了谁就输了。

对于这样一个博弈问题,用 $\operatorname{SG}$ 函数可以解决。

然后可以发现,这个博弈问题的 $\operatorname{SG}$ 函数和上面那个 dp 的状态是一样的。

而这个博弈问题中,三张图之间相互独立。

这让我们想到了 $\operatorname{Nim}$ 游戏,即我们可以将三张图的 $\operatorname{SG}$ 函数分开算,最后 $\operatorname{xor}$ 起来得到原来的 $\operatorname{SG}$ 函数。$\operatorname{SG}$ 函数为 $0$ 的点,即为原问题中要选择的点。

注意到,对于一个 DAG 博弈转移图,$\operatorname{SG}$ 函数值的上界是 $\mathcal O(\sqrt n)$ 的,因此我们可以 $\mathcal O(n)$ 求出答案。

const int N = 1e5 + 7;
const modint K = 1000000000000000000ll % P;
int n;
modint ans;
struct Graph {
    int n, m, sg[N], k;
    modint c[N];
    vi e[N];
    inline Graph() {}
    inline Graph(int n) : n(n) {}
    int SG(int x) {
        if (~sg[x]) return sg[x];
        map<int, bool> p;
        for (int y : e[x]) p[SG(y)] = 1;
        while (p[++sg[x]]);
        return sg[x];
    }
    inline void main() {
        rd(m);
        for (int i = 1; i <= n; i++) sg[i] = -1;
        for (int i = 1, x, y; i <= m; i++) {
            rd(x), rd(y);
            if (x > y) swap(x, y);
            e[x].pb(y);
        }
        for (int i = 1; i <= n; i++) if (!~sg[i]) SG(i);
        for (int i = 1; i <= n; i++) k = max(k, sg[i]), c[sg[i]] += K ^ i;
    }
} G[3];

int main() {
    rd(n);
    for (int i = 0; i < 3; i++) G[i] = Graph(n), G[i].main();
    for (int i = 0; i <= G[0].k; i++)
        for (int j = 0; j <= G[1].k; j++)
            ans += G[0].c[i] * G[1].c[j] * G[2].c[i^j];
    print(ans);
    return 0;
}

Merge Triplet

考虑已知每个序列,我们是如何构造排列的。

按照题意,每次选择最小的开头放入排列,然后扔掉。

这意味着,由于序列长度为 $3$,排列中一定不会出现连续四个(或以上)的数 $x_{1\dots 4}$,满足 $x_1 > x_{2\dots 4}$。

因此,最终的排列中,按照前缀 $\max$ 的位置划分,每一段的长度不超过 $3$,这是必要条件。

充分吗?不充分,比如 $2\ 1\ 4\ 3\ 6\ 5$ 就不可以。

我们发现,按照前缀 $\max$ 的位置划分,有三个长度为 $2$ 的段,而我们没办法讲其拼成两个长度为 $3$ 的序列。

于是另一个必要条件为,长度为 $2$ 的段个数不超过长度为 $1$ 的段个数

充分吗?充分,因为一旦满足这个条件,我们就能构造出来序列。

那么考虑如何计数,设 $f_{i,j}$ 表示考虑前 $i$ 个数,长度为 $1$ 的段个数减去长度为 $2$ 的段个数为 $j$ 的方案数。

转移时枚举下一段的长度 $1/2/3$ 即可,如果长度不为 $1$ 还要额外乘上系数,具体见代码。

时间复杂度 $\mathcal O(n^2)$。

const int N = 2e3 + 7, M = N * 3;
int n;
modint f[M][M<<1], ans;

int main() {
    rd(n), rd(P), n *= 3;
    f[0][M] = 1;
    for (int i = 0; i < n; i++)
        for (int j = -i; j <= i; j++) {
            f[i+1][j+1+M] += f[i][j+M];
            f[i+2][j-1+M] += f[i][j+M] * (i + 1);
            f[i+3][j+M] += f[i][j+M] * (i + 1) * (i + 2);
        }
    for (int j = 0; j <= n; j++) ans += f[n][j+M];
    print(ans);
    return 0;
}

Topology

首先判合法性,显然一个合法点集的所有子集都应该合法,一个非法点集的所有超集都应该非法,特别地,空集必须合法。

判完之后考虑如何构造,考虑一个极小非法点集 $S$。我们如果构造出来一个从 $(0,0)$ 开始的环,使得它在 $S$ 非法,在 $S$ 的真子集合法,那么对于所有的极小非法点集如此构造后,将这些环在 $(0,0)$ 处接起来即可。

考虑对于一个点集 $S$,如何判断一个环合法:

从环的最左端开始,沿一个方向走一圈,穿过第 $i(\in S)$ 条线上方时记录一个 $u_i$,穿过下方时记录一个 $d_i$,这样得到一个字符串。
不断地在字符串中选择两个相邻且相同的字符删掉,如果能清空,则该点集合法,否则非法。

稍微画一下就能证明。

显然如果我们已知这个字符串,是可以还原出这个环的,因此问题转化为构造这个字符串。

考虑如下递归构造,一开始在 $(0,0)$:

  1. 若此时右边只剩下了一个点,则绕一个圈,即返回 $u_1d_1$。
  2. 否则穿过第一个点的上方,然后递归,得到字符串 $t$,然后从第一个点上方穿回来。
  3. 再从第一个点的下方穿过去,按照 $t^r$ 的方式走,然后再从第一个点下方穿回来。
  4. 返回字符串 $u_1tu_1d_1t^r d_1$。

稍微画一下同样能证明这个构造的正确性。

#define Fail prints("Impossible"), exit(0)
#define vp vector<pi>
int n, f[1<<8|1];
string s;
vp p[1<<8|1], ans(1, mp(0, 0));

inline bool pd(int i) {
    for (int j = (i - 1) & i; j; j = (j - 1) & i)
        if (s[j] == '0') return 0;
    return 1;
}

inline void merge(vp &a, vp b) {
    for (pi o : b) a.pb(o);
}

inline vp work(int i) {
    if (p[i].size()) return p[i];
    int j = i & -i, k = f[j];
    p[i].pb(mp(k, 1));
    p[i].pb(mp(k + 1, 1));
    vp t = work(i - j);
    merge(p[i], t);
    p[i].pb(mp(k + 1, 1));
    p[i].pb(mp(k, 1));
    p[i].pb(mp(k, 0));
    p[i].pb(mp(k + 1, 0));
    p[i].pb(mp(k + 1, 1));
    reverse(t.begin(), t.end());
    merge(p[i], t);
    p[i].pb(mp(k + 1, 1));
    p[i].pb(mp(k + 1, 0));
    p[i].pb(mp(k, 0));
    p[i].pb(mp(k, 1));
    return p[i];
}

inline vp get(pi a, pi b) {
    vp ret(1, a);
    if (a.se != b.se) return ret.pb(b), ret;
    while (a != b)
        a.fi += a.fi < b.fi ? 1 : -1, ret.pb(a);
    return ret;
}

inline vp update(vp a) {
    if (a.size() == 1u) return a;
    vp b;
    for (ui i = 1; i < a.size(); i++) merge(b, get(a[i-1], a[i]));
    return b;
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    cin >> n >> s;
    if (s[0] == '0') Fail;
    for (int i = 0; i < (1 << n); i++)
        if (s[i] == '1')
            for (int j = i; j; j = (j - 1) & i)
                if (s[j] == '0') Fail;
    for (int i = 0; i < n; i++) {
        f[1<<i] = i;
        p[1<<i].pb(mp(i, 1));
        p[1<<i].pb(mp(i + 1, 1));
        p[1<<i].pb(mp(i + 1, 0));
        p[1<<i].pb(mp(i, 0));
        p[1<<i].pb(mp(i, 1));
    }
    for (int i = 0; i < (1 << n); i++)
        if (s[i] == '0' && pd(i))
            ans.pb(mp(0, 1)), merge(ans, work(i)),
            ans.pb(mp(0, 1)), ans.pb(mp(0, 0));
    ans = update(ans);
    ans.erase(unique(ans.begin(), ans.end()), ans.end());
    prints("Possible");
    print(ans.size() - 1);
    for (pi o : ans) print(o.fi, o.se);
    return 0;
}

Jewelry Box

题目太神仙了,先咕咕咕着。

发表评论

电子邮件地址不会被公开。 必填项已用*标注