Codeforces Contest 1213

工作之余隨便找?guī)椎篮唵蔚乃惴}練練手，權(quán)當(dāng)鍛煉思維。

A - Chips Moving

題意陷阱，題目寫的很長很玄乎，其實(shí)是最簡單的邏輯。分奇偶，選最少的一邊

#include <iostream>
#include <cstdio>
using namespace std;

typedef long long ll;
typedef unsigned long long llu;

#define MAXN 150000

int main() {
    int n, m, a = 0, b = 0;
    scanf("%d", &n);
    for(int i=0; i<n; ++i) {
        scanf("%d", &m);
        m&1 ? ++a : ++b;
    }
    printf("%d\n", a>b ? b : a);
    return 0;
}

B - Bad Prices

單調(diào)棧

#include <iostream>
#include <cstdio>
using namespace std;

typedef long long ll;
typedef unsigned long long llu;

#define MAXN 150000

int buf[MAXN + 5];

int main() {
    int T;
    scanf("%d",&T);
    while(T--) {
        int n, ans = 0, top = 0;
        scanf("%d", &n);
        int tmp;
        for(int i = 0; i < n; ++i) {
            scanf("%d", &tmp);
            while(top > 0 && buf[top-1] > tmp) {
                --top;
                ++ans;
            }
            buf[top++] = tmp;
        }
        printf("%d\n", ans);
    }
    return 0;
}

C - Book Reading

根據(jù)底數(shù)的奇偶分情況討論，規(guī)律沒找透，被坑了一把...

#include <iostream>
#include <cstdio>
using namespace std;

typedef long long ll;
typedef unsigned long long llu;
 
#define MAXN 1000
 
int main() {
    int T;
    scanf("%d",&T);
    while(T--) {
        ll n, m, ans = 0;
        scanf("%I64d%I64d", &n, &m);
        if(n < m) {
            ans = 0;
        } else {
            ll base = m % 10;
            ll len = m & 1 ? 10 : 5;
            ll sum = 0;
            ll arr[10] = {0};
            for(int i = 0; i < len; ++i) {
                arr[i] = (base * i) % 10;
                sum += arr[i];
            }
            ll div = n / m;
            ans = (div / len) * sum;
            ll last = div % len;
            for(int i = 1; i <= last; ++i) {
                ans += arr[i];
            }
        }
        printf("%I64d\n", ans);
    }
    return 0;
}

D - Equalizing by Division

預(yù)處理，每個數(shù)字維護(hù)能得到的數(shù)字的隊(duì)列，排序后順序地找

#include <cstdio>
#include <algorithm>
#include <iostream>
#include <string>
#include <vector>
#include <queue>
using namespace std;

#define INF (2 * 1000 * 1000 * 1000)
#define MAXN (200 * 1000 + 2)

int buf[MAXN];
vector<int> vec[MAXN];

int main() {
    int n, k;
    scanf("%d%d", &n, &k);
    for (int i = 0; i < n; ++i) {
        scanf("%d", &buf[i]);
    }
    sort(buf, buf + n);
    for (int i = 0; i < n; ++i) {
        int tmp = buf[i], cnt = 0;
        while (tmp > 0) {
            vec[tmp].push_back(cnt);
            tmp = tmp >> 1;
            ++cnt;
        }
        vec[tmp].push_back(cnt);  // tmp == 0
    }
    for (int i = 0; i < MAXN; ++i) {
        if(!vec[i].empty()) {
            sort(vec[i].begin(), vec[i].end());
        }
    }
    int ans = INF;
    for (int i = 0; i < MAXN; ++i) {
        if(vec[i].size() >= k) {
            int cast = 0;
            for(int j = 0; j < k; ++j) {
                cast += vec[i][j];
            }
            ans = min(ans, cast);
        }
    }
    printf("%d\n", ans);
    return 0;
}

E - Two Small Strings

貪心，以兩種方式擴(kuò)展基本串

• abc => aabbcc
• abc => abcabc

在模板串不沖突的情況下，擴(kuò)展出來的串是不會有沖突的

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>
#include <string>
#include <vector>
#include <queue>
using namespace std;

#define INF (2 * 1000 * 1000 * 1000)
#define MAXN (100 * 1000)

char buf[MAXN]; 
vector<string> vec_template = {
    "abc", "acb",
    "bac", "bca",
    "cab", "cba"
};

int main() {
    int n;
    string inp[2];
    cin >> n >> inp[0] >> inp[1];
    string ans;
    if (inp[0][0] == inp[0][1] || inp[1][0] == inp[1][1]) {
        for (int i = 0; i < vec_template.size(); ++i) {
            string th = vec_template[i] + vec_template[i];
            if (th.find(inp[0]) == string::npos &&
                th.find(inp[1]) == string::npos) {
                for (int j = 0; j < n; ++j) {
                    ans.append(vec_template[i]);
                }
                break;
            }
        }
    } else {
        for (int i = 0; i < vec_template.size(); ++i) {
            string & th = vec_template[i];
            if (th.find(inp[0]) == string::npos &&
                th.find(inp[1]) == string::npos) {
                for (int j = 0; j < th.size(); ++j) {
                    ans.append(n, th[j]);
                }
                break;
            }
        }
    }
    if (ans.empty()) {
        cout << "NO" << endl;
    } else {
        cout << "YES" << endl;
        cout << ans << endl;
    }
    return 0;
}

F - Unstable String Sort

給n個節(jié)點(diǎn)和k條有向路徑，得到一個可能帶環(huán)、帶孤點(diǎn)的圖，為圖中每個點(diǎn)標(biāo)一個小寫字母：

• 在a1->a2的情況下，a1標(biāo)的字母<=a2
  也就是說對于一個環(huán)，或者說一個帶環(huán)的連通塊，其中所有節(jié)點(diǎn)的字母是相同的
• 字母數(shù)不少于k個
  所以每個連通塊必須是最小環(huán)

整體思路是找連通塊，然后連通塊縮成一個點(diǎn)，最后得到一個拓補(bǔ)排序，依次標(biāo)字母

void wait();

G - Path Queries

題意是給出一棵樹，然后對于每個query，去除樹中所有邊權(quán)值大于w的邊，求剩下的圖（森林）中的連通量（任意兩點(diǎn)能連通即一個連通量）

離線處理，按權(quán)值對邊排序后從小到大加邊，用并查集表示森林，每次求到連通量并記錄下來

#include <cstdio>
#include <algorithm>
#include <iostream>
#define MAXN 200000

struct Edge {
    int from, to, val;
}edge[MAXN + 5];

bool comp(const Edge & left, const Edge & right) {
    return left.val < right.val;
}

long long count;

int cnt[MAXN + 5];
int father[MAXN + 5];
int find(int now) {
    father[now] = father[now]==now ? now : find(father[now]);
    return father[now];
}
void join(int a, int b) {
    int aa = find(a);
    int bb = find(b);
    count += 1LL * cnt[aa] * cnt[bb];
    if (aa != bb) {
        father[bb] = aa;
        cnt[aa] += cnt[bb];
        cnt[bb] = 0;
    }
}

int query[MAXN + 5];
long long ans[MAXN + 5];

int main() {
    int n, m, a, b, val, max_val = 0;
    scanf("%d%d", &n, &m);
    for (int i=0; i<n-1; ++i) {
        scanf("%d%d%d", &a, &b, &val);
        edge[i].from = a;
        edge[i].to = b;
        edge[i].val = val;
        if (val > max_val) {
            max_val = val;
        }
    }
    for (int i=0; i<m; ++i) {
        scanf("%d", &val);
        query[i] = val>max_val ? max_val : val;
    }
    for (int i=1; i<=n; ++i) {
        father[i] = i;
        cnt[i] = 1;
    }
    std::sort(edge, edge+n-1, comp);
    int idx = 0;
    for (int now=1; now<=max_val; ++now) {
        while (idx<n-1 && edge[idx].val<=now) {
            join(edge[idx].from, edge[idx].to);
            ++idx;
        }
        ans[now] = count;
    }
    for (int i=0; i<m-1; ++i) {
        printf("%lld ", ans[query[i]]);
    }
    printf("%lld\n", ans[query[m-1]]);
    return 0;
}