达成成就： 铁牌首名。
E - Cats and Fish(00:29)
签到题， 模拟， 一顿瞎搞就好。
Code:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
|
using namespace std;
#define endl "n"
int c[105], cnt[105], eating[105];
int () {
ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
int m, n, x;
while (cin >> m >> n >> x) {
for (int i = 0; i < n; i++) {
cin >> c[i];
cnt[i] = 0; eating[i] = 0;
}
sort(c, c + n);
for (int i = 1; i <= x; i++) {
for (int j = 0; j < n; j++) {
if (eating[j]) {
cnt[j]++;
}
else if (m > 0) {
cnt[j] = 1, eating[j] = 1, m--;
}
}
for (int j = 0; j < n; j++) {
if (cnt[j] == c[j]) {
cnt[j] = 0;
eating[j] = 0;
}
}
}
int ing = 0;
for (int j = 0; j < n; j++) {
ing += eating[j];
}
cout << m << " " << ing << endl;
}
}
|
F - Secret Poems(00:52)
签到题 * 2， 模拟 * 2， 瞎搞就好 * 2, WA了两发导致罚时boom。
Code:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
|
using namespace std;
#define endl "n"
const int Move[][2] = { {0, 1}, {1, 0}, {0, -1}, {-1, 0} };
char s[105][105], str[10005], ans[105][105];
int () {
ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
int n;
while (cin >> n) {
for (int i = 0; i < n; i++) {
cin >> s[i];
}
int cnt = 0;
for (int i = 0; i < n; i++) {
if (i % 2 == 0) {
for (int j = 0, k = i; k >= 0; j++, k--) {
str[cnt++] = s[k][j];
}
}
else {
for (int j = i, k = 0; k <= i; j--, k++) {
str[cnt++] = s[k][j];
}
}
}
for (int i = 1; i < n; i++) {
bool flag = (n & 1) ^ (i % 2 == 0) ^ 1;
if (flag) {
for (int j = i, k = n - 1; j < n; j++, k--) {
str[cnt++] = s[k][j];
}
}
else {
for (int j = n - 1, k = i; k < n; j--, k++) {
str[cnt++] = s[k][j];
}
}
}
str[cnt] = 0;
memset(ans, 0, sizeof ans);
for (int pos = 0, i = 0, j = -1; ; ) {
do {
++j;
if (pos == cnt) break;
ans[i][j] = str[pos++];
} while (j < n - 1 && ans[i][j + 1] == 0);
if (pos == cnt) break;
do {
++i;
if (pos == cnt) break;
ans[i][j] = str[pos++];
} while (i < n - 1 && ans[i + 1][j] == 0);
if (pos == cnt) break;
do {
--j;
if (pos == cnt) break;
ans[i][j] = str[pos++];
} while (j > 0 && ans[i][j - 1] == 0);
if (pos == cnt) break;
do {
--i;
if (pos == cnt) break;
ans[i][j] = str[pos++];
} while (i > 0 && ans[i - 1][j] == 0);
if (pos == cnt) break;
}
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
cout << ans[i][j];
}
cout << endl;
}
}
}
|
J - Pangu and Stones(Upsolved)
题意： 需要将所有石子合并成一堆，每次只能合并连续的[L, R]堆，求最小合并费用or不能。
Solution:
区间DP，大概就是模版题的升级版。然而我并不会区间DP= =
转移方程大概为:
$dp[i][j][k] = min ( dp[i][t][1] + dp[t + 1][j][k - 1] ), i leq t < j, k != 1$
$dp[i][j][1] = min ( dp[i][j][t] ), l leq t leq r$
$dp[i][i][0] = 0$
Code:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
|
using namespace std;
#define endl "n"
const long long INF = 0x3f3f3f3f3f3f3f3f;
int n, L, R;
long long a[105], sum[105], dp[105][105][105];
int32_t main() {
ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
while (cin >> n >> L >> R) {
for (int i = 1; i <= n; i++) {
cin >> a[i];
}
memset(dp, 0x3f, sizeof dp);
for (int i = 1; i <= n; i++) {
dp[i][i][1] = 0;
sum[i] = sum[i - 1] + a[i];
}
for (int len = 2; len <= n; len++) {
for (int i = 1; i <= n; i++) {
int j = i + len - 1;
if (j > n) break;
for (int k = len; k >= 2; k--) {
for (int t = i; t < j; t++) {
dp[i][j][k] = min(dp[i][j][k], dp[i][t][1] + dp[t + 1][j][k - 1]);
}
}
for (int t = L; t <= R; t++) {
dp[i][j][1] = min(dp[i][j][1], dp[i][j][t] + sum[j] - sum[i - 1]);
}
}
}
if (dp[1][n][1] != INF) cout << dp[1][n][1] << endl;
else cout << 0 << endl;
}
}
|
近期评论