Codeforces Round #630 (Div. 2) 题解

历史记录

清除记录

猜你想搜

AcWing热点
App
登录/注册

Codeforces Round #630 (Div. 2) 题解

作者：

逆乾 , 2020-04-08 20:54:37 , 所有人可见 , 阅读 1220

A. Exercising Walk

以 $x$ 的移动为例，令 $dis = x2 - x1$ ，那么当它累积向左移动 $dis$ 步，同时累积向右移动 $dis$ 步时就会回到起始点，所以我们可以先将所有能够回到起始点的步数都减掉，使得所需要向左移动的步数以及向右移动的步数中，至少有一个的范围在 $dis$ 以内。

此时就可以用 if else 判断，先向左移动几步，再向右移动几步，…，是否出界。由于至少有一侧的移动步数是小于 $dis$ 的，所以讨论的情况并不多，只是细节需要考虑清楚。

#include <bits/stdc++.h>

using namespace std;

bool check(int p, int l, int r, int a, int b, int dis)
{
    if (a <= p - l) {
        p -= a;
        return b <= r - p;
    }
    a -= p - l;
    if (b <= dis)
        return a <= b;
    b -= dis;
    return a <= dis && b <= a;
}

int main()
{
    int T;
    cin >> T;
    while (T--) {
        int a, b, c, d;
        cin >> a >> b >> c >> d;
        int x, y, x1, y1, x2, y2;
        cin >> x >> y >> x1 >> y1 >> x2 >> y2;
        int dis = x2 - x1, s;
        if (dis)
            s = min(a / dis, b / dis);
        else
            s = 0;
        a -= s * dis, b -= s * dis;
        if (check(x, x1, x2, a, b, dis)) {
            dis = y2 - y1;
            if (dis)
                s = min(c / dis, d / dis);
            else
                s = 0;
            c -= s * dis, d -= s * dis;
            if (check(y, y1, y2, c, d, dis))
                cout << "YES" << endl;
            else
                cout << "NO" << endl;
        } else
            cout << "NO" << endl;
    }
    return 0;
}

B. Composite Coloring

当几个数都是同一个质数的倍数时，它们就可以被涂上相同的颜色。

而题目又保证了颜色数量在 $11$ 以内一定存在解，所以我们可以先把 $1000$ 以内的质数筛出来（数据范围比较小，也不需要用线性筛），然后对于每个质数，再找它的倍数，如果这个倍数在原数组中且未被染色，就涂上一个新的颜色，最后输出颜色数组即可。

#include <bits/stdc++.h>

using namespace std;

const int N = 1010;
int n;
int a[N];
unordered_set<int> exist;
unordered_map<int, int> color;
bool vis[N];

void init()
{
    for (int i = 2; i < N; i++)
        if (!vis[i])
            for (int j = 2; i * j < N; j++)
                vis[i * j] = true;
    return;
}

int main()
{
    init();
    int T;
    cin >> T;
    while (T--) {
        exist.clear();
        color.clear();
        cin >> n;
        for (int i = 1; i <= n; i++) {
            cin >> a[i];
            exist.insert(a[i]);
        }
        int c = 0;
        for (int i = 2; i < N && c <= 10; i++)
            if (!vis[i]) {
                bool find = false;
                for (int j = 1; i * j < N; j++)
                    if (exist.count(i * j) && !color.count(i * j)) {
                        if (!find) {
                            c++;
                            find = true;
                        }
                        color[i * j] = c;
                    }
            }
        cout << c << endl;
        for (int i = 1; i <= n; i++)
            cout << color[a[i]] << ' ';
        cout << endl;
    }
    return 0;
}

C. K-Complete Word

我们来考虑建立这样一张图：

将字符串中的 $n$ 个下标当做点，最终需要变为同一个字母的两个下标之间连一条无向边，由于具有传递性，所以只需要已判定的相同字母的下标集合中的任意一点，与新加入的点连边即可。

建完图之后就可以发现，所有需要出现相同字母的下标之间一定直接或者间接有边相连，否则的话，两个字母可以相同也可以不同。即：这张图上会出现若干个连通块。

对于每一个连通块，记录一下连通块中点的数量以及连通块中每个字母出现的次数，想要改变的次数最少，就是取该连通块中本就存在的字母数量最多的字母，让其它的字母全都变为该字母的操作次数。

最终将每个连通块的操作次数相加即为答案。

#include <bits/stdc++.h>

using namespace std;

const int N = 2e5 + 5, M = 8e5 + 5;
int n, k, res;
int cnt[30];
char str[N];
int h[N], e[M], ne[M], idx;
bool vis[N];

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

void init()
{
    if (idx) {
        for (int i = 0; i < idx; i++)
            h[i] = -1;
        idx = 0;
    } else
        memset(h, -1, sizeof h);
    for (int i = 1; i <= n; i++)
        vis[i] = false;
    return;
}

void dfs(int u)
{
    vis[u] = true;
    cnt[str[u] - 'a']++;
    for (int i = h[u]; ~i; i = ne[i]) {
        int j = e[i];
        if (vis[j])
            continue;
        dfs(j);
    }
    return;
}

int main()
{
    int T;
    scanf("%d", &T);
    while (T--) {
        cin >> n >> k >> str + 1;
        init();
        for (int i = 1, j = n; i < j; i++, j--)
            add(i, j), add(j, i);
        for (int i = 1; i <= k; i++)
            for (int j = i + k; j <= n; j += k)
                add(i, j), add(j, i);
        res = 0;
        for (int i = 1; i <= n; i++)
            if (!vis[i]) {
                memset(cnt, 0, sizeof cnt);
                dfs(i);
                int sum = 0, val = 0;
                for (int i = 0; i < 26; i++) {
                    sum += cnt[i];
                    val = max(val, cnt[i]);
                }
                res += sum - val;
            }
        printf("%d\n", res);
    }
    return 0;
}

D. Walk on Matrix

在样例 $2$ 的启发下，我们能否构造出这样一组解，使得 $(n, m - 1)$ 从上方转移的值为 $k$ ，从左侧转移的值大于 $k$ ，但是和 $k$ 进行与运算之后的结果为 $0$ .

矩阵中数的范围为 $3 \cdot 10^5$ ，而 $k$ 的数据范围只有 $10^5$ ，所以一定存在一个数 $t$ ，使得 $10^5 < 2^t < 3 \cdot 10^5$ ，我们就来构造如下矩阵（令 $val = 2^t$ ）：

val + k       k      0 
   val        k      0 
   val     val + k   k

此时 $(3, 2)$ 这个点从上方转移的话，值为 $k$ ；从左侧转移的话，值为 $val$ ；而 $val > k$ ，所以 $dp[3][3] = val$ ，又因为 $val \ \& \ k = 0$ ，所以 $(3, 3)$ 这个点从左侧转移的话值为 $0$ ，而从上方转移值也为 $0$ 。因此，根据题目所给代码得到的 $dp[3][3]$ 结果为 $0$ ，而实际上， $(3, 2)$ 这个点选择从上方转移，再转移到 $(3, 3)$ 的话，最终的值为 $k$ 。 $k - 0 = k$ ，正好满足题意要求。

综上，只需要找到一个 $val$ ，使得 $val + k \leq 3 \leq 10^5$ ，然后不论输入的 $k$ 是多少，直接输出该矩阵即可。

#include <bits/stdc++.h>

using namespace std;

const int val = 1 << 17;
int k, a[5][5];

int main()
{
    cin >> k;
    a[1][1] = a[3][2] = val + k;
    a[2][1] = a[3][1] = val;
    a[1][2] = a[2][2] = a[3][3] = k;
    cout << 3 << ' ' << 3 << endl;
    for (int i = 1; i <= 3; i++) {
        for (int j = 1; j <= 3; j++)
            cout << a[i][j] << ' ';
        cout << endl;
    }
    return 0;
}

E. Height All the Same

只使用操作 $1$ 的话，我们总能把格子上方块的数量变成只相差一个或者直接相等：

若初始的各个格子方块的数量的奇偶性相同，则通过操作 $1$ 总能使格子上方块的数量同时达到某一个值。
若初始的各个格子方块的数量的奇偶性不同，则通过操作 $1$ 总能使格子上方块的数量两两直接相同或者只相差 $1$ 个。

只使用操作 $2$ 的话，我们总能改变两个格子上方块数量各自的奇偶性，例如用操作 $2$ 变换这些格子： $(m_1, m_2), (m_2, m_3), …, (m_{k - 1}, m_k)$ ，除了 $m_1, m_k$ 上方块数量只增了 $1$ ，改变了数量的奇偶性之外，中间的所有格子上方块的数量都增加了 $2$ ，不改变奇偶性；而如果在操作之前， $m_1, m_k$ 上的方块数量相等，中间各个格子的方块数量相等且比 $m_1, m_k$ 的方块数量多 $1$ ，则经过这个操作之后，再在 $m_1, m_k$ 上各自执行一次操作 $1$ ，这条路径上的方块个数就会相等。

受此启发，不难发现，如果初始方块个数是偶数的格子数量也是偶数个，则它们之间可以两两通过上述方式改变，最终使得每个格子上方块的数量相同，而当 $n \cdot m$ 是奇数时，我们总能变化成该情况，即此时无论初始状态是什么，最终都可以将各个格子上方块的数量变成相等的个数。

接下去讨论 $n \cdot m$ 为偶数的情况，假设 $[L, R]$ 区间内奇数有 $odd$ 个，偶数有 $even$ 个，此时若要从中挑选 $i$ 个格子填偶数，则应有如下数量的填法：
$even^i \cdot odd ^{n \cdot m - i} \cdot C_{n \cdot m}^{i}$
因此，我们分别取 $i$ 为 $even$ 以内的偶数，累加起来就是答案数量，即：
$\sum_{i = 0}^{\frac{n \cdot m}{2}}{even^{2 \cdot i} \cdot odd^{n \cdot m - 2 \cdot i} \cdot C_{n \cdot m}^{2 \cdot i}}$
而
$(even + odd)^{n \cdot m} = \sum_{i = 0}^{\frac{n \cdot m}{2}}{even^{2 \cdot i} \cdot odd^{n \cdot m - 2 \cdot i} \cdot C_{n \cdot m}^{2 \cdot i}} + \sum_{i = 1}^{\frac{n \cdot m}{2}}{even^{2 \cdot i - 1} \cdot odd^{n \cdot m - (2 \cdot i - 1)} \cdot C_{n \cdot m}^{2 \cdot i - 1}}$

$(even - odd)^{n \cdot m} = \sum_{i = 0}^{\frac{n \cdot m}{2}}{even^{2 \cdot i} \cdot odd^{n \cdot m - 2 \cdot i} \cdot C_{n \cdot m}^{2 \cdot i}} - \sum_{i = 1}^{\frac{n \cdot m}{2}}{even^{2 \cdot i - 1} \cdot odd^{n \cdot m - (2 \cdot i - 1)} \cdot C_{n \cdot m}^{2 \cdot i - 1}}$

这两式相加即为答案的两倍，而中间过程取模之后可能改变奇偶性，而 $mod + 1$ 是偶数，且对 $mod$ 取模之后为 $1$ ，所以可以将答案乘上 $mod + 1$ 再除以 $2$ 来得到最终的结果。

#include <bits/stdc++.h>

using namespace std;

typedef long long LL;
const int mod = 998244353;

LL quickpow(LL a, LL b)
{
    LL res = 1;
    while (b) {
        if (b & 1)
            res = res * a % mod;
        a = a * a % mod;
        b >>= 1;
    }
    return res;
}

int main()
{
    LL n, m, l, r;
    cin >> n >> m >> l >> r;
    if (n * m % 2)
        cout << quickpow(r - l + 1, n * m) << endl;
    else {
        LL odd, even;
        if (l & 1) {
            odd = r - l + 1 + 1 >> 1;
            even = r - l + 1 - odd;
        } else {
            even = r - l + 1 + 1 >> 1;
            odd = r - l + 1 - even;
        }
        cout << (quickpow(odd + even, n * m) + quickpow(even - odd, n * m)) * (mod + 1) / 2 % mod << endl;
    }
    return 0;
}

F. Independent Set

对于每一种合法的方案，都可以对应成：将这种方案中的独立集中的点染上色，然后把其余所有点、边都加进来，但是其余点都不染色的方案。

因此我们来考虑如下动态规划： $dp[i][0]$ 表示只考虑以 $i$ 为根的子树，且 $i$ 这个点未被染色的所有方案数； $dp[i][1]$ 表示只考虑以 $i$ 为根的子树，且 $i$ 这个点被染色的所有方案数，由于每一条边的选与不选也会对答案产生影响，所以再定义一个 $f[i]$ 表示删除 $i$ 这个点与其儿子节点的边的方案数。

现假设我们需要计算 $i$ 这个节点的上述三个值，而当前从 $j$ 这个儿子节点回溯：

首先，对于一个节点有多个不同的儿子的时候，每个儿子节点为根的子树的选择方案都不会影响其它儿子，所以不断将答案累乘即可。
对于 $dp[i][0]:$ 在不选择 $i -> j$ 这条边的情况下， $j$ 可以染色也可以不染色，只是当 $j$ 染色的情况下， $j$ 连向其儿子节点的边就至少得选一条，否则的话 $j$ 这个点将孤立，而题意中最后挑选的独立集中的点不可能是孤立点，所以需要减去 $f[j]$ ，因此该情况的方案数为： $dp[j][0] + dp[j][1] - f[j]$ ；在选择 $i->j$ 这条边的情况下， $j$ 也可以选择染色与不染色，该情况方案数为： $dp[j][0] + dp[j][1]$ .
对于 $dp[i][1]:$ 在不选择 $i->j$ 这条边的情况下，与 $dp[i][0]$ 同理，该情况方案数为： $dp[j][0] + dp[j][1] - f[j]$ ；在选择 $i->j$ 这条边的情况下， $j$ 这个点就不能再被染色，因此方案数为： $dp[j][0]$ .
对于 $f[i]:$ 与 $dp[i][0]$ 不选择 $i->j$ 这条边的情况同理，方案数为： $dp[j][0] + dp[j][1] - f[j]$ .

只需要在 $DFS$ 过程中维护这三个值即可，注意中间过程很容易爆 $int$ .

至于最终的答案，不妨设根节点为 $1$ ，根节点可以选择染色也可以不染色，而当根节点染色时，其连向儿子的边至少得有一条，不然根节点就会被孤立（跟上文同理），因此方案数为： $dp[1][0] + dp[1][1] - f[1]$ ，只是需要注意的是，有一种特殊情况也被包含进了该方案数中，即：一条边都不选，一个点都不染色。该情况是不满足题意的，因为题目要求选出的边不能为空集，所以，只需要将这种情况减掉，就是我们最终答案，即： $dp[1][0] + dp[1][1] - f[1] - 1$ .

#include <bits/stdc++.h>

using namespace std;

const int N = 3e5 + 5, M = 6e5 + 5, mod = 998244353;
int n;
int h[N], e[M], ne[M], idx;
int f[N], dp[N][2];

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

void dfs(int u, int fa)
{
    dp[u][0] = dp[u][1] = f[u] = 1;
    for (int i = h[u]; ~i; i = ne[i]) {
        int j = e[i];
        if (j == fa)
            continue;
        dfs(j, u);
        dp[u][0] = dp[u][0] * (((2ll * dp[j][0] + 2 * dp[j][1] - f[j]) % mod + mod) % mod) % mod;
        dp[u][1] = dp[u][1] * (((2ll * dp[j][0] + dp[j][1] - f[j]) % mod + mod) % mod) % mod;
        f[u] = 1ll * f[u] * (((dp[j][0] + dp[j][1] - f[j]) % mod + mod) % mod) % mod;
    }
    return;
}

int main()
{
    scanf("%d", &n);
    memset(h, -1, sizeof h);
    for (int i = 1; i < n; i++) {
        int u, v;
        scanf("%d %d", &u, &v);
        add(u, v);
        add(v, u);
    }
    dfs(1, -1);
    printf("%lld\n", ((1ll * dp[1][0] + dp[1][1] - f[1] - 1) % mod + mod) % mod);
    return 0;
}

G. No Monotone Triples

一开始写了个线段树来维护，测完样例之后发现看漏了题目的约束条件，然后，然后，然后就，好像，对于蒟蒻而言不太可做了？（等以后变强了再补，~~如果还记得的话~~

0 评论

App 内打开