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 的代码。
不知道没有边权的限制还能不能做。
