Codeforces Round #302 (Div. 2) -- (A,B,C)
3545 ワード
タイトル転送:Codeforces Round#302(Div.2)
A. Set of Strings
考え方:先頭文字が異なることに注意
ACコード:
B. Sea and Islands
構想:構造、あなたにn*nの地図をあげて、地図の上でk個の島があることができるかどうかを見て、島は1つの連通ブロックから構成されています(隣接するのは1つの連通ブロックです)
ACコード:
C. Writing Code
考え方:シンプルDP、完全リュック
ACコード:
A. Set of Strings
考え方:先頭文字が異なることに注意
ACコード:
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <cmath>
#include <queue>
#include <stack>
#include <vector>
#include <map>
#include <set>
#include <deque>
#include <cctype>
#define LL long long
#define INF 0x7fffffff
using namespace std;
char s[105];
int flag[26];
int f[26];
int main() {
int k;
scanf("%d", &k);
scanf("%s", s);
int len = strlen(s);
memset(flag, 0, sizeof(flag));
for(int i = 0; i < len; i ++) {
flag[s[i] - 'a'] = 1;
}
int cnt = 0;
for(int i = 0; i < 26; i ++) {
cnt += flag[i];
}
if(cnt < k) {
cout << "NO" << endl;
}
else {
memset(f, 0, sizeof(f));
char cur = s[0];
cout << "YES" << endl;
printf("%c", s[0]);
f[s[0] - 'a'] = 1;
int tt = 1;
for(int i = 1; i < len; i ++) {
if(s[i] != cur && tt != k && f[s[i] - 'a'] == 0) {
printf("
%c", s[i]);
f[s[i] - 'a'] = 1;
tt ++;
cur = s[i];
}
else printf("%c", s[i]);
}
}
return 0;
}
B. Sea and Islands
構想:構造、あなたにn*nの地図をあげて、地図の上でk個の島があることができるかどうかを見て、島は1つの連通ブロックから構成されています(隣接するのは1つの連通ブロックです)
ACコード:
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <cmath>
#include <queue>
#include <stack>
#include <vector>
#include <map>
#include <set>
#include <deque>
#include <cctype>
#define LL long long
#define INF 0x7fffffff
using namespace std;
int main() {
int n, k;
cin >> n >> k;
int sum = n & 1 ? (n * n + 1) / 2 : n * n / 2;//
if(k > sum) {
cout << "NO" << endl;
}
else {
cout << "YES" << endl;
int t = 0;
for(int i = 1; i <= n; i++, printf("
")) {
for(int j = 1; j <= n; j ++) {
if(i & 1 && t != k) {
if(j & 1) {
printf("L");
t ++;
}
else {
printf("S");
}
}
else if(!(i & 1) && t != k){
if(j & 1) {
printf("S");
}
else {
printf("L");
t ++;
}
}
else if(t == k) {
printf("S");
}
}
}
}
return 0;
}
C. Writing Code
考え方:シンプルDP、完全リュック
ACコード:
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <cmath>
#include <queue>
#include <stack>
#include <vector>
#include <map>
#include <set>
#include <deque>
#include <cctype>
#define LL long long
#define INF 0x7fffffff
using namespace std;
LL dp[505][505];
LL a[505];
int main() {
int n, m, b, mod;
scanf("%d %d %d %d", &n, &m, &b, &mod);
for(int i = 1; i <= n; i ++) {
scanf("%d", &a[i]);
}
dp[0][0] = 1;
for(int i = 1; i <= n; i ++) {
for(int j = 1; j <= m; j ++) {
for(int k = 0; k <= b; k ++) {
if(k >= a[i]) dp[j][k] += dp[j-1][k - a[i]];
dp[j][k] %= mod;
}
}
}
LL ans = 0;
for(int i = 0; i <= b; i ++) {
ans += dp[m][i];
ans %= mod;
}
cout << ans << endl;
return 0;
}