这次比赛做得乱七八糟,事实上一共只做出来两道题,结果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://leetcode.com/problems/broken-calculator/description/

标记难度:Medium

提交次数:1/1

代码效率:100.00%(4ms)

题意

给定两个数XY,可以对X执行以下两种操作:

  • 乘2
  • 减1

问最少需要对X执行多少次操作才能将X变成Y?(XY的范围都是1e9)

分析

比赛的时候我居然首先就写了一个BFS,然后自然是超时了……

后来就思考怎么用数学方法解决,也没想出来,各种各样奇怪的贪心大部分也是错的。

后来想到了对X的操作就等同于对Y的除2和加1两种操作,不过想到了也没什么大的突破……

然后就没做出来……


这道题考虑对Y的操作比考虑对X的操作要更容易。如果对Y加1两次再除2,显然不如先除2再加1,因此不会出现两次连续的加1操作。题解[1]是这么说的,不过我感觉有一点不太严谨。倒不如这么说:首先假设有一个最优的操作顺序,需要除2n次,且在第一次除2之前需要加1a[0]次,在第二次除2之前需要加1a[1]次,……,在最后一次除2之后需要加1a[n]次。此时总操作次数为a[0] + a[1] + ... + a[n] + n。假如存在i < na[i] > 1,那显然可以把多余的+1操作下移,变成a'[i] = a[i] - 2 * (a[i]/2)a'[i+1] = a[i+1] + a[i]/2,总操作次数减少a[i]/2次。如果a'[i+1]仍然大于1,则可以继续尝试下移,直到除了a[n]以外的所有a[i]都变成0或1为止。

事实上我大概是做了一个Exchange类型的贪心证明……

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
int brokenCalc(int X, int Y) {
int ans = 0;
while (Y > X) {
if (Y % 2 == 0) {
Y /= 2;
ans++;
}
else {
Y = (Y + 1) / 2;
ans += 2;
}
}
return ans + (X - Y);
}
};

  1. Leetcode Official Solution for 991. Broken Calculator

题意

洛谷 P1467 循环数 Runaround Numbers

定义循环数为满足以下条件的整数:

  • 各个数位都不重复
  • 从最左边的数位开始进行如下操作:
    • 向右循环数该数位对应的数字个数
    • 然后从得到的数位开始继续数
    • 在各个数位都(不重不漏地)开始数了一遍之后,会回到最开始的数

给定正整数M,问大于M的下一个循环数是多少?

分析

按我惯常的习惯,肯定是先去OEIS上查一查,不过结果是并没有。

做题的时候,我首先写了一个暴力判断某个数是否为循环数的代码。本来应该想想怎么优化(毕竟M据说最多9位,如果直接暴力挨个判断比M大的数会超时的吧),但是那天不知道哪根神经出了毛病,直接把暴力给交上去了。结果居然就过了,还挺快……??

看了一眼测试数据,发现这范围跟说好的不一样啊,不是说M最多有9位吗,怎么这里最多只有7位?

1
2
3
4
5
6
7
8
9
10
11
12
13
14
------- test 1 [length 3 bytes] ----
99
------- test 2 [length 7 bytes] ----
111110
------- test 3 [length 7 bytes] ----
134259
------- test 4 [length 7 bytes] ----
348761
------- test 5 [length 8 bytes] ----
1000000
------- test 6 [length 8 bytes] ----
5000000
------- test 7 [length 8 bytes] ----
9000000

仔细一想,我意识到,9位的循环数是不存在的:假设这样的循环数是存在的,因为要求各个数位不同,那么必须有一个数位为9;但是这个数位数了9位之后只会回到自己,没办法构成循环。由此还可以得到一个推论,n位的循环数中必然不存在数位n。所以,暴力代码能过这件事看起来就正常一点了。

但是为什么测试数据只有7位呢?我尝试把所有长度<=9位的循环数都打印出来,结果得到的最大的数是9682415。所以,为什么8位的循环数也不存在呢?

我又仔细想了一下,发现8位的循环数确实不应该存在(而不是我的暴力写错了之类的)。由上面的推论可以得到,8位的循环数中没有8,因此只能是1-7和9这8个数字。假设有这样一个8位的循环数,我们从左侧的第i位出发,遍历了所有数位各一次后,当前的数位应该是(i + 1 + 2 + .. + 7 + 9) % 8,且这个数位应该还是第i位。问题是,1 + 2 + .. + 7 + 9 = 37,这样根本没办法回到原来的位的!所以8位的循环数必然是不存在的。由此还可以得出另一个推论,就是n位的循环数的数位之和必然模n余0。


当然,比较正确(而不依靠随便乱交……)的做法是,枚举出所有长度为n且各个数位不相等的数,然后再判断它们是否为循环数——因为9!=362880,所以不会超时。

题解里还有一种比较神奇的做法——从M直接生成下一个各个数位都不相等的数,然后再判断它们是否为循环数。不过他到底是怎么生成下一个数的我就没细看了……

分析

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
/*
ID: zhanghu15
TASK: runround
LANG: C++14
*/

#include <iostream>
#include <fstream>
#include <sstream>
#include <vector>
#include <algorithm>
#include <cstring>
#include <cmath>

using namespace std;
typedef long long int LL;

bool test(int x) {
int digits[10];
int cnt[10];
memset(cnt, 0, sizeof(cnt));
int n = 0;
while (x > 0) {
digits[n++] = x % 10;
if (cnt[x % 10]) return false;
cnt[x % 10]++;
x /= 10;
}
bool visited[10];
memset(visited, 0, sizeof(visited));
int cur = n - 1;
for (int i = 0; i < n; i++) {
visited[cur] = true;
int next = ((cur - digits[cur]) % n + n) % n;
if (visited[next] && i != n - 1) return false;
cur = next;
}
return cur == n - 1;
}

int main() {
ofstream fout("runround.out");
ifstream fin("runround.in");
int M;
fin >> M;
for (LL i = M + 1; i <= (LL) 1e10; i++)
if (test(i)) {
fout << i << endl;
return 0;
}
return 0;
}

题意

洛谷 P1458 顺序的分数 Ordered Fractions

给定N,求[0, 1]范围内分母小于等于N的所有既约分数,按大小排序。(1 <= N <= 160

分析

作为一道普通的题……可以说它是考察运算符重载之类的花样的(至少对C++选手是这样)。当然也可以写得更简单一些。总之,我就直接枚举了所有这个范围内的分数,把所有既约分数找出来,排了个序,然后输出。

法里数列(Farey sequence)

当然,这道题的题解里还有另一个生成解法:

  • 首先生成列表[0/1, 1/1]
  • 在列表的每两个分数之间插入一个新的分数,其分子和分母各为相邻两个分数分子和分母的和;于是得到:[0/1, 1/2, 1/1]
  • 以此类推:[0/1, 1/3, 1/2, 2/3, 1/1]
  • 继续以此类推:[0/1, 1/4, 1/3, 2/5, 1/2, 3/5, 2/3, 3/4, 1/1]
  • 直到新生成的分数的分母都大于N为止

我觉得这个方法很神奇。通过非常简单的数学推导就可以说明,将两个分数的分子和分母分别相加,得到的新分数的值位于这两个分数之间:

已知$\frac{a_1}{b_1} < \frac{a_2}{b_2}$,即$a_1b_2 < a_2b_1$;

两侧都加上$a_1b_1$,化简后得到$\frac{a_1}{b_1} < \frac{a_1 + a_2}{b_1 + b_2}$;

另一侧同理。

当然,这并不能说明很多其他的问题,比如为什么这种生成方法生成的都是既约分数,而且是不重不漏的。这时候就需要使用Farey sequence的一些性质了。n阶的Farey sequence就是我们题目里所求的序列。它的一个性质是这样的:如果$a/b$和$c/d$在某阶的Farey sequence中是相邻的,那么当Farey sequence的阶增加,它们之间出现的第一项就是$(a+c)/(b+d)$,且这一项会第一次出现在$b + d$阶的数列中。这个生成算法就利用了这一性质:它每次生成的并不严格是某一阶的Farey sequence,而可能会多一些项出来;不过这并不重要,因为它们迟早会出现的。

还有一些详细的分析就不写了,总之这个想法很有趣。

代码

普通的代码

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
/*
ID: zhanghu15
TASK: frac1
LANG: C++14
*/

#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <cstring>
#include <cmath>

using namespace std;
typedef long long int LL;

struct Frac {
// 我着实不想去记分子和分母的英文了……
int up;
int down;

Frac() {
up = down = 0;
}

Frac(int x, int y) {
up = x;
down = y;
}

friend bool operator < (const Frac& f1, const Frac& f2) {
return f1.up * f2.down < f1.down * f2.up;
}
};

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

Frac f[160000];
int N;

int main() {
ofstream fout("frac1.out");
ifstream fin("frac1.in");
fin >> N;
int n = 0;
for (int i = 1; i <= N; i++) {
for (int j = 0; j <= i; j++) {
if (gcd(i, j) > 1) continue;
f[n++] = Frac(j, i);
}
}
sort(f, f + n);
for (int i = 0; i < n; i++)
fout << f[i].up << '/' << f[i].down << endl;
return 0;
}

Farey数列生成器

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
/*
ID: zhanghu15
TASK: frac1
LANG: C++14
*/

#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <cstring>
#include <cmath>

using namespace std;
typedef long long int LL;

ofstream fout("frac1.out");
ifstream fin("frac1.in");

int N;

void farey(int a1, int b1, int a2, int b2) {
if (b1 + b2 > N) return;
farey(a1, b1, a1 + a2, b1 + b2);
fout << (a1 + a2) << '/' << (b1 + b2) << endl;
farey(a1 + a2, b1 + b2, a2, b2);
}

int main() {
fin >> N;
fout << "0/1" << endl;
farey(0, 1, 1, 1);
fout << "1/1" << endl;
return 0;
}

题目来源: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;
}