@Dmaxiya 2019-01-15T19:59:04.000000Z 字数 9349 阅读 1193

Codeforces Round #531 (Div. 3)

Codeforces

Contests 链接：Codeforces Round #531 (Div. 3)
过题数：5
排名：176/9160

A. Integer Sequence Dividing

题意

给定一个整数 $n$ ，将 $[1,n]$ 以内所有的整数分到两个集合 $A$ 和 $B$ 中，每个整数只能被分到一个集合，要求两个集合中所有数字的和的差的绝对值最小，即： $|sum_A-sum_B|$ 的值最小，其中空集合内所有数字的和为 $0$ 。

输入

输入仅包含一个整数 $n~(1\leq n\leq2\times10^9)$ 。

输出

输出题目所求答案。

样例

输入
3
输出
0
提示
其中一种合法的分法是：令 $A=\{1,2\},B=\{3\}$ ，这样 $\|sum_A-sum_B\|=0$ 。

输入
5
输出
1
提示
其中一种合法的分法是：令 $A=\{1,3,4\},B=\{2,5\}$ ，这样 $\|sum_A-sum_B\|=1$ 。

输入
6
输出
1
提示
其中一种合法的分法是：令 $A=\{1,4,5\},B=\{2,3,6\}$ ，这样 $\|sum_A-sum_B\|=1$ 。

题解

通过多次枚举可以发现，如果 $n$ 是 $4$ 的整数倍，那么对于每 $4$ 个数字，就可以用 $a_1+a_4=a_2+a_3$ 将第 $1$ 个和第 $4$ 个分到一个集合中，剩下的分到另一个集合中，而对于 $n$ 不是 $4$ 的整数倍的情况，可以将多出来的 $x~(0<x<4)$ 个数按照 $n=1,2,3$ 时进行划分，就可以得到最小答案。

过题代码

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <cfloat>
#include <climits>
#include <iostream>
#include <string>
#include <vector>
#include <list>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <algorithm>
#include <bitset>
#include <sstream>
using namespace std;
#define LL long long
int n;
int ans[10] = {0, 1, 1, 0};
int main() {
    #ifdef Dmaxiya
    freopen("test.txt", "r", stdin);
    #endif // Dmaxiya
    ios::sync_with_stdio(false);
    while(scanf("%d", &n) != EOF) {
        printf("%d\n", ans[n % 4]);
    }
    return 0;
}

B. Array K-Coloring

题意

给定 $n$ 个整数 $a_1,a_2,\cdots,a_n$ 和 $k$ 种颜色，要求用这 $k$ 种颜色给所有整数上色，并且满足下面三个要求：

每个整数都必须要涂上一种颜色；

每种颜色至少要被涂上一次；

所有被颜色 $i$ 涂上的数字都必须是不同的。

若存在满足上述条件的涂色方案，则输出任意一种，否则输出 $NO$ 。

输入

第一行为两个整数 $n,k~(1\leq k\leq n\leq5000)$ ，第二行为 $n$ 个整数 $a_1,a_2,\cdots,a_n~(1\leq a_i\leq5000)$ 。

输出

如果不存在合法的解，则输出 $NO$ ，否则在第一行输出 $YES$ ，并在第二行给出任意一种合法的解，每种颜色用数字 $[1,k]$ 内的整数表示。

样例

输入
4 2 1 2 2 3
输出
YES 1 1 2 2
提示
$2~1~2~1$ 也是一种合法的涂色方案，当然也存在其他合法的涂色方案。

输入
5 2 3 2 1 2 3
输出
YES 2 1 1 2 1
提示
$1~1~1~2~2$ 也是一种合法的涂色方案，当然也存在其他合法的涂色方案。

输入
5 2 2 1 1 2 1
输出
NO

题解

若存在任意一个颜色出现的次数大于 $k$ ，则输出 $NO$ ，否则将每个数字 $x$ 出现的位置存在一个 vector<int> 数组的第 $x$ 个位置上，然后按下标从小到大遍历这个 vector<int> 数组，按 $[1,k]$ 的循环给所有位置上色。

过题代码

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <cfloat>
#include <climits>
#include <iostream>
#include <string>
#include <vector>
#include <list>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <algorithm>
#include <bitset>
#include <sstream>
using namespace std;
#define LL long long
const int maxn = 5000 + 100;
int x, n, k;
int ans[maxn];
vector<int> G[maxn];
int main() {
    #ifdef Dmaxiya
    freopen("test.txt", "r", stdin);
    #endif // Dmaxiya
    ios::sync_with_stdio(false);
    while(scanf("%d%d", &n, &k) != EOF) {
        for(int i = 0; i < maxn; ++i) {
            G[i].clear();
        }
        for(int i = 1; i <= n; ++i) {
            scanf("%d", &x);
            G[x].push_back(i);
        }
        int Index = 0;
        bool flag = true;
        for(int i = 0; i < maxn; ++i) {
            int len = G[i].size();
            if(len > k) {
                flag = false;
                break;
            }
            for(int j = 0; j < len; ++j) {
                int pos = G[i][j];
                ans[pos] = Index;
                Index = (Index + 1) % k;
            }
        }
        if(!flag) {
            printf("NO\n");
            continue;
        }
        printf("YES\n");
        for(int i = 1; i <= n; ++i) {
            if(i != 1) {
                printf(" ");
            }
            printf("%d", ans[i] + 1);
        }
        printf("\n");
    }
    return 0;
}

C. Doors Breaking and Repairing

题意

有两个人玩一个游戏，最开始有 $n$ 扇门，第 $i$ 扇门初始的耐久性为 $a_i$ ，你是先手，另一个人后手，每当你选择一扇门，可以将这扇门的当前耐久度 $b_i$ 改为 $\max(0,b_i+0)$ ，每当另一个人选择一扇门，若这扇门的当前耐久度不为 $0$ ，则可以将其修改为 $b_i+y$ ，你希望有最多的门的耐久度变为 $0$ ，而另一个人希望有最少的门的耐久度变为 $0$ ，两人都采取最优策略，问经过 $10^{100}$ 轮游戏之后，最多有多少扇门的耐久度变为 $0$ 。

输入

第一行为 $3$ 个整数 $n,x,y~(1\leq n\leq100,1\leq x,y\leq10^5)$ ，第二行有 $n$ 个整数 $a_1,a_2,\cdots,a_n~(1\leq a_i\leq10^5)$ 。

输出

输出题目所求答案。

样例

输入
6 3 2 2 3 1 3 4 2
输出
6

输入
5 3 3 1 2 4 2 3
输出
2

输入
5 5 6 1 2 6 10 3
输出
2

题解

若 $x>y$ ，则先手一定能将所有门的耐久度都变为 $0$ ，否则若先手破坏一道 $a_i>x$ 的门，后手就可以立即对第 $i$ 扇门进行修复，所以先手只能去破坏 $a_i\leq x$ 的门，而后手一定会去修复还没有被破坏的 $a_i\leq x$ 的门，所以先手最多只能破坏 $\lceil\frac{cnt}{2}\rceil$ 扇门，其中 $cnt$ 为 $a_i\leq x$ 的门的数量。

过题代码

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <cfloat>
#include <climits>
#include <iostream>
#include <string>
#include <vector>
#include <list>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <algorithm>
#include <bitset>
#include <sstream>
using namespace std;
#define LL long long
int n, x, y, num, cnt;
int main() {
    #ifdef Dmaxiya
    freopen("test.txt", "r", stdin);
    #endif // Dmaxiya
    ios::sync_with_stdio(false);
    while(scanf("%d%d%d", &n, &x, &y) != EOF) {
        cnt = 0;
        for(int i = 0; i < n; ++i) {
            scanf("%d", &num);
            if(num <= x) {
                ++cnt;
            }
        }
        if(x > y) {
            printf("%d\n", n);
            continue;
        } else {
            printf("%d\n", (cnt + 1) / 2);
        }
    }
    return 0;
}

D. Balanced Ternary String

题意

给定一个长度为 $n$ 的三元字符串，字符串中只包含三种字符：0 1 2，每次可以将字符串中的一个字符替换成另一个字符，要求替换最少的次数，使得这个三元字符串每种字符的个数相等，如果有多种答案，输出字典序最小的一种。

输入

第一行包含一个整数 $n~(3\leq n\leq3\times10^5,3|n)$ ，第二行为一个长度为 $n$ 的三元字符串。

输出

输出题目所求答案。

样例

输入
3 121
输出
021

输入
6 000000
输出
001122

输入
6 211200
输出
211200

输入
6 120110
输出
120120

题解

先统计字符 0 1 2 出现的次数 $cnt_{0,1,2}$ ，然后先从前往后确定所有 $0$ 的位置，若 $cnt_0\geq\frac{n}{3}$ ，则将前 $\frac{n}{3}$ 个 $0$ 标为 $true$ ，表示完全确定，并且不能更改，多出来的 0 为 $false$ ，表示可以更改，若 $cnt_0<\frac{n}{3}$ ，则将靠前的非 0 的 $cnt$ 值大于 $\frac{n}{3}$ 的字符改为 0，并修改相应的 $cnt$ 值，并将该位置标为 $true$ ，对于 1 和 2 也是如此。

过题代码

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <cfloat>
#include <climits>
#include <iostream>
#include <string>
#include <vector>
#include <list>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <algorithm>
#include <bitset>
#include <sstream>
using namespace std;
#define LL long long
const int maxn = 300000 + 100;
int n;
int cnt[3];
bool vis[maxn];
char str[maxn];
int id(char ch) {
    return ch - '0';
}
int main() {
    #ifdef Dmaxiya
    freopen("test.txt", "r", stdin);
    #endif // Dmaxiya
    ios::sync_with_stdio(false);
    while(scanf("%d%s", &n, str) != EOF) {
        int len = strlen(str);
        memset(cnt, 0, sizeof(cnt));
        for(int i = 0; i < len; ++i) {
            ++cnt[id(str[i])];
            vis[i] = false;
        }
        for(int i = 0; i < 3; ++i) {
            if(cnt[i] > n / 3) {
                int tmp = n / 3;
                for(int j = 0; j < len; ++j) {
                    if(str[j] == '0' + i) {
                        vis[j] = true;
                        --tmp;
                        if(tmp == 0) {
                            break;
                        }
                    }
                }
            } else {
                for(int j = 0; j < len; ++j) {
                    if(str[j] == '0' + i) {
                        vis[j] = true;
                    } else {
                        if(!vis[j] && cnt[id(str[j])] > n / 3 && cnt[i] < n / 3) {
                            --cnt[id(str[j])];
                            str[j] = '0' + i;
                            ++cnt[i];
                            vis[j] = true;
                        }
                    }
                }
            }
        }
        printf("%s\n", str);
    }
    return 0;
}

E. Monotonic Renumeration

题意

给定一个长度为 $n$ 的序列 $a$ ，要求生成一个满足以下条件的序列 $b$ ：

$b_1=0$ ；

对于任意的 $1\leq i,j\leq n$ ，若 $a_i=a_j$ ，则 $b_i=b_j$ （若 $a_i\neq a_j$ ，也可以使得 $b_i=b_j$ ）;

对于每一个 $i\in[1,n)$ ，有 $b_i=b_{i+1}$ 或者 $b_i+1=b_{i+1}$ 。

统计总共有多少种 $b$ 序列满足条件，将答案对 $998244353$ 取模后输出。

输入

第一行包含一个整数 $n~(2\leq n\leq2\times10^5)$ ，第二行包含 $n$ 个整数 $a_1,a_2,\cdots,a_n~(1\leq a_i\leq10^9)$ 。

输出

输出题目所求答案。

样例

输入
5 1 2 1 2 3
输出
2

输入
2 100 1
输出
2

输入
4 1 3 3 7
输出
4

题解

由 $2$ 和 $3$ 可知若存在 $a_l=a_r~(l\leq r)$ ，则对于任意 $i,j\in[l,r]$ ，有 $b_i=b_j$ ，因此所有 $n$ 个整数被分为 $x$ 个区间，每个区间内的 $b_i$ 值都必须相等，答案就是 $2^{x-1}\mod998244353$ 。
先记录每个数字 $a_i$ 最后出现的下标 $End_{a_i}$ ，然后将 $j$ 从 $i$ 到 $End_{a_i}$ 扫一遍，在扫的过程中将所有 $End_{a_j}>End_{a_i}$ 的值更新到 $End_{a_i}$ 中，直到停止扫描，则刚刚扫过的整个区间的 $b_j$ 的值都必须相同。即上述的 $x$ 个区间中的其中一个。

过题代码

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <cfloat>
#include <climits>
#include <iostream>
#include <string>
#include <vector>
#include <list>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <algorithm>
#include <bitset>
#include <sstream>
using namespace std;
#define LL long long
const int maxn = 200000 + 100;
const LL MOD = 998244353;
int n;
int num[maxn], End[maxn];
vector<int> sand;
LL fast_pow(LL res, LL n) {
    LL ans;
    for(ans = 1; n != 0; n >>= 1) {
        if((n & 1) == 1) {
            ans = ans * res % MOD;
        }
        res = res * res % MOD;
    }
    return ans;
}
int main() {
    #ifdef Dmaxiya
    freopen("test.txt", "r", stdin);
    #endif // Dmaxiya
    ios::sync_with_stdio(false);
    while(scanf("%d", &n) != EOF) {
        sand.clear();
        for(int i = 1; i <= n; ++i) {
            scanf("%d", &num[i]);
            sand.push_back(num[i]);
        }
        sort(sand.begin(), sand.end());
        sand.erase(unique(sand.begin(), sand.end()), sand.end());
        for(int i = 1; i <= n; ++i) {
            num[i] = lower_bound(sand.begin(), sand.end(), num[i]) - sand.begin() + 1;
            End[num[i]] = i;
        }
        LL ans = 0;
        int Begin = 1;
        int EEnd;
        while(Begin != n + 1) {
            EEnd = End[num[Begin]];
            ++ans;
            for(int i = Begin; i <= EEnd; ++i) {
                EEnd = max(EEnd, End[num[i]]);
            }
            Begin = EEnd + 1;
        }
        printf("%I64d\n", fast_pow(2, ans - 1));
    }
    return 0;
}

F. Elongated Matrix

题意

有一个 $n\times m$ 的矩阵，可以对这个矩阵进行交换任意两行的操作（也可以不进行任何操作），但是列的顺序不能被交换，要求交换完毕后，将最后的矩阵进行按列扫描（即按 $a_{1,1},a_{2,1},\cdots,a_{n,1},a_{1,2},a_{2,2},\cdots,a_{n,2},\cdots,a_{n,m}$ 的顺序扫描），得到一个序列 $s_1,s_2,\cdots,s_{nm}$ ，序列 $s$ 的任意相邻两项之间满足 $|s_i-s_{i+1}|\geq k~(1\leq i<nm)$ ，求最大的 $k$ 值。

输入

第一行为两个整数 $n,m~(1\leq n\leq16,1\leq m\leq10^4,2\leq nm)$ ，接下去 $n$ 行每行 $m$ 个整数，第 $i$ 行第 $j$ 列的整数 $a_{i,j}$ 表示矩阵对应位置的整数，其中 $1\leq a_{i,j}\leq10^9$ 。

输出

输出题目所求答案。

样例

输入
4 2 9 9 10 8 5 3 4 3
输出
5
提示
将矩阵按行交换成如下矩阵，即可得到最大的 $k$ 值 $5$ ： 5 3 10 8 4 3 9 9 此时 $s$ 序列为： $[5,10,4,9,3,8,3,9]$ ，任意两个相邻元素之间的差值至少为 $5$ 。

输入
2 4 1 2 3 4 10 3 7 3
输出
0
提示
将行按任意顺序排列，得到的 $k$ 值都为 $0$ 。

输入
6 1 3 6 2 5 1 4
输出
3
提示
原序列的 $k$ 值已经为 $3$ 。

题解

由于对于任意两行 $i$ 和 $j$ ，只要 $i$ 是 $j$ 的下一行，那么这两行中任意一列的差值都是定值，且从第 $i$ 行到第 $j$ 行的距离必然为 $dis[i][j]=\min(|a_{i,l}-a_{j,l}|),l\in[1,m]$ ，因此可以将 $m$ 列处理成 $1$ 列，不考虑跨列连接的问题的话，就变成了 $n$ 行 $1$ 列的问题了。
定义 $dp[s][t][l]$ 表示以第 $s$ 行为起点，第 $t$ 列为终点， $l$ 的二进制位中所有为 $1$ 的位都被访问过的状态的最大满足条件的距离，假设从 $s$ 到中转行 $c$ 的遍历行数的状态为 $l$ ，那么到达一个新的行 $t$ 的距离，可以用状态转移方程得到：

$dp[s][t][l|(1<<t)]=\max(\min(dp[s][c][l],dis[c][t]))\quad(bit_{l,s}=bit_{l,c}=1,bit_{l,t}=0)$

其中 $bit_{a,b}$ 表示 $a$ 的第 $b$ 个二进制位的值。 $dp$ 的初始值为
$dp[i][j][k]= \begin{cases} \infty&i=j,k=1<<i\\ 0&others \end{cases}$

最后考虑跨列的情况，即以 $s$ 为起始行， $t$ 为最终行，从 $t$ 行的当前列到 $s$ 行的下一列，其距离为： $dis\_next[t][s]=\min(|a_{t,j}-a_{s,j+1}|)~(s\neq t,1\leq j<m)$ ，将所有 $dp[s][t][l]$ 与对应的 $dis\_next$ 取 $\min$ ，再取所有的最大值，就是答案。
注意特判 $n=1$ 的情况。

过题代码

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <cfloat>
#include <climits>
#include <iostream>
#include <string>
#include <vector>
#include <list>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <algorithm>
#include <bitset>
#include <sstream>
using namespace std;
#define LL long long
const int maxn = 16;
const int maxm = 10000 + 100;
int n, m;
int num[maxn][maxm];
int dp[maxn][maxn][1 << maxn];
int dis[maxn][maxn], dis_next[maxn][maxn];
int main() {
    #ifdef Dmaxiya
    freopen("test.txt", "r", stdin);
    #endif // Dmaxiya
    ios::sync_with_stdio(false);
    while(scanf("%d%d", &n, &m) != EOF) {
        for(int i = 0; i < n; ++i) {
            for(int j = 0; j < m; ++j) {
                scanf("%d", &num[i][j]);
            }
        }
        if(n == 1) {
            int ans = INT_MAX;
            for(int i = 1; i < m; ++i) {
                ans = min(ans, abs(num[0][i] - num[0][i - 1]));
            }
            printf("%d\n", ans);
            continue;
        }
        for(int i = 0; i < n; ++i) {
            for(int j = 0; j < n; ++j) {
                dis[i][j] = INT_MAX;
                dis_next[i][j] = INT_MAX;
                if(i == j) {
                    continue;
                }
                for(int k = 0; k < m; ++k) {
                    dis[i][j] = min(dis[i][j], abs(num[i][k] - num[j][k]));
                    if(k != 0) {
                        dis_next[i][j] = min(dis_next[i][j], abs(num[i][k - 1] - num[j][k]));
                    }
                }
            }
        }
        memset(dp, 0, sizeof(dp));
        for(int i = 0; i < n; ++i) {
            dp[i][i][1 << i] = INT_MAX;
        }
        for(int i = 1; i < (1 << n); ++i) {
            for(int s = 0; s < n; ++s) {
                if(((i >> s) & 1) == 0) {
                    continue;
                }
                for(int t = 0; t < n; ++t) {
                    if(s == t || ((i >> t) & 1) == 1) {
                        continue;
                    }
                    for(int j = 0; j < n; ++j) {
                        if(((i >> j) & 1) == 0) {
                            continue;
                        }
                        int tmp = i | (1 << t);
                        dp[s][t][tmp] = max(dp[s][t][tmp], min(dp[s][j][i], dis[j][t]));
                    }
                }
            }
        }
        int ans = 0;
        int tmp = (1 << n) - 1;
        for(int i = 0; i < n; ++i) {
            for(int j = 0; j < n; ++j) {
                if(i == j) {
                    continue;
                }
                ans = max(ans, min(dp[i][j][tmp], dis_next[j][i]));
            }
        }
        printf("%d\n", ans);
    }
    return 0;
}

Codeforces Round #531 (Div. 3)

A. Integer Sequence Dividing

题意

输入

输出

样例

题解

过题代码

B. Array K-Coloring

题意

输入

输出

样例

题解

过题代码

C. Doors Breaking and Repairing

题意

输入

输出

样例

题解

过题代码

D. Balanced Ternary String

题意

输入

输出

样例

题解

过题代码

E. Monotonic Renumeration

题意

输入

输出

样例

题解

过题代码

F. Elongated Matrix

题意

输入

输出

样例

题解

过题代码

内容目录