@Dmaxiya
2018-08-17T10:14:14.000000Z
字数 3948
阅读 887
Codeforces
Contests 链接:Codeforces Round #480 (Div. 2)
过题数:3
排名:804/9913
给定一个只包含
-
和o
的字符串,-
表示项链上的链,o
表示项链上的珍珠,将字符串首尾相连表示一条项链,每次操作可以将任意位置的链或珍珠拆下,插入到另一个位置上,问进行任意多次操作后,能否使得项链上任意两个相邻的珍珠之间的链的数量相等。
输入为一个字符串 ,字符串只包含字符
-
和o
。
如果可以,则输出 ,否则输出 ,大小写任意。
输入 |
---|
-o-o-- |
输出 |
YES |
输入 |
---|
-o--- |
输出 |
YES |
输入 |
---|
-o---o- |
输出 |
NO |
输入 |
---|
ooo |
输出 |
YES |
计算项链上
o
的数量 和-
的数量 ,满足 是 的倍数或者 的数量为 ,就输出 ,否则输出 。
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <climits>
#include <cstring>
#include <string>
#include <vector>
#include <list>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <functional>
#include <algorithm>
using namespace std;
#define LL long long
const int maxn = 100 + 100;
int cnt1, cnt2;
char str[maxn];
int main() {
#ifdef LOCAL
freopen("test.txt", "r", stdin);
// freopen("testout.txt", "w", stdout);
#endif // LOCAL
ios::sync_with_stdio(false);
while(scanf("%s", str) != EOF) {
cnt1 = cnt2 = 0;
for(int i = 0; str[i]; ++i) {
if(str[i] == 'o') {
++cnt1;
} else {
++cnt2;
}
}
if(cnt1 == 0) {
printf("YES\n");
continue;
}
if(cnt2 % cnt1 == 0) {
printf("YES\n");
} else {
printf("NO\n");
}
}
return 0;
}
在一个 ( 为奇数)的网格中,需要设置 个障碍,这 个障碍不能设置在网格的边界上,要求从 到达 的最短路径数量等于从 到 的最短路径数量,两个方格之间的路径长度为 ,当且仅当这两个方格有公共边。
输入只包含两个整数 ,数据保证 为奇数。
如果可以达到要求,第一行输出 ,接下去 行每行 个字符,字符只能包含
.
和#
,其中.
表示空地,#
表示障碍物。
输入 |
---|
7 2 |
输出 |
YES....... .#..... .#..... ....... |
输入 |
---|
5 3 |
输出 |
YES..... .###. ..... ..... |
对于 为偶数的情况,只需要上下对称分布,对于奇数的情况,以下枚举了 时, 等于 的构造方案:
.....
.....
.....
..#..
.###.
.###.
.....
.....
.#.#.
.....
.....
.....
不存在无法构造的情况。
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <climits>
#include <cstring>
#include <string>
#include <vector>
#include <list>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <functional>
#include <algorithm>
using namespace std;
#define LL long long
const int maxn = 100 + 100;
int n, k;
char ans[maxn][maxn];
int main() {
#ifdef LOCAL
freopen("test.txt", "r", stdin);
// freopen("testout.txt", "w", stdout);
#endif // LOCAL
ios::sync_with_stdio(false);
while(scanf("%d%d", &n, &k) != EOF) {
for(int i = 1; i <= 4; ++i) {
for(int j = 1; j <= n; ++j) {
ans[i][j] = '.';
}
}
if(k % 2 == 0) {
for(int j = 2; j < k / 2 + 2; ++j) {
for(int i = 2; i <= 3; ++i) {
ans[i][j] = '#';
}
}
} else {
int up = min(n - 2, k);
int mid = n / 2 + 1;
for(int i = 0; i <= up / 2; ++i) {
ans[2][mid + i] = '#';
ans[2][mid - i] = '#';
}
up = max(k - (n - 2), 0);
for(int i = 0; i < up / 2; ++i) {
ans[3][2 + i] = '#';
ans[3][n - 1 - i] = '#';
}
}
printf("YES\n");
for(int i = 1; i <= 4; ++i) {
for(int j = 1; j <= n; ++j) {
printf("%c", ans[i][j]);
}
printf("\n");
}
}
return 0;
}
给出 个整数和一个阈值 ,所有整数都在 的范围内,要求将所有整数分到一个不阈值大于 的区间内,并从这个阈值内选出一个数字代表这个阈值中的所有数字, 内每个整数都只能属于一个阈值,问将 个整数都用所属阈值的代表数字替换后,字典序最小的结果。
第一行为两个整数 ,第二行为 个整数 。
输出字典序最小的结果。
输入 |
---|
4 3 2 14 3 4 |
输出 |
0 12 3 3 |
提示 |
令 属于 ,代表数字为 , 属于 ,代表数字为 , 属于 ,代表数字为 ,即得到最小字典序结果。 |
输入 |
---|
5 2 0 2 1 255 254 |
输出 |
0 1 1 254 254 |
最初每个数字都属于自身阈值(长度为 ),从前往后,每碰到一个数字,先检查这个数字是否已经属于某一个阈值,如果已经属于,则只能用该阈值的代表数字替换,否则往前找 个数字,保证前 个数字都没有属于某阈值的情况下,贪心地找到最小的能代表的数字,将这一段的代表数字同设置为该数字,一直往后。
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <climits>
#include <cstring>
#include <string>
#include <vector>
#include <list>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <functional>
#include <algorithm>
using namespace std;
#define LL long long
const int maxn = 100000 + 100;
int n, k;
int num[maxn];
int head[1000];
int Find(int x) {
int ret = x;
int kk = k;
while(ret != 0) {
--ret;
--kk;
if(head[ret] != -1) {
++ret;
break;
}
if(kk == 0) {
++ret;
break;
}
}
if(ret == 0) {
return ret;
}
if(x - head[ret - 1] + 1 <= k) {
return head[ret - 1];
} else {
return ret;
}
}
int main() {
#ifdef LOCAL
freopen("test.txt", "r", stdin);
// freopen("testout.txt", "w", stdout);
#endif // LOCAL
ios::sync_with_stdio(false);
while(scanf("%d%d", &n, &k) != EOF) {
memset(head, -1, sizeof(head));
for(int i = 1; i <= n; ++i) {
scanf("%d", &num[i]);
if(head[num[i]] != -1) {
continue;
}
int Index = Find(num[i]);
for(int j = Index; j <= num[i]; ++j) {
head[j] = Index;
}
}
for(int i = 1; i <= n; ++i) {
if(i != 1) {
printf(" ");
}
printf("%d", head[num[i]]);
}
printf("\n");
}
return 0;
}