牛客多校赛题解（九十）

1.Train Wreck

题目链接：F-Train Wreck_2021牛客暑期多校训练营10 (nowcoder.com)

题目大意

给了一个入栈队列和一堆数字，要求构造一个序列，能满足在任意时刻栈里的状态都是一致的

解题思路

将出入栈序列看成一棵树

1. 左括号：生成一个新节点，进入下一层
2. 右括号：将当前的操作回退，此时如果有新的左括号，将放在右边

则，问题将转换成在树上任意一个非叶子节点，他的儿子两两不相等，故只要维护一个优先队列，每次给每个儿子填上不同的元素即可

参考：2021牛客暑期多校训练营10 F. Train Wreck(思维题)_牛客博客 (nowcoder.net)

ACCode:

#include<bits/stdc++.h>
 
const int N = 1e6 + 5;
const int mod = 998244353;
 
std::vector<int> G[N];
int vis[N], ans[N];
 
void solve() {
    int n; std::cin >> n;
    std::string s; std::cin >> s;
    int cnt = 0; // 初始深度为0
    std::vector<int> record;
    record.emplace_back(0);
    for (int i = 0; i < 2 * n; i++) {
        if (s[i] == '(') {
            ++cnt;// 节点编号加1
            G[record.back()].emplace_back(cnt);
            record.emplace_back(cnt);
        } else {
            record.pop_back(); // 回到上一个节点
        }
    }
    for (int i = 1; i <= n; i++) {
        int x; std::cin >> x;
        ++vis[x];
    }
    std::priority_queue<std::pair<int, int> > que;
    for (int i = 1; i <= n; i++) {
        if (vis[i]) {
            que.push({vis[i], i});
        }
    }
    for (int i = 0; i <= n; i++) {
        if (G[i].size() > que.size()) {
            std::cout << "NO\n"; return ;
        }
        std::vector<std::pair<int, int> > buffer; // 暂时缓存
        for (auto v : G[i]) { // 这一层放不同的数字
            ans[v] = que.top().second;
            buffer.emplace_back(que.top());
            que.pop();
        }
        for (auto v : buffer) {
            if (v.first - 1 > 0) {
                que.push({v.first - 1, v.second});
            }
        }
    }
    std::cout << "YES\n";
    for (int i = 1; i <= n; i++) {
        std::cout << ans[i] << " \n"[i == n];
    }
}
 
 
int main() {
    std::cin.sync_with_stdio(false), std::cin.tie(nullptr);
    int T = 1; //std::cin >> T;
    while (T--) {
        solve();
    }
    return 0;
}

2.War of Inazuma (Easy Version)

题目链接：H-War of Inazuma (Easy Version)_2021牛客暑期多校训练营10 (nowcoder.com)

题目大意

有一个n维的立方体，共有2^n^个节点，如果立方体上两个节点相连，那么要求两个点的而精致表示有一位不同，现在要求构造一个2^n^长度的01序列，表示每个点的颜色，要求每个点相邻的点中和这个点颜色相同的点的个数不能超过sqrt(n)向上取整个

解题思路

如果想要让这个构造出来的立方体满足题意，需要使得相同的数字之间没有边，在对应的二进制中去寻找规律就是：而精致中表示偶数个1的填0，奇数个1填1

参考链接： 牛客多校10 War of Inazuma (Easy Version) 构造_yanweiqi1754989931的博客-CSDN博客

ACCode

#include <iostream>
using namespace std;
 
int main() {
    int n;
    cin >> n;
    string ans = "01";
    for (int i = 0; i < n - 1; ++i) {
        int len = ans.size();
        for (int j = 0; j < len; ++j) {
            ans += ans[j] == '0' ? '1' : '0';
        }
    }
    cout << ans << endl;
}

3.Happy Number

题目链接：H-Happy Number_2021牛客暑期多校训练营9 (nowcoder.com)

题目大意

给定数字2 3 6要用这几个数字组成新的数字，称为Happy Number，比如：

2、3、6、22、23、26、32...

现在问，第n个happy number是多少？

解题思路

我最开始考虑的是用三进制来解决，但是把三进制的代码写出来以后，发现样例都过不了（笑死）

后来仔细去分析了这个题的规律，发现：一位的数有3个，两位的数有9个，三位的数有27个，n位的数有3^n^个，现在我们只需要确定这个数是在第多少行，然后再把目标数据与行首的数相减，再转换成三进制就解决了（感觉可能还是写复杂了，不过能过题就是好算法！）

ACCode

/*
 * @Author: NorthCityChen
 * @LastEditTime: 2021-08-19 18:15:51
 * @Description: 
 * @Website: https://grimoire.cn
 * Copyright (c) NorthCityChen All rights reserved.
 */

#include <bits/stdc++.h>
using namespace std;

const int N = 1e6 + 10;
const int M = 1e9 + 10;
int myAns[40], idx = 0;

int main()
{
    long long arr[] = {0, 3, 12, 39, 120, 363, 1092, 3279, 9840, 29523, 88572, 265719, 797160, 2391483, 7174452, 21523359, 64570080, 193710243, 581130732, 1743392199, 5230176600, 15690529803, 47071589412, 141214768239, 423644304720};
    int ans[] = {2, 3, 6};
    long long n;
    cin >> n;
    n--;
    if (n <= 3) {
        cout << ans[n] << endl;
        return 0;
    }
    
    int loc = 25;
    long long res = 0;
    for (int i = 1; i <= 25; i++)
    {
        if (arr[i] <= n && n < arr[i + 1])
        {
            loc = i;
            break;
        }
    }
    // cout << loc << endl;
    res = n - arr[loc];
    // cout << res << endl;

    
    while (res > 0)
    {
        myAns[idx++] = res % 3;
        // cout << "RES" << res % 3 << " ";
        res /= 3;
    }
    // cout << endl;
    for (int i = loc; i >= 0; i--)
    {
        // cout << ans[myAns[i]];
        cout << ans[myAns[i]];
    }
    cout << endl;
    return 0;
}