首页 模拟赛

manacher + 前缀和，点分治 + 贪心 + 双指针

# A. 花海漫步

原题 CF17E\text{CF17E}。

首先要想到的一点是正难则反，答案转化成总回文串个数减去不相交的回文串个数。

我们记 fi,gif_i, g_i 分别表示以 ii 为结尾的回文串个数和以 ii 开头的回文串个数。

那么答案就是：

ANS=∑i=1nfi×gi+1ANS = \sum_{i = 1}^n f_i \times g_{i + 1}

关于 fi,gif_i, g_i 如何求？

我们只需要在 manacher\text{manacher} 过程中维护差分数组，最后做一遍前缀和就行了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
#include <bits/stdc++.h>
#define pb push_back
#define int long long

using namespace std;

namespace IO{
    inline int read(){
        int x = 0, f = 1;
        char ch = getchar();
        while(!isdigit(ch)) {if(ch == '-') f = -1; ch = getchar();} 
        while(isdigit(ch)) x = (x << 3) + (x << 1) + ch - '0', ch = getchar();
        return x * f;
    }

    template <typename T> inline void write(T x){
        if(x < 0) putchar('-'), x = -x;
        if(x > 9) write(x / 10);
        putchar(x % 10 + '0');
    }
}
using namespace IO;

const int N = 4e6 + 10;
const int mod = 1e9 + 7;
int n, tot, ans;
char str[N], s[N];
int p[N], f[N], g[N];

inline int qpow(int a, int b){
    int res = 1;
    while(b){
        if(b & 1) res = 1ll * res * a % mod;
        a = 1ll * a * a % mod, b >>= 1;
    }
    return res;
}

inline void manacher(){
    for(int i = 1; i <= n; ++i)
        s[(i << 1) - 1] = '*', s[i << 1] = str[i];
    s[0] = '#', s[(n << 1) + 1] = '*';
    n = (n << 1) + 1;
    int id = 0, r = 0;
    for(int i = 1; i <= n; ++i){
        if(i < r) p[i] = min(r - i, p[(id << 1) - i]);
        else p[i] = 1;
        while(s[i - p[i]] == s[i + p[i]]) p[i]++;
        if(i + p[i] > r) id = i, r = i + p[i];
        tot = (tot + p[i] / 2) % mod;
        f[i - p[i] + 1]++, f[i + 1]--, g[i]++, g[i + p[i]]--;
    }
}

signed main(){
#ifndef ONLINE_JUDGE
    freopen("test.in", "r", stdin);
    freopen("test.out", "w", stdout);
#endif
    n = read(), scanf("%s", str + 1);
    manacher();
    for(int i = 1; i <= n; ++i)
        f[i] += f[i - 1], g[i] += g[i - 1];
    ans = 1ll * tot * (tot - 1) % mod * qpow(2, mod - 2) % mod;
    // cout << "ans  " << ans << " " << tot << endl;
    int sum = 0;
    for(int i = 2; i <= n - 2; i += 2)
        sum = (sum + g[i]) % mod, ans = ((ans - 1ll * sum * f[i + 2] % mod) % mod + mod) % mod;
    write(ans), puts("");
    return 0;
}

# B. 收购城市

首先有一个非常重要的结论。

定义 fxf_x 表示 xx 到其他所有城市的 Lucky\text{Lucky} 路径个数。

判断一个子段 [l,r][l, r] 是否合法，只需要判断：

∑i=lrfi>∑i=1l−1fi+∑i=r+1nfi\sum_{i = l}^r f_i > \sum_{i = 1}^{l - 1}f_i + \sum_{i = r + 1}^n f_i

证明可以自己推推式子，大概就是两边没有用的都可以抵消掉。

剩下的问题就是如何求 fxf_x 了。

我们考虑使用点分治。对于一个分治点的所有儿子，开个桶记录已经走过的点的大小城市个数差，前缀和查询一遍再后缀和查询一遍即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
#include <bits/stdc++.h>
#define pb push_back
#define int long long

using namespace std;

namespace IO{
    inline int read(){
        int x = 0, f = 1;
        char ch = getchar();
        while(!isdigit(ch)) {if(ch == '-') f = -1; ch = getchar();}
        while(isdigit(ch)) x = (x << 3) + (x << 1) + ch - '0', ch = getchar();
        return x * f;
    }

    template <typename T> inline void write(T x){
        if(x < 0) putchar('-'), x = -x;
        if(x > 9) write(x / 10);
        putchar(x % 10 + '0');
    }
}
using namespace IO;

const int N = 1e5 + 10;
int n;
int a[N], p[N], id[N];
vector <int> G[N];
int siz[N], mx[N], rt, vis[N];

inline void get_root(int x, int fa, int all){
    siz[x] = 1, mx[x] = 0;
    for(auto y : G[x]){
        if(y == fa || vis[y]) continue;
        get_root(y, x, all), siz[x] += siz[y];
        mx[x] = max(mx[x], siz[y]);
    }
    mx[x] = max(mx[x], all - siz[x]);
    if(!rt || mx[rt] > mx[x]) rt = x;
}

unordered_map <int, int> mp;
int s[N];

inline void qry(int x, int fa, int now){
    s[id[x]] += mp[-now];
    for(auto y : G[x])
        if(y != fa && !vis[y]) qry(y, x, now + a[y]);
}

inline void upd(int x, int fa, int now){
    mp[now]++;
    for(auto y : G[x])
        if(y != fa && !vis[y]) upd(y, x, now + a[y]);
}

inline void calc(int x){
    mp.clear(), mp[a[x]]++;
    reverse(G[x].begin(), G[x].end());
    for(auto y : G[x])
        if(!vis[y]) qry(y, x, a[y]), upd(y, x, a[x] + a[y]);
    mp.clear();
    reverse(G[x].begin(), G[x].end());
    for(auto y : G[x])
        if(!vis[y]) qry(y, x, a[y]), upd(y, x, a[x] + a[y]);
    s[id[x]] += mp[0];
}

inline void solve(int x){
    vis[x] = 1, calc(x);
    for(auto y : G[x]){
        if(vis[y]) continue;
        mx[rt = 0] = n, get_root(y, 0, siz[y]), solve(rt);
    }
}

signed main(){
#ifndef ONLINE_JUDGE
    freopen("test.in", "r", stdin);
    freopen("test.out", "w", stdout);
#endif
    n = read();
    for(int i = 1; i <= n; ++i){
        a[i] = read();
        if(!a[i]) a[i] = -1;
    }
    for(int i = 1; i < n; ++i){
        int u = read(), v = read();
        G[u].pb(v), G[v].pb(u);
    }
    for(int i = 1; i <= n; ++i) id[p[i] = read()] = i;
    get_root(1, 0, n), solve(rt);
    for(int i = 1; i <= n; ++i) s[i] += s[i - 1];
    int ans = 0;
    for(int i = 1, j = 0; i <= n; ++i){
        while(j < i && s[i] - s[j] > s[n] - s[i] + s[j]) j++;
        ans += j;
    }
    write(ans), puts("");
    cerr << clock() << endl;
    return 0;
}

# C. 圣战救援

似乎是道披着计算几何皮的结论题。

不过还不会。

更新于 阅读次数 次