Codeforces Round #698 (Div. 2)部分題解（A,B,C,D）-有解無憂

oj: CodeForces

敘述采用倒敘，

D. Nezzar and Board

oj: CodeForces

題意

現有 n n n 個不同的數字組成的陣列 a a a 和一個整數 k k k，你可以執行一下操作任意次：

選擇兩個任意的數字 x x x 和 y y y，然后把 2 x ? y 2x-y 2x?y 加入陣列a，

問你能否通過有限次的操作使得 k k k 被包含在陣列 a a a 里，

題解

我們推理一下這個操作的本質，

2 x ? y 2x-y 2x?y 其實就是 x + x ? y x+x-y x+x?y，也就是 x x x 加上 x x x 和 y y y 的差值，這個差值可以是正的也可以是負的，執行完之后我們可以對新的數字繼續增加這個差值，所以我們就可以根據兩個數字得出一個等引數列，數列內的數字都可以倍包含在陣列 a a a 里，

難點在于選擇不同的數字可以得出不同的等引數列，這些數列中我們可能可以選擇兩個相距更近的數得出一個更小的差值，進而得到一個更密集的數列，

其實這個問題也不難想，當兩個等引數列放到一起時，它們的元素之間相距的最近距離就是兩個數列的差值的最大公因數，

假設 a a a 陣列是2,6,12

從陣列 a a a 中選出 x = 2 , y = 6 x=2,y=6 x=2,y=6，我們可以遞推得到 2,6,10,14 等等，這個數列的公差是4，

然后再選出 x = 6 , y = 12 x=6,y=12 x=6,y=12，我們可以遞推得到0,6,12,18等等，這個數列的公差是6，

把這兩個數列合并，然后找到兩個相距最近的點，可以發現2和0，或者10和12，或者12和14，總之此時最近的距離是2，剛好是兩個公差的最大公因數gcd(4,6)，我們就可以利用這個最近距離來構造更緊密的等引數列，比如從新的陣列 a a a 中選出 x = 0 , y = 2 x=0,y=2 x=0,y=2，就可以構造出0,2,4,6了，

倘若 k k k 等于4，那么在得到2這個公差之前是沒辦法直接得到4的，現在通過公差2可以由2（原 a a a 陣列中的2）+2（公差）=4獲得，

而我們的目的是找出一個最小的差值 d d d，然后分別比對每一個 a i a_i ai? 看是否可以由 a i a_i ai? 和若干個 d d d 得到 k k k，

也不難想，只需要先對 a a a 陣列排個序，然后對所有的 a i ? a i ? 1 a_i-a_{i-1} ai??ai?1? 求最大公因數，就得出了那個最小的差值 d d d，

代碼

#include <bits/stdc++.h>
#define _for(i, a) for(int i = 0, lennn = (a); i < lennn; ++i)
#define _rep(i, a, b) for(int i = (a), lennn = (b); i <= lennn; ++i)
using namespace std;
typedef long long LL;
const int maxn = 200005;

inline LL read() {
    LL x(0), f(1); char ch(getchar());
    while (ch<'0' || ch>'9') { if (ch == '-') f = -1; ch = getchar(); }
    while (ch >= '0'&&ch <= '9') { x = x * 10 + ch - '0'; ch = getchar(); }
    return x * f;
}

int n;
LL a[maxn], k;

int sol() {
    _for(i, n) a[i] = read();
    sort(a, a + n);
    LL gc = a[1] - a[0];
    for(int i = 2; i < n; ++i) {
        gc = __gcd(gc, a[i] - a[i - 1]);
    }
    _for(i, n) if(abs(k - a[i]) % gc == 0) return 1;
    return 0;
}

int main() {
    int T = read();
    _for(i, T) {
        n = read(), k = read();
        printf("%s\n", sol() ? "YES":"NO");
    }
    return 0;
}

C. Nezzar and Symmetric Array

oj: CodeForces

題意

a a a 陣列是一個由 2 n 2n 2n 個互不相同的整陣列成的陣列，且每個 a i a_i ai? 都能找到一個 a j a_j aj? 滿足 a i = ? a j a_i=-a_j ai?=?aj?， d d d 陣列是 d i = ∑ j = 1 2 n ∣ a i ? a j ∣ d_i=∑^{2n}_{j=1}|a_i?a_j| di?=∑j=12n?∣ai??aj?∣，

給出一組 d d d，問是否可以構造出一組合法的 a a a 陣列，

題解

首先對 d d d 陣列排序，然后檢查是否每個數字都出現偶數次，因為 a a a 陣列是對稱出現的，所以 d d d 陣列也應該是對稱出現的，之后我們每隔一位元素取出一個數字，這樣就取出n個數字組成新的 d d d 陣列，

假設有這樣一組 a a a：

那么 a 0 a_0 a0? 對應的 d 0 d_0 d0? 其實就是 ∑ i = 1 n ∣ a i ∣ \sum_{i=1}^{n}{|a_i|} ∑i=1n?∣ai?∣，

而 a 1 a_1 a1? 對應的 d 1 d_1 d1? 就有意思了，我們可以借 d 1 ? d 0 d_1-d_0 d1??d0? 求出 a 1 ? a 0 a_1-a_0 a1??a0?，

對比 d 0 d_0 d0? 的圖，會發現其實 d 1 ? d 0 = 2 ( a 1 ? a 0 ) d_1-d_0=2(a_1-a_0) d1??d0?=2(a1??a0?)

同理可以發現 d 2 ? d 1 = 4 ( a 2 ? a 1 ) d_2-d_1=4(a_2-a_1) d2??d1?=4(a2??a1?)， d 3 ? d 2 = 6 ( a 3 ? a 2 ) d_3-d_2=6(a_3-a_2) d3??d2?=6(a3??a2?)，以此類推，

再配合上文高亮部分，假設 a 0 a_0 a0? 為 x x x，我們就可以列出一個 x x x 的方程，方程有解且解不為0（兩個0就相等了，而 a a a 陣列互不相等）就說明存在合法的 a a a，

x + x + d 1 ? d 0 2 + x + d 2 ? d 1 4 ? + x + d n ? 1 ? d n ? 2 2 ( n ? 1 ) = d 0 2 x+x+\frac{d_1-d_0}{2}+x+\frac{d_2-d_1}{4}\cdots +x+\frac{d_{n-1}-d{n-2}}{2(n-1)}=\frac{d_0}{2} x+x+2d1??d0??+x+4d2??d1???+x+2(n?1)dn?1??dn?2?=2d0??

感謝Tryna1大佬糾正錯誤

剩下的就是各種整除和不為0的判斷了，

代碼

#include <bits/stdc++.h>
#define _for(i, a) for(LL i = 0, lennn = (a); i < lennn; ++i)
#define _rep(i, a, b) for(LL i = (a), lennn = (b); i <= lennn; ++i)
using namespace std;
typedef long long LL;
const LL maxn = 200005;

inline LL read() {
    LL x(0), f(1); char ch(getchar());
    while (ch<'0' || ch>'9') { if (ch == '-') f = -1; ch = getchar(); }
    while (ch >= '0'&&ch <= '9') { x = x * 10 + ch - '0'; ch = getchar(); }
    return x * f;
}

LL n;
LL a[maxn];
map< LL, LL > mp;

void init() {
    mp.clear();
}

LL che() {
    _for(i, n) if(!a[i]) return 0;
    _for(i, n) if(a[i] & 1) return 0;
    for(LL i = n - 1; i > 0; --i) {
        a[i] -= a[i - 1];
        if(a[i] == 0) return 0;
    }
    for(LL i = 1; i < n; ++i) if(a[i] % (i << 1)) return 0;
    LL sum = 0, tem = 0;
    for(LL i = 1; i < n; ++i) {
        tem += a[i] / (i << 1);
        sum += tem;
    }
    LL t = a[0] / 2 - sum;
    if(t <= 0) return 0;
    return t % n == 0;
}

LL che2() {
    _for(i, n) {
        if(mp[a[i]]) --mp[a[i]];
        else ++mp[a[i]];
    }
    for(auto i : mp) {
        if(i.second) return 0;
    }
    return 1;
}

void sol() {
    init();
    n <<= 1;
    _for(i, n) a[i] = read();
    sort(a, a + n);
    if(!che2()) printf("NO\n");
    else {
        n >>= 1;
        _for(i, n) a[i] = a[i << 1];
        printf("%s\n", che() ? "YES":"NO");
    }
}

int main() {
#ifndef ONLINE_JUDGE
    freopen("in.txt", "r", stdin);
#endif
    LL T = read();
    _for(i, T) {
        n = read();
        sol();
    }
    return 0;
}

B. Nezzar and Lucky Number

oj: CodeForces

題意

給你一個 d d d， q q q 次詢問一個數字 a a a 是否可以由若干個數字相加得到且這些數字的數位中都含有 d d d 這個數字，

題解

當 a < 10 d a<10d a<10d 時，假設 a a a 的個位數字是 x x x，那么需要找到一個最小的個數 n n n 使得 n d ≡ x ( m o d 10 ) nd\equiv x(mod\ 10) nd≡x(mod 10) 如果這時 a ≥ n d a\ge nd a≥nd，那么我們就可以構造一組 d , d , ? ? , d ? n ? 1 , a ? ( n ? 1 ) d \underbrace{ d,d,\cdots,d }_{n-1},a-(n-1)d n?1 d,d,?,d??,a?(n?1)d，其中所有的數字的個位數字都是 d d d，那么我們只需要檢查是否可以找到一個 n n n 使得 n d ≡ x ( m o d 10 ) nd\equiv x(mod\ 10) nd≡x(mod 10) 同時 a ≥ n d a\ge nd a≥nd，

當 10 d ≤ a < 20 d 10d\le a< 20d 10d≤a<20d 時，找到一個 x x x 滿足 a ? 10 d ? x ≡ 0 ( m o d d ) a-10d-x\equiv 0(mod\ d) a?10d?x≡0(mod d)， x x x 可以取 0 0 0，那么就相當于構造了一組 10 d + x , d , d , ? ? , d ? a ? 10 d ? x d 10d+x,\underbrace{ d,d,\cdots,d }_{\frac{a-10d-x}{d}} 10d+x,da?10d?x? d,d,?,d??，其中第一個數字的十位是 d d d，其余數字的個位都是 d d d，也就是說當 10 d ≤ a < 20 d 10d\le a< 20d 10d≤a<20d 時都可以構造出一組合法的解，

當 a ≥ 20 d a\ge 20d a≥20d 時我們先讓 a a a 減去若干個 10 d 10d 10d，使得 a a a 滿足 10 d ≤ a < 20 d 10d\le a< 20d 10d≤a<20d，那么問題就回到了情況2，所以此時也是都有解的，

代碼

#include <bits/stdc++.h>
#define _for(i, a) for(int i = 0, lennn = (a); i < lennn; ++i)
#define _rep(i, a, b) for(int i = (a), lennn = (b); i <= lennn; ++i)
using namespace std;
typedef long long LL;
const int maxn = 100005;

inline int read() {
    int x(0), f(1); char ch(getchar());
    while (ch<'0' || ch>'9') { if (ch == '-') f = -1; ch = getchar(); }
    while (ch >= '0'&&ch <= '9') { x = x * 10 + ch - '0'; ch = getchar(); }
    return x * f;
}

int n;
LL d;

int che(LL x) {
    if(x >= d * 10) return 1;
    LL f = 0;
    _rep(i, 1, 9) if(i * d % 10 == x % 10) {
        f = i;
        break;
    }
    if(!f) return 0;
    return x >= f * d;
}

void sol() {
    _for(i, n) {
        LL x = read();
        printf("%s\n", che(x) ? "YES":"NO");
    }
}

int main() {
    int T = read();
    _for(i, T) {
        n = read(), d = read();
        sol();
    }
    return 0;
}

A. Nezzar and Colorful Balls

oj: CodeForces

題意

n個數字組成一個不嚴格的遞增序列，你需要給每個數字染色，以便所有顏色相同的數字的值都不一樣，求出最小的顏色數目，

題解

考慮出現次數最多的數字，由于需要給它們分配不同的顏色，所以出現的次數就是需要的顏色數目，

代碼

#include <bits/stdc++.h>
#define _for(i, a) for(int i = 0, lennn = (a); i < lennn; ++i)
#define _rep(i, a, b) for(int i = (a), lennn = (b); i <= lennn; ++i)
using namespace std;

inline int read() {
    int x(0), f(1); char ch(getchar());
    while (ch<'0' || ch>'9') { if (ch == '-') f = -1; ch = getchar(); }
    while (ch >= '0'&&ch <= '9') { x = x * 10 + ch - '0'; ch = getchar(); }
    return x * f;
}

int a[100005];
int n;

void sol() {
    _for(i, n) a[i] = read();
    int ans = 0, tem = 0;
    _for(i, n - 1) {
        if(a[i] == a[i + 1]) ++tem;
        else tem = 0;
        ans = max(ans, tem);
    }
    printf("%d\n", ans + 1);
}

int main() {
    int T = read();
    _for(i, T) {
        n = read();
        sol();
    }
    return 0;
}

轉載請註明出處，本文鏈接：https://www.uj5u.com/ruanti/254436.html

標籤：其他

上一篇：Codeforces Round #698 (Div. 2) 補題

下一篇：C語言位運算運算子及應用（騷操作）