Codeforces Div,1 AB(C) practice

1019 A

题目大意：

\(n\)个人给\(m\)个党派投票，第\(i\)个人投给\(p_i\)，但如果给他ci元钱，可以让他改选任意党派，最小化消耗的金额使得党派1的票数严格大于其它所有党派。

(\(n,m\le3000,ci\le10^9\))

题解：

枚举党派1获胜至少需要多少票，显然大于等于这个票数的党派都要改票。

\(O(nm)\).

#include <bits/stdc++.h>

#define ALL(x) (x).begin(), (x).end()

const int max_N = 3000 + 21;

using ll = long long;

int n, m, p[max_N], c[max_N], cnt[max_N];

std::vector<int> vec[max_N];

bool check() {
    for (int i = 2; i <= m; ++i)
        if (cnt[1] <= cnt[i]) return false;
    return true;
}

ll greed(int x) {
    std::vector<int> remain;
    ll ret = 0;
    int k = x - cnt[1];
    for (int i = 2; i <= m; ++i) {
        if (cnt[i] < x) {
            for (auto a : vec[i]) remain.push_back(a);
            continue;
        }
        int tmp = cnt[i] - x + 1;
        for (int j = 0; j < tmp; ++j) ret += vec[i][j];
        for (int j = tmp; j < cnt[i]; ++j) remain.push_back(vec[i][j]);
        k -= tmp;
    }
    if (k <= 0) return ret;
    std::nth_element(remain.begin(), remain.begin() + k - 1, remain.end());
    for (int i = 0; i < k; ++i) ret += remain[i];
    return ret;
}

int main() {
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; ++i) {
        scanf("%d%d", p + i, c + i);
        ++cnt[p[i]];
        vec[p[i]].push_back(c[i]);
    }
    if (check()) return puts("0"), 0;
    for (int i = 1; i <= m; ++i) std::sort(ALL(vec[i]));
    ll res = LLONG_MAX;
    for (int i = 1; i <= n; ++i) res = std::min(res, greed(i));
    printf("%lld\n", res);
    return 0;
}

1019 B

题目大意：

交互题。

在一个长度为偶数\(n\le10^5\)的环上，任意相邻两个数的绝对值之差都为1。最多询问60次，确定是否存在一个位置\(i\)，满足它等于\((i+n/2)\pmod{n}\)位置的数。存在则输出一组，否则输出-1.

题解：

差分之后既是问一个长度为\(n/2\)的区间内\(-1\)和\(1\)的数量是否相同。

显然\(n/2\)不为偶数就无解，否则：

先问一下\([1,n/2]\)中哪一个多，如果有解了就退出。

否则在\([1,n/2]\)内二分答案，如果\([mid,mid+n/2)\)内的情况和\([1,n/2]\)相同，则答案区间与[1,n/2]的交集应该减少，反之就增加

#include <bits/stdc++.h>

int n, lo, hi, mi, tp;

int check(int x) {
    int a, b;
    printf("? %d\n", x);
    fflush(stdout);
    scanf("%d", &a);
    printf("? %d\n", x + (n >> 1));
    fflush(stdout);
    scanf("%d", &b);
    if (a == b) {
        printf("! %d\n", x);
        exit(0);
    }
    return (a < b) ? -1 : 1;
}

int main() {
    scanf("%d", &n);
    if (n % 4 != 0) return puts("! -1"), 0;
    tp = check(1);
    lo = 1, hi = (n >> 1);
    while (lo <= hi) {
        mi = (lo + hi) >> 1;
        if (check(mi) == tp) lo = mi + 1;
        else hi = mi - 1;
    }
    return puts("! -1"), 0;
}

1012 A

题目大意：

二维平面上有\(n\le10^5\)个点。

现在它们的横纵坐标被打乱了，只知道一共\(2n\)个数, 但不知道每个数属于哪个点，也不知道是横坐标还是纵坐标。

对于所有可能的情况，求能覆盖这些点的最小矩形面积。

题解：

等价于将数平分到两个集合，最小化两个集合的(\(\max-\min\))乘积。

先排序，如果最小的数和最大的数不属于同一集合，则前\(n\)小的数一个集合最优。

否则，枚举另一个集合，一定是连续的区间，取两种情况的最小值即可。

\(O(n\log{n})\).

#include <bits/stdc++.h>

const int max_N = (int) 2e5 + 21;

int n, a[max_N];

int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n * 2; ++i) scanf("%d", a + i);
    std::sort(a + 1, a + 1 + 2 * n);
    long long ans = 1ll * (a[n] - a[1]) * (a[n * 2] - a[n + 1]);
    for (int i = 2; i <= n; ++i) {
        ans = std::min(ans, 1ll * (a[2 * n] - a[1]) * (a[i + n - 1] - a[i]));
    }
    printf("%lld\n", ans);
    return 0;
}

1012 B

题目大意：

有\(n\)行\(m\)列的网格图，上面有\(q\)个点是黑色，其它点是白色。(\(n,m\le2\times10^5,q\le\min(n\cdot m,2\times10^5)\). 可以无数次进行一种操作：如果一个矩形（不能是只有一行或一列的）的三个顶点都是黑色，而另一个是白色，则可以将其染黑。 问在原有的\(q\)个黑点的基础上至少要新增多少个新点，才可以使得经过若干次操作后使得所有点都是黑色。

题解：

将网格图的行列建成二分图，每个黑点就是二分图中的一条边。

显然，在二分图中不属于同一连通块的无法进行操作，而属于同一连通块的一定可以通过操作全部染黑 （通过找两个不同部分的点，沿着两条它们连向其他点的边不断轮询，如果不能操作就删除这两个点， 再沿这两个点连的两条边轮询，最后直到连通块大小不超过3一定可以进行操作，然后之前轮询过的所有操作也可以完成）。

答案就是连通块数量减去一。

#include <bits/stdc++.h>

const int max_N = (int) 4e5 + 21;

int n, m, q, f[max_N], ans = -1;

void merge(int u, int v) {
    auto find = [&](int x) {
        int r = x, y;
        for (; r != f[r]; r = f[r]);
        for (; x != r; y = f[x], f[x] = r, x = y);
        return x;
    };
    u = find(u), v = find(v);
    f[u] = v;
}

int main() {
    scanf("%d%d%d", &n, &m, &q);
    for (int i = 1; i <= n + m; ++i) f[i] = i;
    for (int i = 1, u, v; i <= q; ++i) {
        scanf("%d%d", &u, &v);
        merge(u, n + v);
    }
    for (int i = 1; i <= n + m; ++i)
        if (f[i] == i) ++ans;
    printf("%d\n", ans);
    return 0;
}

1012 C

题目大意：

有一行\(n\le5000\)个数字，每花\(1\)的代价，就可以指定一个位置将其减小\(1\).

对于\(k\in[1,\lceil\frac{n}{2}\rceil]\)，问至少花多少代价可以让满足严格大于左右两个相邻的数（如果存在）的位置不少于\(k\).

题解：

记录末两位选或不选dp即可，\(O(n^2)\).

coding time: 7 min : 39 sec

#include <bits/stdc++.h>

const int max_N = 5000 + 21;
const int inf = 0x3f3f3f3f;

int n, a[max_N], dp[3][max_N][max_N >> 1];

inline void updt(int &x, int a) { x = std::min(x, a); }

int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; ++i) scanf("%d", a + i);
    // n = 5000;
    // for (int i = 1; i <= n; ++i) a[i] = 1;
    memset(dp, 0x3f, sizeof(dp));
    dp[0][0][0] = 0;
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j <= (i + 1) / 2; ++j) {
            for (int s = 0; s < 3; ++s) {
                int tmp = dp[s][i][j];
                if (tmp == inf) continue;
                updt(dp[s >> 1][i + 1][j], tmp);
                if (s != 2) {
                    int ht = (s == 1) ? std::min(a[i], a[i - 1] - 1) : a[i];
                    int ttmp = tmp + std::max(0, ht - a[i + 1] + 1);
                    if (i + 1 < n) ttmp += std::max(0, a[i + 2] - a[i + 1] + 1);
                    updt(dp[2][i + 1][j + 1], ttmp);
                }
            }
        }
    }
    for (int i = 1; i <= (n + 1) / 2; ++i) {
        int res = inf;
        for (int s = 0; s < 3; ++s) updt(res, dp[s][n][i]);
        printf("%d ", res);
    }
    return 0;
}

1010 A

题目大意：

有一个质量为\(m\)的飞船，要从星球\(1\)出发，依次经过星球\(2,\cdot,n\)再回到星球\(1\).

在星球\(i\)上起飞需要花费总质量（包括燃料质量）除以\(a_i\)单位的燃料，着陆需要花费总质量（包括燃料质量）除以\(b_i\)单位的燃料。

可以认为起飞和着陆的时间很短，当整个过程完成之后，燃料质量才一口气减少消耗的部分。

问至少要携带多少燃料（中途不可以补充），无解输出-1。

题解：

二分答案判断即可。

coding time: 5 min : 50 sec

dirt: 1：二分上界不要恰卡在最大可行范围。

#include <bits/stdc++.h>

const int max_N = 1000 + 21;

int n, m, a[max_N], b[max_N];

std::vector<int> vec;

bool check(double x) {
    for (auto w : vec) {
        double y = (m + x) / w;
        if (y > x) return false;
        x -= y;
    }
    return true;
}

int main() {
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; ++i) scanf("%d", a + i);
    for (int i = 1; i <= n; ++i) scanf("%d", b + i);
    vec.resize(n * 2);
    auto it = vec.begin();
    *it++ = a[1];
    for (int i = 2; i <= n; ++i) *it++ = b[i], *it++ = a[i];
    *it++ = b[1];
    double lo = 0, hi = 2e9, ans = -1;
    while (hi - lo > 1e-9) {
        double mi = (lo + hi) / 2;
        if (check(mi)) ans = hi = mi;
        else lo = mi;
    }
    if (ans > 0) printf("%.10f\n", ans);
    else puts("-1");
    return 0;
}

1010 C

题目大意:

给出\(n\le10^5\)个整数，每个整数可以用无数次，问在模\(k\le10^5\)意义下可以用和的形式凑出哪些数字。

题解：

由裴蜀定理，等价于用这个\(n\)个数的gcd的倍数去凑数字，\(O(n\log{A}+k)\).

coding time: 3 min : 36 sec

#include <bits/stdc++.h>

const int max_N = (int) 1e5 + 21;

int n, k, g, a[max_N], ans;

bool vis[max_N];

int main() {
    scanf("%d%d", &n, &k);
    for (int i = 1; i <= n; ++i) {
        scanf("%d", a + i);
        g = std::__gcd(g, a[i]);
    }
    g %= k;
    int x = g;
    while (!vis[x]) {
        vis[x] = true;
        ++ans;
        x = (x + g) % k;
    }
    printf("%d\n", ans);
    for (int i = 0; i < k; ++i) {
        if (!vis[i]) continue;
        printf("%d ", i);
    }
    return 0;
}

1010 D

题目大意：

给出一个\(n\le10^6\)个节点的二进制表达式树，运算符包括与、或、非和异或四种。

对于每一个叶子，问只有它取值改变后整个表达式的值是多少。

题解：

对于每一个运算符，如果它的一个儿子取值改变后会导致它的取值也改变，就连一条无向边，用并查集判断每个叶子是否与根连通即可，\(O(n)\).

coding time : 10 min : 45 sec

#include <bits/stdc++.h>

const int max_N = (int) 1e6 + 21;

int n, val[max_N], leaf[max_N], tot, f[max_N];

std::vector<int> vec[max_N];

char tp[max_N][5], ans[max_N];

int find(int x) {
    return x == f[x] ? x : f[x] = find(f[x]);
}

void merge(int u, int v) {
    f[find(u)] = find(v);
}

void dfs(int u) {
    if (*tp[u] == 'I') return;
    for (auto v : vec[u]) dfs(v);
    if (*tp[u] == 'N') {
        val[u] = !val[vec[u][0]];
        merge(u, vec[u][0]);
    } else {
        int l = vec[u][0], r = vec[u][1];
        if (*tp[u] == 'A') {
            val[u] = val[l] & val[r];
            if (val[l]) merge(u, r);
            if (val[r]) merge(u, l);
        } else if (*tp[u] == 'O') {
            val[u] = val[l] | val[r];
            if (!val[l]) merge(u, r);
            if (!val[r]) merge(u, l);
        } else {
            val[u] = val[l] ^ val[r];
            merge(u, l), merge(u, r);
        }
    }
}

int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; ++i) {
        f[i] = i;
        scanf("%s", tp[i]);
        if (*tp[i] == 'I') {
            scanf("%d", val + i);
            leaf[++tot] = i;
        } else {
            int sz = (*tp[i] == 'N') ? 1 : 2, x;
            while (sz--) {
                scanf("%d", &x);
                vec[i].push_back(x);
            }
        }
    }
    dfs(1);
    for (int i = 1; i <= tot; ++i) {
        ans[i - 1] = '0' + (find(leaf[i]) == find(1) ? !val[1] : val[1]);
    }
    ans[tot] = '\0';
    puts(ans);
    return 0;
}