Codeforce 789

A – Anastasia and pebbles

大水题

#include <iostream>
#include <cstdio>
#include <cstring>

#define loop(x) for(int _x=0;_x<x;_x++)

using namespace std;

int n, k;

int main() {
    cin >> n >> k;
    long long ans = 0, t;
    loop(n) {
        cin >> t;
        ans += t / k + (t % k != 0);
    }
    cout << ans / 2 + (ans % 2 != 0) << endl;
    return 0;
}

B – Masha and geometric depression

It could be better.

注意判断 q = -1, 0, 1 的情况

此题还有很多别的解法，这里先说三种。

using map to store BAD NUMBERS

using map to store POWER OF b1

verify EACH BAD NUMBERS

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <map>

using namespace std;


#define int long long
const int N = 110000;
int b, q, l, m;
map<int, bool> a;

int fp(int a, int n) {
    int r = 1;
    do {
        if (n & 1) {
            r *= a;
        }
        a *= a;
    } while (n >>= 1);
    return r;
}

#undef int
int main() {
#define int long long
    cin >> b >> q >> l >> m;
    for (int i = 0, t; i < m; i++) {
        cin >> t;
        a[t] = 1;
    }
//check inf
    if (abs(b) > l) {
        cout << 0 << endl;
        return 0;
    }
    if (b == 0) {
        if (a[b]) {
            cout << 0 << endl;
            return 0;
        }
        cout << "inf" << endl;
        return 0;
    }
    if (q == 1) {
        if (a[b]) {
            cout << 0 << endl;
            return 0;
        }
        cout << "inf" << endl;
        return 0;
    }
    if (q == 0) {
        bool fa, fb;
        fa = a[0];
        fb = a[b];
        if (!fa && !fb) {
            cout << "inf" << endl;
            return 0;
        }
        if (fa && !fb) {
            cout << 1 << endl;
            return 0;
        }
        if (!fa && fb) {
            cout << "inf" << endl;
            return 0;
        }
        if (fa && fb) {
            cout << 0 << endl;
            return 0;
        }
        cout << "inf" << endl;
        return 0;
    }
    if (q == -1) {
        bool fa, fb;
        fa = a[b];
        fb = a[-b];
        if (fa && fb) {
            cout << 0 << endl;
            return 0;
        }
        cout << "inf" << endl;
        return 0;
    }
    int u, c;
    u = b;
    c = 0;
    while (1) {
        if (abs(u) > l) {
            cout << c << endl;
            break;
        }
        if (!a[u]) {
            c++;
        }
        u *= q;
    }
    return 0;
}

C – Functions again

可以有更好的写法。

因为答案只有两种情况：

1. 从正的开始，取连续区间最大值
2. 从负的开始，取连续区间最小值

然后求绝对值就可以了。

#include <iostream>
#include <cstdio>
#include <cstring>

using namespace std;

const int N = 110000;
int n, a[N], b[N], c[N];
long long d[N];

int main() {
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }
    for (int i = 1, z = 1, t; i < n; i++) {
        t = abs(a[i + 1] - a[i]);
        b[i] = z * t;
        c[i] = -z * t;
        z = -z;
    }
    long long ans, cur;
    cur = ans = 0;
    for (int i = 1; i <= n; i++) {
        ans += b[i];
        if (ans < 0) {
            ans = 0;
        }
        cur = max(cur, ans);
    }
    ans = 0;
    for (int i = 1; i <= n; i++) {
        ans += c[i];
        if (ans < 0) {
            ans = 0;
        }
        cur = max(cur, ans);
    }
    cout << cur << endl;
    return 0;
}

D – Weird journey

先咕一会

本作品使用基于以下许可授权：Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International License.