牛客多校第十场题解

Browser Games

https://ac.nowcoder.com/acm/contest/11261/A

A - Browser Games

题意：
按顺序往集合中插入字符串，要求输出最少的前缀串数量，使得这些前缀串能匹配出所有已经加入集合的字符串，并且不能匹配出未加入集合的字符串。题目保证任一字符串不是其它字符串的前缀。

思路：
如果不卡空间的话，光字典树就有许多不同的做法。一种是从上到下做，但是这种做法需要表示出每个节点的儿子有哪些，就比较浪费空间。对于一棵树来说，每个节点的父节点是唯一的，压缩字典树的时候应从这一点考虑。所以尝试先写写从下到上的做法。

建立字典树之后，记录每个字符串的尾节点的位置，然后从下往上走。如果遇到的节点只有当前字符串一个儿子，那么就可以继续往上走。当遇到有分叉的节点时，我们记录下已经有几个字符串经过这个节点了。如果经过这个点的字符串数量没到达分叉的数量，我们停止往上走。如果到了，说明后面的字符串都没有拥有当前的前缀，即当前的前缀串能匹配出来的字符串都已经加入集合了，所以我们只需要一个前缀串就能表示出分叉的所有字符串，更新下答案，并继续往上走。

接下来考虑压缩字典树。因为要让儿子指向父亲，就想到了递归处理，处理完了得到儿子节点，再让儿子节点指向当前节点。在字典树中，如果字符串在当前位的字符相同，就会用同一个节点。这一步可以在递归过程中使用桶排处理（好像刚开始在最外面直接sort也行），将要走同一个节点的字符串归类，然后进行递归处理。一长段相同的字符串也可以压成一个节点，写的时候可以用指针来写，不过没必要，因为编译器会把定义了但是没用到的内存忽略掉。

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

typedef long long ll;

const int inf = 0x3f3f3f3f;
const ll INF = 0x3f3f3f3f3f3f3f3f;
const int N = 1e5 + 7;

int n, posNode[N], posStr[N], tot;
char s[N][103];
vector<int> bkt[64];

int getId(char c) {
    if (islower(c)) return c - 'a';
    if (isupper(c)) return c - 'A' + 26;
    if (isdigit(c)) return c - '0' + 52;
    if (c == '.') return 62;
    return 63;
}

struct Node {
    int son, del, fa;
    void init() {
        son = del = fa = 0;
    }
}node[N * 100];

int newNode() {
    node[++tot].init();
    return tot;
}

int bktSort(int dep, int l, int r) {
    if (l == r) {
        return posNode[ posStr[l] ] = newNode(); // 记录尾节点位置
    }

    bool allSame = true; 
    for (int i = l; i < r; ++i) {
        if (s[ posStr[i] ][dep] != s[ posStr[i + 1] ][dep]) {
            allSame = false;
            break;
        }
    }
    if (allSame) { // 如果存在相同的前缀，把这个前缀压成一个节点，节省内存
        int u = bktSort(dep + 1, l, r);
        if (dep) return u;
        node[u].fa = 0; // 如果还没有根节点，先定义出来。这里默认0为根节点。
        return 0;
    }

    for (int i = 0; i < 64; ++i) {
        bkt[i].clear();
    }
    for (int i = l; i <= r; ++i) { // 按照当前位置的字符分到不同的桶里，因为保证了字符串不是其他字符串的前缀，直接分配没问题，最后一定会递归成l == r
        bkt[ getId(s[ posStr[i] ][dep]) ].push_back( posStr[i] );
    }
    int cnt = l;
    vector<int> len;
    for (int i = 0; i < 64; ++i) {
        if (!bkt[i].size()) continue;
        for (auto j : bkt[i]) posStr[cnt++] = j; // 对排序后的字符串重新编号
        len.push_back(bkt[i].size()); // 记录每个桶的大小，不可直接递归，否则后面会影响前面的桶
    }
    int u = newNode();
    for (auto w : len) {
        node[bktSort(dep + 1, l, l + w - 1)].fa = u;
        l += w;
        node[u].son++;
    }
    return u;
}

void solve() {
    scanf("%d", &n);
    for (int i = 0; i < n; ++i) {
        scanf("%s", s[i]);
        posStr[i] = i; // 因为需要桶排，每次移动整个字符串不太好，所以用一个数组代表当前下标代表的字符串
    }
    int rt = bktSort(0, 0, n - 1);
    int ans = 0;
    for (int i = 0; i < n; ++i) {
        int now = posNode[i];
        ans++;
        while ((now = node[now].fa) != rt) {
            node[now].del++;
            if (node[now].son == node[now].del) {
                ans -= node[now].son - 1;
            } else {
                break;
            }
        }
        printf("%d\n", ans);
    }
}

int main() {
    int t = 1;
    while (t--) solve();
    return 0;
}

F - Train Wreck

题意： 左括号表示一列火车进栈，右括号表示一列火车出栈。提供了一些颜色，要求对每列火车进行染色，使得栈中的所有的火车颜色序列不重复。

样例二解释：

4
()(())()
1 2 4 4

栈中各时刻的火车序列为：

[1]
[2]
[2,3]
[4]

样例的染色方案为，4 2 4 1，因此获得的颜色序列为

[4]
[2]
[2, 4]
[1]

题目要求即为这些颜色序列，必须唯一

思路： 只有拥有共同前缀的火车，需要染成不同的颜色

样例解释：

假设当前有如下火车序列:
[1]
[1,2]
[1,2,3]
[1,2,4]
[1,2,5]
[1,2,6]
[1,2,7]

对于火车3，4，5，6，7，他们拥有共同的前缀1-2，因此需要染成不同的颜色，才能保证颜色序列唯一。

根据入栈情况，对火车建边，如3，4，5，6，7都会跟在火车2的后面，由此建立2 → 3、2 → 4、2 → 5、2 → 6、2 → 7的有向边。

即2指向的所有火车，需要染成不同颜色。跑DFS，优先分配数量较多的颜色。

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

#define endl "\n"
#define dbg(x...)             \
    do {                      \
        cout << #x << " -> "; \
        err(x);               \
    } while (0)

void err() { cout << endl; }

template <class T, class... Ts>
void err(const T& arg, const Ts&... args) {
    cout << arg << ' '; err(args...);
}

const int maxn = 1e6 + 10;

int cnt, head[maxn];
struct edge {
    int v, next;
    edge () {}
    edge (int v, int next) :v(v), next(next) {}
} e[maxn << 1];

void add (int u, int v) { 
    e[++cnt] = edge(v, head[u]), head[u] = cnt;
}

struct node {
    int col, cnt;
    node () {}
    node (int col, int cnt) : col(col), cnt(cnt) {}

    bool operator<(const node& A)const { return A.cnt > cnt; }
};

int n, tot;
char s[maxn << 1];

int col[maxn];
int ans[maxn];
priority_queue<node> Q;

bool flag = true;
void dfs (int u) {
    if (!flag) return;

    queue<node> tem;
    for (int i = head[u]; i; i = e[i].next) {
        int v = e[i].v;
        if (Q.size()) {
            node nod = Q.top(); Q.pop();
            ans[v] = nod.col;
            nod.cnt--;
            if (nod.cnt) tem.emplace(nod);
        } else  return (void)( flag = false );
    }

    while (tem.size()) {
        Q.emplace(tem.front());
        tem.pop();
    }

    for (int i = head[u]; i; i = e[i].next) {
        int v = e[i].v;
        dfs(v);
    }
}

int pre[maxn];
void run() {
    scanf("%d", &n);

    scanf("%s", s + 1);

    int idx = 0;
    pre[ ++pre[0] ] = n + 1;    
    for (int i = 1; i <= 2 * n; ++i) {
        if (s[i] == '(') {
            add(pre[ pre[0] ], ++idx);
            pre[ ++pre[0] ] = idx;
        } else pre[0]--;
    }

    for (int i = 1, c; i <= n; ++i) {
        scanf("%d", &c);
        col[c]++;
    }

    for (int i = 1; i <= n; ++i) {
        if (col[i]) Q.emplace(i, col[i]);
    }

    dfs(n + 1);

    if (flag) {
        puts("YES");
        for (int i = 1; i <= n; ++i) {
            printf("%d%c", ans[i], " \n"[i == n]);
        }
    } else {
        puts("NO");
    }
}

int main() {
    int t = 1;
//    scanf("%d", &t);
    while (t--) run();
    return 0;
}
/*
7
((()()()()()))
1 2 3 4 5 5 5
*/

H - War of Inazuma (Easy Version)

题解： 签到题，按 $1$ 的奇偶染色即可

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

#define endl "\n"
#define dbg(x...)             \
    do {                      \
        cout << #x << " -> ";\
        err(x);               \
    } while (0)

void err() {
    cout << endl;
}

template <class T, class... Ts>

void err(const T& arg, const Ts&... args) {
    cout << arg << ' '; err(args...);
}

int n;
string s;

void run() {
    cin >> n;
    n = pow(2, n);
    for(int i = 0; i < n; i++) {
        int num = 0;
        for(int j = 0; j <= 23; j++) {
            if((i >> j) & 1) num++;
        }
        if(num % 2) s += '1';
        else s += '0';
    }
    cout << s << endl;
}

int main() {
    int t = 1;
//    scanf("%d", &t);
    while (t--) run();
    return 0;
}

J - Illuminations

题意： 给出一个凸包以及凸包外若干个点，这些点射出光源，问最少要多少个点就能照亮整个凸包

题解：

先求出点到凸包的两个切点
得到了若干个区间，然后在凸包上求一个环覆盖

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

#define dbg(x...) do { cout << #x << " -> "; err(x); } while (0)
void err () {   cout << endl;}
template <class T, class... Ts>
void err(const T& arg, const Ts&... args) { cout << arg << ' '; err(args...);}

#define ll long long
#define ull unsigned long long
#define LL __int128
#define inf 0x3f3f3f3f
#define INF 0x3f3f3f3f3f3f3f3f
#define pii pair<int, int>
#define PII pair<ll, ll>
#define tint tuple<int, int, int> 
#define fi first
#define se second
#define pb push_back
#define eb emplace_back
#define em emplace
#define mp(a,b) make_pair(a,b)
#define all(x) (x).begin(), (x).end()
#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define PAUSE system("pause");
const double Pi = acos(-1.0);
const double eps = 1e-8;
const int maxn = 2e5 + 10;
const int maxm = 1e5 + 10;
const int mod = 998244353;

inline ll rd() {
    ll f = 0; ll x = 0; char ch = getchar();
    for (; !isdigit(ch); ch = getchar()) f |= (ch == '-');
    for (; isdigit(ch); ch = getchar()) x = (x << 1) + (x << 3) + ch - '0';
    if (f) x = -x;
    return x;
}
void out(ll a) {if(a<0)putchar('-'),a=-a;if(a>=10)out(a/10);putchar(a%10+'0');}
#define pt(x) out(x),puts("")
inline void swap(ll &a, ll &b){ll t = a; a = b; b = t;}
inline void swap(int &a, int &b){int t = a; a = b; b = t;}
inline ll min(ll a, ll b){return a < b ? a : b;}
inline ll max(ll a, ll b){return a > b ? a : b;}
ll qpow(ll n,ll k,ll mod) {ll ans=1;while(k){if(k&1)ans=ans*n%mod;n=n*n%mod;k>>=1;}return ans%mod;}
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

int sgn(double x) {
    if (fabs(x) < eps) return 0;
    else return x < 0 ? -1 : 1;
}

struct Point {
    double x, y;
    Point() {}
    Point(double x, double y) :x(x), y(y) {}
    double operator ^ (const Point b)const {
        return x * b.y - y * b.x;
    }
    Point operator - (const Point b)const {
        return Point(x - b.x, y - b.y);
    }
}p[maxn];

struct polygon {
    int n;
    Point p[maxn];
    int onleft(Point p, Point a, Point b) {
        return sgn((a - p) ^ (b - p));
    }
    pii tangentsConvex(Point u) {
        int l = 0, r = 0;
        for (int k = 20; k >= 0; k--) {
            int d = (1 << k) % n;
            if (onleft(u, p[l], p[(l + d) % n]) <= 0)
                l = (l + d) % n;
            if (onleft(u, p[l], p[(l + n - d) % n]) <= 0)
                l = (l + n - d) % n;
            if (onleft(u, p[r], p[(r + d) % n]) >= 0)
                r = (r + d) % n;
            if (onleft(u, p[r], p[(r + n - d) % n]) >= 0)
                r = (r + n - d) % n;
        }
        return mp(l, r);
    }
}s;

pii a[maxn];
int n, m;
int id[maxn];
int nxt[maxn][22];


void solve() {
    scanf("%d%d", &n, &m);
    s.n = n;
    for (int i = 0; i < n; i++)
        scanf("%lf%lf", &s.p[i].x, &s.p[i].y);
    for (int i = 1; i <= m; i++) {
        Point t;
        scanf("%lf%lf", &t.x, &t.y);
        a[i] = s.tangentsConvex(t);
    }    
    vector<tint> seg;
    for (int i = 1; i <= m; i++) {
        int r = a[i].fi, l = a[i].se;
        if (l <= r) {
            seg.pb({ l, r - 1, i });
            seg.pb({ l + n, r - 1 + n, i });
        }
        else {
            seg.pb({ l, r - 1 + n, i });
        }
    }
    sort(all(seg));
    int right = 0, rightId = 0;
    int p = 0;
    for (int i = 0; i < 2 * n; i++) {
        while (p < seg.size() && get<0>(seg[p]) <= i) {
            if (get<1>(seg[p]) + 1 > right) {
                right = get<1>(seg[p]) + 1;
                rightId = get<2>(seg[p]);
            }
            p++;
        }
        if (i < right) {
            nxt[i][0] = right;
            id[i] = rightId;
        }
    }
    int K = 22;
    for (int i = 2 * n - 1; i >= 0; i--) {
        for (int k = 1; k < K; k++)
            nxt[i][k] = nxt[nxt[i][k - 1]][k - 1];
    }

    int ans = inf, ansSt = 0;
    for (int st = 0; st < n; st++) {
        int now = 0;
        int o = st;
        for (int k = K - 1; k >= 0; k--)
            if (nxt[o][k] != 0 && nxt[o][k] < st + n) {
                o = nxt[o][k];
                now += 1 << k;
            }
        o = nxt[o][0];
        now++;
        if (o != 0 && o >= st + n && now < ans) {
            ans = now;
            ansSt = st;
        }
    }
    if (ans == inf) {
        puts("-1");
    }
    else {
        vector<int> vec;
        int o = ansSt;
        while (o < ansSt + n) {
            vec.eb(id[o]);
            o = nxt[o][0];
        }
        printf("%d\n", vec.size());
        for (auto g : vec)
            printf("%d ", g);
        puts("");
    }        
}

int main() {
//    freopen("in.txt","r",stdin);
//    freopen("out.txt", "w", stdout);
    int t = 1;
    // t = rd();
    // scanf("%d", &t);
    // cin >> t;
    while(t--)
        solve();
    PAUSE;
    return 0;
}