Codeforces Round #790 (Div. 4)

A. Lucky?

#include 
using namespace std;

const int N = 1e6 + 10;

string s;

signed main(){
    int n; cin >> n;
    while(n--)
    {
        cin >> s;
        int pre = 0, last = 0;
        for (int i = 0; i <= 2; i++)
        {
            pre += (s[i] - '0');
            last += (s[5 - i] - '0');
        }
        if (pre == last) puts("YES");
        else puts("NO");
    }
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

B. Equal Candies

#include 
using namespace std;

const int N = 60, inf = 0x3f3f3f3f;

int n, a[N];

void solve()
{
    cin >> n;
    int minn = inf;
    for (int i = 0; i < n; i++) 
    {
        cin >> a[i];
        if (a[i] < minn) minn = a[i];
    }
    int res = 0;
    for (int i = 0; i < n; i++)
    {
        res += (a[i] - minn);
    }
    cout << res << endl;
}
signed main(){
    int t; cin >> t; 
    while(t--) solve();
    return 0;
}
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

C. Most Similar Words

枚举所有可能的字符串对组合，按单个字符找到距离和最小的。

注意不要先把所有字符相加再求距离，因为是距离问题会涉及到绝对值问题，先相加再求距离中间的字符间的绝对值问题就被忽视掉了。

#include 
using namespace std;

const int inf = 0x3f3f3f3f, N = 60;

string s[N];
int n, m;

void solve()
{
    cin >> n >> m;
    int ans = inf;
    for (int i = 0; i < n; i++) cin >> s[i];
    for (int i = 0; i < n; i++)
        for (int j = i + 1; j < n; j++)//枚举所有字符串对
        {
            int res = 0;
            for (int k = 0; k < m; k++)//循环计算单个字符的距离并相加
                res += abs(s[i][k] - s[j][k]);
            ans = min(res, ans);
        }
    cout << ans << endl;  

}
signed main(){
    int t; cin >> t; 
    while(t--) solve();
    return 0;
}
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

D. X-Sum

暴力枚举每个点的$X\_Sum$

竟然被不会$X$遍历打败了TAT

#include 
using namespace std;

const int N = 210;

int g[N][N];
int n, m;

int cal(int x, int y)
{
    //cout << "cal\n";
    int sum = 0;
    for (int i = x, j = y; i && j; i--, j--) sum += g[i][j];
    for (int i = x + 1, j = y + 1; i <= n && j <= m; i++, j++) sum += g[i][j];
    for (int i = x + 1, j = y - 1; i <= n && j; i++, j--) sum += g[i][j];
    for (int i = x - 1, j = y + 1; i && j <= m; i--, j++) sum += g[i][j];
    //cout << "sum = " << sum << endl;
    return sum;
}
void solve()
{
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            cin >> g[i][j];
    int ans = 0;
    cout << "deb1\n";
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            ans = max(ans, cal(i, j));
    cout << ans << endl;
}
signed main(){
    int t; cin >> t;
    while(t--) solve();
    return 0;
}
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

E. Eating Queries

贪心 + 前缀和 + 二分

题意：用最少的数字凑给定的数，求最少需要几个数字才凑够给定的数，凑不够输出$-1$.

从大到小排序，肯定是优先用大数，给递增序列求前缀和，二分查找第一个大于等于给定数字的位置。

注意二分前缀和的时候弄清首尾地址

#include 
using namespace std;

const int N = 150005;

int n, q;
int a[N];
int s[N];

bool cmp(int a, int b) { return a > b; }

void solve()
{
    cin >> n >> q;
    for (int i = 1; i <= n; i++) cin >> a[i];
    sort(a + 1, a + n + 1, cmp);
    for (int i = 1; i <= n; i++) s[i] = s[i - 1] + a[i];//前缀和有效的首地址为s + 1
    int x;
    while(q--)
    {
        cin >> x;
        int pos = lower_bound(s + 1, s + n + 1, x) - s; //因为题目的首地址从1开始，所以这里 -s 而不是 -(s + 1)
        cout << (pos <= n ? pos : -1) << endl;//如果前缀和数组没找到会返回末尾位置，那么pos=n+1,
    }
}
signed main(){
    int t; cin >> t;
    while(t--) solve();
    return 0;
}
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

F. Longest Strike

map + 双指针

这道题目绕的我有点晕@.@

这道题目感觉有点反常规，这里的区间和一般的区间不太一样，是在完整的序列中找到能凑出至少$k$个相同的数的连续的子序列，这道题目的不同之处就在于不是从某一规定区间内寻找，而且这些数字不需要位置相邻，位置是任意的，只要能在这个完整的序列中找到就可。这样的话，就和序列的内部排列无关，我们就可以放心的对序列内的元素进行排序等操作。

在这里我们用$map$能同时对序列进行从小到大排序和统计权值（某个数的个数），把满足规定最小权值的数字$push\_back$进$vector$。

再对$vector$的序列进行统计最长连续序列，记录左右端点。

#include 
using namespace std;

const int N = 2e5 + 10;

int n, k;

void solve()
{
    cin >> n >> k;
    map<int, int>mp;
    int a;
    for (int i = 0; i < n; i++) cin >> a, mp[a]++;
    vector<int>ve;//*存储满足连续个数K的数值
    for (auto t : mp)
        if (t.second >= k) ve.push_back(t.first); 
    if (!ve.size()) 
    {
        puts("-1");
        return;
    }
    int len = ve.size();
    int l = ve[0], r = ve[0];
    int lans = ve[0], rans = ve[0], mxl = 0;
    // for (int i = 0, j = len - 1; i < j && l < r; i++, j--)
    // {   
    //     int lv = ve[i], rv = ve[j];
    //     if (lv + 1 != ve[i + 1]) l = ve[i + 1];
    //     if (rv - 1 != ve[j - 1]) r = ve[j - 1];
    // }
    for (int i = 1; i < len; i++)
    {
        if (ve[i - 1] + 1 == ve[i])//*右比左大1，符合条件
        {
            if (ve[i] - l > mxl)//*此时长度更长，更新
            {
                lans = l, rans = ve[i], mxl = ve[i] - l;//*更新左边界，右边界，区间长度
            }
        }
        else l = ve[i];//*不符合条件，左边界右移
    }
    cout << lans << ' ' << rans << endl;
}
signed main(){
    int t; cin >> t;
    while(t--) solve();    
    return 0;
}
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

G. White-Black Balanced Subtrees

DFS + 树形DP

#include 
using namespace std;

const int N = 8010;

string s;
int h[N], e[N], ne[N], idx;
int f[N][3]; 
int n;
int st[N];
void add(int a, int b)
{
    e[idx] = b, ne[idx] = h[a], h[a] = idx++; 
}

void dfs(int u)
{
    if (st[u]) return;
    //st[u] = 1;//不会重复遍历到同一个点所以不需要标记，因为边都是单向的而且是循环遍历
    if (s[u] == 'W') f[u][0]++;
    else f[u][1] ++;
    for (int i = h[u]; ~i; i = ne[i])
    {
        int j = e[i];
        dfs(j);
        f[u][0] += f[j][0], f[u][1] += f[j][1]; 
    }
}

void solve()
{
    memset(h, -1, sizeof h);
    memset(f, 0, sizeof f);
    idx = 0;//*here 
    cin >> n;
    for (int i = 2; i <= n; i++) 
    {
        int a; cin >> a;
        add(a, i);//*add edge(a->i)
    }
    cin >> s;
    s = " " + s;//*下标可以从1开始，方便书写
    dfs(1);
    int cnt = 0;
    for (int i = 1; i <= n; i++)
        if (f[i][0] == f[i][1]) cnt++;  
    cout << cnt << endl;
}
signed main(){
    int t; cin >> t;
    while(t--) solve();
    return 0;
}
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

研究别人的代码，看了好久才看懂，最终才意识到被骗了TAT

别人建的双向边，但其实根本没必要，只需要建从父节点指向子节点的边就行，$DFS$的时候能保证只从开始节点向子节点搜索。

而让我灰常之疑惑的就是见了双向边怎样防止从这一节点向父节点搜索，离大谱！

代码如下，处理方式可以学习一下：

#include 
using namespace std;

const int N = 8010;

string s;
int h[N], e[N], ne[N], idx;
int f[N][3]; 
int n;
int st[N];
void add(int a, int b)
{
    e[idx] = b, ne[idx] = h[a], h[a] = idx++; 
}

void dfs(int u, int p)
{
    if (s[u] == 'W') f[u][0] ++;
    else f[u][1] ++;
    //if (u == n) return;
    //if (ne[u] == -1) return ;
    for (int i = h[u]; ~i; i = ne[i])
    {
        int j = e[i];
        if (j == p) continue;
        dfs(j, u);
        f[u][0] += f[j][0], f[u][1] += f[j][1];
    }
}
//*标记数组不需要，因为每个点的下一次遍历都只有一条路或没有路（到达叶子节点）
// void dfs(int u)
// {
//     if (st[u]) return;
//     st[u] = 1;
//     if (s[u] == 'W') f[u][0]++;
//     else f[u][1] ++;
//     for (int i = h[u]; ~i; i = ne[i])
//     {
//         int j = e[i];
//         dfs(j);
//         st[j] = 0;
//         f[u][0] += f[j][0], f[u][1] += f[j][1];
        
//     }
// }
int nm = 0;
void solve()
{
    //cout << "case" << nm++ << endl;
    memset(h, -1, sizeof h);
    memset(f, 0, sizeof f);
    memset(st, 0, sizeof st);
    idx = 0;
    cin >> n;
    //cout << "cin n\n";

    for (int i = 2; i <= n; i++) 
    {
        int a; cin >> a;
        add(i, a);//add edge(i->a)
        add(a, i);//add edge(a->i)
    }
    // for (int i = 1; i <= n; i++)
    // {
    //     for (int j = h[i]; ~j; j = ne[j])
    //     {
    //         int u = e[j];
    //         cout << u << ' ';
    //     }
    //     cout << endl;
    // }
    //cout << "cin a i\n";
    //getchar();
    cin >> s;
    //cout << "cin s\n";
    s = " " + s;//下标可以从1开始，方便书写
    dfs(1, -1);
    //dfs(1);
    int cnt = 0;
    //for (int i = 1; i <= n; i++) dfs(i);
    
    for (int i = 1; i <= n; i++)
    {
        //printf("f[%d][0] = %d, f[%d][1] = %d\n", i, f[i][0], i, f[i][1]);
        if (f[i][0] == f[i][1]) cnt++;
    }   
    cout << cnt << endl;
}
signed main(){
    int t; cin >> t;
    while(t--) solve();
    return 0;
}
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

H1. Maximum Crossings (Easy Version)

暴力枚举

找逆序对，数据量较小，两层循环暴力枚举，注意这里的”逆序对“是$i<j,a[i]\ge a[j]$，因为每个下标对应的不是一个点而是一段长度了。

#include 
using namespace std;

const int N = 1010;

int a[N];
int n;

void solve()
{
    cin >> n;
    for (int i = 0; i < n; i++) cin >> a[i];
    int rev = 0;
    for (int i = 0; i < n; i++)
        for (int j = i + 1; j < n; j++)//这样枚举能确保i
            if (a[i] >= a[j]) rev++;
    cout << rev << endl;
}
signed main(){
    int t; cin >> t;
    while(t--) solve();
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

H2. Maximum Crossings (Hard Version)

线段树 $or$ 树状数组

为什么可以用这两个数据结构解决？

准确地说这里的线段树是权值线段树，存储该节点的下标的数字的个数。

查询区间$[a[i],n]$的结果就是与$a[i]$组成的逆序对，所以至关重要的一点就是，先查询再加入节点，这样的话就能保证我们查询的时候查到的数的下标都是在我们当前查询的这个数的前面的，也就是满足$i<j$，但$a[i]\ge a[j]$。

#include 
using namespace std;
#define int long long
#define lowbit(x) x & -x
const int N = 2e5 +10;

int a[N], n;

// struct node
// {
//     int l, r;
//     int s; //*相当于权值线段树，或者说桶，也就是记录这个位置数字的个数
// }tr[N << 2];


// void pushup(int u)
// {
//     tr[u].s = tr[u << 1].s + tr[u << 1 | 1].s;
// }
// void build(int u, int l, int r)
// {
//     tr[u] = {l, r};
//     if (l == r) //*
//     {
//         tr[u].s = 0;
//         return ;
//     }
//     int mid = l + r >> 1;
//     build(u << 1, l, mid), build(u << 1 | 1, mid + 1, r);
//     pushup(u);
// }

// void update(int u, int x, int v)
// {
//     if (tr[u].l == x && tr[u].r == x) tr[u].s += v;
//     else 
//     {
//         int mid = tr[u].l + tr[u].r >> 1;
//         if (mid >= x) update(u << 1, x, v);
//         else update(u << 1 | 1, x, v);
//         pushup(u);//*这里是从子节点向父节点操作
//     }
//     //*如果放到这里就对叶子节点的子节点操作了，会造成数组越界错误
// }

// int query(int u, int l, int r)
// {
//     if (tr[u].l >= l && tr[u].r <= r) return tr[u].s;
//     int mid = tr[u].l + tr[u].r >> 1;
//     int ans = 0;
//     if (mid >= l) ans += query(u << 1, l, r);
//     if (mid < r) ans += query(u << 1 | 1, l, r);
//     return ans;
// }
int bt[N];

int sum(int x)
{
    int res = 0;
    while(x)
    {
        res += bt[x];
        x -= lowbit(x);
    }
    return res;
}
void add(int x, int v)
{
    while(x <= n)
    {
        bt[x] += v;
        x += lowbit(x);
    }
}
int query(int l, int r)//求区间的和
{
    return sum(r) - sum(l - 1);
}
void solve()
{
    memset(bt, 0, sizeof bt);//每次将树状数组清空
    cin >> n;
    //build(1, 1, n);
    for (int i = 1; i <= n; i++) cin>> a[i];
    int ans = 0;
    // for (int i = 1; i <= n; i++)
    // {
   	//注意要先 查找 再 更新（加点）
    //     ans += query(1, a[i], n);//相当于是查询后缀和
    //     update(1, a[i], 1);
    // }
    for (int i = 1; i <= n; i++)
    {
        ans += query(a[i], n);//相当于是查询后缀和，(n-(a[i]-1))
        add(a[i], 1);
    }
    // for(int i=n; i>=1; --i)//先查询的是下标大的，也就是说要找的是比这个数小的，刚好用前缀和
    //             {
    //                     ans += sum(a[i]);
    //                     add(a[i], 1);
    //             }
    cout << ans << endl;
}
signed main(){
    ios_base::sync_with_stdio(0), cin.tie(0);
    int t; cin >> t;
    while(t--) solve();
    return 0;
}
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

这道题目用树状数组时间比线段树快不少！