Educational Codeforces Round 36 (Rated for Div. 2)

https://codeforces.com/contest/915
浓浓ds味的一场edu

A. Garden

找最大因子

#include <bits/stdc++.h>

using namespace std;

void solve () {
    set<int> s;
    vector <int> s2;
    int n, k, x;
    cin >> n >> k;
    while (n--) cin >> x, s.insert (x);
    for (int i = 1; i * i <= k; i++) {
        if (k % i == 0) {
            s2.push_back (i), s2.push_back (k / i);
        }
    }
    sort (s2.begin (), s2.end (), greater<int>());
    for (auto i : s2) {
        if (s.count (i)) {
            cout << k / i << endl;
            break;
        }
    }
}

int main () {
    solve ();
}

B. Browser

分类讨论。

#include <bits/stdc++.h>

using namespace std;

void solve () {
    int n, pos, l, r;
    cin >> n >> pos >> l >> r;
    int ll = l - 1, rr = n - r, ans = 0;
    if (pos >= l && pos <= r) {
        int dl = pos - l, dr = r - pos;
        if (ll && rr)    ans += 2 * min (dl, dr) + max (dl, dr) + 2;
        else if (ll)     ans += dl + 1;
        else if (rr)     ans += dr + 1;
    }
    else if (pos < l) {
        ans += l - pos;
        if (ll)     ans++;
        if (rr)     ans += r - l + 1;
    }
    else {
        ans += pos - r;
        if (rr)     ans++;
        if (ll)     ans += r - l + 1;
    }
    cout << ans << endl;
}

int main () {
    solve ();
}

C. Permute Digits

有点意思。
反悔贪心
贪心失败就回溯修改

#include <bits/stdc++.h>

using namespace std;
string a, b, ans;
bool vis[105], up;//前面有没有放过比b小的数
int n;

void change (int x) { //贪心失败，回溯修改
    bool suc = false;
    ans = ans.substr (0, ans.size () - 1);
    for (int i = 0; i < n; i++) {
        if (!vis[i] && a[i] < b[x]) {
            suc = true, vis[i] = true;
            ans += a[i];
            break;
        }
    }
    //cout << ans << ' ';
    for (int i = 0; i < n; i++) {
        if (vis[i] && a[i] == b[x]) {
            vis[i] = false;
            break;
        }
    }
    if (!suc)   change (x - 1);
    else {
        for (int i = 0; i < n; i++) {
            if (vis[i]) continue;
            vis[i] = true;
            ans += a[i];
        }
        cout << ans << endl;
    }
}

void solve () {
    cin >> a >> b;
    sort (a.begin (), a.end (), greater<char>());
    if (a.size () != b.size ())    cout << a << endl;
    else {
        //cout << a << endl;
        //bool up = false; //前面有没有放过比b小的数
        n = a.size ();
        for (int i = 0; i < n; i++) { //b[i]
            bool find = false;
            for (int j = 0; j < n; j++) {
                if (vis[j])     continue;
                if (up) {
                    vis[j] = true, ans += a[j];
                    find = true;
                    break;
                }
                else {
                    if (a[j] > b[i])    continue;
                    vis[j] = true, ans += a[j];
                    if (a[j] < b[i])   up = true;
                    find = true;
                    break;
                }
            }
            if (!find) {
                change (i - 1); //修改上一位数
                return ;
            }
            //cout << ans << endl;
        }
        cout << ans << endl;
        //for (int i = 0; i < n; i++) if (!vis[i])    cout << i << ' ' << a[i] << endl;
    }
}

int main () {
    solve ();
}

D. Almost Acyclic Graph

神奇的小题。
删边的实质就是把某点入度减一，所以只需枚举点的度数减一然后再做一遍拓扑排序判环即可。

#include <bits/stdc++.h>

using namespace std;
const int N = 505, M = 100005;
int n, m, d[N], dd[N];
int h[N], e[M], ne[M], idx;
int tp[N];

void add (int a, int b) {
    e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}

bool topsort () { //拓扑排序判环
    set<int> s;
    queue<int> q;
    for (int i = 1; i <= n; i++) {
        if (d[i] == 0)  q.push (i), s.insert (i);
    }
    while (!q.empty ()) {
        auto t = q.front ();
        q.pop ();
        s.insert (t);

        for (int i = h[t]; ~i; i = ne[i]) {
            int j = e[i];
            d[j]--;
            if (d[j] == 0)  q.push (j);
        }
    }
    return s.size () >= n;
}

int main () {
    memset (h, -1, sizeof h);
    scanf ("%d%d", &n, &m);
    while (m--) {
        int u, v;
        scanf ("%d%d", &u, &v);
        add (u, v);
        d[v]++;
    }
    // for (int i = 1; i <= n; i++)    cout << d[i] << ' ';
    // cout << endl;
    for (int i = 1; i <= n; i++)    dd[i] = d[i];
    for (int i = 1; i <= n; i++) {
        if (!d[i])   continue;
        d[i]--; //删边等价于入度-1
        if (topsort ()) {
            cout << "YES\n";
            return 0;
        }
        for (int j = 1; j <= n; j++)    d[j] = dd[j];
    }
    cout << "NO\n";
}

E. Physical Education Lessons

珂朵莉树！
适用：有区间推平操作和数据随机时可以使用这种数据结构
教程戳这里
其实就是一种变相的暴力，拿set乱搞
注意输入要用scanf

#include <bits/stdc++.h>

using namespace std;
const int N = 3e5 + 5;
int n, m, sum;

struct Node {
    int l, r, v;
    bool operator<(const Node &t) const {
        return l < t.l;
    }
};

set<Node> s;

auto split (int pos) {
    auto it = s.lower_bound ({pos, 0, 0});
    if (it != s.end () && it->l == pos) return it;
    it--;
    int l = it->l, r = it-> r, v = it->v;
    s.erase ({l, r, v});
    s.insert ({l, pos - 1, v});
    return s.insert ({pos, r, v}).first;
}

void assign (int l, int r, int v) {
    auto ed = split (r + 1), st = split (l); //先r后l不然会RE
    int len = 0, cnt = 0;
    for (auto it = st; it != ed; it++) {
        int dx = it->r - it->l + 1;
        len += dx, cnt += it->v * dx;
    }
    if (v == 0) sum -= cnt;
    else    sum += (len - cnt);
    s.erase (st, ed);
    s.insert ({l, r, v});
}

int main () {
    scanf ("%d%d", &n, &m);
    s.insert ({1, n, 1});
    sum = n;
    while (m--) {
        int l, r, op;
        scanf ("%d%d%d", &l, &r, &op);
        op--;
        assign (l, r, op);
        printf ("%d\n", sum);
    }
}

//珂朵莉树: 有区间赋值操作且数据随机的题目
//珂学家！！！

F. Imbalance Value of a Tree

看着很吓人但其实是小清新ds
首先max和min可以分开求。
考虑求max：把边权从小到大排序，然后用并查集合并，合并的时候计入 \(sz_u\times sz_v\times w\)
注意点权转化为边权的小技巧：edge{u, v}=max(\(w_u, w_v\))

求 min 同理。

#include <bits/stdc++.h>
#define ll long long

using namespace std;
typedef pair<int, int> pii;
const int N = 1e6 + 5;
int v[N], fa[N], sz[N], n;
pii p[N];
ll ans;

int find (int x) {
    if (x != fa[x]) fa[x] = find (fa[x]);
    return fa[x];
}

struct Node {
    int a, b, w;
    bool operator<(const Node &t) const {
        return w < t.w;
    }
}e[N];

bool cmp (Node t1, Node t2) {
    return t1.w > t2.w;
}

int main () {
    scanf ("%d", &n);
    for (int i = 1; i <= n; i++)    scanf ("%d", &v[i]);
    for (int i = 1; i < n; i++)     scanf ("%d%d", &p[i].first, &p[i].second);

    //求max
    for (int i = 1; i <= n; i++)    fa[i] = i, sz[i] = 1;
    for (int i = 1; i < n; i++) {
        int a = p[i].first, b = p[i].second;
        e[i] = {a, b, max (v[a], v[b])};
    }
    sort (e + 1, e + n);
    for (int i = 1; i < n; i++) {
        int a = e[i].a, b = e[i].b, w = e[i].w;
        a = find (a), b = find (b);
        if (a != b)     ans += 1ll * w * sz[a] * sz[b], fa[a] = b, sz[b] += sz[a];
    }
    // printf ("%lld\n", ans);

    //求min
    for (int i = 1; i <= n; i++)    fa[i] = i, sz[i] = 1;
    for (int i = 1; i < n; i++) {
        int a = p[i].first, b = p[i].second;
        e[i] = {a, b, min (v[a], v[b])};
    }
    sort (e + 1, e + n, cmp);
    for (int i = 1; i < n; i++) {
        int a = e[i].a, b = e[i].b, w = e[i].w;
        a = find (a), b = find (b);
        if (a != b)     ans -= 1ll * w * sz[a] * sz[b], fa[a] = b, sz[b] += sz[a];
    }
    printf ("%lld\n", ans);    
}

//max 和 min 分开来求
//点权 -> 边权: e{u, v} = max (a[u], a[v])
//并查集按序合并求