Visits: 378

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

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