5

Facebook Hacker Cup 2021 Round 1

 2 years ago
source link: http://www.shuizilong.com/house/archives/facebook-hacker-cup-2021-round-1/
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
October 21, 2021

A1.
给定一个 ’01-‘ 组成的字符串 s，设 f(s) 为忽略掉 s 中所有 ‘-‘ 字符后，相邻字符发生变换的次数。
求 f(s)。
扫一遍即可。

A2
统计所有 s 的子串的 f 值。
统计相邻的 ’01’ pair 的贡献即可。

const int N = int(1e6) + 9;
char s[N];
int n;
int main() {
#ifndef ONLINE_JUDGE
freopen("in.txt","r",stdin);
freopen("out.txt","w",stdout);
#endif
Rush {
RD(n); RS(s);
Int z = 0;
char lc = '?'; // 上一个字符
int lp = 0; // 上一个字符的位置
REP(i, n) {
char c = s[i];
if(c != 'F') {
if (lc != c) {
if(lc != '?') z += Int(lp) * (n-i);
lc = c;
}
lp = i+1;
}
}
OT(z);
}
}

A3
s 中还包含 ‘.’ 字符，如果出现 ‘.’ 字符，则用此前的字符串替换 ‘.’ 位置，询问 A2。

延续 A2 的思路，我们需要对每个 pair 统计出左边和右边分别有多少字符。
这个比较简单，但是每个 ‘.’ 内部还会出现很多 pair，我们需要对这些内部的 pair 也 O(1) 时间统计。
这样首先我们需要改进 A2 的算法，再开一个 ls 变量记录前面所有 pair 的贡献，这样就可以不支持后续长度的情况下 incremental 的维护答案。

const int N = int(1e6) + 9;
char s[N];
int n;
int main() {
#ifndef ONLINE_JUDGE
freopen("in.txt","r",stdin);
freopen("out.txt","w",stdout);
#endif
Rush {
RD(n); RS(s);
Int z = 0;
char lc = '?'; // 上一个字符
int lp = 0; // 上一个字符的位置
Int ls = 0; // 右边新增加一个字符时答案的增量。
REP(i, n) {
z += ls;
char c = s[i];
if (c != 'F') {
if (lc != '?' && lc != c) {
z += lp;
ls += lp;
}
lp = i+1;
lc = c;
}
}
OT(z);
}
}

进一步考虑 ‘.’ 的影响，我们不仅需要知道当右边新增加一个字符时的增量 ls，还需要对称的，知道当左边新增加一个字符时的增量 rs，
那么新的答案就是 2z + len(ls+rs)，还要考虑合并的位置会不会产生一组新的 pair。
因此还需要维护左右第一个字符是什么和所在位置以及一共有多少 pair。各种维护即可。

const int N = int(1e6) + 9;
char s[N];
int n;
int main() {
#ifndef ONLINE_JUDGE
freopen("in.txt","r",stdin);
freopen("out.txt","w",stdout);
#endif
Rush {
RD(n); RS(s);
Int z = 0;
char lc = '?', rc = '?'; //
Int lp = 0, rp = 0, ct = 0;
Int ls = 0, rs = 0;
Int len = 0;
REP(i, n) {
char c = s[i];
if (c == '.') {
z = z*2 + len*(ls+rs);
ls = ls*2 + len*ct;
rs = rs*2 + len*ct;
ct *= 2;
if (lc != rc) {
ct += 1; ls += lp; rs += (len-rp+1);
z += lp * (len-rp+1);
}
if (lc != '?') lp += len;
len *= 2;
} else {
z += ls;
len += 1;
if (c != 'F') {
if (rc == '?') {
rc = c, rp = len;
}
if (lc != '?' && lc != c) {
z += lp;
ls += lp;
ct += 1;
}
lp = len;
lc = c;
}
rs += ct;
}
}
OT(z);
}
}

C.
感觉是树形 dp 基本功题，最简单的方法应该是 dfs() 两次，
一次得到子树的 dp 状态，一次得到子树外的 dp 状态，但是比赛时思路比较混乱。

赛后读了一下 nhb 的代码，发现忽略了一个重要得条件，就是边权 <= 20。。。
然后就可以直接暴力加维了。。囧。

当然边分治也可以，参考 neal wu 的代码。

不知道没有边权的限制还能不能做。

Posted by xiaodao
Category: 日常


report

Recommend

About Joyk


Aggregate valuable and interesting links.
Joyk means Joy of geeK