Codeforces Round 929 (Div. 3)

Codeforces Round 929 (Div. 3)

A. Turtle Puzzle: Rearrange and Negate

题意：可以对整数数组进行两个操作，一是随意重新排列或保持不变，二是选择连续子段元素符号倒转，求可能最大的所有元素和。

思路：所有元素的绝对值和。

AC code：

void solve() {
    int sum = 0;
    cin >> n;
    for (int i = 0; i < n; i ++) {
        int x; cin >> x;
        sum += abs(x);
    }
    cout << sum << endl;
}

B. Turtle Math: Fast Three Task

题意：给出整数数组a，可以选择任意两种操作，一是选择一个元素从数组a中删除，二是选择一个元素数值增加1；最少需要多少次操作可以使得数组元素之和能被3整除。

思路：

• 元素和本来就能被3整除，0次操作；
• 元素和mod3=2，1次添加操作；
• 元素和mod3=1，若存在删除数组中的一个元素使得元素和被3整除，则1次操作，否则2次添加操作。

AC code：

void solve() {
    cin >> n;
    int sum = 0;
    for (int i = 0; i < n; i ++) {
        cin >> a[i];
        sum += a[i];
    }
    if (sum % 3 == 0) {
        cout << 0 << endl;
        return;
    }
    int u = sum % 3;
    if (u == 2) {
        cout << 1 << endl;
        return;
    }
    for (int i = 0; i < n; i ++) {
        if ((sum - a[i]) % 3 == 0) {
            cout << 1 << endl;
            return;
        }
    }
    cout << 2 << endl;
}

C. Turtle Fingers: Count the Values of k

题意：给出正整数a, b, l，若存在$k$, $x$, $y$ 使得$l=k\cdot a^x\cdot b^y$，则k有多少种不同的可能。

思路：暴力枚举x，y，注意处理枚举边界，即处理出x和y的最大可能再进行枚举。

AC code：

int tmp(int l, int t) {
    int pos = 0;
    while (l % t == 0) {
        l /= t;
        pos ++;
    }
    return pos;
}
 
void solve() {
    int a, b, l; cin >> a >> b >> l;
    int cnt = 0;
    map<int, int> mp;
    int A = tmp(l, a);
    int B = tmp(l, b);
    //cout << A << " " << B <<"+++" << endl;
    for (int i = 0; i <= A; i ++) {
        for (int j = 0; j <= B; j ++) {
            int t = pow(a, i) * pow(b, j);
            if (l % t == 0) {
                mp[l / t]++;
            }
        }
    }
    cout << mp.size() << endl;
}

D. Turtle Tenacity: Continual Mods

题意：给定正整数数组a，重排后得到数组b，是否可能存在$b_1\mathrm{mod}{b}_2\mathrm{mod}\dots \mathrm{mod}{b}_n\ne 0$.

思路：找出所有元素的最小公倍数gcd，若存在题述情况，则gcd出现次数一定小于2，否则mod过程中会出现0.

AC code：

int gcd(int a, int b) {
    if (b) while ((a%=b) && (b%=a));
    return a + b;
}
 
void solve() {
    cin >> n;
    int now = -1;
    for (int i = 1; i <= n; i ++) {
        cin >> a[i];
        if (now == -1) {
            now = a[i];
        } else {
            now = gcd(now, a[i]);
        }
    }
    int cnt = 0;
    for (int i = 1; i <= n; i ++) {
        if (a[i] == now) cnt ++;
    }
    if (cnt < 2) {
        cout << "YES" << endl;
    } else {
        cout << "NO" << endl;
    }
}

E. Turtle vs. Rabbit Race: Optimal Trainings

题意：有n条跑道，每条跑道有$a_i$个部分，给定一个正整数u，每完成一个部分成绩提高u，然后u-1，给出q组l和u，找出一个下标r，使得[l,r]的跑道成绩最高。

思路：二分找到最接近u的区间即可，注意二分的上边界和下边界都有可能成为答案，找到上下最接近u的边界，然后取其中离u最近的部分。

AC code：

void solve() {
    cin >> n;
    for (int i = 0; i <= n; i ++) {
        sum[i] = 0;
    }
    for (int i = 1; i <= n; i ++) {
        cin >> a[i];
        sum[i] = sum[i - 1] + a[i];
    }
    cin >> q;
    while (q --) {
        int l, u; cin >> l >> u;
        int L = l, R = n;
        while (L < R) {
            int mid = L + R + 1 >> 1;
            if (sum[mid] - sum[l - 1] <= u) L = mid;
            else R = mid - 1; 
        }
        int pos1 = L;
        L = l, R = n;
        while (L < R) {
            int mid = L + R >> 1;
            if (sum[mid] - sum[l - 1] >= u) R = mid;
            else L = mid + 1;
        }
        int pos2 = R;
        //cout << pos1 << " " << pos2 << "++++" << endl;
        int now1 = abs(sum[pos1] - sum[l - 1] - u), now2 = abs(sum[pos2] - sum[l - 1] - u);
        if (now1 >= now2) cout << pos2 << " ";
        else cout << pos1 << " "; 
    } cout << endl;
}