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: 日常