http://codeforces.com/contest/1458
B. Glass Half Spilled
题意：有 n 杯水，每杯最大容量为 ai，杯中已经有了 bi 的水，可以从任意杯中倒水至任意杯中，每次倒水时会洒出一半，问对于每个 1≤i≤n，选择 i 杯，最多能有多少水。
dp
起初一直想着直接dp出答案，但是这样需要很多分类讨论，而且还涉及到小数的问题。
但是可以换一种思路，在dp时先不倒水，dp[i][j][k] 表示前 i 杯，选择 j 杯，选中的杯子的总容量为 k 的最大水量。
则转移就很简单了 dp[i][j][k]=dp[i−1][j][k] 不选当前杯子，dp[i][j][k]=dp[i−1][j−1][k−a[i]]+b[i] 选当前杯子。
再考虑答案，在考虑答案的时候再倒水。
对于 dp[i][j][k]，总容量为 k，已经装了 dp[i][j][k] 的水，未被选中的杯子中的水必然都要倒入被选中的杯子里，未被选中的杯子中的总水量为 ∑b−dp[i][j][k]，所以被选中的杯子中最大水量就是 min(k,dp[i][j][k]+2∑b−dp[i][j][k]).
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
| #include <bits/stdc++.h>
#define debug(x) cout << #x << ":\t" << (x) << endl;
using namespace std;
#define ll long long
#define ull unsigned ll
const int N = 40010;
const int INF = 0x3f3f3f3f;
const ll inf = 0x3f3f3f3f3f3f3f3f;
const ll mod = 1e9 + 7;
const ll inv2 = (mod + 1) / 2;
int n;
int a[N], b[N];
int dp[110][N], tmp[110][N];
int main() {
scanf("%d", &n);
for (int i = 1; i <= n; i++)scanf("%d%d", &a[i], &b[i]);
int suma = 0, sumb = 0;
for (int i = 0; i <= n; i++)for (int j = 0; j < N; j++)dp[i][j] = -INF;
dp[0][0] = 0;
for (int i = 1; i <= n; i++) {
suma += a[i];
sumb += b[i];
for (int j = 0; j <= i; j++)for (int k = 0; k <= suma; k++)tmp[j][k] = dp[j][k];
for (int j = 1; j <= i; j++) {
for (int k = a[i]; k <= suma; k++) {
dp[j][k] = max(dp[j][k], tmp[j - 1][k - a[i]] + b[i]);
}
}
}
for (int i = 1; i <= n; i++) {
double ans = 0;
for (int j = 0; j < N; j++)ans = max(ans, min(dp[i][j] + (sumb - dp[i][j])*0.5, 1.0*j));
printf("%.9lf%c", ans, " \n"[i == n]);
}
return 0;
}
|
C. Latin Square
题意：给定一个拉丁矩阵，即每行每列都是 1 到 n 的排列，m 次操作，每次把矩阵整体循环右移一项，或循环左移一项，或循环上移一项，或循环下移一项，或对每一行 p[i]=j 变成 p[j]=i，或对每一列 p[i]=j 变成 p[j]=i，问最终矩阵。
思维
算是一个比较有趣的套路。
矩阵可以看作一个三元组 (i,j,a[i][j])。每次操作都是对所有元素操作，所以可以对这个三元组进行维护。
例如右移：(i,j,a[i][j]) 变为 (i,j+1,a[i][j])。
例如对每行的变换：(i,j,a[i][j]) 变为 (i,a[i][j],j)。
所以设定三个变量分别代表这哥三元组中三个位置的增量。又由于会有交换三元组中某两个位置的操作，所以还要有三个变量分别指向对应的增量。
这三个数始终是 1 到 n 范围内的，包括 a[i][j]，所以最终结果也必须取模到 1 到 n 范围内。
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
| #include <bits/stdc++.h>
#define debug(x) cout << #x << ":\t" << (x) << endl;
using namespace std;
#define ll long long
#define ull unsigned ll
const int N = 2e6 + 10;
const int INF = 0x3f3f3f3f;
const ll inf = 0x3f3f3f3f3f3f3f3f;
const ll mod = 1e9 + 7;
const ll inv2 = (mod + 1) / 2;
int T;
int n, m;
int a[1010][1010], b[3], ad[3], tmp[3], ans[1010][1010];
char s[N];
int main() {
scanf("%d", &T);
while (T--) {
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++)
scanf("%d", &a[i][j]);
}
b[0] = 0; b[1] = 1; b[2] = 2;
ad[0] = ad[1] = ad[2] = 0;
scanf("%s", s);
for (int i = 0; i < m; i++) {
if (s[i] == 'R') {
ad[b[1]]++;
}
else if (s[i] == 'L') {
ad[b[1]]--;
}
else if (s[i] == 'D') {
ad[b[0]]++;
}
else if (s[i] == 'U') {
ad[b[0]]--;
}
else if (s[i] == 'I') {
swap(b[1], b[2]);
}
else if (s[i] == 'C') {
swap(b[0], b[2]);
}
}
ad[0] = (ad[0] + n) % n;
ad[1] = (ad[1] + n) % n;
ad[2] = (ad[2] + n) % n;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
tmp[0] = i, tmp[1] = j, tmp[2] = a[i][j];
ans[(tmp[b[0]] + ad[b[0]] - 1 + n) % n + 1][(tmp[b[1]] + ad[b[1]] - 1 + n) % n + 1] = (tmp[b[2]] + ad[b[2]] - 1 + n) % n + 1;
}
}
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
printf("%d%c", ans[i][j], " \n"[j == n]);
}
}
}
return 0;
}
|
