devbox
小丑西瓜9
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

Codeforces Round #698 (Div.2) A,B,C,D,E_codeforces round #698 (div. 2)

作者：小丑西瓜9 | 2024-02-10 20:54:35

赞

踩

codeforces round #698 (div. 2)

Codeforces Round #698 Div.2 A,B,C,D

A - Nezzar and Colorful Balls

输出序列中出现最多次数的个数。

Code

#include "bits/stdc++.h"
using namespace std;

map<int, int> mp;

void solve() {
    int _; cin >> _;
    while(_--) {
        int n; cin >> n;
        mp.clear();
        int ans = -1;
        for(int i = 1;i <= n; i++) {
            int x; cin >> x;
            mp[x]++;
            ans = max(ans, mp[x]);
        }
        cout << ans << endl;
    }
}
signed main() {
    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

B - Nezzar and Lucky Number

题意：有一个luck数d，问能不能将一个x拆成任意多个数之和，并且每个数之中都要有一个d？

思路：
首先盲猜写 x > d ∗ 10 x>d*10 x>d∗10都是可以的，因为都可以拆成10个数，每个数无非多加了很多个10而已。
所以打表 d ∗ 10 d*10 d∗10之内的数即可，只需要判断尾部，尾部对了，并且小于x，无非就多加几个10而已。

Code

#include "bits/stdc++.h"
using namespace std;

void solve() {
    int _; cin >> _;
    while(_--) {
        int q, d; cin >> q >> d;
        for(int i = 1;i <= q; i++) {
            int x; cin >> x;
            bool flag = false;
            if(x >= d * 10) flag = true;
            for(int j = 1;j <= 10; j++) {
                int t = j * d;
                if(t <= x && (t % 10 == x % 10)) {
                    flag = true;
                    break;
                }
            }
            cout << (flag ? "YES" : "NO") << endl;
        }
    }
}

signed main() {
    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

C - Nezzar and Symmetric Array

题意:给有 2 ∗ n 2*n 2∗n个数字的数组d，问能不能构造出一组“对称数组”（有一个整数a，必然有一个负数-a，0不行），并且一个数和其他所有数之差的绝对值之和都能在原数组找到。即 ∑ j = 1 n ∣ a i − a j ∣ = d 某 个 数 \sum_{j=1}^n|a_i-a_j|=d_{某个数} ∑j=1n​∣ai​−aj​∣=d某个数​。

思路：
因为是对称数组，所以原数组中的数必须有不同的n个偶数，奇数是不行的，因为 ∑ j = 1 n ∣ a i − a j ∣ \sum_{j=1}^n|a_i-a_j| ∑j=1n​∣ai​−aj​∣得出来一定是个偶数。

加入我们设要构造的数组为 a 1 , a 2 . . . a n , − a 1 , − a 2 . . . − a n a_1,a_2...a_n,-a_1,-a_2...-a_n a1​,a2​...an​,−a1​,−a2​...−an​，所以 ∑ j = 1 n ∣ a i − a j ∣ \sum_{j=1}^n|a_i-a_j| ∑j=1n​∣ai​−aj​∣最小的数为 2 ( a 1 + a 2 + . . . + a n ) 2(a_1+a_2+...+a_n) 2(a1​+a2​+...+an​)，这就是为什么一定要是偶数了，方便起见，将d数组每个数都除2判断一下，设 a 1 + a 2 + . . . + a n = s u m a_1+a_2+...+a_n=sum a1​+a2​+...+an​=sum那么我们可以得到所有的数：
(将d数组从小到大排序)

  • 第 一 小 ： s u m = d [ 1 ] 第一小：sum=d[1] 第一小：sum=d[1]
  • 第 二 小 ： s u m + a 2 − a 1 = d [ 2 ] 第二小：sum+a_2-a_1=d[2] 第二小：sum+a2​−a1​=d[2]
  • 第 三 小 : s u m + a 3 − a 2 + a 3 − a 1 = d [ 3 ] 第三小:sum+a_3-a_2+a_3-a_1=d[3] 第三小:sum+a3​−a2​+a3​−a1​=d[3]

这样我们是看不出来什么样的，前后做一个差分可以得到：

s u m = d [ 1 ] sum=d[1] sum=d[1]
a 2 − a 1 = d [ 2 ] − d [ 1 ] a_2-a_1=d[2]-d[1] a2​−a1​=d[2]−d[1]
2 ( a 3 − a 2 ) = d [ 3 ] − d [ 2 ] 2(a_3-a_2)=d[3]-d[2] 2(a3​−a2​)=d[3]−d[2]
3 ( a 4 − a 3 ) = d [ 4 ] − d [ 3 ] 3(a_4-a_3)=d[4]-d[3] 3(a4​−a3​)=d[4]−d[3]
…
( n − 1 ) ( a n − a n − 1 ) = d [ n ] − d [ n − 1 ] (n-1)(a_n-a_{n-1})=d[n]-d[n-1] (n−1)(an​−an−1​)=d[n]−d[n−1]

我们可以解这n个方程，得到a数组的n个正数，但不不好解它，我们先假设 a 1 = 1 ( 不 能 等 于 0 ， 对 称 数 组 ， 0 是 不 允 许 的 ) a_1=1(不能等于0，对称数组，0是不允许的) a1​=1(不能等于0，对称数组，0是不允许的)，然后解出所有的 a i a_i ai​，最后算出 s u m sum sum是 a 1 + . . . + a n a_1+...+a_n a1​+...+an​。

a 2 = d [ 2 ] − d [ 1 ] + a 1 a_2=d[2]-d[1]+a_1 a2​=d[2]−d[1]+a1​
a 3 = d [ 3 ] − d [ 2 ] 2 + a 2 a_3=\frac{d[3]-d[2]}{2}+a_2 a3​=2d[3]−d[2]​+a2​
a 4 = d [ 4 ] − d [ 3 ] 3 + a 3 a_4=\frac{d[4]-d[3]}{3}+a_3 a4​=3d[4]−d[3]​+a3​
…
a n = d [ n ] − d [ n − 1 ] n − 1 + a n − 1 a_n=\frac{d[n]-d[n-1]}{n-1}+a_{n-1} an​=n−1d[n]−d[n−1]​+an−1​

如何判断YES还是NO呢？

我们发现， a 1 a_1 a1​每+1都会使所有数+1，即sum加了n，所以我们判断如果 s u m < = d [ 1 ] ， 并 且 ( d [ 1 ] − s u m ] % n ) = = 0 ， 输 出 Y E S ， 反 之 N O 。 sum<=d[1]，并且(d[1]-sum]\%n)==0，输出YES，反之NO。 sum<=d[1]，并且(d[1]−sum]%n)==0，输出YES，反之NO。

Code

#include "bits/stdc++.h"
using namespace std;

typedef long long ll;

void solve() {
    int _; cin >> _;
    while(_--) {
        int n; cin >> n;
        vector<ll>v(n * 2);
        bool flag = true;
        for(int i = 0;i < n * 2; i++) {
            cin >> v[i];
            if(v[i] & 1) flag = false;
            else v[i] /= 2;
        }
        if(!flag) {
            cout << "NO" << endl;
            continue;
        }
        sort(v.begin(), v.end());
        v.erase(unique(v.begin(), v.end()), v.end());
        if(v.size() != n) {
            cout << "NO" << endl;
            continue;
        }
        ll t = 1;
        ll sum = t;
        for(int i = 1;i < n; i++) {
            if((v[i] - v[i - 1]) % i == 0) {
                ll a = (v[i] - v[i - 1]) / i + t;
                sum += a;
                t = a;
            }
            else {
                flag = false;
                break;
            }
        }
        if(flag && (sum <= v[0] && (v[0] - sum) % n == 0)) {
            cout << "YES" << endl;
        }
        else {
            cout << "NO" << endl;
        }
    }
}

signed main() {
    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

D - Nezzar and Board

题意：给n个数 x 1 , x 2 . . . x n x_1,x_2...x_n x1​,x2​...xn​，从中选择两个数x和y，将 2 ∗ x − y 2*x-y 2∗x−y放入数组中，可以操作多次，问能不能得到一个k。

思路：
2 ∗ x − y = x + x − y 2*x-y=x+x-y 2∗x−y=x+x−y，因为两个数一直辗转相减是可以得到这两个数的最大公因数，所以两个数的差即为最大公因数的倍数，所以为了每个数都可以被用到，我们先求出 n − 1 n-1 n−1个差的 g c d gcd gcd，这样我们可以得到任意多个 g c d gcd gcd的和，然后还剩下一个 x x x，就看看 k k k能不能等于 x i + 任 意 多 个 g c d x_i+任意多个gcd xi​+任意多个gcd，即判断 ( k − x i ) % g c d = = 0 (k-x_i)\%gcd==0 (k−xi​)%gcd==0。

Code

#include "bits/stdc++.h"
using namespace std;

typedef long long ll;


ll gcd(ll a, ll b) {
    return b ? gcd(b, a % b) : a;
}

void solve() {
    int _; cin >> _;
    while(_--) {
        int n;
        ll k;
        cin >> n >> k;
        vector<ll>v(n + 1);
        ll GCD;
        for(int i = 1;i <= n; i++) {
            cin >> v[i];
            if(i == 2) {
                GCD = v[i] - v[i - 1];
            }
            else {
                GCD = gcd(v[i] - v[i - 1], GCD);
            }
        }
        bool flag = false;
        for(int i = 1;i <= n; i++) {
            if((k - v[i]) % GCD == 0) {
                flag = true;
                break;
            }
        }
        cout << (flag ? "YES" : "NO") << endl;
    }
}

signed main() {
    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

E - Nezzar and Binary String

题意：给两个01串，问经过q天之后能不能把s1转化成s2，每一天给一个区间，可以将该区间严格小于一半的字符数变成另一种，最后，如果可以转化输出YES，反之NO。

思路：
从第一天开始，后面的操作是基于前面的，所以我们需要时间逆序。
每一次操作，会有三种情况：

  • 当前1的个数严格小于区间一半，将区间全部变成0
  • 当前0的个数严格小于区间一半，将区间全部变成1
  • 当前1和0的个数相同，直接输出NO

所以需要区间覆盖，想到区间问题，线段树是居家旅行的好东西。
直接用最简单的线段树模拟这个过程即可。

Code

#include "bits/stdc++.h"
using namespace std;

const int N = 1e6 + 10;
int n, q;
string s1, s2;

#define lc u << 1
#define rc u << 1 | 1
#define mid (t[u].l + t[u].r) / 2

struct Tree {
    int l, r;
    int sum;
    int tag;
}t[N << 1];

inline void push_up(int u) {
    t[u].sum = t[lc].sum + t[rc].sum;
}

inline void push_down(int u) {
    if(t[u].tag == -1) return ;
    t[lc].sum = t[u].tag * (t[lc].r - t[lc].l + 1);
    t[rc].sum = t[u].tag * (t[rc].r - t[rc].l + 1);
    t[lc].tag = t[u].tag;
    t[rc].tag = t[u].tag;
    t[u].tag = -1;
}

void build(int u, int l, int r) {
    t[u].l = l; t[u].r = r;
    t[u].sum = 0;
    t[u].tag = -1;
    if(l == r) {
        t[u].sum = s2[l - 1] - '0';
        return ;
    }
    int m = (l + r) >> 1;
    build(lc, l, m);
    build(rc, m + 1, r);
    push_up(u);
}

void modify(int u, int ql, int qr, int v) {
    if(ql <= t[u].l && t[u].r <= qr) {
        t[u].sum = v * (t[u].r - t[u].l + 1);
        t[u].tag = v;
        return ;
    }
    push_down(u);
    if(ql <= mid) modify(lc, ql, qr, v);
    if(qr > mid)  modify(rc, ql, qr, v);
    push_up(u);
}

int query(int u, int ql, int qr) {
    if(ql <= t[u].l && t[u].r <= qr) {
        return t[u].sum;
    }
    push_down(u);
    int ans = 0;
    if(ql <= mid) ans += query(lc, ql, qr);
    if(qr > mid)  ans += query(rc, ql, qr);
    return ans ;
}

void solve() {
    int _; cin >> _;
    while(_--) {
        cin >> n >> q;
        cin >> s1 >> s2;
        build(1, 1, n);
        vector<int> l(q + 1), r(q + 1);
        for(int i = 1;i <= q; i++) {
            cin >> l[i] >> r[i];
        }
        bool flag = true;
        for(int i = q;i >= 1; i--) {
            int len = r[i] - l[i] + 1;
            int v = query(1, l[i], r[i]);
            if(v * 2 < len) modify(1, l[i], r[i], 0);
            else if(v * 2 > len) modify(1, l[i], r[i], 1);
            else {
                flag = false;
                break;
            }
        }

        for(int i = 1;i <= n; i++) {
            if(query(1, i, i) != s1[i - 1] - '0') {
                flag = false;
                break;
            }
        }

        cout << (flag ? "YES" : "NO") << endl;
    }
}

signed main() {
    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
  • 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
声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/小丑西瓜9/article/detail/75405
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号