Codeforces Round #407 (Div. 2)

Codeforces Round #407 (Div. 2)#

A. Anastasia and pebbles#

Just take greedily.
The rule is that each pocket can only hold one type of pebble, and all the stones must be taken.
So just try to pack as much as possible.
In short, it's a greedy algorithm.

#include <cstdio>
#include <cstdlib>

using namespace std;

/*
 * 20/4=5..0
 * 13/4=3..1
 */
int main() {
//    freopen("input.txt", "r", stdin);
    int n, k;
    int a[100005];
    int cnt = 0;
    scanf("%d %d\n", &n, &k);
    for (int i = 0; i < n; i++) {
        scanf("%d", &a[i]);
    }
    for (int i = 0; i < n;) {
        if (a[i] <= 0) {
            i++;
            continue;
        }
        if (a[i] >= (k + k)) {
            cnt += a[i] / (k + k);
            a[i] %= (k + k);
        } else if (a[i] > k) {
            a[i]=0;
            cnt++;
        }else {
            cnt++;
            a[i]-=k;
            a[i+1]-=k;
        }
    }
    printf("%d\n", cnt);

}

B. Masha and geometric depression#

Simply use unordered_set and brute force simulation.
Remember that int may not be large enough.

#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <unordered_set>

using namespace std;

unordered_set<long long> s;

int main() {
//    freopen("input.txt", "r", stdin);
    long long b, q, l, m;
    scanf("%I64d%I64d%I64d%I64d", &b, &q, &l, &m);
    for (int i = 0; i < m; i++) {
        long long tmp;
        scanf("%I64d", &tmp);
        s.insert(tmp);
    }
    if (abs(b) > l) {
        printf("0\n");
        return 0;
    }
    if (b == 0) {
        if (s.find(0) != s.end()) {
            printf("0\n");
        } else {
            printf("inf\n");
        }
        return 0;
    }
    if (q == 0) {
        if (s.find(0) != s.end()) {
            if (s.find(b) != s.end())
                printf("0\n");
            else
                printf("1\n");
        } else {
            printf("inf\n");
        }
        return 0;
    }
    if (q == 1) {
        if (s.find(b) != s.end()) {
            printf("0\n");
        } else {
            printf("inf\n");
        }
        return 0;
    } else if (q == -1) {
        if (s.find(b) != s.end() && s.find(-b) != s.end()) {
            printf("0\n");
        } else {
            printf("inf\n");
        }
        return 0;
    }
    int cnt = 0;
    for (; abs(b) <= l; b *= q) {
        if (s.find(b) != s.end()) {
            continue;
        }
        cnt++;
    }
    printf("%d\n", cnt);

}

C. Functions again#

This problem should be considered a thinking problem.

First, preprocess the array to get a new array with the differences.

Then, convert the array to positive and negative alternately.

- - - - +

There are only these two types of arrays, and then find the maximum subsequence.

#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <unordered_set>

using namespace std;

int a[100009];
int s[100008];

int main() {
//    freopen("input.txt", "r", stdin);
    int n;
    scanf("%d", &n);
    for (int i = 0; i < n; i++) {
        scanf("%d", &a[i]);
    }
    for (int i = 0; i < n - 1; i++) {
        s[i] = abs(a[i] - a[i + 1]);
    }
    int f=1;
    long long res = 0, now = 0, now2 = 0;
    for (int i = 0; i < n - 1; i++) {
        int current = s[i] * f;
        int current2 = s[i] *(-f);
        now += current;
        now2 += current2;
        if (now < 0)
            now = 0;
        if(now2<0)
            now2=0;
        res = max(max(res, now), now2);
        f *= -1;
    }
    printf("%I64d\n", res);

}

D. Weird journey#

This problem is also a thinking problem + Euler circuit.
Going back and forth twice is equivalent to adding one edge to another.
We can know that:
An Euler circuit has only 0 or 2 vertices with odd degrees.

Deleting two edges with no common vertices = not an Euler circuit (because there are 4 vertices with odd degrees)
Deleting two edges with common vertices = an Euler circuit (because there are 2 vertices with odd degrees)
Deleting two self-loops = an Euler circuit (because there are 0 vertices with odd degrees)
Deleting one self-loop and any other edge = an Euler circuit (because there are 2 vertices with odd degrees)

This solves about half of the problem.

First, remember to check if the graph is connected using disjoint set.

Then, calculate the count.

For deleting two edges with common vertices, enumerate each vertex and take the permutation of its degree 2 (enumerate the sum of all degrees of edges).

For deleting two self-loops, it is the sum of all permutations of self-loops.

For deleting one self-loop and any other edge, it is the product of all self-loops and all edges (i.e., the permutation of self-loops and edges).

#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cstring>
#include <set>

typedef long long ll;

using namespace std;

struct edge {
    int x, y;
};

int deg[1000009] = {0};
edge edges[1000009];

int p[1000006];
int vis[1000006] = {0};
int n, m;

int getf(int x) {
    return x == p[x] ? x : (p[x] = getf(p[x]));
}

void _union(int x, int y) {
    x = getf(x), y = getf(y);
    p[x] = y;
}

bool connect() {
    for (int i = 0; i < n; i++) {
        p[i] = i;
    }
    for (int i = 0; i < m; i++) {
        _union(edges[i].x, edges[i].y);
    }
    set<int> bag;
    for (int i = 0; i < n; i++) {
        if (!vis[i])continue;
        bag.insert(getf(i));
    }
    return bag.size() <= 1;
}

ll loops = 0;

int main() {
//    freopen("input.txt", "r", stdin);
    scanf("%d %d", &n, &m);

    for (int i = 0; i < m; i++) {
        int x, y;
        scanf("%d %d", &x, &y);
        x--;
        y--;
        edges[i].x = x;
        edges[i].y = y;
        vis[x] = 1;
        vis[y] = 1;
        if (x == y) {
            loops++;
        } else {
            deg[x]++;
            deg[y]++;
        }
    }
    if (!connect()) {
        printf("0\n");
        return 0;
    }
    ll cnt = 0;
    cnt += loops * (m - loops);
    cnt += loops * (loops - 1) / 2;
    for (int i = 0; i < n; i++) {
        cnt += (ll) (deg[i]) * (deg[i] - 1) / 2;
    }
    printf("%I64d", cnt);
}