Codeforces Round #698 (Div. 2)

链接：Codeforces Round #698 (Div. 2)

A - Nezzar and Colorful Balls

思路：答案就是出现次数最多的数出现的次数

#include 
#include 
#include 
#include 

using namespace std;

typedef long long ll;

const int N = 110;

int T, n, c[N], a[N];

int main()
{
    // freopen("in.txt", "r", stdin);
    // freopen("out.txt", "w", stdout);
    scanf("%d", &T);
    while (T--) {
        scanf("%d", &n);
        for (int i = 1; i <= n; i++) c[i] = 0;
        int imax = 0;
        for (int i = 1; i <= n; i++) {
            scanf("%d", &a[i]);
            c[a[i]] += 1;
            imax = max(imax, c[a[i]]);
        }
        printf("%d\n", imax);
    }
    return 0;
}

B - Nezzar and Lucky Number

思路：很显然$x\geq 10*d$时，$x$可以表示为$x=(10*d+t)+d+d+\cdots$的形式，$0\leq t\leq 9$，显然$10*d+t$包含数字$d$，所以答案肯定是YES，当$x < 10*d$时，暴力即可

#include 
#include 
#include 
#include 

using namespace std;

typedef long long ll;

int T, q, d;

bool check(int x)
{
    for (int i = 1; i <= 10; i++) {
        if (i * d <= x && (i * d) % 10 == x % 10) return true;
    }
    return false;
}

int main()
{
    // freopen("in.txt", "r", stdin);
    // freopen("out.txt", "w", stdout);
    scanf("%d", &T);
    while (T--) {
        scanf("%d%d", &q, &d);
        for (int i = 1; i <= q; i++) {
            int x;
            scanf("%d", &x);
            if (x >= 10 * d || check(x)) printf("YES\n");
            else printf("NO\n");
        }
    }
    return 0;
}

C - Nezzar and Symmetric Array

思路：假设$a$数组中的正数为$a_{1}\ a_{2}\cdots a_{n}$，假设$a_{1}

$$d_{1}=2\sum_{1}^{n}a_{i}$$

$$d_{2}=2\sum_{1}^{n}a_{i}+2a_{2}-2a_{1}$$

$$d_{3}=2\sum_{1}^{n}a_{i}+4a_{3}-2a_{1}-2a_{2}$$

$$\vdots$$

$$d_{n}=2\sum_{1}^{n}+2(n-1)a_{n}-2a_{1}-2a_{2}\cdots -2a_{n-1}=2na_{n}$$

通过$d_{n}$求出$a_{n}$后，$d_{i}-d_{i-1}=2(i-1)a_{i}-2(i-1)a_{i-1}$，然后从后向前反推出$a$数组，最后判断$a[1]$是否大于0即可

#include 
#include 
#include 
#include 
#include 

using namespace std;

typedef long long ll;

const int N = 200010;

int T, n;
ll res[N];
vector alls;

int main()
{
    // freopen("in.txt", "r", stdin);
    // freopen("out.txt", "w", stdout);
    scanf("%d", &T);
    while (T--) {
        alls.clear();
        scanf("%d", &n);
        for (int i = 1; i <= 2 * n; i++) {
            ll x;
            scanf("%lld", &x);
            alls.push_back(x);
        }
        sort(alls.begin(), alls.end());
        alls.erase(unique(alls.begin(), alls.end()), alls.end());
        if (n != alls.size() || 0 != alls[n - 1] % (2 * n)) {
            printf("NO\n");
            continue;
        }
        res[n] = alls[n - 1] / (2 * n);
        int f = 1;
        for (int i = n - 1; i >= 1; i--) {
            ll d = alls[i] - alls[i - 1];
            if (0 == d || 0 != d % (2 * i)) f = 0;
            res[i] = res[i + 1] - d / (2 * i);
        }
        if (f && res[1] > 0) printf("YES\n");
        else printf("NO\n");
    }
    return 0;
}

D - Nezzar and Board

思路：选中的$x$、$y$的系数为1，组成的数$2x-y$的系数和也为1，所以无论怎么组合，最后组成成的数系数和一定为1，对于每一个组合成的数，都可以表示成$k=x_{1}(a_{2}-a_{1})+x_{2}(a_{3}-a_{1})+\cdots + x_{n-1}(a_{n}-a_{1})+a_{i}$，即

$$k-a_{i}=x_{1}(a_{2}-a_{1})+x_{2}(a_{3}-a_{1})+\cdots + x_{n-1}(a_{n}-a_{1})$$

根据裴蜀定理$O(n)$遍历$a_{i}$验证即可

#include 
#include 
#include 
#include 
#include 

using namespace std;

typedef long long ll;

const int N = 200010;

int T, n;
ll k, a[N];

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

int main()
{
    // freopen("in.txt", "r", stdin);
    // freopen("out.txt", "w", stdout);
    scanf("%d", &T);
    while (T--) {
        scanf("%d%lld", &n, &k);
        for (int i = 1; i <= n; i++) scanf("%lld", &a[i]);
        ll d = 0;
        for (int i = 2; i <= n; i++) d = gcd(d, abs(a[i] - a[1]));
        int f = 0;
        for (int i = 1; i <= n; i++)
            if (0 == (k - a[i]) % d) f = 1;
        printf(f ? "YES\n" : "NO\n");
    }
    return 0;
}