算法
(前缀和,数学,组合计数,乘法原理,加法原理) $O(\frac{n^2}{9})$
一个魔法阵如下所示:
A和B之间的距离是2t,B和C之间的距离是6t+k,C和D之间的距离是t,其中t, k均为正整数。
左边红色部分框出的A和B是绑定的,右边绿色部分框出的C和D也是绑定的。
因此整个系统共有三个自由度:t、红色部分、绿色部分。
同时枚举三个自由度的计算量过大。在1秒内,我们只能枚举其中两个自由度。
首先枚举t。接下来并列枚举绿色部分和红色部分:
- 从左到右枚举绿色部分,当绿色部分固定后,则C应该累加的次数是所有满足要求的A和B的
cnt[A] * cnt[B]
的和,再乘以cnt[D]
。其中cnt[A], cnt[B], cnt[D]
是A, B, D
出现的次数。所有满足要求的A和B就是整个线段左边的某个前缀,因此可以利用前缀和算法来加速计算。cnt[D]
同理可得。 - 从右到左枚举红色部分可做类似处理。
时间复杂度
由于A, B, C, D均在1到n之间,因此 $1 \le t \le \frac{n-2}{9}$。所以总枚举次数大约是 $\frac{n-2}{9} * n = O(\frac{n^2}{9}) = 2.5 \times 10^7$。
参考文献
C++ 代码
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 15010, M = 40010;
int n, m;
int cnt[N];
int a[N], b[N], c[N], d[N], x[M];
int main()
{
scanf("%d%d", &n, &m);
for (int i = 1; i <= m; i ++ )
{
scanf("%d", &x[i]);
cnt[x[i]] ++ ;
}
for (int t = 1; t * 9 + 2 <= n; t ++ )
{
int sum = 0;
for (int D = t * 9 + 2; D <= n; D ++ )
{
int A = D - t * 9 - 1;
int B = A + t * 2;
int C = D - t;
sum += cnt[A] * cnt[B];
c[C] += sum * cnt[D];
d[D] += sum * cnt[C];
}
sum = 0;
for (int A = n - t * 9 - 1; A; A -- )
{
int B = A + t * 2;
int D = A + t * 9 + 1;
int C = D - t;
sum += cnt[C] * cnt[D];
a[A] += sum * cnt[B];
b[B] += sum * cnt[A];
}
}
for (int i = 1; i <= m; i ++ ) printf("%d %d %d %d\n", a[x[i]], b[x[i]], c[x[i]], d[x[i]]);
return 0;
}
请问A可以从小到大枚举么?
老师您好,在这想您提问,确有不妥,不过我还是想问一下,为什么刷了LeetCode200道,笔试算法题,还是通过率极低,咋办啊,,,,,我刚才在你这看见了LeetCode题库,请问,您是按照刷题优先顺序排列?我可以按照这顺序学习吧.谢谢老师!
这里leetcode的题解是按照题目编号排列的。
我之前按专题讲过一些leetcode的题目,可以参考一下。直播录像在这里。
为了提高通过率,可以刷一些难度较大的题目,比如可以在这里搜一些竞赛题目来做。