牛客周赛57

A 小红喜欢 1

小红拿到了一个长度为 $5$ 的、仅由 $0$ 和 $1$ 组成的数组 ${a_{1}, a_{2}, a_{3}, a_{4}, a_{5}}$ ，其中恰好有一个 $1$ ，其余元素都是 $0$ 。请你直接输出 $1$ 所在的位置。

void solve() {
    for (int i = 1;i <= 5;i++) {
	    int x;cin>>x;if (a[i])cout << i << '\n';
    }
}

B 小红的树切割

小红定义一棵树是“好树”，当且仅当任意相邻的两个节点的颜色不同（特殊的，一个节点组成的树一定是好树）。

现在小红拿到了一棵树，一些节点被染成红色，其余节点为白色。小红希望切割若干条边形成森林，使得森林的每棵树都是“好树”。小红想知道，最少需要切割多少条边？

void solve() {
    int n;cin >> n;
    string s;cin >> s;s = ' ' + s;
    vector<vector<int>> g(n + 1);
    for (int i = 1;i < n;i++) {
        int u, v;cin >> u >> v;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    int ans = 0;
    for (int i = 1;i <= n;i++) {
        char clr = s[i];
        for (auto v : g[i]) {
            if (s[v] == clr)ans++;
        }
    }
    cout << ans / 2 << '\n';
}

C 小红的双好数（easy）

小红定义 $n$ 是 $k$ - 好数，当且仅当 $n$ 在 $k$ 进制表示下，每一位都不大于 $1$ 。

现在输入了一个正整数 $n$ ，小红希望你找到两个不同的正整数 $k_{1}$ 和 $k_{2} (2 \leq k_{1} < k_{2} \leq 10^{18})$ ，满足 $n$ 既是 $k_{1}$ -好数，也是 $k_{2}$ -好数，你能帮帮她吗？

易得：除了 1，2 之外所有数在二进制下都满足要求，以及所有数在 $n$ 进制下都是 10 也满足要求

#define int long long
void solve() {
    int n;cin >> n;
    if (n == 2) {
        cout << "NO\n";return;
    }
    cout << "YES\n";
    if (n == 1) n += 2;
    cout << 2 << " " << n << '\n';
}

D 小红的线段

在平面直角坐标系中有 $2 \times n$ 个点和一条直线 $y = k x + b$ 。

小红准备在这 $2 \times n$ 个点中连 $n$ 条线段（每个点只能连接一次），她希望 和直线有交点的线段 的数量尽可能多。

请你给出一个连接方案。

理解偏差，题目意思是两个点都在直线上也算是有交点

#define int long long
void solve() {
    int n, k, b;cin >> n >> k >> b;
    vector<int> x(2 * n + 1), y(2 * n + 1);
    for (int i = 1;i <= 2 * n;i++)cin >> x[i] >> y[i];
    vector<int> L, R, E;
    for (int i = 1;i <= 2 * n;i++) {
        if (y[i] < k * x[i] + b)L.push_back(i);
        else if (y[i] > k * x[i] + b)R.push_back(i);
        else E.push_back(i);
    }
    while (E.size()) {
        if (L.size() < R.size()) {
            L.push_back(E.back());
        } else {
            R.push_back(E.back());
        }
        E.pop_back();
    }
    int t = min(L.size(), R.size());
    cout << t << '\n';
    for (int i = 0; i < t; i++) {
        cout << L[i] << ' ' << R[i] << " Y\n";
    }
    for (int i = t; i < L.size(); i += 2) {
        cout << L[i] << ' ' << L[i + 1] << " N\n";
    }
    for (int i = t; i < R.size(); i += 2) {
        cout << R[i] << ' ' << R[i + 1] << " N\n";
    }
}

E 小红的双好数（hard）

给定 $k_{1}, k_{2}$ ，求 $n$ 使得 $n$ 在 $k_{1}, k_{2}$ 进制下每一位都不大于 1。 $k_{1}, k_{2}, n \in [2, 10^{18}]$

Solution

构造

#define int long long
void solve() {
    int k1, k2;cin >> k1 >> k2;

    auto check = [&](int n) {
        while (n) {
            if (n % k1 > 1)return 0;
            n /= k1;
        }
        return 1;
        };
    queue<int> q;
    q.push(k2);q.push(k2 + 1);
    while (q.size()) {
        auto cur = q.front();q.pop();
        if (check(cur)) {
            cout << "YES\n";
            cout << cur << '\n';return;
        }
        if (cur <= 1e18 / k2)q.push(cur * k2);
        if (cur <= (1e18 - 1) / k2)q.push(cur * k2 + 1);
    }
    cout << "NO\n";
}

F 小红的数组操作

小红拿到了 $n$ 个数组，她有以下两种操作：

输入 $1 i j x$ 将第 $i$ 个数组的第 $j$ 个元素修改为 $x$ ；
输入 $2 i$ 查询前 $i$ 个数组的最小值。

Solution

线段树 +前缀和

将 $n$ 个数组接在一起即变为了单点修改，区间查最小值

设置一个 $p r e_{i}$ 数组来作为数组大小的前缀和。方便后续的点修和区查

按照我的码风，更方便

#define lc (u << 1)
#define rc (u << 1 | 1)
int a[100005];
struct TREE {
    ll l, r, min;
}tr[100005 << 2];
void pushup(int u) {
    tr[u].min = min(tr[lc].min, tr[rc].min);
}
void build(int u, int l, int r) {
    tr[u] = {l,r,a[l]};
    if (l == r) return;
    int mid = l + r >> 1;
    build(lc, l, mid);
    build(rc, mid + 1, r);
    pushup(u);
}

void update(int u, int l, int r, int x) {
    if (tr[u].l == tr[u].r) {
        tr[u].min = x;
        return;
    }
    int mid = tr[u].l + tr[u].r >> 1;
    if (mid >= l)
        update(lc, l, r, x);
    if (mid < r)
        update(rc, l, r, x);
    pushup(u);
}

ll query(int u, int l, int r) {
    if (l <= tr[u].l && tr[u].r <= r) {
        return tr[u].min;
    }
    ll ans = 2e9;
    int mid = tr[u].l + tr[u].r >> 1;
    if (mid >= l)
        ans = min(ans, query(lc, l, r));
    if (mid < r)
        ans = min(ans, query(rc, l, r));
    return ans;
}

void solve() {
    int t;
    cin >> t;
    int n = 0;
    vector<int> pre(t + 1);
    for (int i = 1; i <= t; i++) {
        int x;cin >> x;
        n += x;
        pre[i] = pre[i - 1] + x;
        for (int j = pre[i - 1] + 1; j <= pre[i]; j++) {
            cin >> a[j];
        }
    }
    build(1, 1, n);

    int m;cin >> m;
    while (m--) {
        int op, i;
        cin >> op >> i;
        if (op == 1) {
            int j, x;cin >> j >> x;
            int pos = pre[i - 1] + j;
            update(1, pos, pos, x);
        } else {
            cout << query(1, 1, pre[i]) << '\n';
        }
    }
}

G 小红的双排列构造

构造一个长度为 $2 \times n$ 的双排列，满足：恰好有 $k$ 个长度为 $n$ 的区间为排列。

定义双排列为两个长度为 $n$ 的排列打乱顺序后得到的数组，或者说是由 $1$ 到 $n$ 中的 $n$ 个不同整数、按任意顺序组成的数组，其中每个整数恰好出现两次。

Solution

构造

构造思路：

易得：当 $k = n + 1$ 时，构造序列为 $1 \dots n, 1 \dots n$

当 $k = n$ 时，构造序列为 $2, 1, 3, \dots n, 1 \dots n$ ，将前两个数字翻转

所以，将前 $n + 1 - k + 1$ 个数字翻转即可( $k \geq 2$ )

当 $k = 0, 1$ 时，这样的方式不行，则

当 $k = 0$ 时，构造 $1, 1, 2, 2, \dots n, n$ ( $n = 1 / 2$ 时不行需要特判)
当 $k = 1$ 时，构造 $1, 1, 2, \dots n, 2, 3, \dots n$ ( $n = 1$ 时不行需要特判)

对于 1，2 的情况需要特判

void solve() {
    int n, k;cin >> n >> k;
    if (n == 1) {
        if (k != 2) {
            cout << "-1\n";
        } else {
            cout << "1 1\n";
        }
        return;
    } else if (n == 2) {
        if (k == 0) {
            cout << "-1\n";
        } else if (k == 1) {
            cout << "1 1 2 2\n";
        } else if (k == 2) {
            cout << "2 1 1 2\n";
        } else {
            cout << "1 2 1 2\n";
        }
        return;
    }
    vector<int> ans(2 * n + 1);
    if (k < 2) {
        if (!k) {
            for (int i = 1;i <= n;i++)cout << i << " " << i << " \n"[i == n];
        } else {
            cout << "1 ";
            for (int i = 1;i <= n;i++) cout << i << " ";
            for (int i = 2;i <= n;i++) cout << i << " \n"[i == n];
        }
        return;
    }
    for (int i = 1;i <= 2 * n;i++) {
        if (i <= n)ans[i] = i;
        else ans[i] = i - n;
    }
    int c = n + 1 - k;
    reverse(ans.begin() + 1, ans.begin() + 2 + c);
    for (int i = 1;i <= 2 * n;i++)cout << ans[i] << " \n"[i == 2 * n];
}