Educational Codeforces Round 49 (Rated for Div. 2)

C - Minimum Value Rectangle

题意：给n根木棒，选4根组成长方形，使得这个长方形的周长的平方比上其面积最小。

题解：对那个式子求导，发现对于同一个长来说，是长和宽越接近，上式越小。那么排序之后每个和他附近的一个组装一下就行了。

map<int, int> m;
vector<int> v;

void test_case() {
    int n;
    scanf("%d", &n);
    m.clear();
    for(int i = 1; i <= n; ++i) {
        int ai;
        scanf("%d", &ai);
        m[ai]++;
    }
    v.clear();
    for(auto &j : m) {
        if(j.second == 2 || j.second == 3)
            v.push_back(j.first);
        else if(j.second >= 4) {
            printf("%d %d %d %d\n", j.first, j.first, j.first, j.first);
            return;
        }
    }
    ll fz, fm, a, b;
    n = v.size();
    for(int i = 0; i < n - 1; ++i) {
        ll nfz = 2ll * (v[i] + v[i + 1]);
        nfz *= nfz;
        ll nfm = 1ll * v[i] * v[i + 1];
        if(i == 0 || nfz * fm < fz * nfm) {
            a = v[i];
            b = v[i + 1];
            fz = nfz;
            fm = nfm;
        }
    }
    printf("%lld %lld %lld %lld\n", a, a, b, b);
}

事实上可能不需要map，直接来一波快排，然后跑一遍nxt。

int a[1000005];
int b[1000005];
 
void test_case() {
    int n;
    scanf("%d", &n);
    for(int i = 1; i <= n; ++i)
        scanf("%d", &a[i]);
    sort(a + 1, a + 1 + n);
    int w, h, btop = 0;
    for(int i = 1, nxt; i <= n; i = nxt) {
        for(nxt = i + 1; nxt <= n && a[nxt] == a[i]; ++nxt);
        int cnt = nxt - i;
        if(cnt >= 4) {
            printf("%d %d %d %d\n", a[i], a[i], a[i], a[i]);
            return;
        }
        if(cnt >= 2)
            b[++btop] = a[i];
    }
    ll fz, fm;
    for(int i = 1; i < btop; ++i) {
        ll nfz = 2ll * (b[i] + b[i + 1]);
        nfz *= nfz;
        ll nfm = 1ll * b[i] * b[i + 1];
        if(i == 1 || nfz * fm < fz * nfm) {
            w = b[i];
            h = b[i + 1];
            fz = nfz;
            fm = nfm;
        }
    }
    printf("%d %d %d %d\n", w, w, h, h);
}

Mouse Hunt

题意：有n个房间，有1个老鼠，开始可能在任意一个房间，在第i个房间放陷阱花ci，老鼠在第i个房间下一次就会到ai。求最便宜的陷阱总额。

题解：基环树的内向树。乱搞一点直接套Kosaraju缩点，然后缩点之后的代表点放这堆点的最小值，然后把所有0出度的ci加起来。

Educational Codeforces Round 49 (Rated for Div. 2)

原文：https://www.cnblogs.com/KisekiPurin2019/p/11979991.html