鹏鹏的算法博客

学习...学习..学习.



Codeforces Round #576 Div.1 解题报告

题目地址:https://codeforces.com/contest/1198
题解地址:https://codeforces.com/blog/entry/68812


A. MP3

需要存储n个数,共有I字节的空间。选择一个区间[l, r],在这个区间外的数都会被置为边界。如果有K个不同的数,则每个数需要\( \lceil log_2{K} \rceil \)个比特位。问在满足空间大小的情况下,最少需要重置几个数。
问题就是在求一个最合适的区间[l, r],而这个l和r肯定是这些数里的两个,我们就可以先枚举这个l。
输入n个数到数组a,先排序,再去除重复的数到数组b,不重复的数个数记为m。l就在b中从小到大枚举,而r就在l之后的数里面找。这里可以用二分查找在[l, m]来找这个r。
二分出一个r,此时K=r-l+1,如果此时每个数需要的空间乘上数的个数n,不超过总空间,则合法,此时可以在a中二分找b[l]和b[r]的位置,就能知道总共需要重置几个数,也就是当前的答案,记录下来。显然,区间越大,所需要的空间越大,那么此时我们可以扩大区间,把二分区间取右边,扩大r。
如果空间不足,说明要缩小区间,则r到左半边继续查找。
这样当l枚举完以后,就能知道最小的答案了。

#include <cstdio>
#include <algorithm>
#include <cmath>
using namespace std;

const int N = 400000 + 10, INF = 1000000000;

int n, I, a[N], b[N], m;

int count(int l, int r) {
    int pl = lower_bound(a + 1, a + n + 1, l) - a, pr = upper_bound(a + 1, a + n + 1, r) - a;
    return pl - 1 + n - pr + 1;
}

int main() {

    scanf("%d%d", &n, &I);
    for (int i = 1; i <= n; ++i) {
        scanf("%d", &a[i]);
    }

    sort(a + 1, a + n + 1);
    a[0] = -1;
    for (int i = 1; i <= n; ++i) {
        if (a[i] != a[i - 1]) b[++m] = a[i];
    }

    if (m == 1) {
        printf("0");
        return 0;
    }

    int ans = INF;

    for (int l = 1; l <= m; ++l) {
        int left = l, right = m, r;
        while (left <= right) {
            r = left + right >> 1;
            if ((long long)(ceil(log2(r - l + 1))) * n > (long long)I * 8) {
                right = r - 1;
            }
            else {
                left = r + 1;
                ans = min(ans, count(b[l], b[r]));
            }
        }
    }

    printf("%d", ans);

    return 0;
}

B. Welfare State

给n个数,q个操作。操作有两种,一种是1 q x,将第q个数修改为x;另一种是2 x,将所有小于x的数修改为x。求操作完成后的序列。
很显然的算法是用线段树,单点和区间修改以及单点查询。需要加上lazy标签,代表要将整个区间的小于lazy的数修改为lazy。和普通线段树的区别是,这个地方把lazy往下推的时候,是需要和子节点的lazy和value取最大值的。另外就是裸线段树了,

#include <bits/stdc++.h>
using namespace std;

const int N = 200000 + 10;

class SegTree {
private:
    struct Node {
        int l, r, val, lazy;
    } tree[N * 4];
    int ls(int u) { return u << 1; }
    int rs(int u) { return u << 1 | 1; }
    void getmax(int &a, int b) { if (a < b) a = b; }
public:
    void build(int now, int l, int r) {
        tree[now] = (Node){l, r, 0, 0};
        if (l == r) return;
        int mid = l + r >> 1;
        build(ls(now), l, mid);
        build(rs(now), mid + 1, r);
    }
    void pushdown(int now) {
        if (!tree[now].lazy) return;
        if (tree[now].l != tree[now].r) {
            getmax(tree[ls(now)].lazy, tree[now].lazy);
            getmax(tree[rs(now)].lazy, tree[now].lazy);
            getmax(tree[ls(now)].val, tree[now].lazy);
            getmax(tree[rs(now)].val, tree[now].lazy);
        }
        tree[now].lazy = 0;
    }
    void update(int now, int l, int r, int k) {
        pushdown(now);
        if (tree[now].l == tree[now].r) { getmax(tree[now].val, k); return; }
        if (tree[now].l == l && tree[now].r == r) { getmax(tree[now].lazy, k); getmax(tree[now].val, k); return; }
        int mid = tree[now].l + tree[now].r >> 1;
        if (mid >= r) update(ls(now), l, r, k);
        else if (mid + 1 <= l) update(rs(now), l, r, k);
        else update(ls(now), l, mid, k), update(rs(now), mid + 1, r, k);
    }
    void update(int now, int x, int k) {
        pushdown(now);
        if (tree[now].l == tree[now].r) { tree[now].val = k; return; }
        int mid = tree[now].l + tree[now].r >> 1;
        if (x <= mid) update(ls(now), x, k);
        else update(rs(now), x, k);
    }
    int query(int now, int x) {
        pushdown(now);
        if (tree[now].l == tree[now].r) return tree[now].val;
        int mid = tree[now].l + tree[now].r >> 1;
        if (x <= mid) return query(ls(now), x);
        else return query(rs(now), x);
    }
} segTree;

int main() {

    int n, a, q;
    scanf("%d", &n);
    segTree.build(1, 1, n);
    for (int i = 1; i <= n; ++i) {
        scanf("%d", &a);
        segTree.update(1, i, a);
    }

    scanf("%d", &q);
    while (q--) {
        int op, p, x;
        scanf("%d", &op);
        if (op == 1) {
            scanf("%d%d", &p, &x);
            segTree.update(1, p, x);
        }
        else {
            scanf("%d", &x);
            segTree.update(1, 1, n, x);
        }
    }

    for (int i = 1; i <= n; ++i) {
        printf("%d ", segTree.query(1, i));
    }

    return 0;

}

另一种算法是,先找出规律。假设对i位置进行了多次的单点修改,则只会有最后一次单点修改可能是最后的答案,并且,一次单点修改过后,之前的所有全体修改在这个点都失效了。所以我们只要记录某个点它最后一次单点修改是在第几个操作,然后再记录在这个操作之后的那些全体修改是否比这次单点修改要大,大的话则最后答案就是最大的那次全体修改,否则就是它最后一次单点修改。
用last[i]存i位置的最后一次单点修改,用payoff[i]存从第i个操作到最后,全体操作的最大值。在输入完q个操作后,就可以倒序初始化payoff数组,payoff[i]=max(payoff[i], payoff[i+1])。
完成后再看看每个数最后一次单点修改后的值,如果这个值比它这次操作以后出现的全体操作要小,则修改为全体操作的值。最后输出即可。

#include <bits/stdc++.h>
using namespace std;

#define read(a) scanf("%d", &a)

const int N = 200000 + 10;

int n, q, a[N], last[N], payoff[N];

int main() {

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

    read(q);
    for (int i = 1; i <= q; ++i) {
        int op, p, x;
        read(op);
        if (op == 1) {
            read(p);
            read(x);
            a[p] = x;
            last[p] = i;
        }
        else {
            read(x);
            payoff[i] = x;
        }
    }

    for (int i = q - 1; i >= 1; --i) {
        payoff[i] = max(payoff[i], payoff[i + 1]);
    }

    for (int i = 1; i <= n; ++i) {
        a[i] = max(a[i], payoff[last[i] + 1]);
        printf("%d ", a[i]);
    }

    return 0;

}

C. Matching vs Independent Set

给一张有3n个点m条边的图,找出n条互不共享顶点的边或者n个互不直接相连的点。
一开始看到这题,觉得是很难的图论题,我不知道该怎么求。
正解其实非常简单。独立的边要求没有相同的点,那么就可以枚举每一条边,如果这条边的两个顶点都没有被访问过,则加入这条边并且标记两个顶点访问过了,如果有任何一个顶点访问过了,则跳过。枚举完后如果加入的边数大于等于n则说明找到了答案,随便输出n条就可以了。如果不足n条,则说明能访问的点都访问完了,再也找不到不重复的直接相连的两个点了,那么剩下的那些点就都是不直接相连的点了。因为不足n条,顶点数不足2n,所以剩下的点数大于n,随便输出n个就可以了。

#include <bits/stdc++.h>
using namespace std;

#define read(a) scanf("%d", &a)

const int N = 300000 + 10;

int T, n, m, ans[N], len;
bool vis[N];

int main() {

    read(T);
    while (T--) {
        len = 0;
        memset(vis, false, sizeof(vis));
        read(n);
        read(m);
        for (int i = 1; i <= m; ++i) {
            int x, y;
            read(x);
            read(y);
            if (!vis[x] && !vis[y]) {
                vis[x] = vis[y] = true;
                ans[++len] = i;
            }
        }
        if (len < n) {
            len = 0;
            for (int i = 1; i <= 3 * n && len < n; ++i) {
                if (!vis[i]) {
                    ans[++len] = i;
                }
            }
            printf("IndSet\n");
        }
        else {
            printf("Matching\n");
        }
        for (int i = 1; i <= n; ++i) {
            printf("%d ", ans[i]);
        }
        printf("\n");
    }

    return 0;

}

D. Rectangle Painting 1

给一个n×n的矩阵,每个元素是黑或白。每次可以任意选择一个h×w的子矩阵,将这个子矩阵中的元素全部置为白色,代价为 \( max(h, w) \) 。问将整个矩阵都置为白色的最小代价。
容易想到是动态规划。用dp[x1][y1][x2][y2]表示将(x1, y1)-(x2, y2)这个矩阵全部置为白色的最小代价,用两重循环枚举这个子矩阵的大小,再用两重循环枚举这个子矩阵的左顶点,这样这个子矩阵就确定下来了,接下来两重循环在这个子矩阵中枚举每个点,这样就可以把这个矩阵分为四部分,将四部分的代价加起来去最小值即可。这样的时间复杂度为 \( O(n^{6}) \) ,显然是太高的。实际上我们没有必要将子矩阵分为四部分,用一重循环分为上下或左右两部分即可,时间复杂度为 \( O(n^{5}) \) 。这样的方法充分性应该可以这样说明:现在将一个矩阵分为上下两部分,那么之前两个子矩阵肯定是尝试过分为左右和上下两部分,所以也就相当于尝试过把当前这个矩阵分为四个部分了。
这个动态规划也可以写成记忆化搜索的形式,此时dp[x][y][h][w]含义为左顶点为(x, y)的h×w的矩阵的最小代价。
记忆化搜索:

#include <bits/stdc++.h>
using namespace std;

const int N = 50 + 5;

int n, dp[N][N][N][N];
char g[N][N];

int dfs(int x, int y, int h, int w) {
    if (dp[x][y][h][w] != -1) return dp[x][y][h][w];
    if (h == 1 && w == 1) return dp[x][y][h][w] = g[x][y] == '#';
    if (h == 0 || w == 0) return dp[x][y][h][w] = 0;
    dp[x][y][h][w] = max(h, w);
    for (int i = 0; i <= h; ++i) {
        dp[x][y][h][w] = min(dp[x][y][h][w], dfs(x, y, i, w) + dfs(x + i, y, h - i, w));
    }
    for (int j = 0; j <= w; ++j) {
        dp[x][y][h][w] = min(dp[x][y][h][w], dfs(x, y, h, j) + dfs(x, y + j, h, w - j));
    }
    return dp[x][y][h][w];
}

int main() {

    memset(dp, -1, sizeof(dp));

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

    printf("%d", dfs(1, 1, n, n));

    return 0;

}

动态规划:

#include <bits/stdc++.h>
using namespace std;

const int N = 50 + 5;

int n, dp[N][N][N][N];

int main() {

    memset(dp, 0x5f, sizeof(dp));

    cin >> n;
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= n; ++j) {
            char ch;
            cin >> ch;
            dp[i][j][i][j] = ch == '#';
        }
    }

    for (int h = 1; h <= n; ++h) {
        for (int w = 1; w <= n; ++w) {
            for (int x = 1; x + h - 1 <= n; ++x) {
                for (int y = 1; y + w - 1 <= n; ++y) {
                    int nx = x + h - 1, ny = y + w - 1;
                    dp[x][y][nx][ny] = min(dp[x][y][nx][ny], max(h, w));
                    for (int i = 1; i < h; ++i) {
                        dp[x][y][nx][ny] = min(dp[x][y][nx][ny], dp[x][y][x + i - 1][ny] + dp[x + i][y][nx][ny]);
                    }
                    for (int j = 1; j < w; ++j) {
                        dp[x][y][nx][ny] = min(dp[x][y][nx][ny], dp[x][y][nx][y + j - 1] + dp[x][y + j][nx][ny]);
                    }
                }
            }
        }
    }

    printf("%d", dp[1][1][n][n]);

    return 0;

}

E. Rectangle Painting 2

题意类似上题。n×n的矩阵,有m个黑的子矩阵,其他元素都是白的。一次操作可以把h×w的子矩阵置为白色,代价为 \( min(h, w) \) 。求最小代价。
这题和上题的区别在于代价是长宽的最小值。显然,肯定是直接一行或者一列这样的操作能达到最小值。
这里我们把每个黑点拆成两个点,分成两部分,左边是行,右边是列,如果左右有一条边,就表示某一行某一列是黑点。接下来就只需要在这个二分图里求最小顶点覆盖即可,每选一个点就表示对某一行或某一列进行操作。最小顶点覆盖的含义是,选出若干个点,使得每条边至少有一个顶点在这些点中。而求最小顶点覆盖也就是求最大匹配。
但是这题中,n有10亿,所以黑点的个数会很多,因为黑点都是一个个矩阵,所以可以对点进行压缩。我们这里直接把子矩阵的左下和右上顶点的坐标作为图的两部分。因为矩阵可能会有重叠,所以需要先排序再去重,重叠的部分,实际上就可以分为多个部分。
修改原先边的定义。左右两边的边,流量都设为INF,如果有边,表示有i行j列的矩阵是黑的,而这i就表示为源点到所有行的边的流量,j就表示为所有列到汇点的边的流量。这样只需要再跑一边最大流,就是答案了。
至于为什么这样做是对的,希望以后细致学习网络流以后能够明白。

#include <bits/stdc++.h>
using namespace std;

const int N = 500, INF = 1 << 30;

int n, m;
struct Rectangle {
    int x1, y1, x2, y2;
    void read() {
        scanf("%d%d%d%d", &x1, &y1, &x2, &y2);
    }
} rect[N];
int xx[N], yy[N];
int cntx, cnty;
int cap[N][N];
bool vis[N];

int SRC, TRGT;
int ans = 0, min_flow = INF;

int dfs(int x, int flow) {
    vis[x] = true;
    if (x == TRGT) return flow;
    for (int y = SRC; y <= TRGT; ++y) {
        if (vis[y]) continue;
        if (cap[x][y] < min_flow) continue;
        int cur_flow = dfs(y, min(flow, cap[x][y]));
        if (cur_flow > 0) {
            cap[x][y] -= cur_flow;
            cap[y][x] += cur_flow;
            return cur_flow;
        }
    }
    return 0;
}

int main() {

    scanf("%d%d", &n, &m);
    for (int i = 1; i <= m; ++i) {
        rect[i].read();
        xx[i * 2 - 1] = rect[i].x1;
        xx[i * 2] = rect[i].x2 + 1;
        yy[i * 2 - 1] = rect[i].y1;
        yy[i * 2] = rect[i].y2 + 1;
    }

    sort(xx + 1, xx + 2 * m + 1);
    sort(yy + 1, yy + 2 * m + 1);

    cntx = unique(xx + 1, xx + 2 * m + 1) - xx - 1;
    cnty = unique(yy + 1, yy + 2 * m + 1) - yy - 1;

    SRC = 0;
    TRGT = cntx + cnty + 1;

    for (int i = 1; i <= m; ++i) {
        int q = lower_bound(xx + 1, xx + cntx + 1, rect[i].x2 + 1) - xx;
        for (int x = lower_bound(xx + 1, xx + cntx + 1, rect[i].x1) - xx; x < q; ++x) {
            int p = lower_bound(yy + 1, yy + cnty + 1, rect[i].y2 + 1) - yy;
            for (int y = lower_bound(yy + 1, yy + cnty + 1, rect[i].y1) - yy; y < p; ++y) {
                cap[x][cntx + y] = INF;
            }
        }
    }

    for (int i = 1; i < cntx; ++i) {
        cap[SRC][i] = xx[i + 1] - xx[i];
    }
    for (int i = 1; i < cnty; ++i) {
        cap[cntx + i][TRGT] = yy[i + 1] - yy[i];
    }

    while (min_flow) {
        memset(vis, false, sizeof(vis));
        int cur_flow = dfs(SRC, INF);
        if (cur_flow > 0) ans += cur_flow;
        else min_flow >>= 1;
    }

    printf("%d", ans);
 
    return 0;

}

F. GCD Groups 2

给n个数,问是否能分成两个集合,每个集合的最大公约数都为1。能则输出划分方案。
偷瞄了别人的代码,看到了暴力的代码。于是自己也写了一个,结果超时了,呵呵原来是改数据了。
这里的暴力也是有一定的贪心的,x和y分别为两部分的最大公约数,a[i]为当前的数,如果x不等于1并且如果把当前数加进去,x会变,才会尝试去把当前数加到第一个集合里面,否则就加到y里面。有一个剪枝是,如果当前数加到两个集合以后,x和y都不变,那么就无所谓了,直接放x里。还有一个剪枝是如果数还没用完,而x和y都是1了,就直接退出,后面的数随便放哪个集合都可以。

#include <bits/stdc++.h>
using namespace std;

const int N = 100000 + 10;

int n, a[N], p[N];

int gcd(int a, int b) {
    int c;
    while (b > 0) {
        c = a % b;
        a = b;
        b = c;
    }
    return a;
}

bool dfs(int i, int x, int y) {
    if (x == 1 && y == 1) return true;
    if (i == n + 1) return false;
    int nx = gcd(x, a[i]), ny = gcd(y, a[i]);
    if (nx == x && ny == y) {
        p[i] = 1;
        return dfs(i + 1, x, y);
    }
    else{
        if (nx != x) {
            p[i] = 1;
            if (dfs(i + 1, nx, y)) return true;
        }
        if (ny != y) {
            p[i] = 2;
            if (dfs(i + 1, x, ny)) return true;
        }
    }
    return false;
}

int main() {

    scanf("%d", &n);
    for (int i = 1; i <= n; ++i) {
        scanf("%d", a + i);
    }

    if (dfs(2, a[1], 0)) {
        printf("YES\n");
        for (int i = 1; i <= n; ++i) {
            printf("%d ", p[i]? p[i]: 1);
        }
    }
    else {
        printf("NO");
    }

    return 0;

}

能AC的方法是随机。只要时间还没到,就每次随机一个序列的出现顺序,然后按照刚才暴力的方法依次放每个数,直到x和y都为1。如果时间到了还没找到答案,就认为无解。
从没用过随机算法的我真的震惊了,这样“瞎搞”居然也可以.....
打乱顺序是O(n),加数是O(n),总的就是O(n),那么在时限内能凑很多很多次,居然就能找到答案了嘤嘤嘤。tql

#include <bits/stdc++.h>
using namespace std;

const int N = 100000 + 10;

int n, a[N], p[N], t[N];

int main() {

    scanf("%d", &n);
    for (int i = 1; i <= n; ++i) {
        scanf("%d", a + i);
        p[i] = i;
    }

    while (clock() < 450) {
        random_shuffle(p + 1, p + n + 1);
        int x = 0, y = 0, tmp;
        for (int i = 1; i <= n; ++i) {
            if (x != 1 && (tmp = __gcd(x, a[p[i]])) != x) {
                x = tmp;
                t[p[i]] = 1;
            }
            else {
                y = __gcd(y, a[p[i]]);
                t[p[i]] = 2;
            }
        }
        if (x == 1 && y == 1) {
            printf("YES\n");
            for (int i = 1; i <= n; ++i) {
                printf("%d ", t[i]);
            }
            return 0;
        }
    }

    printf("NO\n");

    return 0;

}

正解好像是状压dp,英文题解我看不太懂.....(就算是中文我也不懂噗)

All numbers have no more than \( k=9 \) different prime divisors.
If there exist a solution, then for every number there exist a solution in which this number is in group of size not more than \( (k+1) \) , because all we have to do is to "kill" all prime numbers from this number, and to do it we only need one number for each prime.
If \( n \le 2(k+1) \) , we can try all the splits in time \( O(2^{n} (n + \log C)) \) .
Let's take two numbers which will be in different groups. How to do it? — let's take random pair. For fixed first number probability of mistake is no more than \( \frac{k}{n-1} \) . Now in each group we have to kill no more than k primes. Let's do subset DP — our state is what primes are still alive. This solution has complexity \( O(n 2^{2k}) \) .
But we actually don't need all \( n \) numbers. For each prime we can look at no more than \( 2k \) candidates which can kill it, because to kill all other primes we need strictly less numbers, and we will have a spare one anyways. Thus the solution has complexity \( O(2^{2k}k^{2} + nk) \) . We don't need factorization for any numbers except two chosen, and we can factorize them in \( O(\sqrt{C}) \) .

等以后有能力了再回来看正解。