10.8模拟赛 —— Violet4

2022秋

Contest_Summary

Expcet：

Present：

• T1结论很好猜，但是构造比较玄学，做得时间太久但是还是没构造出来。
• T2想到了最大独立集，但实际上是个最长反链
• T3简单题。

T1 Rabbit

Description

Solution

首先考虑猜答案，显然是 $n * (n - 1) >> 1$

考虑怎么构造方案，把 $n$ 个点排成一个圈，可以发现选取公差为 $len$ 的等差序列，即可使每个点对都正好被覆盖 $3$ 次。

Code

//The Code Is From Dawn
#include<bits/stdc++.h>
using namespace std;
inline int read() {
    int x = 0;
    char c = getchar();
    bool f = 0;
    while(!isdigit(c)) f |= (c == '-'), c = getchar();
    while(isdigit(c)) x = (x * 10) + (c ^ 48), c = getchar();
    return f ? -x : x; 
}
const int maxn = 1005;
int n;
int main() {
//  freopen("rabbit.in", "r", stdin);
//  freopen("rabbit.out", "w", stdout);
    n = read();
    printf("%d\n", n * (n - 1) >> 1);
    for(register int i = 1; i <= n; ++i)
        for(register int j = 1; j <= (n - 1) / 2; ++j)
            printf("%d %d %d\n", i, ((i + j) % n == 0 ? n : (i + j) % n), ((i + (j << 1)) % n == 0 ? n : (i + (j << 1)) % n));
    return 0;
}

Summary

考场上猜规律猜得太久了，浪费了很多时间。

T2 Travel

Description

Solution

就是 [CTSC2008]祭祀 的前两问。

一道非常好的网络流题，此题就是要求最长反链/最大独立集。

首先有个结论：

最长反链 = 最小可重链覆盖

由于 $n$ 很小，我们直接传递闭包，把每个点对的连通性求出来，所以对于 DAG：

最长反链 = 最小不可重链覆盖

其实也就是

最大独立集 = n - 最小点覆盖

两种方式理解都可以。

然后套路的把点拆成入点和出点，建出二分图，最大匹配。

最小不可重链覆盖 = n - 最小点覆盖 = n - 最大匹配

第一问的答案就求出来了。

第二问有两种求法：

$1 ^ o$ Sol1

考虑哪些点可能成为最长反链上的点，可以发现如果删去一个点，答案 $-1$，则此点可以是最长反链上的点，称这些点为可行点。

然后做一个染色，任选一个可行点染上颜色 $i$，并把所有可到达的可行点也染成 $i$，总颜色数就是答案。

复杂度瓶颈在找可行点，复杂度 $O(n^{3.5})$

$2 ^o$ Sol2

一个很奇妙的结论：

原图的最大独立集由入点与出点都在二分图最大独立集中的点组成。

考虑感性证明一下这个结论。

如果某点在原图的最大独立集中，拆点后入点与出点一定也在二分图的最大独立集中。

所以把二分图最大独立集中那些单独多出来的点剃掉，应该就是原图的最大独立集（其实证的不完备，理解即可）。

然后就是如何求二分图的最大独立集。

从左侧未匹配点开始，从左往右只跑未匹配边，从右往左只跑匹配边，跑个 $dfs$。
那么左侧未被跑到的点与右侧被跑到的点就是最小点覆盖，补集就是最大独立集。

这一部分的复杂度是 $O(n + m)$，总复杂度 $O(n^3)$，瓶颈在匈牙利与传递闭包。

//The Code Is From Dawn
#include<bits/stdc++.h>
using namespace std;
inline int read() {
    int x = 0;
    char c = getchar();
    bool f = 0;
    while(!isdigit(c)) f |= (c == '-'), c = getchar();
    while(isdigit(c)) x = (x * 10) + (c ^ 48), c = getchar();
    return f ? -x : x; 
}
const int maxn = 205, maxm = 4 * 1e4 + 5;
int n, m, Cnt;
int mapp[maxn][maxn], Vst[maxm], Match[maxm], flag[2][maxm], Use[maxm];
inline bool Search(int x) {
    Vst[x] = 1;
    for(register int y = 1; y <= n; ++y)
        if(mapp[x][y] && (!Match[y] || (!Vst[Match[y]] && Search(Match[y])))) { Match[y] = x; return 1; }
    return 0;
}
inline void Get_Ans(int x) {
    flag[1][x] = 1;
    for(register int y = 1; y <= n; ++y)
        if(mapp[x][y] && Match[y] != x && !flag[0][y]) {
            flag[0][y] = 1;
            if(Match[y] != 0) Get_Ans(Match[y]);
        }
}
int main() {
//  freopen("travel.in", "r", stdin);
//  freopen("travel.out", "w", stdout);
    n = read(), m = read();
    for(register int i = 1; i <= m; ++i) {
        int u = read(), v = read();
        mapp[u][v] = 1;
    }
    for(register int k = 1; k <= n; ++k)
        for(register int i = 1; i <= n; ++i)
            for(register int j = 1; j <= n; ++j) mapp[i][j] |= (mapp[i][k] && mapp[k][j]);
    for(register int i = 1; i <= n; ++i) {
        memset(Vst, 0, sizeof(Vst));
        if(Search(i)) Cnt++;
    }
    printf("%d\n", n - Cnt);
    for(register int i = 1; i <= n; ++i) Use[Match[i]] = 1;
    for(register int i = 1; i <= n; ++i) 
        if(!Use[i]) Get_Ans(i);
    for(register int i = 1; i <= n; ++i)
        if(!flag[1][i] || flag[0][i]) continue;
        else printf("%d ", i);
    return 0;
}

Summary

一道值得反复思考的好题，用到了很多二分图/网络流的经典结论。

T3 galaxy

Description

Solution

看着很唬人，其实是个简单题。

考虑二操作其实是没限制的，所以 $(x, y)$ 与 $(x + 3 * k, y + 3 * k)$ 等价。

那么可以把棋盘缩成 $3 * 3$ 的大小，把所有坐标都对 $3$ 取余。

考虑记录每个点上有多少个棋子，此时只剩下一操作，Hash 下整个棋盘的状态，然记忆化 Search 即可。

注意：$n,m$ 小于 $3$ 的情况需要特殊判断。

//The Code Is From Dawn
#include<bits/stdc++.h>
#define int long long
using namespace std;
inline int read() {
    int x = 0;
    char c = getchar();
    bool f = 0;
    while(!isdigit(c)) {
        if(c == EOF) return -1;
        f |= (c == '-'), c = getchar();
    }
    while(isdigit(c)) x = (x * 10) + (c ^ 48), c = getchar();
    return f ? -x : x; 
}
const int maxn = 5;
int K, n, m, Ex, Ey;
map <int, int> Mapp;
int num[maxn][maxn], Maxx[maxn][maxn];
int go[8][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}, {1, 1}, {1, -1}, {-1, 1}, {-1, -1}};
inline int Hash() {
    int tot = 0;
    for(register int i = 0; i < 3; ++i)
        for(register int j = 0; j < 3; ++j) tot = tot * 11 + num[i][j];
    return tot;
}
inline int Search(int now) {
    if(now == 1) { return num[Ex][Ey] ? 1 : -1; }
    int State = Hash();
    if(Mapp[State]) return Mapp[State];
    for(register int x = 0; x < 3; ++x)
        for(register int y = 0; y < 3; ++y) {
            if(!num[x][y]) continue;
            for(register int i = 0; i < 8; ++i) {
                int nx = (x + go[i][0] + 3) % 3, ny = (y + go[i][1] + 3) % 3;
                if(nx < 0 || ny < 0 || nx >= n || ny >= m || !num[nx][ny]) continue;
                int Nex_nx = (nx + go[i][0] + 3) % 3, Nex_ny = (ny + go[i][1] + 3) % 3;
                if(Nex_nx < 0 || Nex_ny < 0 || Nex_nx > n || Nex_ny > m) continue;
                num[Nex_nx][Nex_ny]++, num[nx][ny]--, num[x][y]--;
                int tot = Search(now - 1);
                num[Nex_nx][Nex_ny]--, num[nx][ny]++, num[x][y]++;
                if(tot == 1) return Mapp[State] = 1;
            }
        }   
    return Mapp[State] = -1;
}
signed main() {
//  freopen("galaxy.in", "r", stdin);
//  freopen("galaxy.out", "w", stdout);
    while(~(K = read())) {
        n = read(), m = read(), Ex = (read() - 1) % 3, Ey = (read() - 1) % 3; 
        Mapp.clear();
        memset(num, 0, sizeof(num)), memset(Maxx, 0, sizeof(Maxx));
        for(register int i = 0; i < n; ++i)
            for(register int j = 0; j < m; ++j) Maxx[i % 3][j % 3]++;
        for(register int i = 1; i <= K; ++i) {
            int x = (read() - 1) % 3, y = (read() - 1) % 3;
            num[x][y]++;
        }
        if(n == 1 && m == 3 && Ey == 1) { printf("No\n"); continue; }
        if(Search(K) == 1) printf("Yes\n");
        else printf("No\n");
    }
    return 0;
}

Summary

无限制的移动，可以考虑可不可以缩到一个很小的范围之内。