牛客多校第十场题解
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)
题解： 签到题，按的奇偶染色即可
#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;
} 
