CF Edu Round 37

A

Problem

有一个水池如下图, 有从$1$ 到 $n$ 共 $n$ 个槽. 其中有 $k$ 个被注满水. 如果打开阀门的话, 水会从该槽中流到相邻的两个槽. 一秒过后, 隔壁的两个槽都被注水. 我们假设在完整的一秒过后才会被注水, 而不考虑不到一秒的情况.

我们的Max想要同时打开所有的阀门, 现在他想知道全部水槽都被注水的最短时间.

CF920A

I/O

第一行输入一个整数 $t$, 需要解决的情况个数($1 \leq t \leq 200$).

接下来有 $t$ 个情况, 每个情况有两个整数, $n$ 和 $k$ ($1 \leq n \leq 200, 1 \leq k \leq n$), 水槽的数量和注水槽的数量.

接下来是 $k$ 个整数 $x_i$ ($1 \leq x_i \leq n$) 表示第 $i$ 个注水槽的位置.

保证对任意 $2 \leq i \leq k$, 有 $x_{i-1} < x_i$.


每个情况输出一个整数, 即最少需要的时间.

Solution

依照惯例, CF前几道都是水题, 由于除了两端, 整个水槽中任意的无水槽都是两端的有水槽注入进来, 为了代码简便, 我们假设在两头都加入一个有水槽, 它们的位置到两个端点使第一个(或最后一个)有水槽到两个端点的距离相等. 这样我们只需要遍历一遍, 找到最大的即可. 即一个$O(n)$的时间复杂度.

int main() {
    int t;  // test case
    scanf("%d", &t);
    int i = 0; // count
    while (i < t) {
        int n, k;
        scanf("%d %d", &n, &k);
        double *x;
        x = static_cast<double *>(malloc((k + 2) * sizeof(double)));
        for (int j = 1; j <= k; j++) {
            scanf("%lf", &x[j]);
        }
        double max_interval = 0;
        x[0] = -(x[1] - 1);
        x[k+1] = 2 * (n + 1) - x[k] - 1;

        for (int j = 1; j <= k + 1; ++j) {
            double temp_interval = ceil((x[j] - x[j-1] + 1) / 2.0);
            if (temp_interval > max_interval) {
                max_interval = temp_interval;
            }
        }
        free(x);
        printf("%d\n", (int)max_interval);
        i++;
    }
    return 0;
}

B

Problem

有 $n$ 个学生排队喝茶, 第 $i$ 个学生在 $l_i$ 秒到达队伍的末尾. 如果有几个学生在同一时刻到达, 则按照他们的编号, 大的在后面. 他们在队伍中是这样的: 如果他的前面没有人, 那么他就使用茶壶倒茶, 并在一秒后离开; 否则, 他就继续等待. 如果他在第 $r_i$ 秒仍然没有排到, 那么他就离开队伍. 计算每个学生在第几秒使用到茶壶倒茶.

I/O

第一行一个整数 $t$, 表示需要解决的问题情况数($1 \leq t \leq 1000$).

接下来有 $t$ 个情况, 每个的第一行是学生的数量 $n$ ($1 \leq n \leq 1000$).

接下来是 $n$ 行, 每行有两个整数 $l_i, r_i$, 表示第 $l_i$ 秒学生到达队伍和第 $r_i$ 秒学生离开队伍.

保证对每个 $2 \leq i \leq n$, 有 $l_{i-1} \leq l_i$.


对每个情况输出 $n$ 个整数, 即每个学生倒茶的时间, 如果没有就输出 $0$.

Solution

这道题也不难, 最朴素的算法就是稍微复杂了一点. 其实写完发现有没考虑到的情况, 所以像打补丁一样加上去导致整个代码逻辑有点乱. 首先来一个排队函数, 维护一个排队数组queue, queue[j] = i表示第 $i$ 个学生排在了第 $j$ 秒. 排完队以后我发现我还没解决超过等待时间半途走掉的情况😂 我们只好来遍历这个数组, 每次有人排队时, 向前找到第一个有人排队的某个时刻, 即queue[?] != 0. 那此时他的排队时刻就是上一个人时刻加一和他目前排到时刻的较大者. 将其与每个人的等待时间上限比较即可. emm, 时间复杂度最坏情况可能会有$O(n^2)$… ╮(╯▽╰)╭

int queue[10100];

void lineup(int l, int i) {
    int j = 0;
    while (queue[l+j] != 0) {
        j++;
    }
    queue[l+j] = i;
}

int main() {
    int t;  // test case
    scanf("%d", &t);
    int i = 0;  // count
    while (i < t) {
        int n;  // the no of students
        scanf("%d", &n);
        int l[5050], r[5050];   // the second come and leave
        for (int j = 1; j <= n; ++j) {
            scanf("%d %d", &l[j], &r[j]);
        }

        int output[5050];
        for (int j = 0; j < 10100; ++j) {
            queue[j] = 0;
        }
        for (int j = 0; j < 5050; ++j) {
            output[j] = 0;
        }

        for (int j = 1; j <= n; ++j) {
            lineup(l[j], j);
        }

        for (int j = 0; j < 10100; ++j) {
            if (queue[j] != 0) {
                int k = 1;
                while (queue[j - k] == 0 && (j - k > 0)) {
                    k++;
                }
                int pre = queue[j - k];
                int max = std::max(pre + 1, l[queue[j]]);
                if (max <= r[queue[j]]) {
                    output[queue[j]] = max;
                    queue[j] = max;
                } else {
                    queue[j] = 0;
                }
            }
        }

        for (int j = 1; j <= n; ++j) {
            printf("%d ", output[j]);
        }
        printf("\n");

        i++;
    }
    return 0;
}

C

Problem

交换相邻元素的问题, 一个数组有 $n$ 个整数, 每个整数从 $1$ 到 $n$ 有且仅有一次.(其实就是个 $1$ 到 $n$ 的排列啦)

对某些 $i$ ($1 \leq i \leq n-1$), 你能交换第 $i$ 个元素和第 $(i+1)$ 个元素.

请问能不能通过若干次交换后使其变成一个递增的数组.

I/O

第一行是一个整数 $n$ ($2 \leq n \leq 200000$), 即数组中元素的个数.

第二行包含 $n$ 个整数, $a_1, a_2, …, a_n$ ($1 \leq a_i \leq 200000$), 即数组的元素.

第三行包含一个 $(n-1)$ 个字符的字符串, 每一项是 $0$ 或 $1$. 如果第 $i$ 个字符为 $1$, 则表示可以交换第 $i$ 个元素和第 $(i+1)$ 个元素; 为 $0$ 则不能交换.


输出"YES”, 如果可以满足递增要求, 反之输出"NO”.

Solution

第三行能否交换的字符串, 把数组分成了一块一块, 在一块内是连续的, 可以经过交换满足递增的要求.

所以我们构建了两个数组, upperlower, 分别表示第 $i$ 位交换达到的最高和最低位置.

int main() {
    int n;
    scanf("%d", &n);
    int a[200010], upper[200010], lower[200010];
    char flag[200010];
    for (int i = 1; i <= n; ++i) {
        scanf("%d", &a[i]);
    }

    for (int i = 0; i <= n; ++i) {
        scanf("%c", &flag[i]);
    }
    for (int i = 1; i <= n; ++i) {
        upper[i] = 0;
        lower[i] = 0;
    }

    int j = 1;
    int min = 0, max = 0, f = 0;
    while (j <= n) {
        while (flag[j] == '1') {
            if (f == 0) {
                min = j;
            }
            j++;
            f = 1;
        }
        if (f != 0) {
            max = j;
            for (int k = min; k <= max; ++k) {
                lower[k] = min;
                upper[k] = max;
            }
            f = 0;
        } else {
            j++;
        }
    }

    int output = 1;
    for (int i = 1; i <= n; ++i) {
        if (lower[i] == 0 && upper[i] == 0) {
            if (a[i] != i) {
                output = 0;
            }
        } else {
            if (lower[i] > a[i] || upper[i] < a[i] ) {
                output = 0;
            }
        }
    }
    if (output == 0) {
        printf("NO");
    } else {
        printf("YES");
    }

    return 0;
}

D

Problem

我们的主人公Petya想要用水桶去浇水, 他有 $N$ 个水桶, 第 $i$ 个水桶有 $a_i$ 毫升的水. 我们假设这些水桶足够大, 能放下任意多的水.

当然Petya也有一个能容纳 $K$ 毫升的勺子(初始水量为零), 它可以用来在水桶间舀水. Petya从水桶中能的得到 $min(v, K)$ 的水, $v$ 是水桶中当前的水量.

请问是否有可能获得一个水桶刚好有 $V$ 毫升水? 可能的话输出每次的操作(任意一种即可).

I/O

第一行包含三个整数: $N$($2 \leq N \leq 5000$), $K$($1 \leq K \leq 5000$), $V$($0 \leq V \leq 10^9$). 分别是水桶数量, 勺子容量和最后需求的水.

第二行输出 $N$ 个整数: $a_i$($0 \leq a_i \leq 10^5$), $a_i$ 表示第 $i$ 个水桶的初始水量.


如果不存在可行解, 输出"NO”.

反之, 输出"YES”, 并从第二行开始, 输出如下格式的序列:

每行包含三个数字: “$cnt$ $x$ $y$”($1 \leq cnt \leq 10^9$, $1 \leq x, y \leq N$). $x$ 是得到水的水桶序号, $y$ 是舀出水的水桶序号, $cnt$ 是我们从水桶 $x$ 到 $y$ 的舀水次数.

Solution

这道题感觉很难, 我做了好几天, 现场也只有 34 个人AC了这道题(相比之下, A掉水题的最多有3k+)… 其实它并没有什么高深的数论知识, 只用到了一个完全剩余系, 甚至你可以不知道这个概念而把它DP出来. 接下来是动态规划的具体过程: 我们通过一个二维数组 m[i][j]来表示到第 $i$ 个水桶为止, 是否存在一个前 $i$ 个水桶的组合, 使其与 $j$ 模 $k$ 同余.

我们有如下两条规则:

  1. 前 $i$ 个水桶的排列满足的话, 前 $i+1$ 也满足.
  2. 前 $i$ 个水桶的排列满足与 $j$ 模 $k$ 同余的话, 前 $i+1$ 模 $k$ 与 $j + a[i+1] % k$ 同余. (同余的性质: $k + x \equiv (k + (x\ mod\ m)) mod\ m$ )

这样我们就简化成了一个复杂度为 $O(nk)$ 的动态规划问题.

然而问题远远没有解决, 对于存在可行解的情况, 我们还要输出其解决方案.

我们先找出数组中同余的最小 $i$ 值. 然后我们把问题简化成两个水桶, 即水桶1是目标最后要求的水桶, 其他都相当于在水桶2中. 在每次水桶1的水小于零时给其加水, 如果不够加也不可行; 同时构造一个计算次数的函数.

/*
 * n: the number of tanks
 * k: the maximum volume of water the scoop can contain
 * v: the required amount of water in some tank
 * a[i]: initial volume of water in i-th tank
 *
 * m[i][j]: up to i-th tank, exist a combination and j can congruent modulo k
 */

int n, k, v;
const int N = 5010;
int a[N];
int m[N][N];

/*
 * x: the index of the tank where we get water
 * y: the index of the tank where we pour water
 */
int count(int x, int y) {
    int cnt = a[x] / k;
    if (a[x] % k != 0) {
        cnt++;
    }
    a[y] += a[x];
    a[x] = 0;
    return cnt;
}

struct Node {
    int cnt, x, y;
} ans[N];

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

    m[0][0] = true;
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < k; ++j) {
            if (m[i][j]) {
                m[i+1][j] = true;
                m[i+1][(j+(a[i+1])%k)%k] = true;
            }
        }
    }

    if (!m[n][v%k]) {
        printf("NO\n");
        return 0;
    }

    vector<int> sequence;
    int res = v % k;
    for (int i = n; i > 0; --i) {
        if (m[i-1][res]) {
            continue;
        }
        sequence.push_back(i);
        res -= a[i] % k;
        if (res < 0) {
            res += k;
        }
    }

    /*
     * tank1: a[tank1] = v (mod k)
     * tank2: a[tank1] + a[tank2] = total
     */
    int tank1, tank2 = -1;
    int cur = 0;
    if (sequence.empty()) {
        ans[++cur] = (Node){count(1,2), 1, 2};
        tank1 = 1;
    } else {
        tank1 = sequence[0];
    }
    for (int i = 1; i < sequence.size(); ++i) {
        ans[++cur] = (Node){count(sequence[i], tank1), sequence[i], tank1};
    }
    for (int i = 1; i <= n; ++i) {
        if (i != tank1) {
            tank2 = i;
            break;
        }
    }
    for (int i = 1; i <= n; ++i) {
        if ((i != tank1) && (i != tank2) && a[i]) {
            ans[++cur] = (Node){count(i, tank2), i, tank2};
        }
    }
    if (a[tank1] < v) {
//        printf("%d %d %d %d\n", tank1, tank2, a[tank1], a[tank2]);
        int gap = (v - a[tank1]) / k;
        int cnt = min(a[tank2] / k, gap);
        if (cnt < gap) {
            printf("NO\n");
            return 0;
        }
        ans[++cur] = (Node){cnt, tank2, tank1};
        a[tank1] += cnt * k;
        a[tank2] -= cnt * k;
    } else if (a[tank1] > v) {
//        printf("%d %d %d %d\n", tank1, tank2, a[tank1], a[tank2]);
        int gap = (a[tank1] - v) / k;
        ans[++cur] = (Node){gap, tank1, tank2};
    }
    printf("YES\n");
    for (int i = 1; i <= n; ++i) {
        if (ans[i].cnt) {
            printf("%d %d %d\n", ans[i].cnt, ans[i].x, ans[i].y);
        }
    }

    return 0;
}

E

Problem

这是一道求连通块数的问题. 一个无向图有 $n$ 个顶点和 $\frac{n(n-1)}{2} - m$ 条边. 不是给你已经存在的边, 题目给出的是 $m$ 对 ($x, y$) 表示点 $x$ 和 $y$ 间没有边. 输出全连通图被割边以后的连通块个数及每个连通块的顶点数.

I/O

第一行包含两个整数 $n$, $m$ ($1 \leq n \leq 200000$, $0 \leq m \leq min(\frac{n(n-1)}{2}, 200000)$).

接下来 $m$ 行输出没有边的点对 ($x, y$).($1 \leq x, y \leq n, x \neq y$)


输出图的连通块个数 $k$, 并非降序输出每个连通块的顶点数.

Solution

这道题踩了很多坑, 这是第一个版本, 尝试用并查集配合路径压缩来解决这个问题.

开始是保存图的信息的时候由于太大超过了空间限制.

后来仅仅保存被割掉的边的信息, 每次遍历时去查找, 果不其然地超时了, 虽然同样是求连通块个数, 这种逆向割边会把限制卡的很紧, 挣扎之后我放弃了并查集的做法, 尸体如下.

const int N = 200010;
int n, m;

int father[N];
map<int, vector<int>> cutEdge;

int getFather(int x) {
    if (father[x] != x) {
        father[x] = getFather(father[x]);
    }
    return father[x];
}

int main() {
    scanf("%d %d", &n, &m);
    int a, b;
    
   	for (int i = 1; i <= n; ++i) {
       	father[i] = i;
   	}
   	for (int i = 0; i < m; ++i) {
       	scanf("%d %d", &a, &b);
       	if (a < b) {
            swap(a, b);
       	}
       	cutEdge[a].push_back(b);
   	}

    for (int i = 1; i <= n; ++i) {
        int tmpFather = getFather(i);
        for (int j = 1; j < i; ++j) {
            if (find(cutEdge[i].begin(), cutEdge[i].end(), j) == cutEdge[i].end()) {
                if (tmpFather != getFather(j)) {
                    father[getFather(j)] = tmpFather;
                }
            }
        }
    }

    map<int, int> edges;
    for (int i = 1; i <= n; ++i) {
        edges[getFather(i)] += 1;
    }
    vector<int> ans;
    ans.reserve(edges.size());
    for (auto &edge : edges) {
        ans.push_back(edge.second);
    }

    printf("%lu\n", ans.size());
    sort(ans.begin(), ans.end());
    for (int &an : ans) {
        printf("%d ", an);
    }
    printf("\n");
    
    return 0;
}

于是我换了一个新的思路. 对图中的每个点, 手动通过BFS查找它的连通块, 由于点会比较多, 我们使用双向链表来降低复杂度$O(V+E)$, 并且及时剪枝: 在原图中每个点最大的枚举次数等于它的度, 及时在枚举完后删除这个点.

const int N = 200010;
int n, m;

bool visited[N];
bool visiting[N];
vector<int> vertices[N];
vector<int> ans;

struct Node {
    int prev, next;
} nodes[N];

void del(int x) {
    nodes[nodes[x].prev].next = nodes[x].next;
    nodes[nodes[x].next].prev = nodes[x].prev;
}

void bfs(int vertex) {
    visited[vertex] = true;
    queue<int> waiting;
    waiting.push(vertex);
    int cnt = 0;
    while (!waiting.empty()) {
        int cur = waiting.front();
        cnt++;
        waiting.pop();
        for (auto v: vertices[cur]) {
            visiting[v] = true;
        }
        for (int i = nodes[0].next; i != 0; i = nodes[i].next) {
            if (!visiting[i] && !visited[i]) {
                waiting.push(i);
                del(i);
                visited[i] = true;
            }
        }
        for (auto v: vertices[cur]) {
            visiting[v] = false;
        }
    }
    ans.push_back(cnt);
}

int main() {
    scanf("%d %d", &n, &m);
    int a, b;

    for (int i = 0; i < m; ++i) {
        scanf("%d %d", &a, &b);
        vertices[a].push_back(b);
        vertices[b].push_back(a);
    }

    for (int i = 1; i <= n; ++i) {
        nodes[i].prev = i - 1;
        nodes[i-1].next = i;
    }
    nodes[n].next = 0;

    for (int i = 1; i <= n; ++i) {
        if (!visited[i]) {
            bfs(i);
        }
    }
    
    sort(ans.begin(), ans.end());
    printf("%lu\n", ans.size());
    for (auto &itr: ans) {
        printf("%d ", itr);
    }
    printf("\n");
    
    return 0;
}

后记

emm, 还有F和G没做, 放假实在是太躺了, 再说吧 :)

假装做完了…

CF37

Reference

https://github.com/zjzsliyang/Charms

http://codeforces.com/contest/920

http://codeforces.com/blog/entry/57516

http://blog.csdn.net/Yancy_/article/details/79256048

Avatar
Yang Li
@zjzsliyang