第四屆桂冠闖關組

a.cpp

#include <cstdio>
#include <vector>

using namespace std;

typedef long long ll;
typedef pair<int, int> ii;

int main()
{
    int ncase;
    scanf("%d", &ncase);
    while (ncase--) {
        int a;
        scanf("%d", &a);
        printf("%d %d\n", a * a, a * a * a);
    }
    return 0;
}

b.cpp

#include <algorithm>
#include <cstdio>
#include <vector>

using namespace std;

typedef long long ll;
typedef pair<int, int> ii;

int cal(int x)
{
    int ret = 0;
    while (x > 0) {
        ret += x % 10;
        x /= 10;
    }
    return ret;
}

bool cmp(const int &a, const int &b)
{
    if (cal(a) == cal(b))
        return a < b;
    return cal(a) < cal(b);
}

int main()
{
    int ncase;
    scanf("%d", &ncase);
    while (ncase--) {
        int n;
        scanf("%d", &n);

        int inp[n];
        for (int i = 0; i < n; i++)
            scanf("%d", &inp[i]);

        sort(inp, inp + n, cmp);

        for (int i = 0; i < n; i++)
            printf("%d%c", inp[i], i == n - 1 ? '\n' : ' ');
    }
    return 0;
}

c.cpp

#include <cstdio>
#include <map>
#include <vector>

using namespace std;

typedef long long ll;
typedef pair<int, int> ii;

int main()
{
    int n;
    while (scanf("%d", &n) == 1) {
        map<int, int> inp;
        for (int i = 0; i < n; i++) {
            int num;
            scanf("%d", &num);
            inp[num]++;
        }

        vector<int> ans;
        for (map<int, int>::iterator it = inp.begin(); it != inp.end(); it++) {
            if (it->second == 1)
                ans.push_back(it->first);
        }

        if ((int)ans.size() == 0)
            printf("N/A\n");
        else
            for (int i = 0; i < (int)ans.size(); i++)
                printf("%d%c", ans[i], i == (int)ans.size() - 1 ? '\n' : ' ');
    }
    return 0;
}

d.cpp

#include <cstdio>
#include <cstring>
#include <vector>

using namespace std;

typedef long long ll;
typedef pair<int, int> ii;

int main()
{
    int ncase;
    scanf("%d", &ncase);
    while (ncase--) {
        int coeff[3], d;
        scanf("%d %d %d %d", &coeff[2], &coeff[1], &coeff[0], &d);

        int mx = 3 + 2 * (d - 1);
        int ans[mx], tmp[mx];
        memset(ans, 0, sizeof(ans));
        ans[0] = 1;
        for (int i = 0; i < d; i++) {
            memset(tmp, 0, sizeof(tmp));
            for (int j = 0; j < mx; j++) {
                for (int k = 0; k < 3; k++) {
                    tmp[j + k] += ans[j] * coeff[k];
                }
            }
            memcpy(ans, tmp, sizeof(ans));
        }

        for (int i = mx - 1; i >= 0; i--) {
            printf("%d%c", ans[i], i == 0 ? '\n' : ' ');
        }
    }
    return 0;
}

e.cpp

#include <cstdio>
#include <vector>

using namespace std;

typedef long long ll;
typedef pair<int, int> ii;

const int coins[5] = {1, 5, 10, 20, 50};

int main()
{
    ll dp[15001] = {0};
    dp[0] = 1;
    for (int i = 0; i < 5; i++) {
        for (int j = 0; j + coins[i] < 15001; j++) {
            if (dp[j] > 0) {
                dp[j + coins[i]] += dp[j];
            }
        }
    }

    int ncase;
    scanf("%d", &ncase);
    while (ncase--) {
        int n;
        scanf("%d", &n);

        printf("%lld\n", dp[n]); // bro, this overflows
    }
    return 0;
}

f.cpp

#include <climits>
#include <cstdio>
#include <vector>

using namespace std;

typedef long long ll;
typedef pair<int, int> ii;

int dfs(int l, int r, vector<int> &cut, vector< vector<int> > &dp)
{
    if (r - l == 1)
        return 0;
    if (dp[l][r] != -1)
        return dp[l][r];

    int mn = INT_MAX;
    for (int i = l + 1; i < r; i++) {
        mn = min(mn, cut[r] - cut[l] + dfs(l, i, cut, dp) + dfs(i, r, cut, dp));
    }

    return dp[l][r] = mn;
}

void solve()
{
    int n, k;
    scanf("%d %d", &n, &k);

    vector<int> cut(k + 2);
    vector< vector<int> > dp(k + 2, vector<int>(k + 2, -1));
    cut[0] = 0;
    cut[k + 1] = n;
    for (int i = 1; i <= k; i++)
        scanf("%d", &cut[i]);

    printf("%d\n", dfs(0, k + 1, cut, dp));
}

int main()
{
    int ncase;
    scanf("%d", &ncase);
    while (ncase--) {
        solve();
    }
    return 0;
}

g.cpp

// binary search + MST
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <vector>

using namespace std;

typedef long long ll;
typedef pair<int, int> ii;
typedef pair<int, ii> rec;
vector<rec> g;

struct UFDS {
    int par[1111];
    void init()
    {
        memset(par, -1, sizeof(par));
    }

    int root(int x)
    {
        return par[x] < 0 ? x : par[x] = root(par[x]);
    }

    void merge(int x, int y)
    {
        x = root(x);
        y = root(y);

        if (x == y)
            return;
        if (par[x] > par[y])
            swap(x, y);
        par[x] += par[y];
        par[y] = x;
    }
} uf;

bool check(int limit, int n, int &ans)
{
    uf.init();
    int acc = 0, total = 0;
    for (int i = (int)g.size() - 1; i >= 0; i--) {
        if (g[i].first > limit)
            break;
        if (acc == n - 1)
            break;

        int u = g[i].second.first, v = g[i].second.second;
        if (uf.root(u) != uf.root(v)) {
            acc++;
            uf.merge(u, v);
            total += g[i].first;
        }
    }

    if (acc == n - 1)
        ans = max(ans, total);
    return acc == n - 1;
}

void solve()
{
    g.clear();

    int n, m;
    scanf("%d %d", &n, &m);
    for (int i = 0; i < m; i++) {
        int u, v, w;
        scanf("%d %d %d", &u, &v, &w);

        g.push_back(rec(w, ii(u, v)));
    }
    sort(g.begin(), g.end());

    int l = 0, r = 0x3f3f3f3f, ans = 0;
    while (r - l > 1) {
        int mid = l + (r - l) / 2;
        if (check(mid, n, ans))
            r = mid;
        else
            l = mid;
    }

    check(r, n, ans); // crucial
    printf("%d\n", ans);
}

int main()
{
    int ncase;
    scanf("%d", &ncase);
    while (ncase--) {
        solve();
    }
    return 0;
}

h.cpp

#include <cstdio>
#include <queue>
#include <vector>

using namespace std;

typedef long long ll;
typedef pair<int, int> ii;

int main()
{
    int ncase;
    scanf("%d", &ncase);
    while (ncase--) {
        int n;
        scanf("%d", &n);

        priority_queue< int, vector<int>, greater<int> > pq;
        for (int i = 0; i < n; i++) {
            int num;
            scanf("%d", &num);
            pq.push(num);
        }

        int ans = 0;
        while (pq.size() > 0) {
            ans = pq.top();

            if ((int)pq.size() == 1)
                break;

            int l = pq.top();
            pq.pop();
            int r = pq.top();
            pq.pop();

            pq.push(max(l, r) + 1);
        }

        printf("%d\n", ans);
    }
    return 0;
}

i.cpp

#include <cstdio>
#include <queue>
#include <vector>
#include <climits>

using namespace std;

typedef long long ll;
typedef pair<int, int> ii;

struct Data {
    int v;
    int risk;
    int len;
};

const int oo = 0x3f3f3f3f;

bool check(int limit, int n, vector< vector<Data> > &g, int &ans)
{
    priority_queue<ii, vector<ii>, greater<ii> > pq;
    pq.push(ii(0, 0));
    vector<int> dist(n, oo);
    dist[0] = 0;
    while (pq.size() > 0) {
        ii cur = pq.top(); // dist, who
        pq.pop();

        if (cur.first > dist[cur.second])
            continue;

        for (int i = 0; i < (int)g[cur.second].size(); i++) {
            Data &nxt = g[cur.second][i];
            if (nxt.risk > limit)
                continue;
            int nDist = dist[cur.second] + nxt.len;
            if (nDist < dist[nxt.v]) {
                dist[nxt.v] = nDist;
                pq.push(ii(nDist, nxt.v));
            }
        }
    }

    if (dist[n - 1] != oo)
        ans = min(ans, dist[n - 1]);
    return dist[n - 1] != oo;
}

void solve()
{
    int n, m;
    scanf("%d %d", &n, &m);

    vector< vector<Data> > g(n, vector<Data>());
    for (int i = 0; i < m; i++) {
        Data tmp;
        int u;
        scanf("%d %d %d %d", &u, &tmp.v, &tmp.risk, &tmp.len);

        g[u].push_back(tmp);
    }

    // binary search max risk
    int l = -1, r = oo;
    int ans = oo;
    while (r - l > 1) {
        int mid = l + (r - l) / 2;
        if (check(mid, n, g, ans))
            r = mid;
        else
            l = mid;
    }

    // r
    ans = oo;
    check(r, n, g, ans);
    if(r == 0 || ans == oo)
        printf("-1\n");
    else
        printf("%d %d\n", r, ans);
}

int main()
{
    int ncase;
    scanf("%d", &ncase);
    while (ncase--) {
        solve();
    }
    return 0;
}