Codeforces Round #809 (Div. 2)

A .Another String Minimization Problem

很自然想到，枚举数组取

t=min(a[i],m+1−a[i])t = min( a[i] , m+1 -a[i] )

k=max(a[i],m+1−a[i])k = max(a[i],m+1-a[i])

若 s[t]s[t] 不为 AA, 变为 AA 并标记

s[t]s[t] 被标记,则把s[k]s[k] 变为 AA 并标记

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
void solve(){
    int n,m;
    cin>>n>>m;
    vector<int> a(n+1);
    forr(i,1,n) cin >> a[i];
    string s;
    forr(i,1,m) s+="B";
    //cout << s << endl;
    map<int,int> mp;
    forr(i,1,n){
        int t = min(a[i],m+1-a[i]);
        int k = max(a[i],m+1-a[i]);
        if(mp[t-1]){
            s[k-1] = 'A';
            mp[k-1]++;
        }
        else{
            mp[t-1]++;
            s[t-1] = 'A';
        }
        //cout << s << endl;
    }
    cout << s << endl;
}

B .Making Towers

找规律

对于数 ii ， 当数 ii 之间间隔为偶数时 ,ans[i]++ans[i]++;

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
vector<int> g[100005];
void solve(){
    int n;cin>>n;
    vector<int> a(n+1);
    set<int> s;
    forr(i,1,n) cin >> a[i],g[a[i]].push_back(i),s.insert(a[i]);
    map<int,int> mp;
    for(auto it = s.begin();it!=s.end();it++){
        int t = *it;
        mp[t] = 1;
        for(int i = 1;i < g[t].size();i++){
            int tt = g[t][i] - g[t][i-1] - 1;
            if( (tt%2)==0) mp[t]++;
        }
    }
    forr(i,1,n) cout << mp[i] <<" \n"[i==n];
    for(auto it = s.begin();it!=s.end();it++) g[*it].clear();
}

C .Qpwoeirut And The City

先要求峰最多再要求添加最少

奇数答案一定隔一个判断一次，贡献一次答案

考虑偶数

​ 偶数在满足峰最多的前提，有一次可以隔两个选并且只有一个位置,否则不可能取到最多峰

​ 那么枚举哪个位置隔二个，很多题解都是通过两个前缀来做

​ 官方 tutorial 方法更容易理解

image-20220719221721952

​

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
int a[100005];
int cal(int x){
    return max(0ll,(max(a[x-1],a[x+1])+1-a[x]));
}

void solve(){
    int n;
    cin >> n;
    forr(i,1,n) cin >> a[i];
    int res = 0;
    if(n&1){
        for(int i = 2;i <= n;i+=2){
            if(a[i] > a[i-1] && a[i] > a[i+1]) continue;
            else {
                res += max(a[i-1],a[i+1]) + 1-a[i];
            }
        }
            cout << res << endl;
    }
    else{
            for(int i = 2; i < n;i+=2){
                if(a[i] > a[i-1] && a[i] > a[i+1]) continue;
                else {
                    res += max(a[i-1],a[i+1]) + 1-a[i];
                }                
            }
            int sum = res;
            for(int i = n-1;i>1;i-=2){
                res -= cal(i-1);
                res += cal(i);
                sum = min(res,sum);
            }
            cout << sum << endl;
        }
}

D1 .Chopping Carrots (Easy Version)

$n <= 3000 $

考虑 min⁡1<=i<=n(⌊aipi⌋) = v\min\limits_{1<=i<=n}(\lfloor \frac{a_i}{p_i} \rfloor) \ = \ v

分析可知 v∈[0,a1]v ∈ [0,a_1]

反证

​ 若 v∈[a2,an]v ∈ [a_2,a_n] 因为 min⁡1<=i<=n(⌊aipi⌋) = v\min\limits_{1<=i<=n}(\lfloor \frac{a_i}{p_i} \rfloor) \ = \ v ， 那么对于 x = [a1,v−1]x \ =\ [a_1,v-1] , 总有 xpi<v\frac{x}{p_i} < v

故 v∈[0,a1]v ∈ [0,a_1]

那么枚举 vv, 计算出 pi=min(k,ai/v)p_i = min(k,a_i/v) ,再用计算出的 pip_i 求出 max⁡1<=i<=n(⌊aipi⌋)\max\limits_{1<=i<=n}(\lfloor \frac{a_i}{p_i} \rfloor) 和 min⁡1<=i<=n(⌊aipi⌋)\min\limits_{1<=i<=n}(\lfloor \frac{a_i}{p_i} \rfloor)

做差求最大的差值 resres

O(n∗ai)O(n*a_i)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
void solve(){
    int n,k;
    cin>>n>>k;
    vector<int> a(n+1);
    forr(i,1,n) cin >> a[i];
    int mx = -inf,mi = inf;
    int res = inf;
    for(int v = 0;v <= a[1];v++){
        int p;
        forr(i,1,n){
            if(!v) p = k;
            else p = min(k,a[i]/v);
            mx = max(mx,a[i]/p);
            mi = min(mi,a[i]/p);
        }
        // cout << mx << " " << mi << endl;
        // cout << res << endl;
        res = min(res,mx-mi);
        mx = -inf,mi = inf;
    }
    cout << res << endl;
}

E .Qpwoeirut and Vertices

Kruskal 重构树

给一个区间[l,r][l,r]

要求的就是这个区间的子区间 （ [a,b]  l<=a<=b<=r[a,b]\,\ l<=a<=b<=r a→ba\rightarrow b 的所有路径最长边权的最小值 ）的最大值

[a,b]  l<=a<=b<=r[a,b]\,\ l<=a<=b<=r a→ba\rightarrow b 的所有路径最长边权的最小值 ，可以用Kruskal重构树直接求出

然后就是对 [l,r] 的一次区间求和, 因为是静态的可使用 $ ST表 $ O(n)O(n) 预处理

注意各种数组的初始化问题

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
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
int n, m, q;
struct node
{
    int u, v, w;
    bool operator<(const node &t) const
    {
        return w < t.w;
    }
} edge[400005];
struct nod
{
    int to, ne;
} e[400005<<1];
int h[400005<<1], cnt = 1;
void add(int u, int v)
{
    e[++cnt] = {v, h[u]};
    h[u] = cnt;
}
int pre[400005<<1];
int tot;
int val[400005];
int d[400005<<1];
int f[200005][21]; 

int find(int x)
{
    return x == pre[x] ? x : pre[x] = find(pre[x]);
}

void dfs(int u, int fa)
{
    d[u] = d[fa] + 1;
    // cout <<u <<" "<<  d[u] << endl;
    for (int i = h[u]; i; i = e[i].ne)
    {
        int v = e[i].to;
        if (v == fa)
            continue;
        f[v][0] = u;
        forr(k, 1, 20) 
            if (f[v][k - 1])
                f[v][k] = f[f[v][k - 1]][k - 1];
            else 
                break;
        dfs(v, u);
    }
}

int lca(int a, int b)
{
    if (d[a] > d[b])
        swap(a, b);
    for (int i = 20; i >= 0; i--)
        if (d[f[b][i]] >= d[a])
            b = f[b][i];
    if (a == b)
        return a;
    for (int i = 20; i >= 0; i--)
        if (f[a][i] != f[b][i])
            a = f[a][i], b = f[b][i];
    return f[a][0];
}

void kruskal()
{
    sort(edge + 1, edge + 1 + m);
    forr(i, 1, n) pre[i] = i,d[i] = 0;
    tot = n;
    forr(i, 1, m)
    {
        int a = find(edge[i].u), b = find(edge[i].v);
        if (a != b)
        {
            val[++tot] = edge[i].w;
            d[tot] = 0;
            pre[tot] = pre[a] = pre[b] = tot;
            add(tot, a);
            add(a, tot);
            add(b, tot);
            add(tot, b);
        }
    }
    for (int i = tot; i >= 1; i--)
    {
        if (!d[i]){
            dfs(i, -1);
        }
    }
}

int dis[200005];
int ff[200005][21];
void ST(){
    // 不用初始化
    forr(i,1,n-1) ff[i][0] = dis[i];
    forr(i,1,20)for(int j = 1;j+(1<<i)-1 <= n-1;j++){
        ff[j][i] = max(ff[j][i-1],ff[j+(1<<(i-1))][i-1]);
    }
}


int query(int l,int r){
	int s = __lg(r-l+1);
	return max(ff[l][s],ff[r-(1<<s)+1][s]);
}
void solve()
{

    cin >> n >> m >> q;
    cnt = 1;
    forr(i,1,2*n) h[i] = 0;
    forr(i,1,2*n) forr(j,1,20) f[i][j] = 0;
    cnt = 1;
    forr(i, 1, m)
    {
        int u, v;
        cin >> u >> v;
        edge[i] = {u, v, i};
    }
    kruskal();

    for(int i = 1;i<n;i++){
        int t = lca(i,i+1);
        dis[i] = val[t];
    }
    ST();
    while (q--)
    {
        int l, r;
        cin >> l >> r;
        if(l==r) cout << 0 <<" ";
        else cout << query(l,r-1) << " ";
    }
    cout << endl;
}