牛客周赛126题解

A

分类讨论即可

#include <bits/stdc++.h>

#define x first
#define y second
#define all(x) x.begin(), x.end()

using namespace std;
using i128 = __int128;
using u128 = unsigned __int128;

typedef long long LL;
typedef long double LD;
typedef unsigned long long ULL;
typedef pair<int, int> PII;
typedef pair<LL, LL> PLL;

const int N = 1e5 + 10, MOD = 998244353;
const int INF = 1e9;
const LL LL_INF = 1e18;
const LD EPS = 1e-8;

istream &operator>>(istream &is, i128 &val) {
    string str;
    is >> str;
    val = 0;
    bool flag = false;
    if (str[0] == '-') flag = true, str = str.substr(1);
    for (char &c: str) val = val * 10 + c - '0';
    if (flag) val = -val;
    return is;
}

ostream &operator<<(ostream &os, i128 val) {
    if (val < 0) os << "-", val = -val;
    if (val > 9) os << val / 10;
    os << static_cast<char>(val % 10 + '0');
    return os;
}

void solve() {
    int x;
    cin >> x;
    if (x > 5) {
        for (int i = 6; i <= 10; ++i) cout << i << '\n';
    }
    else {
        for (int i = 1; i <= 5; ++i) cout << i << ' ';
    }
    cout << '\n';
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);

    int T = 1;
    while (T--) solve();
    cout << fixed << setprecision(15);

    return 0;
}

B

注意到给定字符串是有前缀关系的, 直接对字符串按照字典序排序

无解情况就是第 $k$ 小的字符串有多个

#include <bits/stdc++.h>

#define x first
#define y second
#define all(x) x.begin(), x.end()

using namespace std;
using i128 = __int128;
using u128 = unsigned __int128;

typedef long long LL;
typedef long double LD;
typedef unsigned long long ULL;
typedef pair<int, int> PII;
typedef pair<LL, LL> PLL;
typedef pair<LD, LD> PLD;

const int N = 2e5 + 10, MOD = 998244353;
const int INF = 1e9;
const LL LL_INF = 1e18;
const LD EPS = 1e-8;
const int dx4[] = {-1, 0, 1, 0}, dy4[] = {0, 1, 0, -1};
const int dx8[] = {-1, -1, -1, 0, 0, 1, 1, 1}, dy8[] = {-1, 0, 1, -1, 1, -1, 0, 1};

istream &operator>>(istream &is, i128 &val) {
    string str;
    is >> str;
    val = 0;
    bool flag = false;
    if (str[0] == '-') flag = true, str = str.substr(1);
    for (char &c: str) val = val * 10 + c - '0';
    if (flag) val = -val;
    return is;
}

ostream &operator<<(ostream &os, i128 val) {
    if (val < 0) os << "-", val = -val;
    if (val > 9) os << val / 10;
    os << static_cast<char>(val % 10 + '0');
    return os;
}

bool cmp(LD a, LD b) {
    if (fabs(a - b) < EPS) return 1;
    return 0;
}

void solve() {
    int n, k;
    cin >> n >> k;
    vector<string> a(n);
    for (int i = 0; i < n; ++i) cin >> a[i];

    sort(all(a));

    if (k < n && a[k - 1] == a[k]) {
        cout << -1 << '\n';
        return;
    }

    cout << a[k - 1] + '!' << '\n';
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);

    int T = 1;
    while (T--) solve();
    cout << fixed << setprecision(15);

    return 0;
}

C

注意到只需要将 $k$ 个数字设置为奇数个即可, 剩余以两对两对出现

#include <bits/stdc++.h>

#define x first
#define y second
#define all(x) x.begin(), x.end()

using namespace std;
using i128 = __int128;
using u128 = unsigned __int128;

typedef long long LL;
typedef long double LD;
typedef unsigned long long ULL;
typedef pair<int, int> PII;
typedef pair<LL, LL> PLL;
typedef pair<LD, LD> PLD;

const int N = 1e5 + 10, MOD = 998244353;
const int INF = 1e9;
const LL LL_INF = 1e18;
const LD EPS = 1e-8;
const int dx4[] = {-1, 0, 1, 0}, dy4[] = {0, 1, 0, -1};
const int dx8[] = {-1, -1, -1, 0, 0, 1, 1, 1}, dy8[] = {-1, 0, 1, -1, 1, -1, 0, 1};

istream &operator>>(istream &is, i128 &val) {
    string str;
    is >> str;
    val = 0;
    bool flag = false;
    if (str[0] == '-') flag = true, str = str.substr(1);
    for (char &c: str) val = val * 10 + c - '0';
    if (flag) val = -val;
    return is;
}

ostream &operator<<(ostream &os, i128 val) {
    if (val < 0) os << "-", val = -val;
    if (val > 9) os << val / 10;
    os << static_cast<char>(val % 10 + '0');
    return os;
}

bool cmp(LD a, LD b) {
    if (fabs(a - b) < EPS) return 1;
    return 0;
}

void solve() {
    int n, k;
    cin >> n >> k;

    int v = n - k;
    if (v % 2) {
        cout << -1 << '\n';
        return;
    }

    vector<int> ans;
    v /= 2;
    int t = 1;
    for (int i = 0; i < v; ++i) {
        ans.push_back(t);
        ans.push_back(t);
        t++;
    }

    for (int i = 0; i < k; ++i) ans.push_back(++t);

    for (int c : ans) cout << c << ' ';
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);

    int T = 1;
    while (T--) solve();
    cout << fixed << setprecision(15);

    return 0;
}

D

首先考虑无解情况, 当结尾两个位置(最大值)不相等一定无解

如果 $n < x + y - 1$ 也无法构造出, 因为给定的一定不包含重复字符, 题目要求的是严格大于或者小于

然后有解的情况拼接即可

#include <bits/stdc++.h>

#define x first
#define y second
#define all(x) x.begin(), x.end()

using namespace std;
using i128 = __int128;
using u128 = unsigned __int128;

typedef long long LL;
typedef long double LD;
typedef unsigned long long ULL;
typedef pair<int, int> PII;
typedef pair<LL, LL> PLL;
typedef pair<LD, LD> PLD;

const int N = 1e5 + 10, MOD = 998244353;
const int INF = 1e9;
const LL LL_INF = 1e18;
const LD EPS = 1e-8;
const int dx4[] = {-1, 0, 1, 0}, dy4[] = {0, 1, 0, -1};
const int dx8[] = {-1, -1, -1, 0, 0, 1, 1, 1}, dy8[] = {-1, 0, 1, -1, 1, -1, 0, 1};

istream &operator>>(istream &is, i128 &val) {
    string str;
    is >> str;
    val = 0;
    bool flag = false;
    if (str[0] == '-') flag = true, str = str.substr(1);
    for (char &c: str) val = val * 10 + c - '0';
    if (flag) val = -val;
    return is;
}

ostream &operator<<(ostream &os, i128 val) {
    if (val < 0) os << "-", val = -val;
    if (val > 9) os << val / 10;
    os << static_cast<char>(val % 10 + '0');
    return os;
}

bool cmp(LD a, LD b) {
    if (fabs(a - b) < EPS) return 1;
    return 0;
}

void solve() {
    int x, y, n;
    cin >> x >> y >> n;
    vector<int> a(x), b(y);
    for (int i = 0; i < x; ++i) cin >> a[i];
    for (int i = 0; i < y; ++i) cin >> b[i];

    if (a[x - 1] != b[y - 1] || n < x + y - 1) {
        cout << -1 << '\n';
        return;
    }

    vector<int> ans;
    for (int i = 0; i < x; ++i) ans.push_back(a[i]);
    if (n == x + y - 1) {
        for (int i = y - 2; i >= 0; --i) ans.push_back(b[i]);
    }
    else for (int i = y - 1; i >= 0; --i) ans.push_back(b[i]);

    int d = n - (x + y);
    for (int i = 0; i < d; ++i) ans.push_back(b[0]);
    for (int c : ans) cout << c << ' ';
    cout << '\n';
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);

    int T = 1;
    while (T--) solve();
    cout << fixed << setprecision(15);

    return 0;
}

E

注意到数据范围不会超过 $10 ^ 18$ , 也就是位数不会超过 $18$

可以枚举从当前位置向后接几位, 假设是 $k$ 那么数的范围是 $[n \times 10 ^ k, (n + 1) \times 10 ^ k - 1]$

检查完全平方数是否存在假设存在 $x \le r$ , 直接输出

#include <bits/stdc++.h>

#define x first
#define y second
#define all(x) x.begin(), x.end()

using namespace std;
using i128 = __int128;
using u128 = unsigned __int128;

typedef long long LL;
typedef long double LD;
typedef unsigned long long ULL;
typedef pair<int, int> PII;
typedef pair<LL, LL> PLL;

const int N = 1e5 + 10, MOD = 998244353;
const int INF = 1e9;
const LL LL_INF = 1e18;
const LD EPS = 1e-8;
const int dx4[] = {-1, 0, 1, 0}, dy4[] = {0, 1, 0, -1};
const int dx8[] = {-1, -1, -1, 0, 0, 1, 1, 1}, dy8[] = {-1, 0, 1, -1, 1, -1, 0, 1};

istream &operator>>(istream &is, i128 &val) {
    string str;
    is >> str;
    val = 0;
    bool flag = false;
    if (str[0] == '-') flag = true, str = str.substr(1);
    for (char &c: str) val = val * 10 + c - '0';
    if (flag) val = -val;
    return is;
}

ostream &operator<<(ostream &os, i128 val) {
    if (val < 0) os << "-", val = -val;
    if (val > 9) os << val / 10;
    os << static_cast<char>(val % 10 + '0');
    return os;
}

bool cmp(LD a, LD b) {
    if (fabs(a - b) < EPS) return 1;
    return 0;
}

void solve() {
    int n;
    cin >> n;

    for (int k = 1; k < 18; ++k) {
        LL l = n * powl(10, k), r = n * powl(10, k) + powl(10, k) - 1;
        LL v = sqrt(l);
        i128 ans = (i128) v * v;
        if (ans < l) {
            v++;
            ans = (i128) v * v;
        }
        if (ans <= r) {
            cout << ans << '\n';
            return;
        }
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);

    int T;
    cin >> T;
    while (T--) solve();
    cout << fixed << setprecision(15);

    return 0;
}

F

基环树就是树加了一条边

对于树来说可以用二分图进行染色

那么在冲突的位置换一个颜色即可

#include <bits/stdc++.h>

#define x first
#define y second
#define all(x) x.begin(), x.end()

using namespace std;
using i128 = __int128;
using u128 = unsigned __int128;

typedef long long LL;
typedef long double LD;
typedef unsigned long long ULL;
typedef pair<int, int> PII;
typedef pair<LL, LL> PLL;
typedef pair<LD, LD> PLD;

const int N = 1e5 + 10, MOD = 998244353;
const int INF = 1e9;
const LL LL_INF = 1e18;
const LD EPS = 1e-8;
const int dx4[] = {-1, 0, 1, 0}, dy4[] = {0, 1, 0, -1};
const int dx8[] = {-1, -1, -1, 0, 0, 1, 1, 1}, dy8[] = {-1, 0, 1, -1, 1, -1, 0, 1};

istream &operator>>(istream &is, i128 &val) {
    string str;
    is >> str;
    val = 0;
    bool flag = false;
    if (str[0] == '-') flag = true, str = str.substr(1);
    for (char &c: str) val = val * 10 + c - '0';
    if (flag) val = -val;
    return is;
}

ostream &operator<<(ostream &os, i128 val) {
    if (val < 0) os << "-", val = -val;
    if (val > 9) os << val / 10;
    os << static_cast<char>(val % 10 + '0');
    return os;
}

bool cmp(LD a, LD b) {
    if (fabs(a - b) < EPS) return 1;
    return 0;
}

void solve() {
    int n;
    cin >> n;
    vector<vector<int>> g(n + 1);
    vector<PII> e(n);
    for (int i = 0; i < n; ++i) {
        int a, b;
        cin >> a >> b;
        g[a].push_back(b);
        g[b].push_back(a);
        e.push_back({a, b});
    }

    vector<int> col(n + 1);
    function<void(int, int)> dfs = [&](int u, int c) {
        col[u] = c;

        for (int v : g[u]) {
            if (!col[v]) dfs(v, 3 - c);
        }
    };

    dfs(1, 1);
    for (auto &[x, y] : e) {
        if (col[x] == col[y]) col[y] = 3; 
    }

    for (int i = 1; i <= n; ++i) cout << col[i] << ' ';
    
    cout << '\n';
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);

    int T = 1;
    while (T--) solve();
    cout << fixed << setprecision(15);

    return 0;
}

G

注意到这里的字符串不再有前缀关系

那么为了计算前缀信息, 需要使用前缀树, 也就字典树

在每个字符串结尾位置打上标记

标记数量达到 $k$ 说明找到了字符串

难点在 $dfs$ , 需要开一个 $ok$ 变量记录是否已经找打了答案, 如果找到了答案直接返回即可

#include <bits/stdc++.h>

#define x first
#define y second
#define all(x) x.begin(), x.end()

using namespace std;
using i128 = __int128;
using u128 = unsigned __int128;

typedef long long LL;
typedef long double LD;
typedef unsigned long long ULL;
typedef pair<int, int> PII;
typedef pair<LL, LL> PLL;
typedef pair<LD, LD> PLD;

const int N = 4e5 + 10, MOD = 998244353;
const int INF = 1e9;
const LL LL_INF = 1e18;
const LD EPS = 1e-8;
const int dx4[] = {-1, 0, 1, 0}, dy4[] = {0, 1, 0, -1};
const int dx8[] = {-1, -1, -1, 0, 0, 1, 1, 1}, dy8[] = {-1, 0, 1, -1, 1, -1, 0, 1};

istream &operator>>(istream &is, i128 &val) {
    string str;
    is >> str;
    val = 0;
    bool flag = false;
    if (str[0] == '-') flag = true, str = str.substr(1);
    for (char &c: str) val = val * 10 + c - '0';
    if (flag) val = -val;
    return is;
}

ostream &operator<<(ostream &os, i128 val) {
    if (val < 0) os << "-", val = -val;
    if (val > 9) os << val / 10;
    os << static_cast<char>(val % 10 + '0');
    return os;
}

bool cmp(LD a, LD b) {
    if (fabs(a - b) < EPS) return 1;
    return 0;
}

void solve() {
    int n, k;
    cin >> n >> k;

    vector<string> a(n);
    int sz = 0;
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
        sz += a[i].size();
    }

    vector<vector<int>> tr(sz + 1, vector<int>(2));
    vector<int> cnt(sz + 1);
    int idx = 0;

    auto insert = [&](string &s) {
        int p = 0;
        for (char c : s) {
            int v = c - '0';
            if (!tr[p][v]) tr[p][v] = ++idx;
            p = tr[p][v];
        }
        cnt[p]++;
    };

    for (int i = 0; i < n; ++i) insert(a[i]);

    string ans;
    bool ok = 0;
    function<void(int, int, string)> dfs = [&](int u, int sum, string cur) {
        if (ok) return;
        if (sum == k) {
            ok = 1;
            cout << cur << '\n';
            return;
        }

        for (int i = 0; i <= 1; ++i) {
            if (tr[u][i]) {
                cur += i + '0';
                dfs(tr[u][i], sum + cnt[tr[u][i]], cur);
                cur.pop_back();
                if (ok) return;
            }
        }
    };

    dfs(0, 0, "");

    if (!ok) cout << -1 << '\n';
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);

    int T = 1;
    while (T--) solve();
    cout << fixed << setprecision(15);

    return 0;
}