2021牛客暑期多校训练营10

F

题意

有n个火车
左括号表示火车进站右括号表示是火车出站
给定每个火车的颜色，问如何安排顺序使得在同一时刻内，火车站内没有相同颜色的火车

solution

#include <bits/stdc++.h>
#define sc(x) scanf("%lld", &(x))
#define pr(x) printf("%lld\n", (x))
#define rep(i, l, r) for (int i = l; i <= r; ++i)
using namespace std;
typedef long long ll;
const int N = 1e6 + 7;
const int mod = 1e9 + 7;
char s[N * 2];
unordered_map<int, int> color;
struct cmp {
    bool operator()(const int &a, const int &b) const { return a > b; }
};
multimap<int, int, cmp> mp;
deque<int> idx[N];
int a[N];
int res[N];
void dfs(int L, int R, int dep) {
    if (idx[dep].empty()) return;
    vector<int> pos;
    for (int &x : idx[dep]) {
        if (L <= x and x <= R) {
            pos.push_back(x);
            idx[dep].pop_front();
        } else
            break;
    }
    //
    int sz = pos.size();
    if (!sz) return;
    if (mp.size() < sz) {
        puts("NO");
        exit(0);
    }
    vector<pair<int, int>> vec;
    rep(i, 1, sz) {
        vec.emplace_back(*mp.begin());
        mp.erase(mp.begin());
    }
    int i = 0;
    for (auto p : vec) {
        res[pos[i++]] = p.second;
        p.first--;
        if (p.first) mp.insert(p);
    }
    //
    if (sz >= 2) {
        for (int R = 1; R < sz; ++R) {
            dfs(pos[R - 1], pos[R] - 1, dep + 1);
        }
        dfs(pos[sz - 1], R, dep + 1);
    } else if (sz == 1) {
        dfs(pos[0], R, dep + 1);
    }
}
signed main() {
    int n, x;
    scanf("%d%s", &n, s + 1);
    rep(i, 1, n) {
        scanf("%d", &x);
        ++color[x];
    }
    for (auto p : color) mp.insert({p.second, p.first}); 

    int p = 0, st = 0;
    rep(i, 1, n * 2) {
        if (s[i] == '(')
            ++st, a[++p] = st;
        else
            --st;
    }

    rep(i, 1, n) idx[a[i]].emplace_back(i);
    dfs(1, n, 1);
    puts("YES");
    rep(i, 1, n) printf("%d%c", res[i], i == n ? '\n' : ' ');
    return 0;
}
/*

(()())(()())
1     1
 2     2
   2     2
表示一辆火车进站时，它是火车站内的第几辆火车
*/

时间复杂度分析

采用了unordedmap做颜色统计，线性处理， $O(n)$
计算栈内数量，线性处理， $O(n)$
dfs按层访问，原子操作是 $O(n)$ 的，因为考虑 $1e6$ 辆火车，每一层的原子操作都对应着一辆火车
每个原子操作采用了multimap的弹出压入操作，单次的时间复杂度是 $O(\log n)$

来看这段在dfs的代码

    vector<pair<int, int>> vec;
    rep(i, 1, sz) {
        vec.emplace_back(*mp.begin());
        mp.erase(mp.begin());
    }
    int i = 0;
    for (auto p : vec) {
        res[pos[i++]] = p.second;
        p.first--;
        if (p.first) mp.insert(p);
    }

首先，multimap的key的总和的上限就是 $10^6$ ；
其次，每个multimap的弹出操作对应的就是写出一个火车对应的答案。
所以时间复杂度是 $O(n\log n)$ 这一点是不应该有任何争议的。

然后来分析常数：
每个火车对应一次unordered_map的插入，一次multimap的删除、一次multimap的插入、一次deque的插入和一次vector的插入。

考虑常数就是四个STL的常数之和。

这一做法采用了multimap实现对单键值排序的大顶堆，由于优先队列对于这一问题的优化，所以可以采用priority_queue这一数据结构对它完成优化，常数会小一点。

为了不让写法过于复杂，就不对单键值排序了，反正也没什么影响。

#include <bits/stdc++.h>
#define sc(x) scanf("%lld", &(x))
#define pr(x) printf("%lld\n", (x))
#define rep(i, l, r) for (int i = l; i <= r; ++i)
using namespace std;
typedef long long ll;
const int N = 1e6 + 7;
const int mod = 1e9 + 7;
char s[N * 2];
unordered_map<int, int> color;
priority_queue<pair<int, int>> mp;
deque<int> idx[N];
int a[N];
int res[N];
void dfs(int L, int R, int dep) {
    if (idx[dep].empty()) return;
    vector<int> pos;
    for (int &x : idx[dep]) {
        if (L <= x and x <= R) {
            pos.push_back(x);
            idx[dep].pop_front();
        } else
            break;
    }
    //
    int sz = pos.size();
    if (!sz) return;
    if (mp.size() < sz) {
        puts("NO");
        exit(0);
    }
    vector<pair<int, int>> vec;
    rep(i, 1, sz) {
        vec.emplace_back(mp.top());
        mp.pop();
    }
    int i = 0;
    for (auto p : vec) {
        res[pos[i++]] = p.second;
        p.first--;
        if (p.first) mp.push(p);
    }
    //
    if (sz >= 2) {
        for (int R = 1; R < sz; ++R) {
            dfs(pos[R - 1], pos[R] - 1, dep + 1);
        }
        dfs(pos[sz - 1], R, dep + 1);
    } else if (sz == 1) {
        dfs(pos[0], R, dep + 1);
    }
}
signed main() {
    int n, x;
    scanf("%d%s", &n, s + 1);
    rep(i, 1, n) {
        scanf("%d", &x);
        ++color[x];
    }
    for (auto p : color) mp.push({p.second, p.first});

    int p = 0, st = 0;
    rep(i, 1, n * 2) {
        if (s[i] == '(')
            ++st, a[++p] = st;
        else
            --st;
    }

    rep(i, 1, n) idx[a[i]].emplace_back(i);
    dfs(1, n, 1);
    puts("YES");
    rep(i, 1, n) printf("%d%c", res[i], i == n ? '\n' : ' ');
    return 0;
}

H

思维题，控制每个相邻点的二进制表示的1的个数奇偶不同就行

#include <bits/stdc++.h>
#define sc(x) scanf("%lld", &(x))
#define pr(x) printf("%lld\n", (x))
#define rep(i, l, r) for (int i = l; i <= r; ++i)
using namespace std;
typedef long long ll;
const int N = 1e5 + 7;
const int mod = 1e9 + 7;
signed main() {
    int n;
    scanf("%d", &n);
    int t = 1 << n;
    for (int i = 0; i < t; ++i) {
        if (__builtin_popcount(i) & 1)
            putchar('1');
        else
            putchar('0');
    }
    return 0;
}