首页 > 其他分享 >codeforces 1002, div2, B-E1

codeforces 1002, div2, B-E1

时间:2025-02-04 23:20:04浏览次数:1  
标签:cnt 数字 int codeforces ++ vector && E1 div2

cf2059

坐了一天的车后就不该打 cf

B

  • 特判 n == k 的情况
  • 先看能否让第一个数不是 1 :
    • 第一个数一定是第一组, 因此从第二个数开始遍历
    • 遍历到一个不等于 1 的数, 检查如果把这个数作为第二组, 剩下的数够不够分组
    for (int i = 2; i <= n; i++) {
        if (a[i] != 1) {
            if (n - i >= k - 2) {
                cout << "1\n";
                return;
            }
        }
    }
    
  • 否则, 一定有很长的前缀使得前缀中每个数都是 1, 那么一定可以选择两个 1 作为第二组, 此时答案为 2

C

  • 操作就是取后缀, 且每一种长度的后缀只能取一次
  • 因为每个数字最小为 1, 又每一种长度的后缀只能取一次, 所以我们只能取全为 1 的后缀去构造 mex
  • 记录每一行最长的全为 1 的后缀长度, 再统计每种长度的数量
  • 如果较小的长度没有, 可以用较大的长度去补
    for (int i = 0, t = 0; i <= n; i++) {
        if (cnt[i] == 0) {
            t = max(t, i);
            while (t <= n) {
                if (cnt[t]) {
                    cnt[t]--, cnt[i]++;
                    break;
                }
                t++;
            }
    
            if (cnt[i] == 0) {
                cout << i << "\n";
                return;
            }
        }
    }
    
  • 完整代码
inline void solve() {
    cin >> n;

    vector<vector<int> > a(n + 1, vector<int>(n + 1));

    for (int i = 1; i <= n; i++) {
        for (int t = 1; t <= n; t++) cin >> a[i][t];
    }

    vector<int> mx(n + 1);

    for (int i = 1; i <= n; i++) {
        for (int t = n; t >= 1; t--) {
            if (a[i][t] != 1) break;
            mx[i]++;
        }
    }

    vector<int> cnt(n + 1);

    for (int i = 1; i <= n; i++) cnt[mx[i]]++;

    for (int i = 0, t = 0; i <= n; i++) {
        if (cnt[i] == 0) {
            t = max(t, i);
            while (t <= n) {
                if (cnt[t]) {
                    cnt[t]--, cnt[i]++;
                    break;
                }
                t++;
            }

            if (cnt[i] == 0) {
                cout << i << "\n";
                return;
            }
        }
    }    
}

D

  • 如果两个图中有一条相同的边, 且两个标记能同时达到这条边的同一个端点, 答案才有限
  • 把一对点看作一个点, 建图跑最短路
    for (int i = 1; i <= n; i++) {
        for (int t = 1; t <= n; t++) {
            for (auto u : g1[i]) {
                for (auto v : g2[t]) {
                    if (u == v && i == t) { // 两个图中有一条相同的边
                        flag = 1;
                        f[id[i][t]] = f[id[u][v]] = 1; // 标记这样的点对, 如果能到达这样的点对, 答案有限
                    }
    
                    g[id[i][t]].push_back({id[u][v], abs(u - v)});
                }
            }
        }
    }
    
  • 完整代码
inline void solve() {
    cin >> n >> s1 >> s2;

    cin >> m1;

    vector<vector<int> > g1(n + 1);

    for (int i = 1; i <= m1; i++) {
        int a, b;
        cin >> a >> b;
        g1[a].push_back(b);
        g1[b].push_back(a);
    }

    cin >> m2;

    vector<vector<int> > g2(n + 1);

    for (int i = 1; i <= m2; i++) {
        int a, b;
        cin >> a >> b;
        g2[a].push_back(b);
        g2[b].push_back(a);
    }

    int P = 0;
    vector<vector<int> > id(n + 1, vector<int>(n + 1));

    for (int i = 1; i <= n; i++) {
        for (int t = 1; t <= n; t++) {
            id[i][t] = ++P;
        }
    }

    vector<int> f(P + 1);
    vector<vector<pair<int, int> > > g(P + 1);

    bool flag = 0;

    for (int i = 1; i <= n; i++) {
        for (int t = 1; t <= n; t++) {
            for (auto u : g1[i]) {
                for (auto v : g2[t]) {
                    if (u == v && i == t) {
                        flag = 1;
                        f[id[i][t]] = f[id[u][v]] = 1;
                    }

                    g[id[i][t]].push_back({id[u][v], abs(u - v)});
                }
            }
        }
    }

    if (!flag) {
        cout << "-1\n";
        return;
    }

    vector<int> d(P + 1, inf), vis(P + 1);

    priority_queue<pair<int, int>, vector<pair<int, int> >, greater<pair<int, int> > > q;
    q.push({d[id[s1][s2]] = 0, id[s1][s2]});

    while (q.size()) {
        auto [dis, u] = q.top();
        q.pop();

        if (f[u]) {
            cout << dis << "\n";
            return;
        }

        for (auto [t, w] : g[u]) {
            if (d[t] > d[u] + w) {
                d[t] = d[u] + w;

                if (!vis[t]) {
                    vis[t] = 1;
                    q.push({d[t], t});
                }
            }
        }
    }

    cout << "-1\n";
}

E1

  • 操作数尽量少就是让原本在 a 中数字留下来的尽量多
  • 由操作可知, 如果保留了后面的数字, 则前面的数字也必须保留, 因此这些留下来的数字一定对应 a 中的一个前缀
  • 注意数字都是两两不同的, 即一个数字只对应一个位置, 那么 a 中数字在 b 中可以匹配的位置是固定的
  • 依次检查前缀:
    • 如果 a 中相邻两个数字 a[i-1] 和 a[i] 在 b 中匹配的位置不相邻, 说明在 a[i-1] 后面需要添加数字
    for (int i = 0, t = 0; i < n * m && t < n * m; i++, t++) {
        int st = t;
    
        while (t < n * m && b[t] != a[i]) t++;
    
        if (i != 0 && t > st && check(i)) break; // t > st 说明 a[i-1] 和 a[i] 在 b 中匹配的位置不相邻
        if (t == n * m) break;
    
        cnt[i] = (i == 0 ? 0 : cnt[i - 1]) + t - st, ans--;
    }
    
    • 进而说明: 某一时刻, a[i-1] 需要排在某一行的最后一列
    • 进而说明: a[i-1] 前面添加的数字数量, 需要不小于 a[i-1] 原本所在列到最后一列的距离
    • 如果条件不满足, 说明前缀到此为止, a[i] 不能保留
    • 还没完: 不保留 a[i], a[i-1] 后面还是需要添加数字, 但不符合条件, 因此 a[i-1] 也不能保留
    • 而 a[i-1] 不保留, 就要继续看 a[i-2]...于是我写了一个"回溯"函数
    auto check = [&] (int i) -> bool {
        bool flag = 0;
        while (ans < n * m) {
            int j = m - 1 - (i - 1) % m;
            if (cnt[i - 1] >= j) { // cnt[i] 记录了 a[i] 前面添加的数字的数量
                break;
            }
            flag = 1; // 说明前缀到此为止
            ans++, i--;
        }
        return flag;
    };
    
  • 完整代码
inline void solve() {
    cin >> n >> m;

    vector<int> a(n * m);
    for (int &x : a) cin >> x;

    vector<int> b(n * m);
    for (int &x : b) cin >> x;

    int ans = n * m;

    vector<int> cnt(n * m);

    auto check = [&] (int i) -> bool {
        bool flag = 0;
        while (ans < n * m) {
            int j = m - 1 - (i - 1) % m;
            if (cnt[i - 1] >= j) {
                break;
            }
            flag = 1;
            ans++, i--;
        }
        return flag;
    };

    for (int i = 0, t = 0; i < n * m && t < n * m; i++, t++) {
        int st = t;

        while (t < n * m && b[t] != a[i]) t++;
    
        if (i != 0 && t > st && check(i)) break;
        if (t == n * m) break;

        cnt[i] = (i == 0 ? 0 : cnt[i - 1]) + t - st, ans--;
    }

    cout << ans << "\n";
}

标签:cnt,数字,int,codeforces,++,vector,&&,E1,div2
From: https://www.cnblogs.com/wxgmjfhy/p/18697291

相关文章