牛客 2021 年度训练联盟热身训练赛第二场回顾

比赛链接：https://ac.nowcoder.com/acm/contest/12794

非常的垃圾，这一场几乎全部都是水题== 当然还混入了大量说不清道不明的阅读理解一般又臭又长的题面…… 只能说恶心他🐎给恶心开门，恶心到家了（）

实况：AK（10/10），Rank=39

Penalty	A	B	C	D	E	F	G	H	I	J
1056	+	+	+	+1	+1	+1	+5	+1	+	+

没什么好说的，，直接贴代码好了~~这将成为目前为止本博客最水题解~~

题解

A - Binarize It

签到，队友 A 的：

int t, n, m, k;
int main()
{
// #define COMP_DATA
#ifndef ONLINE_JUDGE
    freopen("in.txt", "r", stdin);
#endif
    int tcase;
    read(tcase);
    while (tcase--)
    {
        read(n);
        printf("Input value: %d\n%d\n\n", n, int(pow(2, int(ceil(log10(n) / log10(2))))));
    }
    return 0;
}

虽然有些意义不明的变量（

B - g2g c u l8r

纯字符串暴力题；让我熟悉了在 C++ 中读入整行的一些操作和注意事项

signed main()
{
    // ios::sync_with_stdio(false);
    // std::cin.tie(nullptr);
    // std::cout.tie(nullptr);
#if 0
    freopen("in.txt", "r", stdin);
#endif
    int T, q; cin >> T;
    unordered_map<string, string> dict;
    string s, t;
    while (T --)
    {
        cin >> s;
        getline(cin, t);
        int cur = 0, size = t.length();
        while (cur < size) if (t[cur] == ' ') ++ cur; else break;
        dict[s] = t.substr(cur);
    }
    cin >> q; getline(cin, s);
    while (q --)
    {
        getline(cin, s);
        stringstream ss(s), out;
        while (ss >> t)
            if (dict.count(t)) out << dict[t] << ' ';
            else out << t << ' ';
        auto str = out.str();    
        cout << str << endl;  
    }
    return 0;
}

回想起了刚入坑时在洛谷训练场写红题的恐惧（

C - Tip to be Palindrome

签到；虽然可以考虑一些手段，但是因为数据范围实在是太小了，所以只需要模拟就行了……

bool check(int n)
{
    s = to_string(n);
    for (int i = 0; i < s.length() / 2; i++)
    {
        int j = s.length() - i - 1;
        if (s[i] != s[j])
            return false;
    }
    return true;
}
int main()
{
// #define COMP_DATA
#ifndef ONLINE_JUDGE
    freopen("in.txt", "r", stdin);
#endif
    ios::sync_with_stdio(false);
    int tcase;
    cin >> tcase;
    for (int i = 5; i <= 20000; i++)
    {
        if (check(i))
            q.push_back(i);
    }
    while (tcase--)
    {
        cin >> n;
        int l = ceil(1.0 * n * 1.2);
        cout << "Input cost: " << n << endl;
        int ans = q[lower_bound(q.begin(), q.end(), l) - q.begin()];
        cout << ans - n << " " << ans << endl
            << endl;
    }
    return 0;
}

上面的代码就是先预处理完了所有的回文，然后根据输入去查找答案。

D - Soccer Standings

运算符重载题，当然前提是你读完了那又臭又长的题面描述：

signed main()
{
    ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::cout.tie(nullptr);
#if 0
    freopen("in.txt", "r", stdin);
#endif
    int n, t, g;
    cin >> n;
    using team = tuple<int, int, int, int, int, int, int>;
    vector<string> ss;
    unordered_map<string, int> val;
    vector<team> cnt;
    const auto init = [&]
    {
        ss.clear(), val.clear();
        cnt.clear();
    };
    const auto cmp = []
    (const team &a, const team &b) -> bool
    {
        auto &[ano, a1, a0, aw, at, al, apt] = a;
        auto &[bno, b1, b0, bw, bt, bl, bpt] = b;
        auto ad = a1 - a0, bd = b1 - b0;
        if (apt != bpt) return apt > bpt;
        else if (ad != bd) return ad > bd;
        else if (a1 != b1) return a1 > b1;
        else return ano < bno;
    };
    string s, a, b; int aa, bb;
    for (int i = 1; i <= n; ++ i)
    {
        init();
        cin >> t >> g;
        while (t --)
        {
            cin >> s;
            ss.push_back(s);
        }
        sort(ss.begin(), ss.end());
        t = ss.size();
        for (int i = 0; i < t; ++ i)
            val[ss[i]] = i,
            cnt.emplace_back(i, 0, 0, 0, 0, 0, 0);    
        while (g --)
        {
            cin >> a >> aa
                >> b >> bb;
            int aaa = val[a], bbb = val[b];
            auto &[ano, a1, a0, aw, at, al, apt] = cnt[aaa];
            auto &[bno, b1, b0, bw, bt, bl, bpt] = cnt[bbb];
            a1 += aa, b0 += aa, b1 += bb, a0 += bb;
            if (aa > bb)
            {
                ++ aw, ++ bl;
                apt += 3;
            }
            else if (aa < bb)
            {
                ++ bw, ++ al;
                bpt += 3;
            }
            else ++ at, ++ bt, ++ apt, ++ bpt;
        }   
        sort(cnt.begin(), cnt.end(), cmp);
        cout << "Group " << i << ":\n";
        for (auto &ii : cnt)
        {
            auto [no, _1, _0, win, tie, lose, pt] = ii;
            cout << ss[no] << ' ' << pt << ' ' << win << ' '
                 << lose << ' ' << tie << ' ' << _1 << ' '
                 << _0 << endl;
        }
        cout << endl;
    }
    return 0;
}

确实，属性并不是都同号的 😃

E - NIH Budget

本场为数不多的有点技术含量的题目之一——不过是个背包板子；

const int N = 1e5 + 5;
int dp[N];
array<pair<int, int>, 4> info[20];

signed main()
{
    ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::cout.tie(nullptr);
#if 0
    freopen("in.txt", "r", stdin);
#endif
    int n = scanner.nextInt(), d, b;
    for (int i = 1; i <= n; ++ i)
    {
        scanner(d, b);
        memset(dp, 0, sizeof(int) * (b + 1));
        for (int j = 0; j < d; ++ j)
            for (auto &[cost, save] : info[j])
                scanner(cost, save);
        for (int j = 0; j < d; ++ j)
            for (int x = b; x >= 0; -- x)
                for (auto &[cost, save] : info[j])
                    if (x - cost >= 0)
                        maximize(dp[x], dp[x - cost] + save);
        cout << "Budget #" << i << ": Maximum of " << dp[b]
             << " lives saved." << endl << endl;
    }
    return 0;
}

不会有人不会写背包吧，~~不会这个人就是我自己吧（逃~~

F - Interstellar Love

并查集；注意只有一个的星星的连通块不是一个星座

const int N = 1100;

namespace DSU
{
    int fa[N], siz[N], cnt[N];

    void init(int n)
    {
        for (int i = 0; i <= n; ++ i)
            fa[i] = i, siz[i] = 1, cnt[i] = 0;
    }

    int father(int u)
    {return fa[u] == u ? u : (fa[u] = father(fa[u]));}

    void join(int x, int y)
    {
        int fx = father(x), fy = father(y);
        if (fx == fy) return void(cnt[fx] ++);
        if (siz[fx] <= siz[fy]) 
            fa[fx] = fy, siz[fy] += siz[fx], 
            cnt[fy] += cnt[fx] + 1;
        else fa[fy] = fx, siz[fx] += siz[fy], 
            cnt[fx] += cnt[fy] + 1;
    }
}

signed main()
{
    ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::cout.tie(nullptr);
#if 0
    freopen("in.txt", "r", stdin);
#endif
    int n = scanner.nextInt();
    for (int tt = 1; tt <= n; ++ tt)
    {
        int s = scanner.nextInt(),
            c = scanner.nextInt();
        DSU::init(s + 1);
        while (c --)
        {
            int u = scanner.nextInt(), 
                v = scanner.nextInt();
            DSU::join(u, v);    
        }
        bitset<N> star, fix;
        for (int i = 1; i <= s; ++ i)
        {
            auto fa = DSU::father(i);
            auto e = DSU::cnt[fa], v = DSU::siz[fa];
            if (v <= 1) continue;
            star.set(fa);
            if (e >= v) fix.set(fa);
        }
        cout << "Night sky #" << tt << ": " << star.count()
             << " constellations, of which " << fix.count()
             << " need to be fixed." << endl << endl;
    }
    return 0;
}

G - Plate Spinning

虽然没什么内容但是被恶心到了…… 需要特判当只有一个盘子的时候始终可行。

signed main()
{
    ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::cout.tie(nullptr);
#if 0
    freopen("in.txt", "r", stdin);
#endif
    int T = scanner.nextInt();
    for (int i = 1; i <= T; i++)
    {
        int n = scanner.nextInt(),
            m = scanner.nextInt();
        auto t = 1.0 * n * 0.5 * 5;
        print("Circus Act ", i, ":\n");
        if (n == 1 || t <= 1.0 * m)
            println("Chester can do it!\n");
        else println("Chester will fail!\n");
    }
    return 0;
}

然后这一个题就奉献了快两个小时的罚时（）

H - The Eternal Quest for Caffeine

除了单程往返，还要考虑源点在中间，路径绕一个环的情况；我最开始的时候就没有考虑那种情况，所以莽了（）后来队友给我改成了遍历一个段，就对了（

const int N = 16;
array<bitset<N>, N> machine;
bitset<N> ok;
 
signed main()
{
    ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::cout.tie(nullptr);
#if 0
    freopen("in.txt", "r", stdin);
#endif
    int n, s, m, t, x;
    char state;
    for (int T = 1; T; ++T)
    {
        cin >> n >> s >> m;
        if (!n && !s && !m) return 0;
        for (auto &ii : machine) ii.reset();
        ok.reset();
        for (int i = 1; i <= n; ++i)
        {
            cin >> t;
            while (t--) cin >> x, machine[i].set(x);
            cin >> state;
            if (state == 'Y') ok.set(i);
        }
        int ans = 0x3f3f3f3f;
        for (int i = 1; i <= n; ++i)
            for (int j = i; j <= n; ++j)
            {
                bool haveSource = false, flag = false;
                bitset<N> tmp;
                for (int k = i; k <= j; ++k)
                {
                    tmp |= machine[k];
                    if (k == s) haveSource = true;
                    if (ok[k]) flag = true;
                }
                if (haveSource && flag && tmp.count() == m)
                    ans = min(ans, (j - i) * 2);
            }
        cout << "Test case #" << T << ": ";
        if (ans < 0x3f3f3f3f) cout << ans << endl << endl;
        else cout << "Impossible" << endl << endl;
    }
    return 0;
}

虽然是队友给我改过的，但是这也算是我过的吧（

I - Pegasus Circle Shortcut

平面几何运算板子题：对着题目嗯模拟就成了

namespace Geo {...}

signed main()
{
    ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::cout.tie(nullptr);
#if 0
    freopen("in.txt", "r", stdin);
#endif
    double cx, cy, sx, sy, tx, ty;
    const string ans[] = {"Stick to the Circle.", "Watch out for squirrels!"};
    using Geo::point, Geo::number;
    const number PI = 3.1415926535897932384626;
    cout << fixed << setprecision(8);
    for (int T = 1, n; T; ++ T)
    {
        cin >> cx >> cy >> sx >> sy >> tx >> ty;
        if (cx == 0. && cy == 0. && sx == 0. &&
            sy == 0. && tx == 0. && ty == 0.) break;
        point s(sx, sy), t(tx, ty), c(cx, cy);    
        point last(sx, sy), now;
        number interior = 0;
        for (cin >> n; n --;)
        {
            cin >> now.x >> now.y;
            interior += now.distance(last);
            last = now;
        } interior += t.distance(last);
        auto str0 = s - c, str1 = t - c;
        auto ang = abs(str0.angle() - str1.angle());
        number d = c.distance(s) + c.distance(t);
        minimize(ang, 2 * PI - ang);
        number circular = d * ang / 2;
        bool ok = Geo::compareTo(interior, circular) <= 0;
        cout << "Case #" << T << ": " << ans[ok] << endl << endl;
    }
    return 0;
}

当然，前提是要有靠谱的板子。

J - Lowest Common Ancestor

用数组模拟二叉树，给定两个下标求它们的 LCA 的下标；很显然，用数组模拟二叉树的子节点就是 <<= 1；所以 LCA 显然就是在二进制表示下两个节点下标的公共前缀代表的下标。

问题就是题目给的还是恶心的 16 进制；我队友拿 Python 写过了，但是我尝试拿 C++ 写崩了…… 所以最后屈服于 Java:

import java.math.BigInteger;
import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
	    var sc = new Scanner(System.in);
	    int T = sc.nextInt();
	    sc.nextLine();
	    for (int i = 1; i <= T; ++ i)
        {
            var line = sc.nextLine();
            var ab = line.split(" ");
            var a = new BigInteger(ab[0], 16);
            var b = new BigInteger(ab[1], 16);
            var aa = a.toString(2);
            var bb = b.toString(2);
            int lim = Math.min(aa.length(), bb.length());
            int cur = 0;
            while (cur < lim &&
                aa.charAt(cur) == bb.charAt(cur))
                ++ cur;
            var prefix = aa.substring(0, cur);
            var c = new BigInteger(prefix, 2);
            System.out.printf("Case #%d: %s\n\n", i, c.toString(16));
        }
    }
}

🐎的，在 C++ 我都不用 printf，在 Java 里却用的一身的劲儿（

特别注意：因为 ACM 是只保证有 Java 8 的，所以上面的代码过不了编译（

后记

没什么好说的…… 只能说这样的比赛差不多得了，好自为之（）

但是打的还是有那么一点点捞；要是模拟题写的这么慢准度这么差那我也差不多得了（

牛客 2021 年度训练联盟热身训练赛第二场 回顾

题解