前言

fw又来了，如果有问题欢迎大家评论或私信指出

题解

A.小红喜欢1

输出1的位置即可

#include<bits/stdc++.h>

using i64 = long long;
using u64 = unsigned long long;

void solve() {
    for (int i = 1; i <= 5; i++) {
        int a;
        std::cin >> a;
        if (a == 1) {
            std::cout << i;
        }
    }
} 

signed main() {
    std::ios::sync_with_stdio(0);
    std::cout.tie(0);
    std::cin.tie(0);

    i64 t = 1; 
    // std::cin >> t;
    while (t--) {
        solve();
    }
}

B.小红的树切割

从任意一点开始dfs，如果相邻两个节点颜色一致++

#include<bits/stdc++.h>

using i64 = long long;
using u64 = unsigned long long;

void solve() {
    int n;
    std::cin >> n;
    std::string s;
    std::cin >> s;
    s = ' ' + s;

    std::vector<std::vector<int> > e(n + 1);
    for (int i = 1; i < n; i++) {
        int u, v;
        std::cin >> u >> v;
        e[u].push_back(v);
        e[v].push_back(u);
    }

    int ans = 0;

    auto dfs = [&] (auto self, int u, int f) -> void {
        for (auto v : e[u]) {
            if (v == f) continue;
            if (s[u] == s[v]) {
                ans++;
            }
            self(self, v, u);
        }
    };

    dfs(dfs, 1, 0);

    std::cout << ans;
} 

signed main() {
    std::ios::sync_with_stdio(0);
    std::cout.tie(0);
    std::cin.tie(0);

    i64 t = 1; 
    // std::cin >> t;
    while (t--) {
        solve();
    }
}

C.小红的双好数（easy）

一个数在二进制和本身进制下的数一定是符合条件的，特判一下和即可

#include<bits/stdc++.h>

using i64 = long long;
using u64 = unsigned long long;

void solve() {
    i64 n;
    std::cin >> n;
    if (n == 1) {
        std::cout << "YES" <<'\n';
        std::cout << 2 << ' ' << 3 <<'\n';
        return;
    }
    if (n == 2) {
        std::cout << "NO" << '\n';
        return;
    }
    std::cout << "YES" << '\n';
    std::cout << 2 << ' ' << n << '\n';
} 

signed main() {
    std::ios::sync_with_stdio(0);
    std::cout.tie(0);
    std::cin.tie(0);

    i64 t = 1; 
    // std::cin >> t;
    while (t--) {
        solve();
    }
}

D.小红的线段

我们把直线看成++的形式，把给定的点带入，如果算出来的值会出现大于0，小于0和等于0，如果等于0说明点在直线上，大于和小于说明在直线的两侧，那我们把三种情况的点分别存起来，首先让大于0和小于0的点去连，其次用等于0的点去连接剩下的，最后剩下的点互相连，这样就会做到与给定直线交点最多。

#include<bits/stdc++.h>

using i64 = long long;
using u64 = unsigned long long;

void solve() {
    i64 n, k, b;
    std::cin >> n >> k >> b;

    std::vector<int> v1, v2, v3;
    for (int i = 1; i <= n * 2; i++) {
        i64 x, y;
        std::cin >> x >> y;
        i64 tmp = k * x + b - y;
        if (tmp < 0) {
            v1.push_back(i);
        }
        else if (tmp == 0) {
            v2.push_back(i);
        }
        else {
            v3.push_back(i);
        }
    }

    if (v1.size() > v3.size()) {
        std::swap(v1, v3);
    }

    int ans = 0;
    std::queue<std::pair<int, int> > q;
    for (int i = 0; i < (int)v1.size(); i++) {
        q.push({v1[i], v3[i]});
        ans++;
    }

    int tmp = 0, i = 0;
    for (i = (int)v1.size(); i < (int)v3.size() && tmp < (int)v2.size(); i++, tmp++) {
        q.push({v3[i], v2[tmp]});
        ans++;
    }

    std::vector<int> v;
    if (tmp != (int)v2.size()) {
        ans += (v2.size() - tmp) / 2;
        for (; tmp < (int)v2.size(); tmp += 2) {
            q.push({v2[tmp], v2[tmp + 1]});
            
        }
    }
    else {
        for (; i < (int)v3.size(); i+=2) {
            q.push({v3[i], v3[i + 1]});
        }
    }
    
    std::cout << ans << '\n';
    while(!q.empty()) {
        if (ans) {
            std::cout << q.front().first << ' ' << q.front().second << ' ' << 'Y' << '\n';
            ans--;
        }
        else {
            std::cout << q.front().first << ' ' << q.front().second << ' ' << 'N' << '\n';
        }
        q.pop();
    }
    
} 

signed main() {
    std::ios::sync_with_stdio(0);
    std::cout.tie(0);
    std::cin.tie(0);

    i64 t = 1; 
    // std::cin >> t;
    while (t--) {
        solve();
    }
}

E小红的双好数（hard）

这个我们可以简单手搓一下，可以算出来一个1e18在7进制下也仅有20位，由于每一位只能是0或1，所以所有符合条件的数只有个，题里给定了k1<k2，如果k2 >= 7就去遍历所有在k2进制下符合条件的数再去check是否在k1条件下符合，如果k2 < 7可以本地打表得知答案很小（具体证明看讲题视频或者别的题解吧，我也不知道）这样就可以搜出来所有答案了

#include<bits/stdc++.h>

using i64 = long long;
using u64 = unsigned long long;

void solve() {
    i64 k1, k2;
    std::cin >> k1 >> k2;

    auto check = [&] (i64 k, i64 n) -> bool {
        if (k < 2) return false;
        while (n) {
            if (n % k > 1) return false;
            n /= k;
        }
        
        return true;
    };

    std::vector<std::vector<int> > a(10, std::vector<int>(10, 2));
    for (int i = 2; i < 7; i++) {
        for (int j = i + 1; j < 7; j++) {
            while (!(check(i, a[i][j]) && check(j, a[i][j]))) {
                a[i][j]++;
            }
        }
    }

    if (k2 < 7) {
        std::cout << "YES" << '\n';
        std::cout << a[k1][k2] << '\n';
        return;
    }

    auto cal = [&] (i64 a, i64 b) -> __int128 {
        __int128 res = 0, power = 1;
        while (a) {
            if (a & 1) res += power;
            a >>= 1;
            power = power * b;
        }
        
        return res;
    };

    int cnt = 2;
    while (true) {
        __int128 num = cal(cnt, k2);
        if (num > 1e18) {
            std::cout << "NO" << '\n';
            return;
        }
        if (check(k1, num) && check(k2, num)) {
            std::cout << "YES" << '\n';
            std::cout << (i64)num << '\n';
            return;
        }
        cnt++;
    }
    
} 

signed main() {
    std::ios::sync_with_stdio(0);
    std::cout.tie(0);
    std::cin.tie(0);

    i64 t = 1; 
    // std::cin >> t;
    while (t--) {
        solve();
    }
}

F.小红的数组操作

线段树维护区间最小值，单点修改，区间查询的板子

#include <bits/stdc++.h>

using i64 = long long;
using u64 = unsigned long long;

#define lson (rt << 1)
#define rson (rt << 1 | 1)
int lowbit(int x) {
    return x & (-x);
}
int a[100005];
struct node {
    i64 sum, lz;
}tr[100005 << 2];

void build(int rt, int l, int r) {
    if (l == r) {
        tr[rt].sum = a[l];
        return;
    }
    int mid = l + r >> 1;
    build(lson, l, mid);
    build(rson, mid + 1, r);
    tr[rt].sum = std::min(tr[lson].sum, tr[rson].sum);
}

void update(int rt, int l, int r, int L, int R, int x) {
    if (l >= L && r <= R) {
        tr[rt].sum = x;
        return;
    }
    int mid = l + r >> 1;
    if (mid >= L)
        update(lson, l, mid, L, R, x);
    if (mid < R) {
        update(rson, mid + 1, r, L, R, x);
    }
    tr[rt].sum = std::min(tr[lson].sum, tr[rson].sum);
}

i64 query(int rt, int l, int r, int L, int R) {
    if (l >= L && r <= R) {
        return tr[rt].sum;
    }
    i64 ans = 1e9 + 1;
    int mid = l + r >> 1;
    if (mid >= L)
        ans = std::min(ans,query(lson, l, mid, L, R));
    if (mid < R)
        ans = std::min(ans, query(rson, mid + 1, r, L, R));
    return ans;
}

void solve() {
    int t;
    std::cin >> t;
    int n = 0;
    std::vector<int> pre(t + 1);
    for (int i = 1; i <= t; i++) {
        int x;
        std::cin >> x;
        n += x;
        pre[i] = pre[i - 1] + x;
        for (int j = pre[i - 1] + 1; j <= pre[i]; j++) {
            std::cin >> a[j];
        }
    }
    // std::cout << n << '\n';
    build(1, 1, n);
 
    int m;
    std::cin >> m;
    while (m--) {
        int op;
        std::cin >> op;
        if (op == 1) {
            int i, j, x;
            std::cin >> i >> j >> x;
            int pos = pre[i - 1] + j;
            update(1, 1, n, pos, pos, x);
        }
        else {
            int x;
            std::cin >> x;
            std::cout << query(1, 1, n, 1, pre[x]) << '\n';
        }
    }
}

signed main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);

    int t = 1;
    // std::cin >> t;
    while (t--) {
        solve();
    }

    return 0;
}

G.小红的双排列构造

构造方法很多吧，这里提供一种我的构造方法，如果k==0，输出 1 1 2 2 3 3 ... n n，如果k==1，输出1 1 2 3 4 ...n 2 3 4...n，否则比如n == 6, k == 4，构造1 2 3 4 5 6 1 2 6 5 4 3，即前n个是一个排列，后n个是一个排列，这样至少会有两个排列，如果再多的话，就在第n+1位再依次输出1 2 3...。没懂的话可以复制一下我的代码，看一下我输出的是什么

#include<bits/stdc++.h>

using i64 = long long;
using u64 = unsigned long long;

void solve() {
    int n, k;
    std::cin >> n >> k;
    if (n == 1) {
        if (k == 0) {
            std::cout << -1 << '\n';
        }
        if (k == 1) {
            std::cout << -1 << '\n';
        }
        if (k == 2) {
            std::cout << "1 1" << '\n';
        }
        return;
    }
    if (k == 0) {
        if (n == 2) {
            std::cout << -1 << '\n';
            return;
        }
        for (int i = 1; i <= n; i++) {
            std::cout << i << ' ' << i << ' ';
        }
    }
    else if (k == 1) {
        std::cout << "1 1 ";
        for (int i = 2; i <= n; i++) {
            std::cout << i << ' ';
        }
        for (int i = 2; i <= n; i++) {
            std::cout << i << ' ';
        }
    }
    else {
        for (int i = 1; i <= n; i++) {
            std::cout << i << ' ';
        }
        for (int i = 1; i <= k - 2; i++) {
            std::cout << i << ' ';
        }
        for (int i = n; i >= k - 1; i--) {
            std::cout << i << ' ';
        }
    }
} 

signed main() {
    std::ios::sync_with_stdio(0);
    std::cout.tie(0);
    std::cin.tie(0);

    i64 t = 1; 
    // std::cin >> t;
    while (t--) {
        solve();
    }
}