今天的题目感觉难度分度有点奇怪，第二题是水题， 其次是第一题，再然后是最恶心的第三题

T1：大新闻

　　bz原题看到就想吐槽，原来刷数位dp的时候以为是到神题并没有写（刚开始想过果断弃疗），考场上想了半个小时发现可做

　　只要对两种情况分别处理就好了

　　加密的话，对每一位分别考虑统计有多少对数异或之后这一位是1，把贡献累加起来再除以 n2就可以了

　　不加密，要确定每个数的最优解，我们还是考虑每一位，统计有多少个数在最优情况下异或该位为0 （详见代码）

#include 
     
      #include 
      
       #define eps 1e-7 using namespace std; typedef long long ll;typedef long double ld; ld ans1, ans2;double p; ll n, f[110][2], num[110];int tim, len, nw, bit[110], vis[110][2]; ll Dp(int dep, int fg) {    if(dep==0) return 1ll;    if(vis[dep][fg]==tim) return f[dep][fg];    vis[dep][fg] = tim;    int l = (dep==len)?1:0, r = fg?bit[dep]:1;    ll ret = 0;    for(int i = l ; i <= r ; ++ i) {        if(dep==nw&&i!=1) continue;        ret += Dp(dep-1, fg&&(i>=r));    }    return f[dep][fg] = ret;} int main() {    scanf("%lld%lf", &n, &p);    -- n;    ll now_n = n;    while(now_n) bit[++ len] = now_n&1ll, now_n >>= 1ll;    for(int i = len ; i >= 1 ; -- i) {        ++ tim;        nw = i;        num[i] = Dp(len, 1);        if(i!=len&&len>=2) num[i] += 1ll<<(len-2);        ld w = 2.*(ld)(n+1ll-num[i])*1.*num[i]*(ld)(1ll<<(i-1));        ans2 += w/((ld)(n+1ll)*(ld)(n+1ll));    }    ll v = 1ll;    ans1 = (ld)((1ll<
       
        = 1 ; -- i) {        if(bit[i]==0) {            ld w = (ld)v*((ld)(1ll<
        
         <
        
       
      
     

T2：谈笑风生

　　仍是bz原题，但并没有看到过

　　对于每个询问，要考虑两种情况，一种是b是a的祖先， 用 a 的深度和k取一个 min 乘以 a 的子树大小 （并不包含 a 本身， 下同）

　　另一种， b 是 a 的子树中的一个节点，这样的话我们枚举 a 的子节点， 所有子节点的子树中的节点总和就是答案

　　所以我们对每个点记录它子树的 size ，再记录它子树的size 的和

　　我们只要用 a 的子树的子树 size 的 和减掉 不合法的子树的size， 我们可以把bfs 序 搞出来，维护 size 的和的前缀和

　　 不合法的子树是 从 depth[a]+k+1 开始的 所有在 a 的子树中的 节点

　　把最开始不合法的区间找到并减去就可以了。

#define MAXN 300010UL#include 
     
      #include 
      
       #define INF 1e9 using namespace std; typedef long long ll; int n, m, t, num, hd, tl, cnt, q[MAXN], bg[MAXN], tr[MAXN], ls[MAXN], rs[MAXN], d[MAXN], fa[MAXN], sn[MAXN], st[MAXN], ed[MAXN];ll sum[MAXN], se[MAXN], pr[MAXN]; struct Edge { int hou, nt; } sg[MAXN<<1]; void Add(int x, int y) {    sg[t] = (Edge){y, d[x]}, d[x] = t ++;    sg[t] = (Edge){x, d[y]}, d[y] = t ++;    return;} void Dfs(int x, int _fa, int dep) {     st[x] = ++ num, sn[x] = dep, se[x] = 0, sum[x] = 0, fa[x] = _fa;    for(int i = d[x] ; i != -1 ; i = sg[i].nt) {        if(sg[i].hou==_fa) continue;        Dfs(sg[i].hou, x, dep+1);        se[x] += se[sg[i].hou]+1ll;        sum[x] += sum[sg[i].hou];    }    sum[x] += (ll)se[x];    ed[x] = num;    return;} ll Solve(int dep, int L, int R) {    if(ls[dep]==INF) return 0;    int l = ls[dep], r = rs[dep], ans = -1;    while(l<=r) {        int mid = (l+r)>>1;        if(st[tr[mid]]>=L) r = mid-1, ans = mid;        else l = mid+1;    }    if(ans==-1) return 0;    int ans1 = -1;    l = ans, r = rs[dep];    while(l<=r) {        int mid = (l+r)>>1;        if(st[tr[mid]]<=R) l = mid+1, ans1 = mid;        else r = mid-1;    }    if(ans1==-1) return 0;    return pr[ans1]-pr[ans-1];} int main() {//  freopen("laugh.in", "r", stdin);//  freopen("laugh.out", "w", stdout);    memset(d, -1, sizeof(d));    int x, y;    scanf("%d%d", &n, &m);    for(int i = 2 ; i <= n ; ++ i) scanf("%d%d", &x, &y), Add(x, y);    for(int i = 1 ; i <= n ; ++ i) ls[i] = INF, rs[i] = -INF;    Dfs(1, 0, 1);    hd = tl = 0;    q[++ tl] = 1;    while(hd
       
        cnt) ls[sn[op]] = cnt;        if(rs[sn[op]]
        
         =1) ans += 1ll*k*se[p];        else ans += 1ll*(ll)(sn[p]-1)*se[p];        printf("%lld\n", ans);    }    return 0;}
        
       
      
     

T3：图样图森破

　　　是道神题 直接粘题解      

　　　如果某个串本身就是回文串，那么答案必然为无穷大。直接特判这种情况。 对于一般的情况，我们枚举回文串的中心的

位置。如果以串 s 的某个位置为中心的最 长回文串“半径”超过了 s 的边界（不妨认为是左边界，右边界的情况同理），那么 s

的右端 一定剩下了一段没有被加入回文串。但这一部分是可能在回文串里面的，我们可以枚举另 一个串 t，使得 t 的后若干字

符和 s 右端剩下的部分回文，这样 t 的一部分和 s 剩下的部分 都可以加入回文串了。此时 t 的左侧还可能剩下一段没有加入

回文串的部分，那么我们可 以重复一遍上面的过程。 但直接这样做与暴力无异。我们用图论模型来描述这个过程。对每个位

置建两个点， 分别代表当前剩余的部分为这个位置以左和以右的部分。新设一个起点，向串内的每个越 过了边界的回文串的

另一侧的位置对应点连一条有向边，边权为回文串长度。在枚举串 t 的时候，如果发现一个可以匹配的 t，就从 s 的位置对应

点向匹配到的 t 的位置对应点连一 条有向边，边权为这一段的长度。如果 t 正好被完全匹配，就连向一个特殊的节点。　　

　　　建出这个模型后，一个可以出现在 S 中的回文子串会对应从起点出发的一条路径。如 果从起点可以走到一个环，或者

可以到达特殊节点，就意味着答案是无穷大。否则答案就 是从起点出发的最长路。 这个拓扑图的点数为 O(m) 级别，边数为

O(nm) 级别，当然实际上不会有这么恐怖。 我们只需要一个可以快速查询两个串的 LCP 的数据结构，后缀数组 +ST 表足以

胜任。 总复杂度为 O(m log m + nm)，可以通过全部数据。 如果使用 Hash 求 LCP，或者用单次查询 O(log m) 的 RMQ

数据结构，则复杂度为 O(nm log m)，只能通过 60% 的数据。 另外，理论上答案可以达到 O(mL) 级别，不过这样的数据

几乎不可能构造出来。实际 测试数据中，n > 1 的测试点的答案均未超过 40000。 

 　　

#define MAXN 220010UL#define MAXM 22000010UL#include 
     
      #include 
      
       #include 
       
         using namespace std; typedef long long ll; ll dis[MAXN];int n, t, d[MAXN], cnt, bin[20], lg[MAXN], len[MAXN], slen[MAXN];int m, sym, lc[MAXN], rc[MAXN], sa[MAXN], rk[MAXN], ht[MAXN], st[20][MAXN], s[MAXN];int S, T, T_, wa[MAXN], wb[MAXN], wv[MAXN], ws[MAXN], du[MAXN], q[MAXN];bool vis[MAXN], inq[MAXN];char str[MAXN]; struct Edge { int hou, nt, zhi; } sg[MAXM]; bool Cmp(int *r, int a, int b, int l) {    return (r[a]==r[b])&&(r[a+l]==r[b+l]);} void Get_sa(int *r, int n, int m) {    int *x = wa, *y = wb, *t, i, j, p;    for(i = 0 ; i < m ; ++ i) ws[i] = 0;    for(i = 0 ; i < n ; ++ i) ++ ws[x[i] = r[i]];    for(i = 1 ; i < m ; ++ i) ws[i] += ws[i-1];    for(i = n-1 ; i >= 0 ; -- i) sa[-- ws[x[i]]] = i;    for(j = 1, p = 1 ; p < n ; j <<= 1, m = p) {        for(i = n-j, p = -1 ; i < n ; ++ i) y[++ p] = i;        for(i = 0 ; i < n ; ++ i) if(sa[i]>=j) y[++ p] = sa[i]-j;        for(i = 0 ; i < n ; ++ i) wv[i] = x[y[i]];        for(i = 0 ; i < m ; ++ i) ws[i] = 0;        for(i = 0 ; i < n ; ++ i) ++ ws[wv[i]];        for(i = 1 ; i < m ; ++ i) ws[i] += ws[i-1];        for(i = n-1 ; i >= 0 ; -- i) sa[-- ws[wv[i]]] = y[i];        for(t = x, x = y, y = t, i = 1, p = 1, x[sa[0]] = 0 ; i < n ; ++ i) {            x[sa[i]] = Cmp(t, sa[i-1], sa[i], j)?p-1:p ++;        }    }    return;} void Get_height(int *r, int n) {    int i, j, k = 0;    for(i = 1 ; i <= n ; ++ i) rk[sa[i]] = i;    for(i = 0 ; i < n ; ht[rk[i ++]] = k) {        for(k?-- k:k = 0, j = sa[rk[i]-1] ; r[i+k]==r[j+k] ; ++ k);    }    return;} void Get_ST(int n) {    for(int i = 1 ; i <= n ; ++ i) st[0][i] = ht[i];    for(int i = 1 ; i <= lg[n] ; ++ i) {        for(int j = 1 ; j+bin[i]-1 <= n ; ++ j) {            st[i][j] = min(st[i-1][j], st[i-1][j+bin[i-1]]);                }    }    return;} int Get_id(int x, int y) {    if(x==0) return S;    if(x==-1) return T;    if(y==0||y>len[x]) return T_;    if(y>0) return slen[x-1]*2+y;    return slen[x-1]*2+len[x]-y;} int Query_ST(int x, int y) {    x = rk[x], y = rk[y];    if(x>y) swap(x, y);    ++ x;    int k = lg[y-x+1];    return min(st[k][x], st[k][y-bin[k]+1]);} int Query(int a, int x, int b, int y) {    if(x>0) a = lc[a]+x-1;    else a = rc[a]+(len[a]+x);    if(y>0) b = lc[b]+y-1;    else b = rc[b]+(len[b]+y);    return Query_ST(a, b);} bool loop(int x) {    vis[x] = inq[x] = 1;    for(int i = d[x] ; i != -1 ; i = sg[i].nt) {        ++ du[sg[i].hou];        if(inq[sg[i].hou]||(!vis[sg[i].hou]&&loop(sg[i].hou))) return true;    }    return inq[x] = 0;} void Add_edge(int x, int y, int z) {    sg[t] = (Edge){y, d[x], z}, d[x] = t ++;    return;} void Add(int a, int x, int b, int y, int w) {    a = Get_id(a, x), b = Get_id(b, y);    Add_edge(a, b, w);    return;} int main() {    bin[0] = 1;    for(int i = 1 ; i < 20 ; ++ i) bin[i] = bin[i-1]<<1;    lg[0] = -1;    for(int i = 1 ; i < MAXN ; ++ i) lg[i] = lg[i>>1]+1;    sym = 26;    scanf("%d", &n);    for(int i = 1 ; i <= n ; ++ i) {        scanf("%s", str);        len[i] = strlen(str);        slen[i] = slen[i-1]+len[i];        s[m ++] = ++ sym, lc[i] = m;        for(int j = 0 ; j < len[i] ; ++ j) s[m ++] = str[j]-'a'+1;        s[m ++] = ++ sym, rc[i] =m;        for(int j = 0 ; j < len[i] ; ++ j) s[m ++] = str[len[i]-j-1]-'a'+1;    }    Get_sa(s, m+1, 300);    Get_height(s, m);    Get_ST(m);    S = 0, T = slen[n]*2+10, T_ = T+1;    bool fg = true;    for(int i = 1 ; i <= n ; ++ i) if(Query(i, 0, i, -(len[i]+1))==len[i]) fg = false;    memset(d, -1, sizeof(d));    ll ans = 0;    for(int i = 1 ; fg && i <= n ; ++ i) {        for(int j = 1 ; j <= len[i] ; ++ j) {            int r = Query(i, j, i, -j), l = min(j, len[i]-j+1);            ans = max(ans, (ll)r*2-1);            if(l==r) {                if(j>len[i]-j+1) Add(0, 0, i, -(j-r), r*2-1);                else Add(0, 0, i, j+r, r*2-1);            }        }        for(int j = 2 ; j <= len[i] ; ++ j) {            int r = Query(i, j, i, -(j-1)), l = min(j-1, len[i]-j+1);            ans = max(ans, (ll)r*2);            if(l==r) {                if(j-1>len[i]-j+1) Add(0, 0, i, -(j-1-r), r*2);                else Add(0, 0, i, j+r, r*2);            }        }        Add(0, 0, i, 1, 0);        Add(0, 0, i, -len[i], 0);        for(int j = 1 ; j <= len[i] ; ++ j) {            int wf = 0, wr = 0;            for(int k = 1 ; k <= n ; ++ k) {                int r = Query(i, j, k, -len[k]);                if(r==len[i]-j+1) Add(i, j, k, -(len[k]-r), r*2);                else if(r==len[k]) Add(i, j, i, j+r, r*2);                else wf = max(wf, r*2);                r = Query(i, -j, k, 1);                if(r==j) Add(i, -j, k, r+1, r*2);                else if(r==len[k]) Add(i, -j, i, -(j-r), r*2);                else wr = max(wr, r*2);            }            if(wf>0) Add(i, j, -1, 0, wf);            if(wr>0) Add(i, -j, -1, 0, wr);        }    }    for(int i = 0 ; i < MAXN ; ++ i) du[i] = vis[i] = inq[i] = 0;    if(!fg || loop(S) || vis[T_]) ans = -1;    else {        int hd = 0, tl = 0;        q[++ tl] = S;        for(int i = 0 ; i < MAXN ; ++ i) dis[i] = 0;        while(hd