「考试总结」ZROI-21-NOIP10连-DAY2 总结

#T1 比赛

#题意简述

有 \(2^n(n\le15)\) 个人玩剪刀石头布，每个人出的手式固定，已知有 \(r\) 个石头，\(p\) 个布，\(s\) 个剪刀，每一轮让相邻奇偶位的人玩，赢得进入下一轮，要求构造一种安排方式使得游戏最终一定有一个赢家。多组数据。

#大体思路

不难想到如果要出某个手势的人胜利，那么整个匹配树（恰好是完全二叉树）上的每一层节点包含的 \(R,P,S\) 的个数一定是确定的，于是便可以提前计算出不同层数的匹配树的不同根时的 \(R,P,S\) 分别有多少个，可以直接判无解的情况。

同样的，我们也可以直接构造出一组合法的解（不一定字典序最小），最后我们只需要取出对应层上的解并进行排序即可。

关于这里的排序，我们不难发现交换顺序只能是二叉树的一个结点的左右儿子进行交换，于是我们可以选择递归进行合并式的排序，这里笔者怕传参出现问题，直接写成非递归形式，模拟自下而上地合并，时间复杂度为 \(O(2^n\log 2^n)=O(n2^n)\).

#Code

#define mset(l, x) memset(l, x, sizeof(l))

const int N = 200010;
const int INF = 0x3fffffff;

int t, r, p, s, a[3][20][N], cnt[3][20][3], lg[N], ans[N], tmp[N];

inline void get_base() {
    for (int i = 1; i <= 100000; ++ i)
      lg[i] = lg[i >> 1] + 1;
    mset(a, -1); a[0][1][1] = 0;
    a[1][1][1] = 1, a[2][1][1] = 2;
    for (int i = 1; i < 16; ++ i)
      for (int j = 1 << (i - 1); j < (1 << i); ++ j)
        for (int k = 0; k <= 2; ++ k) {
            if (a[k][i][j] == 0) {
                a[k][i + 1][j << 1] = 0;
                a[k][i + 1][j << 1 | 1] = 1;
            } else if (a[k][i][j] == 1) {
                a[k][i + 1][j << 1] = 1;
                a[k][i + 1][j << 1 | 1] = 2;
            } else if (a[k][i][j] == 2) {
                a[k][i + 1][j << 1] = 0;
                a[k][i + 1][j << 1 | 1] = 2;
            }
        }
    cnt[0][1][0] = cnt[1][1][1] = cnt[2][1][2] = 1;
    for (int i = 2; i <= 16; ++ i) {
        for (int j = 0; j <= 2; ++ j) {
            cnt[0][i][j] = cnt[0][i - 1][j] + cnt[1][i - 1][j];
            cnt[1][i][j] = cnt[1][i - 1][j] + cnt[2][i - 1][j];
            cnt[2][i][j] = cnt[0][i - 1][j] + cnt[2][i - 1][j];
        }
    }
}

inline int check(int n, int i, int j, int k) {
    for (int o = 0; o <= 2; ++ o)
      if (cnt[o][n][0] == i && cnt[o][n][1] == j && cnt[o][n][2] == k)
        return o;
    return -1;
}

int main() {
    scanf("%d", &t); get_base();
    while (t --) {
        scanf("%d%d%d", &r, &p, &s);
        int n = r + p + s;
        int op = check(lg[n], p, r, s);
        if (!(~op)) {printf("-1\n"); continue;}
        /*取出答案*/
        for (int i = 1 << (lg[n] - 1); i < 1 << lg[n]; ++ i)
          ans[i - (1 << (lg[n] - 1)) + 1] = a[op][lg[n]][i];
        /*以下是对答案进行排序*/
        for (int i = 2; i <= n; i <<= 1) {
            for (int j = 1; j <= n; j += i)
              for (int k = 1; k <= i >> 1; ++ k) {
                  if (ans[j + k - 1] < ans[j + (i >> 1) + k - 1]) break;
                  if (ans[j + k - 1] > ans[j + (i >> 1) + k - 1]) {
                      for (int l = j; l <= j + (i >> 1) - 1; ++ l)
                        swap(ans[l], ans[l + (i >> 1)]);
                      break;
                  }
              }
        }
        for (int i = 1; i <= n; ++ i)
          if (ans[i] == 0) printf("P");
          else if (ans[i] == 1) printf("R");
          else if (ans[i] == 2) printf("S");
        printf("\n");
    }
    return 0;
}

#T2 幸运数字

#题意简述

给定一个数 \(a(a\in Z^+)\) 和一个数位集合 \(d_1\dots d_k\)，求一个最小的 \(b=da(d\in Z^+)\) 满足 \(b\) 没有前缀 \(0\)，且不包含 \(d_1\dots d_k\) 中的任意一个数位。

无解输出 \(-1\)，保证答案位数小于等于 \(10^6\).

#大体思路

乍一看会以为是数位 DP，但是显然答案范围太大了，不是数位 DP 可以处理的，注意到比较难处理的是倍数这一条件，考虑从倍数的性质入手，怎样的数是 \(a\) 的倍数呢？应当是 \(\bmod a=0\) 的数，这样的一个数 \(x\) 显然可以通过一个 \(\bmod a\ne0\) 的数 \(\left\lfloor\frac{x}{10}\right\rfloor\) 后面加上 \([0,9]\) 中的一位得到。

再来考虑模 \(a\) 得到的余数是如何变化的，不难想到对于一个 \(\bmod a=x\) 的数 \(\alpha\)，后面加上一位 \(y\)，新的余数应当是 \((x\times10+y)\bmod a\)，发现对于同一个 \(y\)，得到的余数结果与 \(\alpha\) 无关，只与 \(x\) 有关，而我们要求最小的答案，所以对于余数相同的只需要知道最小的是谁就好，那么这个过程可以枚举下一位是什么用 bfs 实现。

最差情况下 \(a\) 的每一个余数都被遍历到，时间复杂度为 \(O(a)\).

#Code

const int N = 2000010;
const int INF = 0x3fffffff;

struct Node {int val, pre, mod;} p[N];

int n, k, vis[N], ctuse[10], cnt, tal;

queue <int> q;

void print(int x) {
    if (!x) {return;} print(p[x].pre); 
    printf("%d", p[x].val);
}

int main() {
    scanf("%d%d", &n, &k);
    for (int i = 1; i <= k; ++ i) {
        int x; scanf("%d", &x);
        ctuse[x] = 1;
    }
    p[0] = (Node){0, -1, 0}; q.push(0);
    while (q.size()) {
        int now = q.front(), i = 0; q.pop();
        if (p[now].mod == 0) i = 1;
        for (; i <= 9; ++ i) if (!ctuse[i]) {
            int nmod = (p[now].mod * 10 + i) % n;
            if (!vis[nmod]) {
                vis[nmod] = 1; p[++ cnt] = (Node){i, now, nmod};
                if (!nmod) {tal = cnt; print(tal); return 0;}
                q.push(cnt);
            }
        }
    }
    printf("-1"); return 0;
}

#T3 匹配

#题意简述

给定一个 \(2n\) 个点的二分图，最初有 \(m\) 条边，要求添加尽可能少的边，使得无论怎么选 \(n\) 条边，都可以得到一张完全二分图。

#大体思路

首先不难得到 \(2n\) 个点的联通块，其中左部点和右部点数量相同（即为二分图），如果要满足题目条件，需要 \(n^2\) 条边，也就是对于每一个左部点向任意一个右部点都有边，否则一定存在一种选边方法使得无法满足条件，证明不难，略。

于是最差的情况不过是要连 \(n^2-m\) 条边。之后的想法便是不断考虑将几个联通块合成一个，而这样的需要添加边数与联通块的形态显然无关，只与已有边数有关，但可以到最后一起减去，于是之后便是不断考虑结合单点合成联通块，通过搜索剪枝进行更新答案，本质不同的联通块个数不多，可通过 DP 计算得到，于是时间复杂度得到保证。详细实现请结合代码理解。

#Code

#define pii pair <int, int>
#define mp(a, b) make_pair(a, b)

const int N = 100010;
const int INF = 0x3fffffff;

template <typename T>
inline T Max(const T a, const T b) {return a > b ? a : b;}

template <typename T>
inline T Min(const T a, const T b) {return a < b ? a : b;}

char s[N];
int t, n, m, fa[N], lsiz[N], rsiz[N], ans, sum, vis[N];

vector <pii > v;

inline int calc(int x) {return x * x;}

inline void init() {
    for (int i = 1; i <= n << 1; ++ i)
      fa[i] = i, lsiz[i] = (i <= n), rsiz[i] = (i > n);
}

inline int find(int x) {
    while (x != fa[x])
      x = fa[x] = fa[fa[x]];
    return x;
}

inline void merge(int x, int y) {
    x = find(x), y = find(y);
    if (x != y) {
        fa[x] = y;
        lsiz[y] += lsiz[x];
        rsiz[y] += rsiz[x];
    }
}

/*参数分别代表已经处理的联通块个数，选择的上一个要合成的联通块的位置*/
/*单个左部点个数，单个右部点个数，当前并入的联通块多出的右部点个数*/
void dfs(int k, int lst, int tot, int ltot, int rtot, int delta) {
    if (sum + Max(ltot, rtot) >= ans) return; //剪枝，显然不会有更优贡献
    if (!(~lst)) { //尝试更新答案
        if (k == v.size()) {ans = Min(ans, sum + ltot); return;}
    } else {
        sum += calc(tot + Max(0, delta));
        if (delta > 0) {
            if (ltot >= delta) dfs(k, -1, 0, ltot - delta, rtot, 0);
        } else {
            if (rtot + delta >= 0) dfs(k, -1, 0, ltot, rtot + delta, 0);
        } //回溯
        sum -= calc(tot + Max(0, delta));
    }
    pii now = mp(0, 0);
    for (int i = lst + 1; i < v.size(); ++ i)
      if (!vis[i] && v[i] != now) {
          /*相同形态的没必要进行反复查询*/
          now = v[i]; vis[i] = 1;
          dfs(k + 1, i, tot + v[i].first, ltot, rtot, delta - v[i].first + v[i].second);
          vis[i] = 0;
      }
}

int main() {
    scanf("%d", &t);
    while (t --) {
        scanf("%d", &n); init(); v.clear();
        ans = n * n, sum = m = 0;
        for (int i = 1; i <= n; ++ i) {
            scanf("%s", s + 1);
            for (int j = 1; j <= n; ++ j)
              if (s[j] == '1') ++ m, merge(i, j + n);
        }
        int ltot = 0, rtot = 0;
        for (int i = 1; i <= n << 1; ++ i)
          if (fa[i] == i) {
              if (lsiz[i] == rsiz[i])
                sum += calc(lsiz[i]);
              else if (!lsiz[i]) ++ rtot;
              else if (!rsiz[i]) ++ ltot;
              else v.push_back(mp(lsiz[i], rsiz[i]));
          }
        sort(v.begin(), v.end());
        dfs(0, -1, 0, ltot, rtot, 0);
        printf("%d\n", ans - m);
    }
    return 0;
}

#T4 拓扑

#题意简述

有一张有向图，有 \(2n^2\)个点，分成 \(n\) 组，每组 \(2n\) 个点。

对于每一组内，对于所有 \(1\le i<n\) 都有 \(i\to i+1,n+i\to n+i+1\) 的边，对于所有 \(1\le i\le n\) 都有 \(i\to n+i\) 的边。

然后对于所有 \(2\le i\le n\)，第 \(1\) 组的 \(i+n−1\) 号点向第 \(i\) 组的 \(1\) 号，第 \(1\) 组的 \(i\) 号点向第 \(i\) 组的 \(n+1\) 号点都有连边。求这张图的拓扑序个数，答案很大，对读入的 \(p\) 取模。

例如 \(n=3\) 的时候图长这样：

#大体思路

这种计数问题很大概率是 DP，题目中给出的图已经很好的展现了整张图的性质，即如果已经选择了 \((1,i)\) 号点，且又选择了 \((1, n+i-1)\) 号点，那么就有一组点完全独立出来了，这时第一组怎么选已经影响不到这一组选择的顺序了，于是我们考虑对于第一组点做 DP。

设 \(f_{i,j}\) 表示当前第一组第一行选了 \(i\) 个点，第二行选了 \(j\) 个点的方案数，我们做如下讨论：

• 下一步再选第一行的下一个点，那么直接将 \(f_{i,j}\) 加到 \(f_{i+1,j}\) 中即可；
• 下一步选第二行的下一个点，
  • 如果当前 \(j<i-1\)，那么意味着此时会有新的一组解锁，这一组完全独立，在后面所有的位置中选出 \(2n\) 个位置，并算出选这一组可行的排列数量（设为 \(g\)，后面会讲如何递推 \(g\)），乘上此时的 \(f\) 贡献到 \(f_{i,j+1}\) 即可；
  • 否则选完之后，对于第一组下一步一定是接着选第一行的下一个，所以可以直接贡献到 \(f_{i+1,j+1}\)，但是在选第一行下一个前，可以先从第 \(j+1\) 组中选出 \(k\) 个，这一部分的贡献同样可以通过组合数计算位置个数乘上 \(g\) 得到；

上面就是 \(f\) 的递推过程，来看如何递推 \(g\)；设 \(g_{i,j}\) 表示单独一组第一行选了 \(i\) 个，第二行选了 \(j\) 个，此时剩下的部分可行的拓扑序数量，对于 \(i>j\) 的情况，下一步可以选第一行的，也可以选第二行的，于是就有 \[ g_{i,j}=g_{i+1,j}+g_{i,j+1},\tag{1} \] 当 \(i<j\) 时，不合法，规定这样的可行数量为 \(0\)，当 \(i=j\) 时，应当只能选第一行的，但根据我们上面 \(i<j\) 时的定义，发现此时仍然适用式 \((1)\)，所以不必特判。

边界是 \(g_{n,n}=1\).

#Code

常数大的离谱，荣登最劣解（

const int N = 3010;
const int M = 20000010;
const int INF = 0x3fffffff;

template <typename T>
inline T Min(const T a, const T b) {return a < b ? a : b;}

int n, m, MOD; ll f[N][N], g[N][N];
int fac[M], inv[M], invf[M];

inline int C(int a, int b) {
    if (a - b < MOD && MOD <= a) return 0;
    return 1ll * fac[a] * inv[b] % MOD * inv[a - b] % MOD;
}

signed main() {
    scanf("%d%d", &n, &MOD); m = 2 * n * n;
    fac[0] = inv[0] = inv[1] = 1;
    for (int i = 1; i < M; ++ i)
      if (i == MOD) fac[i] = fac[i - 1];
      else fac[i] = 1ll * fac[i - 1] * i % MOD;
    for (int i = 2; i < M; ++ i)
      if (i >= MOD) inv[i] = inv[i - MOD];
      else inv[i] = 1ll * (MOD - MOD / i) * inv[MOD % i] % MOD;
    for (int i = 1; i < M; ++ i)
      inv[i] = 1ll * inv[i - 1] * inv[i] % MOD;
    f[1][0] = 1, g[n][n] = 1;
    for (int i = n; ~i; -- i)
      for (int j = Min(n - 1, i); ~j; -- j)
        g[i][j] = (g[i + 1][j] + g[i][j + 1]) % MOD;
    for (int i = 1; i <= n; ++ i) {
        for (int j = 0; j < i; ++ j) {
          int rest = 2 * n * (n - j) - i - j;
          if (j == i - 1) {
              if (i == n) {printf("%d", f[i][j]); return 0;}
              (f[i + 1][j + 1] += 1ll * f[i][j] * C(rest - 2, n << 1) % MOD * g[1][0] % MOD) %= MOD;
              for (int k = 1; k <= n; ++ k)
                (f[i + 1][j + 1] += 1ll * f[i][j] * C(rest - k - 2, (n << 1) - k) % MOD * g[k][0] % MOD) %= MOD;
          } else (f[i][j + 1] += 1ll * f[i][j] * C(rest - 1, n << 1) % MOD * g[1][0] % MOD) %= MOD;
          if (i < n) (f[i + 1][j] += f[i][j]) %= MOD;
        }
    } 
    return 0;
}