Codeforces Round #407 (Div. 2)

A. Anastasia and pebbles

貪心的拿取就可以了
規則是每一個口袋只能裝一種鵝卵石，且要把所有石頭拿完
所以就是儘量裝就結束了
總之就是貪心法

#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

簡單來講只要利用unordered_set跟暴力模擬就解決了
記得int不夠大

#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

這題應該算思路題

先把陣列做相差預處理之後得到新的陣列

在以這個陣列做正負轉換
+ - + - + - +
- + - + - + -
總共只有這兩種陣列，再做最大化的子序列就結束了

#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

這題也是思路題+歐拉迴路
來回兩次也就是把一條邊再加上另一條邊
可以知道
歐拉迴路奇度點只能是0或2

• 刪除沒有任何共同點的兩條邊 = 不是歐拉迴路 （因為奇度點有4個 ）
• 刪除有共同點的兩條邊 = 是歐拉迴路 （因為奇度點有2個 ）
• 刪除兩個自環 = 是歐拉迴路 （因為奇度點有0個 ）
• 刪除一個自環跟隨便一個邊 = 是歐拉迴路 （因為奇度點有2個 ）
  這樣大概就解決一半了

一開始記得要判斷連通圖，利用disjoint set即可
接著算數量
以刪除有共同點的兩條邊來說，枚舉每個點然後那點的度數取2的排列組合就可以了（枚舉所有度數的邊的總和）
以刪除兩個自環來說，則是所有自環的排列組合總和
以刪除一個自環跟隨便一個邊來說，則是所有自環x所有邊（也就是自環跟邊的排列組合）

#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);
}

​