Chgtaxihe's blog

训练补题-牛客训练赛2

# 牛客训练赛2补题记录

# B: Boundary 几何

几何一直很差，主要靠队友，可惜队友没能做出来。

特意去学了一下求三角形外心，顺便扩充一下几何模板。

AC代码

template<class T>
struct geometry{
	// 模板
};

using geo = geometry<ll>;

geo::point p[2020];

void solve(){
    int n; cin >> n;
    for(int i=0; i<n; i++) cin >> p[i].x >> p[i].y;

    geo::point ori(0, 0);
    int ans = 0;
    
    for(int i=0; i<n; i++){
        map<pair<double, double>, int> cnt;
        for(int j=i+1; j<n; j++){
            if(p[i] * p[j] == 0) continue; // 叉乘等于0，说明共线
            pair<double, double> circ = geo::circumcentre_pr(ori, p[i], p[j]);
            int num = ++cnt[circ];
            ans = max(ans, num);
        }
    }
    cout << ans + 1 << '\n';
}

signed main(){
    Android;
    solve();
}
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

# F: Fake Maxpooling 二维单调队列

比赛的时候，瞎猜了一个结论：记以(x,y)(x,y)为右下角的k×kk\times k的矩阵中，元素最大值为mat(x,y)mat(x,y)，对于k≥2k\ge 2的情况，有mat(a,b)≤max(c,d)(a≤c,b≤d)mat(a,b)\le max(c,d)(a\le c,b\le d)，然后就过了。

正确做法是二维单调，先找到每一行的最优列，在处理每一列的每一行

#include <bits/stdc++.h>
#define ll long long
using namespace std;

const int maxn = 5050;
int val[maxn][maxn], n, m, k;
int mx_col[maxn][maxn];
int que[maxn], l, r;

int _lcm(int x, int y){
    return x * y / __gcd(x, y);
}

void solve(){
    cin >> n >> m >> k;
    for(int i=1; i<=n; i++) for(int j=1; j<=m; j++) val[i][j] = _lcm(i, j);

    for(int i=1; i<=n; i++){ // 先处理行
        l = r = 0;
        for(int j=1; j<=m; j++){
            while(r > l && j - k >= que[l]) l++;
            while(r > l && val[i][que[r-1]] < val[i][j]) r--;
            que[r++] = j;
            mx_col[i][j] = que[l];
        }
    }

    ll ans = 0;
    for(int i=k; i<=m; i++){ // 处理列
        l = r = 0;
        for(int j=1; j<=n; j++){ // 遍历所有行
            while(r > l && j - k >= que[l]) l++;
            while(r > l && val[que[r-1]][mx_col[que[r-1]][i]] < val[j][mx_col[j][i]]) r--;
            que[r++] = j;
            if(j >= k) {
                int row = que[l];
                ans += val[row][mx_col[row][i]];;
            }
        }
    }
    cout << ans << '\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

# C: Cover the Tree 思维

设叶子数量为nn，显然答案为⌈n2⌉\lceil\frac{n}{2}\rceil。重点在于如何构造方案。

首先，选取一个度数大于2的点作为根

将所有叶子按照dfsdfs序排列，若nn为偶数，则构造l1↔ln2+1,l2↔ln2+2,⋯,ln2↔lnl_1\leftrightarrow l_{\frac{n}{2}+1},l_2\leftrightarrow l_{\frac{n}{2}+2},\cdots,l_{\frac{n}{2}}\leftrightarrow l_{n}即可。

假设边ee所连接的深度较大的点为uu，以uu为根的子树覆盖的叶子dfsdfs序排名为[L,R][L,R]

显然只要L≠1L\ne1或R≠nR\ne n，则一定有某个链li↔li+n2l_i\leftrightarrow l_{i+\frac{n}{2} }，使得L≤dfn[i]≤RL \le dfn[i]\le R，且 dfn[i+n2]dfn[i+\frac{n}{2}]（或dfn[i−n2]dfn[i-\frac{n}{2}]）不在[L,R][L,R]内。其中dfn[x]dfn[x]代表第xx个叶子的dfsdfs序排名。

若L=1,R=nL=1,R=n，此时说明该节点是根节点（没有需要被覆盖的边），否则说明根节点的度数为11！

# G: Greater and Greater 思维

两种做法，个人更倾向于第一种，而第二种与题解的做法更相似

# 做法1

利用单调性和bitset。SxS_x代表为串AA中以第xx个数字为开头，长为mm的串；fail[i]fail[i]代表SiS_i是否符合条件。同时，用vis[x]vis[x]代表串AA的第xx个数字是否被访问。

接下来，对串A,BA,B合并后排序，并依次访问。若当前访问的为AA中第xx个数字，则打上vis[x]vis[x]标记；若当前访问的为BB中的第xx个数字，说明对于任意i∈{x∣vis[i]}i\in\{x\mid vis[i]\}，其将导致Si−x+1S_{i-x+1}失败，即要在fail[i−x+1]fail[i-x+1]打上标记。

使用Bitset加速上述打标记的过程即可。

#include <bits/stdc++.h>
#define Android ios::sync_with_stdio(false), cin.tie(NULL)
#define pii pair<int, int>
using namespace std;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

const int maxn = 1e5 + 5e4 + 1000;

int n, m;
bitset<maxn> vis, fail;
vector<pii> num;

void solve(){
    cin >> n >> m;
    for(int i=1, u; i<=n; i++){
        cin >> u;
        num.push_back({u, i});
    }
    for(int i=1, u; i<=m; i++){
        cin >> u;
        num.push_back({u, -i});
    }
    sort(num.begin(), num.end());

    for(pii & p: num){
        if(p.second > 0){
            vis[p.second] = 1;
        }else{
            fail |= vis>>(-p.second-1);
        }
    }
    int ans = 0;
    for(int i=1; i<=n-m+1; i++){
        if(fail[i] == 0) ans++;
    }
    cout << ans << '\n';
}
  
signed main(){
    Android;
    solve();
}
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

# 做法2

设SiS_i为AA中以ii开头，长mm的串；succ[i]succ[i]为串SiS_i是否成功的标记。

考虑现在读入AiA_i，则需要对succ[i−m+1],…,succ[i]succ[i-m+1],\dots,succ[i]进行更新，具体更新如下：

succ[i−m+1]&=Ai≥B[i−(i−m+1)]+1succ[i−m+2]&=Ai≥B[i−(i−m+2)]+1⋯succ[i]&=Ai≥B1\begin{aligned}succ[i-m+1]&\&=A_i\ge B_{[i-(i-m+1)]+1}\\succ[i-m+2]&\&=A_i\ge B_{[i-(i-m+2)]+1}\\&\cdots \\succ[i]&\&=A_i\ge B_1\end{aligned}

稍微改写一下得:

succ[i−m+1]&=Ai≥Bmsucc[i−m+2]&=Ai≥Bm−1⋯succ[i]&=Ai≥B1\begin{aligned}succ[i-m+1]&\&=A_i\ge B_{m}\\succ[i-m+2]&\&=A_i\ge B_{m-1}\\&\cdots \\succ[i]&\&=A_i\ge B_1\end{aligned}

使用bitset加速上述过程

#include <bits/stdc++.h>
#define pii pair<int, int>
using namespace std;

const int inf = 0x3f3f3f3f;
const int maxn = 1e5 + 5e4 + 1000;
const int maxm = 4e4 + 1000;

int n, m;
bitset<maxm> bit[maxm], res;
pii B[maxm];
int A[maxn];

void solve(){
    cin >> n >> m;
    for(int i=1; i<=n; i++) cin >> A[i];
    for(int i=1; i<=m; i++){
        cin >> B[i].first;
        B[i].second = i;
    }

    sort(B + 1, B + 1 + m);
    for(int i=1; i<=m; i++){
        bit[i][B[i].second] = 1;
        bit[i] |= bit[i-1];
    }

    int ans = 0;
    for(int i=1; i<=n; i++){
        int pos = upper_bound(B + 1, B + 1 + m, make_pair(A[i], inf)) - B - 1;
        res[0] = 1;
        res = (res<<1) & bit[pos];
        if(res[m] == 1) ans++;
    }
    cout << ans << '\n';
}
  
signed main(){
    Android;
    solve();
}
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

# A: All with Pairs KMP理解

这题比较考验对Kmp的理解

由于后缀的数量不会超过∑∣si∣\sum\mid s_i\mid，因此可以把所有后缀的hash值计算出来。（也有些许麻烦）

接着，枚举每个串sis_i，统计其每一个前缀的出现次数cnt[j]cnt[j]。

此时的cntcnt数组并非最终答案：假设串s="aba"s="aba"，另一个串t="aba"t="aba"。ss的前缀(a),(aba)(a),(aba)分别会对cnt[0],cnt[2]cnt[0],cnt[2]产生1个单位的贡献，但只有前缀(aba)(aba)是合法的，因此要去掉(a)(a)的贡献。

根据题意，我们可以把每个串的failfail指针算出来，sijs_{ij}的failfail指针指向的位置便是被重复计算了的长度

#include <bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define Android ios::sync_with_stdio(false), cin.tie(NULL)
using namespace std;

const int maxn = 1e5 + 1000;
const ull base = 131;
const ll mod = 998244353;
 
ll cnt[(int)(1e6 + 100)];
int fail[(int)(1e6 + 100)];
ull pow_base[(int)(1e6 + 100)];
unordered_map<ull, ll> hsh;
string s[maxn];
int n;
 
void calc_fail(int x){
    string & str = s[x];
    int k = 0;
    fail[0] = fail[1] = 0;
    for(int i=1; i<str.size(); i++){
        while(k && str[k] != str[i]) k = fail[k];
        fail[i + 1] = (str[k]==str[i])?++k:0;
    }
}
 
void solve(){
    pow_base[0] = 1;
    for(int i=1; i<=1e6; i++) pow_base[i] = pow_base[i-1] * base;
 
    cin >> n;
    for(int i=0; i<n; i++) cin >> s[i];
    for(int i=0; i<n; i++){
        ull final_hsh = 0, cur = 0;
        for(int j=0; j<s[i].size(); j++)
            final_hsh = final_hsh * base + (s[i][j] - 'a' + 1);
        for(int j=0; j<s[i].size(); j++){
            ull h = final_hsh - cur * pow_base[s[i].size()-j];
            hsh[h]++;
            cur = cur * base + (s[i][j] - 'a' + 1);
        }
    }
 
    ll ans = 0;
    for(int i=0; i<n; i++){
        ull h = 0;
        calc_fail(i);
        for(int j=0; j<s[i].size(); j++){
            h = h * base + (s[i][j] - 'a' + 1);
            cnt[j] = hsh[h];
        }
        for(int j=1; j<=s[i].size(); j++){
            int nxt = fail[j];
            if(nxt > 0) cnt[nxt-1] -= cnt[j-1];
        }
        for(ll j=0; j<s[i].size(); j++)
            ans = (ans + (j + 1) * (j + 1) * cnt[j] % mod) % mod;
    }
    cout << ans << '\n';
}
 
signed main(){
    Android;
    solve();
}
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

# H: Happy Triangle 动态开点线段树/平衡树

对于操作3，如果存在可行方案，那么集合中一定存在可行方案(c,d)(d≥c)(c,d)(d\ge c)使得cc为dd的前驱。

因此只需要考虑相邻的两个数即可，对于相邻的数(a,b)(a≤b)(a,b)(a\le b)，只要满足b−a<x<a+bb-a\lt x\lt a+b，则方案(a,b)(a,b)对于查询xx可行。

可以使用平衡树来维护入点和出点，然而我选择逃课...

用动态开点线段树做本体，就要注意优化：

  1. 仍然使用前缀和来判断区间是否被覆盖，而不是无脑给区间所有数字加1
  2. 在(1)的前提下，本题可以不使用lazy，减少内存占用
#include <bits/stdc++.h>
#define ll long long
#define Android ios::sync_with_stdio(false), cin.tie(NULL)
using namespace std;

const int maxn = 2e5 + 2000;
const int maxr = 2e9 + 1;

struct nd{
    int val, lson, rson;
}nodes[50 * maxn];
int root, node_cnt;

void modify(int & rt, ll l, ll r, ll ql, ll qr, int val){
    if(ql > qr) return;
    if(rt == 0) rt = ++node_cnt;
    if(ql <= l && r <= qr){
        nodes[rt].val += val;
        return;
    }
    int mid = (l + r) >> 1;
    if(ql <= mid) modify(nodes[rt].lson, l, mid, ql, qr, val);
    if(qr > mid) modify(nodes[rt].rson, mid + 1, r, ql, qr, val);
}

int query(int & rt, ll l, ll r, ll pos){
    if(rt == 0) return 0;
    if(l == r) return nodes[rt].val;
    int mid = (l + r) >> 1;
    if(pos <= mid) return query(nodes[rt].lson, l, mid, pos) + nodes[rt].val;
    if(pos > mid) return query(nodes[rt].rson, mid + 1, r, pos) + nodes[rt].val;
    return 0;
}

multiset<int> ms;
int q;
void solve(){
    cin >> q;
    for(int i=0; i<q; i++){
        int op, x;
        cin >> op >> x;
        if(op == 1){
            auto ptr = ms.upper_bound(x);
            if(ptr != ms.begin()){
                auto pre = prev(ptr);
                if(ptr != ms.end()) modify(root, 1, maxr, *ptr - *pre + 1, *ptr + *pre - 1, -1);
                modify(root, 1, maxr, x - *pre + 1, x + *pre - 1, 1);
            }
            if(ptr != ms.end()){
                modify(root, 1, maxr, *ptr - x + 1, x + *ptr - 1, 1);
            }
            ms.insert(x);
        }
        if(op == 2){
            auto ptr = ms.find(x);
            ptr = ms.erase(ptr);
            if(ptr != ms.begin()){
                auto pre = prev(ptr);
                modify(root, 1, maxr, x - *pre + 1, x + *pre - 1, -1);
                if(ptr != ms.end()) modify(root, 1, maxr, *ptr - *pre + 1, *ptr + *pre - 1, 1);
            }
            if(ptr != ms.end()){
                modify(root, 1, maxr, *ptr - x + 1, x + *ptr - 1, -1);
            }
        }
        if(op == 3){
            cout << (query(root, 1, maxr, x)>0?"Yes":"No") << '\n';
        }
    }
}
  
signed main(){
    Android;
    solve();
}
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

# E/I/J/K

未补

上次更新: 2021/02/24, 03:37:30
训练补题-牛客训练赛10
训练补题-牛客训练赛3

← 训练补题-牛客训练赛3→

最近更新
01
深入理解Java虚拟机
 03-04
02
DNS工作原理
 02-27
03
改用VuePress啦
 02-23
更多文章>
Theme by Vdoing | Copyright © 2019-2021