@Dmaxiya
2019-01-15T19:59:04.000000Z
字数 9349
阅读 1214
Codeforces
Contests 链接:Codeforces Round #531 (Div. 3)
过题数:5
排名:176/9160
给定一个整数 ,将 以内所有的整数分到两个集合 和 中,每个整数只能被分到一个集合,要求两个集合中所有数字的和的差的绝对值最小,即: 的值最小,其中空集合内所有数字的和为 。
输入仅包含一个整数 。
输出题目所求答案。
输入 |
---|
3 |
输出 |
0 |
提示 |
其中一种合法的分法是:令 ,这样 。 |
输入 |
---|
5 |
输出 |
1 |
提示 |
其中一种合法的分法是:令 ,这样 。 |
输入 |
---|
6 |
输出 |
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
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;
}
给定 个整数 和 种颜色,要求用这 种颜色给所有整数上色,并且满足下面三个要求:
- 每个整数都必须要涂上一种颜色;
- 每种颜色至少要被涂上一次;
- 所有被颜色 涂上的数字都必须是不同的。
若存在满足上述条件的涂色方案,则输出任意一种,否则输出 。
第一行为两个整数 ,第二行为 个整数 。
如果不存在合法的解,则输出 ,否则在第一行输出 ,并在第二行给出任意一种合法的解,每种颜色用数字 内的整数表示。
输入 |
---|
4 2 1 2 2 3 |
输出 |
YES 1 1 2 2 |
提示 |
也是一种合法的涂色方案,当然也存在其他合法的涂色方案。 |
输入 |
---|
5 2 3 2 1 2 3 |
输出 |
YES 2 1 1 2 1 |
提示 |
也是一种合法的涂色方案,当然也存在其他合法的涂色方案。 |
输入 |
---|
5 2 2 1 1 2 1 |
输出 |
NO |
若存在任意一个颜色出现的次数大于 ,则输出 ,否则将每个数字 出现的位置存在一个
vector<int>
数组的第 个位置上,然后按下标从小到大遍历这个vector<int>
数组,按 的循环给所有位置上色。
#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;
}
有两个人玩一个游戏,最开始有 扇门,第 扇门初始的耐久性为 ,你是先手,另一个人后手,每当你选择一扇门,可以将这扇门的当前耐久度 改为 ,每当另一个人选择一扇门,若这扇门的当前耐久度不为 ,则可以将其修改为 ,你希望有最多的门的耐久度变为 ,而另一个人希望有最少的门的耐久度变为 ,两人都采取最优策略,问经过 轮游戏之后,最多有多少扇门的耐久度变为 。
第一行为 个整数 ,第二行有 个整数 。
输出题目所求答案。
输入 |
---|
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 |
若 ,则先手一定能将所有门的耐久度都变为 ,否则若先手破坏一道 的门,后手就可以立即对第 扇门进行修复,所以先手只能去破坏 的门,而后手一定会去修复还没有被破坏的 的门,所以先手最多只能破坏 扇门,其中 为 的门的数量。
#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;
}
给定一个长度为 的三元字符串,字符串中只包含三种字符:
0
1
2
,每次可以将字符串中的一个字符替换成另一个字符,要求替换最少的次数,使得这个三元字符串每种字符的个数相等,如果有多种答案,输出字典序最小的一种。
第一行包含一个整数 ,第二行为一个长度为 的三元字符串。
输出题目所求答案。
输入 |
---|
3 121 |
输出 |
021 |
输入 |
---|
6 000000 |
输出 |
001122 |
输入 |
---|
6 211200 |
输出 |
211200 |
输入 |
---|
6 120110 |
输出 |
120120 |
先统计字符
0
1
2
出现的次数 ,然后先从前往后确定所有 的位置,若 ,则将前 个 标为 ,表示完全确定,并且不能更改,多出来的0
为 ,表示可以更改,若 ,则将靠前的非0
的 值大于 的字符改为0
,并修改相应的 值,并将该位置标为 ,对于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;
}
给定一个长度为 的序列 ,要求生成一个满足以下条件的序列 :
- ;
- 对于任意的 ,若 ,则 (若 ,也可以使得 );
- 对于每一个 ,有 或者 。
统计总共有多少种 序列满足条件,将答案对 取模后输出。
第一行包含一个整数 ,第二行包含 个整数 。
输出题目所求答案。
输入 |
---|
5 1 2 1 2 3 |
输出 |
2 |
输入 |
---|
2 100 1 |
输出 |
2 |
输入 |
---|
4 1 3 3 7 |
输出 |
4 |
由 和 可知若存在 ,则对于任意 ,有 ,因此所有 个整数被分为 个区间,每个区间内的 值都必须相等,答案就是 。
先记录每个数字 最后出现的下标 ,然后将 从 到 扫一遍,在扫的过程中将所有 的值更新到 中,直到停止扫描,则刚刚扫过的整个区间的 的值都必须相同。即上述的 个区间中的其中一个。
#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;
}
有一个 的矩阵,可以对这个矩阵进行交换任意两行的操作(也可以不进行任何操作),但是列的顺序不能被交换,要求交换完毕后,将最后的矩阵进行按列扫描(即按 的顺序扫描),得到一个序列 ,序列 的任意相邻两项之间满足 ,求最大的 值。
第一行为两个整数 ,接下去 行每行 个整数,第 行第 列的整数 表示矩阵对应位置的整数,其中 。
输出题目所求答案。
输入 |
---|
4 2 9 9 10 8 5 3 4 3 |
输出 |
5 |
提示 |
将矩阵按行交换成如下矩阵,即可得到最大的 值 : 5 3 10 8 4 3 9 9 此时 序列为:,任意两个相邻元素之间的差值至少为 。 |
输入 |
---|
2 4 1 2 3 4 10 3 7 3 |
输出 |
0 |
提示 |
将行按任意顺序排列,得到的 值都为 。 |
输入 |
---|
6 1 3 6 2 5 1 4 |
输出 |
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
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;
}