牛客周赛92 - 民间题解

A. 小红的签到题

题意分析

构造一个长度为 $n$ 的字符串，字符串中仅包含小写字母，和唯一的一个 _，设 _ 坐标为 $p$ ，有 $p \neq 0 \land p \neq n - 1$

题解

随便输出一个字母，然后输出一个 _，然后随便输出 $n - 2$ 个字母即可。

代码

print('a_' + ("a" * (int(input()) - 2)))

void solve(){
    int n; cin >> n;
    cout << "a_";
    for(int i = 0; i < n - 2; ++i) cout << "a";
    return;
}

或者你也可以

from string import ascii_lowercase as al
import random as rd

n = int(input())
s = "x_"
t = n - 2
tmp = rd.choices(al, k = t)
print(s + ''.join(tmp))

B. 小红的模拟题

题意分析

给定一个 $n \times m$ 的迷宫，有一点是陷阱，构造一个移动方案，使小红可以从 $(1, 1)$ 走到 $(n, m)$ 且不踩到陷阱。

题解

我们可以考虑两个路径：先向右走到 $(1, m)$ ，然后向下走到 $(n, m)$ ；先向下走到 $(n, 1)$ ，再向右走到 $(n, m)$ 。

对于第一种方案，我们只要考虑这个陷阱不在矩形的上边或右边，第二种方案只需要考虑不在矩形的左边或下边，即可直接输出方案。

~~当然，你也可以写一个记忆化搜索回溯方案，但是这是B，何必折磨自己呢？~~

代码

int main(){
    int n, m;
    cin >> n >> m;
    vector<string> G(n);
    for(int i = 0; i < n; ++i) cin >> G[i];
    int sx = -1, sy = -1;
    for(int i = 0; i < n; ++i){
        for(int j = 0; j < m; ++j){
            if(G[i][j] == '#'){
                sx = i;
                sy = j;
                break;
            }
        }
        if(~sx) break;
    }
    if((sy != 0 and sx != n - 1)){ // 不在左和不在下
        for(int i = 0; i < n - 1; ++i) cout << "S";
        for(int i = 0; i < m - 1; ++i) cout << "D";
    }else if((sy != m - 1 and sx != 0)){ // 不在上和不在右
        for(int i = 0; i < m - 1; ++i) cout << "D";
        for(int i = 0; i < n - 1; ++i) cout << "S";
    }
    cout << endl;
    return false;
}

C. 小红的方神题

题意分析

题目中说的好像非常的明白。

题解

我们考虑这样一个排列：

$a = \{2, 3, 4, 5 ..., n - 2, n - 1, n, 1\}$

$b = f(a) = \{1, 1, 1, ...., 1, 1, n - 1\}$

$c = f(b) = \{0, 0, ..., 0, n - 2\}$

由于 $c$ 中除了 $n - 2$ 外全是 $0$ ，所以 $f$ 操作无法影响 $c$ 中这唯一一个正整数，故在经历若干次 $f$ 操作后，最后必然生成一个 $\{n - 2\}$ 。

即为所求。

代码

#define neg {cout << -1 << endl; return;}
void solve(){
    int n; cin >> n;
    if(n <= 2) neg;
    for(int i = 2; i <= n; ++i) cout << i << " ";
    cout << 1;
    cout << endl;
    return;
}

D. 小红的数学题

题意分析

好像就是简单直白，没什么可说的。

题解

设方程的两个根分别为 $a, b$ ，则根据韦达定理，有： $a + b = p, a \times b = q$ ，又因为 $p + q = k$ ，故有 $a + ab + b = k$ ，整理得到 $(a + 1)(b + 1) = k + 1$ 。

所以问题便转换为将 $k + 1$ 分解为两个不小于 $2$ 的因子 $A, B$ ，其中 $A = a + 1, B = b + 1$ ，使得 $A \times B = k + 1$ 。

此时， $p = A + B - 2, q = (A - 1)(B - 1)$ 。

我们枚举 $k$ 的全部因子，带入式子验证能否满足条件即可，如果能满足，则原方程一定有解。

总时间复杂度 $O(\sqrt {k + 1})$ ，在 $k = 10^{12}$ 的时候也仅有 $10^6$ 级别完全可以暴力枚举。

代码

import math
k = int(input())
kk = k + 1
pl = math.ceil(math.sqrt(kk))
for i in range(1, pl + 1):
    if(kk % i != 0):
        continue
    p = i + kk // i - 2
    q = (i - 1) * (kk // i - 1)
    if p and q:
        print(p, q)
        exit(0);
print(-1)

E. 小红的ds题

题意分析

非常的直观，非常得明了。

题解

我们设 $1$ 为根，为每层的每个节点分配编号，由于二叉树的定义是儿子数不超过 $2$ ，所以可以对于每一个第 $i$ 层的点，从 $i + 1$ 层找两个没有被分配过父亲的点并领养。第 $n$ 层全是叶子，不用处理，其他层没有儿子的节点就放任它当叶子即可。

然后就是愉快的模拟时间。

代码

void solve(){
    int n; cin >> n;
    vector<int> a(n + 5);
    vector<vector<int>> fl(n + 5);
    int cnt = 0;
    int k = 0;
    for(int i = 1; i <= n; ++i){
        cin >> a[i];
        k += a[i];
        for(int j = 0; j < a[i]; ++j) fl[i].push_back(++cnt); // 逐层分配该层的点的编号
    }
    vector<vector<int>> G(k + 5); // 建图，如果用pair的话就初始化为{-1, -1}然后填入即可。
    for(int i = 1; i <= n - 1; ++i){
        int mx = a[i + 1], now = 0;
        for(int j = 0; j < fl[i].size(); ++j){
            if(now < mx and G[fl[i][j]].size() < 2) G[fl[i][j]].push_back(fl[i + 1][now]), ++now;
            if(now < mx and G[fl[i][j]].size() < 2) G[fl[i][j]].push_back(fl[i + 1][now]), ++now; // 两个都是对未触及边界且该点未满情况的处理，复制粘贴即可，反而更快。不用设置退出条件，当然设了更好。
        }
    }
    cout << 1 << endl; // 我们钦定1是根
    for(int i = 1; i <= k; ++i){
        if(G[i].size() == 2) cout << G[i][0] << " " << G[i][1] << endl;
        else if(G[i].size() == 1) cout << G[i][0] << " -1" << endl;
        else cout << "-1 -1" << endl; // 分情况输出，因为我感觉写循环有点麻烦:(
    }
    return;
}

F. 小红的小苯题

~~无语，和你说不下去，典型的小红/小苯思维~~

题意分析

好像没什么可分析的，字面意思

题解

我们令行异或和数列为 $F_x = [1, n] \cap \Bbb Z^+$ ，列异或和数列为 $F_y = [n + 1, m] \cap \Bbb Z^+$ ，则满足 $F_x + F_y = [1, n + m] \cap \Bbb Z^+$ 。

令 $f(a)$ 表示数列 $a$ 的异或和，结果矩阵为 $R$ ，则有：

$f(F_x) \oplus f(F_y) = \bigoplus_{i = 1}^n\bigoplus_{j = 1}^m R_{ij}\;\oplus \bigoplus_{j = 1}^m \bigoplus_{i = 1}^n R_{ij}$

由此可见，每个 $R_{ij}$ 均被异或了恰好两次，所以上式等于 $0$ ，所以 $f(F_x) \oplus f(F_y) = 0$ ，而该式是 $f([1, n + m] \cap \Bbb Z^+)$ ，所以根据异或和的结论，从 $1$ 开始的长度为 $k$ 的排列异或和为 $0$ 的充要条件是 $k \mod 4 = 3$ ，即

$n + m \mod 4 = 3$

若不满足，则无解。

我们首先对于 $R_{im} = F_{x(i)}(i \in [1, n - 1] \cap \Bbb Z^+)$ ， $R_{ni} = F_{y(i)}(i \in [1, m - 1] \cap \Bbb Z^+)$ ，那么余下一个 $R_{nm}$ ，我们希望有：

$\bigoplus_{i = 1}^{n - 1} F_{x(i)} \oplus R_{nm} = F_{y(m)}, \bigoplus_{i = 1}^{m - 1} F_{y(i)} \oplus R_{nm} = F_{x(n)}$

则有：

$R_{nm} = \bigoplus_{i = 1}^{n - 1} F_{x(i)} \oplus F_{y(m)}$

矩阵 $R$ 即为所求。

代码

#define neg {cout << -1 << endl; return;}
void solve(){
    int n, m;
    cin >> n >> m;
    if((n + m) % 4 != 3) neg
    vector<vector<int>> R(n + 1, vector<int>(m + 1, 0));
    for(int i = 1; i < n; ++i) R[i][m] = i;
    for(int i = 1; i < m; ++i) R[n][i] = n + i;
    int xs = 0;
    for(int i = 1; i < n; ++i) xs ^= i;
    R[n][m] = xs ^ (n + m);
    for(int i = 1; i <= n; ++i){
        for(int j = 1; j <= m; ++j) cout << R[i][j] << " ";
        cout << endl;
    }
    return;
}