这次比赛做得乱七八糟,事实上一共只做出来两道题,结果rating还涨了一点点,看来确实有点难。。

1117A

题目来源:https://codeforces.com/contest/1117/problem/A

提交次数:1/1

题意

给定一个数组,问数组中满足平均数最大的前提下长度最长的子数列。

分析

就是找到最大值然后计算最大值最多连续出现了多少次而已。水题。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <iostream>
using namespace std;
int n;
int a[100005];
int main() {
int maxn = -1;
cin >> n;
for (int i = 0; i < n; i++) {
cin >> a[i];
maxn = max(maxn, a[i]);
}
int ans = 0, l = 1;
for (int i = 1; i <= n; i++) {
if (i == n || a[i] != a[i - 1]) {
if (a[i - 1] == maxn) ans = max(l, ans);
l = 1;
}
else l++;
}
cout << ans << endl;
return 0;
}

1117B

题目来源:https://codeforces.com/contest/1117/problem/B

提交次数:1/1

题意

给定n个emote,每个emote可以将对手的快乐值增加a[i],你可以使用一些emote共m次,相同的emote最多连续使用k次,问最多能增加多少快乐值?

分析

找出值最大和值次大的emote,连续用最大的emotek次,用一次次大的emote,再接着用最大的emote,以此类推,直到一共用了m次为止。水题。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long LL;
LL n, m, k;
LL a[200005];
int main() {
cin >> n >> m >> k;
for (int i = 0; i < n; i++)
cin >> a[i];
sort(a, a + n);
LL cnt = m / (k + 1);
LL ans = cnt * (a[n-1] * k + a[n-2]) + (m - (k + 1) * cnt) * a[n-1];
cout << ans << endl;
return 0;
}

1117C

题目来源:https://codeforces.com/contest/1117/problem/C

提交次数:1/4

题意

你在(x1, y1)处有一艘船,每天可以向上或下、左、右移动1格。每天的移动效果会和天气效果叠加,天气效果会使得船根据风向往上或下、左、右移动一格。给定m天的天气,之后的天气是循环的,问最少需要几天,船才能到达(x2, y2)处?

分析

比赛的时候我意识到走完一个天气循环之后,能到的位置是一个菱形了(或者说是一个尖朝上的正方形);但很可惜我没有意识到这件事的本质,还打算拿计算几何来做(??)。显然,这件事的本质是这样的:把天气推船走的路和船自己走的路分开,可以得出一个结论:天气在一个循环内推船走的路是固定的,不妨记为(dx, dy);船自己可以在这个点周围走出一个菱形,或者说是所有满足|x-dx|+|y-dy|<=n的点。所以对天数二分查找就好了。当然,还是需要重视一下二分查找的前提:只要x天能到,那么y>=x天也能到。(大不了不动)[1]

除此之外就是注意上界。显然如果能到达(x2, y2),每个天气循环至少要向这个方向前进1格(曼哈顿距离),所以上界是(|x2-x1| + |y2-y1|)*n。如果走了这么多还没到,说明到不了了。

代码

因为long long int的使用错了好多次……

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
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long LL;
LL x1, y1, x2, y2;
int n;
char s[100005];
pair<LL, LL> pos[100005];
LL fx, fy;
// U, R, D, L
int mx[4] = {0, 1, 0, -1};
int my[4] = {1, 0, -1, 0};

bool isOk(LL days) {
LL sx = (days / n) * fx, sy = (days / n) * fy;
sx += pos[days % n].first, sy += pos[days % n].second;
return abs(x2 - sx) + abs(y2 - sy) <= days;
}

int main() {
cin >> x1 >> y1 >> x2 >> y2;
x2 -= x1;
y2 -= y1;
cin >> n;
cin >> s;
for (int i = 1; i <= n; i++) {
int d;
if (s[i-1] == 'U') d = 0;
else if (s[i-1] == 'R') d = 1;
else if (s[i-1] == 'D') d = 2;
else if (s[i-1] == 'L') d = 3;
pos[i].first = pos[i-1].first + mx[d];
pos[i].second = pos[i-1].second + my[d];
}
fx = pos[n].first, fy = pos[n].second;

LL l = 0, r = (abs(x2) + abs(y2)) * n;
while (l < r) {
LL m = (l + r) / 2;
if (isOk(m)) r = m;
else l = m + 1;
}
if (!isOk(l)) cout << -1 << endl;
else cout << l << endl;
return 0;
}

1117D

题目来源:https://codeforces.com/contest/1117/problem/D

提交次数:1/1

题意

一颗魔法宝石可以分裂成M颗普通宝石,问有多少种选择魔法宝石的方法,使得分裂后总的宝石数量是N?不同的魔法宝石数量和不同index的分裂被认为是不同的方法。N<=10^18M<=100

分析

比赛的时候我努力推了一个公式出来:

$$\sum_{i=0}^{\lfloor N/M \rfloor} \binom{N-(M-1)i}{i}$$

但是肯定不能这么算,因为N太大了。我心想:用动态规划估计也不行。

事实上得用到动态规划递推的思路,看到NM的大小,我早该想到是矩阵快速幂才对。

f[n]表示N=n时的方法数量。显然有两种方法进行递推:一种是加上一块不分裂的宝石(f[n-1]);另一种是加上一块分裂的宝石(f[n-M])。(虽然第二维看起来没有什么意义……)考虑到递推的本质,不需要乘新加的宝石的位置,因此:

1
f[n] = f[n-1] + f[n-M]

现在就可以造一个矩阵乘法迭代公式了:

1
2
3
4
5
| f[n-M]  f[n-M+1]  ...  f[n-1] | * | 0 0 0 ... 0 1 | = | f[n-M+1] |
| 1 0 0 ... 0 0 | | f[n-M+2] |
| 0 1 0 ... 0 0 | | ... |
| 0 0 1 ... 0 0 | | f[n-1] |
| 0 0 0 ... 1 1 | | f[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
63
64
65
66
67
68
69
70
71
72
73
#include <iostream>
#include <cstring>
using namespace std;
typedef long long LL;
LL N;
int M;

const LL P = 1000000007;

struct Matrix {
int n, m;
LL a[105][105];

Matrix(int _n, int _m) {
memset(a, 0, sizeof(a));
n = _n;
m = _m;
}

friend Matrix operator * (const Matrix& m1, const Matrix& m2) {
Matrix m3(m1.n, m2.m);
for (int i = 1; i <= m1.n; i++)
for (int j = 1; j <= m1.m; j++)
for (int k = 1; k <= m2.m; k++)
m3.a[i][k] = (m3.a[i][k] + m1.a[i][j] * m2.a[j][k]) % P;
return m3;
}

void print() {
cout << n << ' ' << m << endl;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++)
cout << a[i][j] << ' ';
cout << endl;
}
}
};

Matrix getIdentity(int n) {
Matrix mat(n, n);
for (int i = 1; i <= n; i++)
mat.a[i][i] = 1;
return mat;
}

int main() {
cin >> N >> M;
if (N < M) {
cout << 1 << endl;
return 0;
}
Matrix v(1, M);
for (int i = 1; i < M; i++)
v.a[1][i] = 1;
v.a[1][M] = 2;

Matrix x(M, M);
for (int i = 2; i <= M; i++)
x.a[i][i - 1] = 1;
x.a[1][M] = x.a[M][M] = 1;

LL delta = N - M;
Matrix pow = x;
Matrix ans = getIdentity(M);
while (delta > 0) {
if (delta & 1) ans = ans * pow;
delta >>= 1;
pow = pow * pow;
}
v = v * ans;
cout << v.a[1][M] << endl;
return 0;
}

1117E

题目来源:https://codeforces.com/contest/1117/problem/E

提交次数:1/1

题意

这是一道交互题。给定一个字符串,已知对它进行了<=n次swap操作;你可以拿出一个新的和它长度一样的字符串,然后得到对这个字符串进行相同的swap之后的结果。你最多可以提交三次字符串。问原来的字符串是多少?

分析

比赛的时候,我看了看这道题……觉得很有趣,但应该想半天也做不出来吧。(我从来没在比赛里做对过交互题)这道题的一种解法是这样的:既然每次提交的字符串的swap操作是一样的,不妨把提交的三次字符串看成是一个字符串,它的每个位置是由三个字符组成的一个“超字符”。这样我们就可以认为每个位置的“超字符”是两两不等的了!因为26^3 = 17576 >= 1e4,这是可行的。

然后就可以立即得到每个输入位置到输出位置的映射了,倒过来对原来的字符串重新做一遍就行了。

评论区里还出现了用中国剩余定理的做法,我没细看。[2]

代码

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
#include <iostream>
#include <cstring>
using namespace std;

char s[10005];
char q[3][10005];
char a[3][10005];
int mapping[10005];
int n;

int main() {
cin >> s;
n = strlen(s);
int m = 0;
for (int i = 0; i < 26; i++) {
for (int j = 0; j < 26; j++) {
for (int k = 0; k < 26; k++) {
q[0][m] = i + 'a';
q[1][m] = j + 'a';
q[2][m] = k + 'a';
m++;
if (m >= n) break;
}
if (m >= n) break;
}
if (m >= n) break;
}
for (int i = 0; i < 3; i++) {
cout << "? " << q[i] << endl;
cin >> a[i];
}
for (int i = 0; i < n; i++) {
int idx = (a[0][i] - 'a') * 26 * 26 + (a[1][i] - 'a') * 26 + (a[2][i] - 'a');
mapping[idx] = i;
}
cout << "! ";
for (int i = 0; i < n; i++)
cout << s[mapping[i]];
cout << endl;
return 0;
}

1117F

题目来源:https://codeforces.com/contest/1117/problem/F

提交次数:?/?

题意

还没看懂,感觉有点难度。

111G

题目来源:https://codeforces.com/contest/1117/problem/G

提交次数:?/?

题意

给定一个由1到n的全排列组成的数组,记m[l, r]范围内的最大元素index,定义函数

1
2
f(l, r) = (r - l + 1) + f(l, m - 1) + f(m + 1, r) (l <= r)
f(l, r) = 0 (l > r)

给定q个询问,请给定f的值。

1 <= n, q <= 1e6

分析

这道题我比赛的时候自然是不会做的。比赛完了,看看题解,发现也晦涩难懂。[1]

首先需要把f分解成两个函数,flfr

1
2
3
fl(l, r) = (m - l) + fl(l, m-1) + fl(m+1, r)
fr(l, r) = (r - m) + fr(l, m-1) + fr(m+1, r)
f(l, r) = (r - l + 1) + fl(l, r) + fr(l, r)

可以用数学归纳法简单地证明这个分解的正确性(虽然我可不知道为什么要这样分解……):

1
2
3
4
5
f(l, r) = (r - l + 1) + fl(l, r) + fr(l, r)
= (r - l + 1) + fl(l, m-1) + fl(m+1, r) + (m - l)
+ fr(l, m-1) + fr(m+1, r) + (r - m)
= (r - l + 1) + f(l, m-1) - (m-1 - l + 1) + f(m+1, r) - (r - (m+1) + 1) + (r - l)
= (r - l + 1) + f(l, m-1) + f(m+1, r)

然后不妨举一个例子来看看fl是怎么算出来的:

fl的例子

(显然fl(i, i) = fr(i,i) = 0

把这些式子全部展开,就会变成:

1
2
3
4
fl(1, 6) = (3-1) + fl(1, 2) + fl(4, 6)
= (3-1) + (1-1) + fl(2, 2) + (4-4) + fl(5, 6)
= (3-1) + (1-1) + (2-2) + (4-4) + (6-5) + fl(5, 5)
= (3-1) + (1-1) + (2-2) + (4-4) + (6-5) + (5, 5)

可以看出,fl其实是由6项组成的,而且每一项都是某个l <= i <= r与它左边最近的比它小的元素(或者l)之间的距离。这么想其实很合理。记i左边离它最近的比它大的元素为lf[i],可以看出,它对fl(l, r)产生贡献当且仅当它被作为最大元素选中了,且贡献大小为min(i - l, i - lf[i] - 1)


  1. Educational Codeforces Round 60 Editorial

  2. saeed_odak's comment for 1117E

题目来源:https://codeforces.com/contest/1107/problem/E

提交次数:1/1

题意

给定一个长度为n的只包含0和1的字符串,将该串中连续i个相同字符消去将得到a[i]的收益,问消去整个字符串能得到的最大收益是多少?

分析

在不会做的三道题上鸽了好久,最后还是觉得DP最好写……


这个题解[soln1]特别简明扼要,大概抓住了问题的本质,不过我可能还没有完全理解它:

  • 每一个状态都可以用[start, end, prefix]表示,其中startend是字符串中的起始和结束index(不妨假设两端都是闭区间)(不是也行),prefix是字符串前面附加的和s[start]相等的字符的数量(包括s[start])(不包括大概也行)
  • 每一个状态都有两种递推方法:
    • 第一种是直接消去字符串前面附加的字符:dp[start, end, prefix] = a[prefix] + dp[start + 1, end, 1]
    • 第二种是在字符串其他位置找到一个和s[start]相同的字符,然后消去中间的字符,获得一个更大的前缀:dp[start, end, prefix] = max(dp[start+1, i-1, 1] + dp[i, end, prefix+1]) (start < i <= end, s[i] == s[start])

虽然这个做法看起来很有道理,但其实我会有几个疑问。比如说,一些状态看起来其实是等价的:对于字符串"0001"dp[0, 3, 1]dp[2, 3, 3]表示的都是整个字符串。显然我们在递推过程中更容易得到前一种(没有被简化的)状态。那这两种状态有什么关系呢?是否需要手动简化?事实上,并不需要手动简化,dp[0, 3, 1]在递推中会自动得到dp[1, 3, 2]这个状态,并且进一步得到dp[2, 3, 3]。所以,与其说后一种状态是“简化之后的”,不如说是另一种对状态的看法,而且是一种一般化的表示。

至于递推的顺序,大概是得end - start从小到大,且prefix从小到大。这听起来有点麻烦(而且可能会增加复杂度),不如就写成递归形式算了。

[soln1]: Codeforces Blog - Quick unofficial editorial for Educational Round 59 (Div. 2)

[soln2]: Codeforces Blog - Educational Codeforces Round 59 Editorial

代码

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
#include <iostream>
#include <cstring>
using namespace std;
typedef long long int LL;
int n;
bool s[105];
LL a[105];
LL f[105][105][105];

LL calc(int start, int end, int p) {
if (f[start][end][p] != -1) return f[start][end][p];
if (start > end) return 0;
if (start == end) {
f[start][end][p] = a[p];
return f[start][end][p];
}
f[start][end][p] = a[p] + calc(start + 1, end, 1);
for (int i = start + 1; i <= end; i++) {
if (s[i] != s[start]) continue;
f[start][end][p] = max(f[start][end][p], calc(start + 1, i - 1, 1) + calc(i, end, p + 1));
}
return f[start][end][p];
}

int main() {
cin >> n;
for (int i = 0; i < n; i++) {
char ch;
cin >> ch;
s[i] = ch - '0';
}
for (int i = 1; i <= n; i++)
cin >> a[i];

memset(f, -1, sizeof(f));
cout << calc(0, n-1, 1) << endl;
}

题目来源:https://codeforces.com/contest/1107/problem/D

提交次数:2/2

题意

给定一个n*n的01矩阵A,定义A的x-压缩矩阵Bn/x * n/x大小的矩阵,且对于$i \in [1, n], , j \in [1, n]$,有

$$A[i][j] = B[\lceil \frac{i}{x} \rceil][\lceil \frac{j}{x} \rceil]$$

显然必须要求x整除n,且A中映射到B中同一位置的不同元素必须相等。问x的最大值是多少。

分析

这道题我比赛的时候看错题了。不过其实它并不是很难。显然有

$$B[i][j] = A[(i-1)x + 1...x][(j-1)x + 1...x]$$

[soln1]: Codeforces Blog - Quick unofficial editorial for Educational Round 59 (Div. 2)

[soln2]: Codeforces Blog - Educational Codeforces Round 59 Editorial

比较简单的解法1

显然每个B[i][j]都对应A中的一块矩形区域。那么就直接查看A中的这些矩形区域是否都为0或者都为1。但是这样做的话,每个x需要的复杂度是n^2,很可能太慢了。(事实上并不慢,因为x的总数是$\sigma(n)$,它的一个显然的上界是$\sqrt{n}$。)

不过还是可以做点优化的,求出包含A中左上元素的每个矩形的面积,然后就可以用它们加加减减来求出任何矩形的面积了。然后就可以直接判断每个矩形是否为全0或全1了……

矩形面积示意图

上图中:

Area(x1, y1, x2, y2) = S[x2][y2] - S[x2][y1-1] - S[x1-1][y2] + S[x1-1][y1-1]

对于每个x,一共有$(n/x)^2$个矩形需要考虑。由于

$$\sum_{x | n} (n/x)^2 = n^2 \sum_{x | n} 1/x^2 < n^2 \sum_{x=1}^{+\infty}1/x^2 = n^2 \pi^2/6$$

因此这个方法的复杂度是O(n^2)。[soln1]

更复杂一些的解法2

这种方法更巧妙(不过大概也更难想到)。

  • 找出矩形中每一行中所有连续的0或1线段的长度的最大公约数
  • 对矩形的每一列同样求最大公约数
  • 则该最大公约数就是所求x

如果矩形能被压缩,则显然上述条件是满足的。从上述条件推出能被压缩也是比较简单的:首先将每一行压缩成n/x个点,然后再对列进行压缩即可。[soln2]

代码

解法1

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
#include <iostream>
#include <cstdio>
using namespace std;
bool matrix[5205][5205];
int colSum[5205][5205];
int sum[5205][5205];
int n;

// 求左上角坐标为(lr, lc),右下角坐标为(rr, rc)的矩形和
int getSum(int lr, int lc, int rr, int rc) {
int s11 = sum[lr-1][lc-1];
int s12 = sum[lr-1][rc] - s11;
return sum[rr][rc] - s12 - sum[rr][lc-1];
}

int main() {
cin >> n;
char c;
for (int i = 1; i <= n; i++) {
for (int j = 0; j < n / 4; j++) {
scanf(" %c", &c);
int x = '0' <= c && c <= '9' ? c - '0' : c - 'A' + 10;
matrix[i][j*4 + 1] = (x & 8) > 0;
matrix[i][j*4 + 2] = (x & 4) > 0;
matrix[i][j*4 + 3] = (x & 2) > 0;
matrix[i][j*4 + 4] = (x & 1) > 0;
}
}
// 求和
// sum[i][j]:右下端点为(i, j)的矩形的和
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
colSum[i][j] = colSum[i-1][j] + matrix[i][j];
}
}
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
sum[i][j] = sum[i][j-1] + colSum[i][j];
}
}
for (int x = n; x >= 1; x--) {
if (n % x != 0) continue;
bool ok = true;
for (int i = 1; i <= n; i += x) {
for (int j = 1; j <= n; j += x) {
int s = getSum(i, j, i + x - 1, j + x - 1);
if (!(s == 0 || s == x * x)) {
ok = false;
break;
}
}
if (!ok) break;
}
if (ok) {
cout << x << endl;
return 0;
}
}
return 0;
}

解法2

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
#include <iostream>
#include <cstdio>
using namespace std;
bool matrix[5205][5205];
int n;

int gcd(int a, int b) {
if (b == 0) return a;
return gcd(b, a % b);
}

int main() {
cin >> n;
char c;
for (int i = 1; i <= n; i++) {
for (int j = 0; j < n / 4; j++) {
scanf(" %c", &c);
int x = '0' <= c && c <= '9' ? c - '0' : c - 'A' + 10;
matrix[i][j*4 + 1] = (x & 8) > 0;
matrix[i][j*4 + 2] = (x & 4) > 0;
matrix[i][j*4 + 3] = (x & 2) > 0;
matrix[i][j*4 + 4] = (x & 1) > 0;
}
}
int ans = n;
for (int i = 1; i <= n; i++) {
int start = 1;
for (int j = 2; j <= n + 1; j++) {
if (j > n || matrix[i][j] != matrix[i][j-1]) {
ans = gcd(ans, j - start);
start = j;
}
}
}
for (int i = 1; i <= n; i++) {
int start = 1;
for (int j = 2; j <= n + 1; j++) {
if (j > n || matrix[j][i] != matrix[j-1][i]) {
ans = gcd(ans, j - start);
start = j;
}
}
}
cout << ans << endl;
return 0;
}

题目来源:https://codeforces.com/contest/1107/problem/C

提交次数:1/1

题意

给定n个英文小写字符和对应的n个值,按某个字符就可以得到对应的值,不能连续按某个字符超过k次,问得到的值的总和最大是多少。

分析

这次比赛我做得乱七八糟。从提交数量来看,C应该是道很简单的题,但是我却做不出来。事后我发现我看错题了。

PS. 我决定以后CF比赛中我能做出来的题就不写题解了。不然题目实在太多了。。。


对于一串连续的字符,如果它的长度超过了k,那么从里面挑k个最大值就行。没了!

(比赛的时候我以为是要把这个串分割成若干个长度小于k的串。)

[soln1]: Codeforces Blog - Quick unofficial editorial for Educational Round 59 (Div. 2)

[soln2]: Codeforces Blog - Educational Codeforces Round 59 Editorial

代码

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
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long LL;
int k, n;
LL a[200005];
char s[200005];
int main() {
cin >> n >> k;
for (int i = 0; i < n; i++) {
cin >> a[i];
}
cin >> s;
LL ans = 0;
int start = 0;
for (int i = 1; i <= n; i++) {
if (i == n || s[i] != s[i-1]) {
if (i - start > k)
sort(a + start, a + i);
for (int j = 0; j < k && i-j-1 >= start; j++)
ans += a[i - j - 1];
start = i;
}
}
cout << ans << endl;
return 0;
}

题目来源:https://codeforces.com/contest/1102/problem/F

提交次数:2/3

题意

给定一个n1<=n<=16)行m列的矩阵,重新排列矩阵的各行,使得逐列遍历矩阵时相邻两个数之差绝对值的最小值最大。

分析

还是一道状态压缩DP。首先计算出每两行之间的距离(注意第一行和最后一行的距离)。

然后对于每种状态,枚举可能的起始结点,最大化路径上边权重的最小值。状态总数是n * 2^n(末尾结点*状态总数),枚举起始结点的代价为O(n),枚举上一个结点的代价是O(n),总计算复杂度是O(n^3 * 2^n)。如果不用递归还要多一个O(n),不知道有没有解决这个问题的方法。

另一种比较神奇的方法是二分答案,然后在图上寻找回路。题解里的具体方法是这样的:枚举起始点i,对于每个点j,寻找一条从ij的经过了所有结点的路径,然后再判断ji是否有路径。题解[1]里这种方法的复杂度是O(n^2 * log(MAXN) * 2^n)。但是我并不会题解里的写法,所以我写出来的还是平凡的O(n^3 * 2^n)的求哈密顿回路法……

代码

迭代写法的DP

相当慢……

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
#include <iostream>
#include <cmath>
#include <cstdio>
using namespace std;
int a[16][10000];
int nextOk[16][16];
int firstLastOk[16][16];
int f[16][16][1 << 16];
int n, m, k;
int main() {
cin >> n >> m;
for (int i = 0; i < n; i++)
for (int j = 0; j < m; j++)
scanf("%d", &a[i][j]);
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
int x = 1e9;
for (int k = 0; k < m; k++) {
x = min(x, (int) abs(a[i][k] - a[j][k]));
if (x == 0) break;
}
nextOk[i][j] = nextOk[j][i] = x;
}
}
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
int x = 1e9;
for (int k = 1; k < m; k++) {
x = min(x, (int) abs(a[j][k-1] - a[i][k]));
if (x == 0) break;
}
firstLastOk[i][j] = x;
}
}

if (n == 1) {
cout << firstLastOk[0][0] << endl;
return 0;
}

int ans = 0;
// 枚举路径长度
for (int len = 1; len <= n; len++) {
for (int status = 0; status < (1 << n); status++) {
if (__builtin_popcount(status) != len) continue;
for (int first = 0; first < n; first++) {
if (!(status & (1 << first))) continue;
if (len == 1) {
f[first][first][status] = 1e9;
continue;
}
for (int cur = 0; cur < n; cur++) {
if (!(status & (1 << cur)) || first == cur) continue;
f[first][cur][status] = 0;
for (int last = 0; last < n; last++) {
if (!(status & (1 << last)) || cur == last) continue;
int x = min(f[first][last][status ^ (1 << cur)], nextOk[last][cur]);
if (len == n) x = min(x, firstLastOk[first][cur]);
f[first][cur][status] = max(f[first][cur][status], x);
}
if (len == n) ans = max(f[first][cur][status], ans);
}
}
}
}
cout << ans << endl;
return 0;
}

递归写法的DP+二分答案

因为常数写多了所以甚至更慢了……

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
83
84
85
86
87
88
89
90
91
#include <iostream>
#include <cmath>
#include <cstring>
#include <cstdio>
using namespace std;
int a[16][10000];
int nextOk[16][16];
int firstLastOk[16][16];
int f[16][1 << 16];
bool g[16][16];
int n, m, k;

int calc(int x, int state) {
if (f[x][state] != -1) return f[x][state];
f[x][state] = 0;
for (int i = 0; i < n; i++) {
if (i != x && (state & (1 << i)) && g[i][x] && calc(i, state ^ (1 << x))) {
f[x][state] = 1;
break;
}
}
return f[x][state];
}

bool isOk(int thres) {
memset(g, 0, sizeof(g));
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (i != j && nextOk[i][j] >= thres)
g[i][j] = true;
}
}

for (int i = 0; i < n; i++) {
memset(f, -1, sizeof(f)); // 因为这句memset位置错了,调了一阵子
// 控制只能从i开始
for (int j = 0; j < n; j++)
f[j][1 << j] = j == i ? 1 : 0;
for (int j = 0; j < n; j++) {
if (firstLastOk[i][j] >= thres) {
if (calc(j, (1 << n) - 1)) return true;
}
}
}
return false;
}

int main() {
cin >> n >> m;
for (int i = 0; i < n; i++)
for (int j = 0; j < m; j++)
scanf("%d", &a[i][j]);
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
int x = 1e9;
for (int k = 0; k < m; k++) {
x = min(x, (int) abs(a[i][k] - a[j][k]));
if (x == 0) break;
}
nextOk[i][j] = nextOk[j][i] = x;
}
}
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
int x = 1e9;
for (int k = 1; k < m; k++) {
x = min(x, (int) abs(a[j][k-1] - a[i][k]));
if (x == 0) break;
}
firstLastOk[i][j] = x;
}
}

if (n == 1) {
cout << firstLastOk[0][0] << endl;
return 0;
}

// 二分答案
// 这个写法是从题解里抄的(感觉也不是很优雅啊)
// <del>谁叫你也写不出优雅的</del>
int l = 0, r = 1e9;
while (l < r - 1) {
int m = (l + r) >> 1;
if (isOk(m)) l = m;
else r = m;
}
if (isOk(r)) cout << r << endl;
else cout << l << endl;
return 0;
}

  1. Codeforces Round #531 (Div. 3) Editorial

题目来源:https://codeforces.com/contest/1102/problem/E

提交次数:1/1

题意

给定一个长度为n的数组a,要求为a生成一个对应的数组b,满足:

  • b[0] = 0
  • 对于任意0 <= i < j <= n,如果满足a[i] == a[j],必有b[i] == b[j](不过a[i] != a[j]时也可能有b[i] == b[j]
  • 任取0 <= i < n - 1,必有b[i] = b[i+1]b[i] + 1 = b[i+1]

问共有多少种可能的b

分析

显然b[i]是一个递增序列,因此可以自然推出,若a[i] == a[j],则必有b[i] == b[i+1] == ... = b[j],也就是说,对于a中任意位置两个相等的元素,它们在b中对应的是一整段相等的元素。显然这种元素相等是可能会发生重叠的,因此一个自然的想法就是,把重复的元素建模成线段,然后合并发生overlap的线段以得到相等元素的最长长度。

我的做法是,从后向前遍历a,如果发现当前元素和后面的元素重复了,则取index最靠后的元素,组成一条线段,插入到栈中与其他元素合并;否则把它自己的index作为一条线段插入到栈中。最后栈中留下的就是几条互不相交(且并组成了整个区间)的线段。

对于(除了第一条之外)每条线段,我们可以选择让它的值和前一条相等,也可以选择让它的值是前一条+1。每种选择都会导致生成一种新的b。于是结果是2^{线段数-1}

例子:对于a = {1, 2, 1, 2, 3},1对应的线段是[0, 2],2对应的线段是[1, 3],3对应的线段是[4, 4];合并之后得到两条线段,[0, 3][1, 4];只有两种b,分别是{0, 0, 0, 0, 0}{0, 0, 0, 0, 1}

代码

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
#include <iostream>
#include <vector>
#include <map>
using namespace std;
int a[200005];
int n;

typedef long long int LL;
const LL P = 998244353;

LL pow2(LL x) {
LL pow = 2, ans = 1;
while (x > 0) {
if (x & 1)
ans = (ans * pow) % P;
pow = (pow * pow) % P;
x >>= 1;
}
return ans;
}

int main() {
map<int, int> indMap;
vector<pair<int, int>> s;
cin >> n;
for (int i = 0; i < n; i++) {
cin >> a[i];
if (indMap.find(a[i]) == indMap.end()) {
indMap[a[i]] = i;
}
}
for (int i = n - 1; i >= 0; i--) {
pair<int, int> interval;
if (indMap.find(a[i]) != indMap.end() && indMap[a[i]] < i) {
interval = make_pair(indMap[a[i]], i);
}
else {
interval = make_pair(i, i);
}
if (!s.empty() && s.back().first <= interval.first && s.back().second >= interval.second)
continue;
if (!s.empty() && interval.second >= s.back().first) {
interval.second = s.back().second;
s.pop_back();
s.push_back(interval);
}
if (s.empty() || interval.second < s.back().first)
s.push_back(interval);
}


int cnt = 0;
if (!s.empty() && s.front().second < n - 1) cnt++;
if (!s.empty() && s.back().first > 0) cnt++;
for (int i = 0; i < s.size(); i++) {
cnt++;
// 本条线段和前一条线段之间的间隔
if (i > 0 && s[i - 1].second < s[i].first - 1)
cnt++;
}
cout << pow2(cnt - 1) << endl;
return 0;
}

题目来源:https://codeforces.com/contest/1102/problem/D

提交次数:1/1

题意

给定一个只包含0、1、2的长度是3的倍数的字符串,要求替换最少数量的字符,使得其中0、1、2的数量相等,且得到的字符串字典序最小。

分析

这道题让我想起之前的某道USACO题(Sorting a Three-Valued Sequence)。好吧,其实没啥太大的关系(除了都是三值序列以外)。

既然要求替换最少数量的字符,那么把什么字符换成什么字符,以及换多少个其实都是确定的。如果这一点听起来不是很直接的话……比如,0的数量和1的数量都比n/3多,那么多出来的0和1都要换成2。如果0的数量和1的数量都比n/3少,那么多出来的2要分别换成0和1。实际上只有这两种情况。

然后就可以开始考虑怎么换了。显然,如果要把小的字符换成大的字符,应该从后向前换,换完为止;如果把大的字符换成小的字符,应该从前往后换,也是换完为止。

光考虑这一点还不够。比如说我们需要把两个0换成1,两个0换成2,那么应该先(从后向前)换2,再(从后向前)换1。

然后就能过啦。

代码

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
#include <iostream>
using namespace std;
int n;
int a[300000];
int cnt[3];
int main() {
char c;
cin >> n;
for (int i = 0; i < n; i++) {
cin >> c;
a[i] = c - '0';
cnt[a[i]]++;
}
int m = n / 3;
// 从i改成j
int order[3][3] = {
{2, 1, 0},
{0, 1, 2},
{0, 1, 2}
};
for (int i = 0; i < 3; i++) {
for (int j1 = 0; j1 < 3; j1++) {
int j = order[i][j1];
if (i == j) continue;
if (cnt[i] == m || cnt[j] == m) continue;
if (cnt[i] < m || cnt[j] > m) continue;
// 从后向前改
if (i < j) {
for (int k = n - 1; k >= 0; k--) {
if (cnt[i] == m || cnt[j] == m) break;
if (a[k] == i) {
a[k] = j;
cnt[i]--;
cnt[j]++;
}
}
}
// 从前向后改
if (i > j) {
for (int k = 0; k < n; k++) {
if (cnt[i] == m || cnt[j] == m) break;
if (a[k] == i) {
a[k] = j;
cnt[i]--;
cnt[j]++;
}
}
}
}
}
for (int i = 0; i < n; i++)
cout << a[i];
cout << endl;
return 0;
}

题目来源:https://codeforces.com/contest/1102/problem/C

提交次数:1/1

题意

n扇门,每扇门的耐久度是a[i],两个人轮流对这些门做一些操作:

  • 我可以任选一扇门,如果它的耐久度是b[i],则可以将它降低到max(0, b[i]-x)
  • 之后对方可以选择一扇门,如果它的耐久度是b[i]b[i] > 0,则可以将它增加到b[i]+y
  • 两人轮流进行游戏

游戏共有10^100轮。问游戏结束后耐久度变成0的门的数量最多是多少?

分析

这道题说是博弈论,其实没啥博弈的……(或者说没有什么复杂的算法)

如果x > y,那么最后肯定是我方完全胜利(这么多轮,无论对方怎么加耐久,我们都可以和对方对敲,然后把所有门都敲爆……)。

如果x <= y,事情就变得有些复杂了。如果我们任选一扇门来敲(且没有敲到0),那么对方在下一轮就可以把它补好,甚至比之前还牢靠(y > x);所以我们选能敲到0的门才有效果。对方的最佳策略显然就是把那些耐久值<=x的门赶紧补齐,补到一下敲不坏为止。所以我方能最终敲坏的门的数量就是耐久值<=x的门的总数除2(取ceil)(因为是我方先开始游戏,可以多敲坏一扇门)。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
#include <iostream>
using namespace std;
int a[100];
int main() {
int n, x, y, cnt = 0;
cin >> n >> x >> y;
for (int i = 0; i < n; i++) {
cin >> a[i];
if (a[i] <= x) cnt++;
}
if (x > y) cout << n << endl;
else cout << (cnt + 1) / 2 << endl;
return 0;
}

题目来源:https://codeforces.com/contest/1102/problem/B

提交次数:1/4

题意

给定n个整数,要求将它们染成k种颜色,满足:

  • 每种颜色至少出现一次
  • 相同的整数不能染成相同的颜色

求任意一种染色方法。

分析

比赛的时候被Hack了,不过好像也无所谓,因为被Hack说明本来就做错了(

最开始的做法是这样的:

  • 计算每种整数的数量(如果有超过k个的,则显然无法满足要求)
  • 为每种整数记录当前颜色上限,当前出现过的颜色的upper-bound
  • 如果当前整数之前还没有被染过色,则将它对应的初始颜色值设为当前upper-bound;否则进行对应的染色,更新颜色上限和upper-bound

显然这种做法存在一个问题:颜色还是会重复,在比较tricky的情况下就会爆掉,比如n=k的情况。于是我被hack了。

这个做法的想法本身倒是没有什么问题,在颜色还没有出现完之前,认定每种整数出现颜色的起始值是之前所有类型整数的数量之和就行了。

题解里的做法看起来更巧妙(不过复杂度升高了……),就是先把整个数组排序,然后直接把每个元素染成颜色i % k。这样,连续的小于k个元素恰好不会被染成重复的颜色。[1]这也说明了,判断完整数数量之后,只要n>=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
37
38
39
40
41
42
43
44
#include <iostream>
#include <cstring>
using namespace std;
int a[5000];
int cnt[5001];
int colorCnt[5001];
int color[5000];
int main() {
int n, k;
cin >> n >> k;
for (int i = 0; i < n; i++) {
cin >> a[i];
cnt[a[i]]++;
}
// 必然失败的情况
for (int i = 1; i <= 5000; i++) {
if (cnt[i] > k) {
cout << "NO" << endl;
return 0;
}
}

int nextColor = 1, maxColor = -1;
for (int i = 0; i < n; i++) {
// 如果nextColor大于k,说明已经全部出现完了,可以随便染
if (colorCnt[a[i]] == 0) {
colorCnt[a[i]] = nextColor > k ? 1 : nextColor;
nextColor += cnt[a[i]];
}
// 模k循环染色
color[i] = colorCnt[a[i]]++;
if (colorCnt[a[i]] > k) colorCnt[a[i]] -= k;
maxColor = max(color[i], maxColor);
}
if (nextColor < k) {
cout << "NO" << endl;
return 0;
}
cout << "YES" << endl;
for (int i = 0; i < n; i++)
cout << color[i] << ' ';
cout << endl;
return 0;
}

  1. Codeforces Round #531 (Div. 3) Editorial