题目来源:https://leetcode.com/problems/largest-perimeter-triangle/description/

标记难度:Easy

提交次数:1/1

代码效率:20.00%(64ms)

题意

给定N个正数(N<=10000),求以这些正数作为边长能组成的周长最大的三角形的周长。

分析

我第一次看的时候看成了面积,好在及时纠偏了。(问题:如果是面积,那应该怎么做呢?)

显然,用O(N^3)的方法(枚举每种组合成三角形的方式)可做,但是肯定会超时。那么不妨考虑只选两条边,然后用某种方法选出最大的第三条边的过程。(虽然O(N^2)也会超时,但是姑且先这么做着。)

不妨先将数组A排序。如果先尝试选出较小的两条边A[i]A[j]i < j),那么第三条边A[k]需要满足A[j]-A[i] < A[k] < A[i]+A[j]。那么肯定是选择小于A[i]+A[j]的最大的A[k]。而且我们希望A[i]+A[j]尽量大……

用上面这种思路肯定是可以做出来的,因为它本质上和这一种一样,不过我觉得这样更好想一些。先尝试选择较大的两条边A[j]A[k],则A[i]需要满足A[k]-A[j] < A[i] < A[j]+A[k]。因为A[i]是较小的边,因此必然满足A[i] < A[j]+A[k],于是只需考虑A[i] > A[k]-A[j]这一条件。在选定A[k]之后,选择最大的比它小的A[j](也就是A[k-1])可以同时最大化这条边的边长和A[i],因此只需对于每个k >= 2,找出满足A[i] > A[k]-A[k-1] && i < k-1的最大的i

这种做法的复杂度是O(N*log(N)),排序是O(N*log(N)),对于每个k求upper-bound也是O(N*log(N))

显然后一个O(N*log(N))有点儿蠢。如果满足A[i] > A[k]-A[k-1]的最小的i小于k-1,那么无论如何都应该选择A[i] = A[k-2];否则就找不到满足条件的三角形。所以直接看A[k]A[k-1]A[k-2]就可以了!

事实上,按照题解的说法:假设三条边的边长是a, b, c,且满足a <= b <= c,那么这三条边能组成三角形的充要条件是a + b > c。对于每个c,考虑最大的a, b就足够了![1]

代码

这里是比较愚蠢的做法……

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
int largestPerimeter(vector<int>& A) {
int n = A.size();
int ans = 0;
sort(A.begin(), A.end());
for (int i = n - 2; i > 0; i--) {
int thes = A[i+1] - A[i];
int idx = upper_bound(A.begin(), A.end(), thes) - A.begin();
if (idx < n && idx < i)
ans = max(ans, A[i+1] + A[i] + A[i - 1]);
}
return ans;
}
};

  1. Leetcode Official Solution for 976

题目来源:https://leetcode.com/problems/k-closest-points-to-origin/description/

标记难度:Easy

提交次数:2/5

代码效率:

  • 普通方法:80.0%(208ms)
  • 堆:60.00%(212ms)
  • 快排:40.00%(224ms)

题意

给定平面上的若干个(<=10000)点,求距离原点最近的K个点。保证结果对应的点集唯一,以任意顺序返回都可以。

分析

其实我睡过了这次比赛。随后又撞上期末考试和毕设,感觉流年不利。


显然可以把距离算出来之后排序,然后取前K个点,时间复杂度为O(N*log(N))

如果想做得更好一点的话,可以用一个大小为K的堆来维护距离前K小的点,时间复杂度为O(N*log(K))

题解里给出了一种神奇的方法,思路是用类似于快排的方法求前K小的点,感觉很有趣。不过为了严格起见,大概还是要每次随机选主元才行……[1]

快排!快排!

为了写好题解里快排的方法,浪费了一两个小时。我果然又把快排的写法忘光了!姑且先总结一下。

快排的第一种写法不妨称之为交替填坑法。这种做法的核心规律是,先把序列最靠左的元素拿出来作为主元(并空出来一个坑),然后从右向左找到第一个可以填这个坑的元素(也就是第一个比主元小的元素),把它拿出来填到这个坑里。此时右边就空出来一个新坑。然后从左边刚被填完的坑向右扫描,找到第一个能够填右边的坑的元素(也就是第一个比主元大的元素),把它拿出来填到右边的坑里。此时左边又空出来一个新坑……以此类推。最后中间剩下一个坑,满足左边的元素都比主元小,右边的元素都比主元大,再把主元填到这个坑里。

以序列[3, 6, 5, 4, 2, 1, 0]为例:

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
| 3 | 6 | 5 | 4 | 2 | 1 | 0 |
^
pivot

pivot = 3, remove pivot
| x | 6 | 5 | 4 | 2 | 1 | 0 |
i j

pivot = 3, move A[j] to A[i], i++
| 0 | 6 | 5 | 4 | 2 | 1 | x |
i j

pivot = 3, move A[i] to A[j], j--
| 0 | x | 5 | 4 | 2 | 1 | 6 |
i j

pivot = 3, move A[j] to A[i], i++
| 0 | 1 | 5 | 4 | 2 | x | 6 |
i j

pivot = 3, move A[i] to A[j], j--
| 0 | 1 | x | 4 | 2 | 5 | 6 |
i j

pivot = 3, move A[j] to A[i], i++
| 0 | 1 | 2 | 4 | x | 5 | 6 |
i j

pivot = 3, move A[i] to A[j], j--
| 0 | 1 | 2 | x | 4 | 5 | 6 |
i j

found i==j, put pivot into i (or j)
| 0 | 1 | 2 | 3 | 4 | 5 | 6 |
i j

显然可以看出,每个周期包含两次指针移动和交换,其中ij的含义是分阶段而不同的。

此处有坑,明天再填。

2019.1.17 UPDATE:坑应该是填不动了。简单来说,还有一种常用的写法是不移出主元,而是让它在里面跟着交换。这两种写法都解决不了主元重复的问题,此时最好改成CLRS式的写法。

代码

普通方法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
vector<vector<int>> kClosest(vector<vector<int>>& points, int K) {
vector<pair<int, int>> toSort;
for (int i = 0; i < points.size(); i++) {
toSort.emplace_back(points[i][0] * points[i][0] + points[i][1] * points[i][1], i);
}
sort(toSort.begin(), toSort.end());
vector<vector<int>> ans;
for (int i = 0; i < K; i++)
ans.push_back(points[toSort[i].second]);
return ans;
}
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
vector<vector<int>> kClosest(vector<vector<int>>& points, int K) {
priority_queue<pair<int, int>> q;
for (int i = 0; i < points.size(); i++) {
q.emplace(points[i][0] * points[i][0] + points[i][1] * points[i][1], i);
if (q.size() > K) q.pop();
}
vector<vector<int>> ans;
while (!q.empty()) {
ans.push_back(points[q.top().second]);
q.pop();
}
return ans;
}
};

快排

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
class Solution {
private:
int dist(vector<int>& p) {
return p[0] * p[0] + p[1] * p[1];
}

void partition(vector<vector<int>>& points, int l, int r, int& K) {
if (l >= r) return;
if (l >= K) return;
if (r < K) return;
// int x = rand() % (r - l + 1) + l;
int x = l;
int i = l, j = r;
int pivot = dist(points[x]);
while (i < j) {
// why <, not <=?
while (dist(points[i]) < pivot && i < j) i++;
while (pivot < dist(points[j]) && i < j) j--;
if (i < j) swap(points[i], points[j]);
}
partition(points, l, i - 1, K);
partition(points, i + 1, r, K);
}

public:
vector<vector<int>> kClosest(vector<vector<int>>& points, int K) {
partition(points, 0, points.size() - 1, K);
return vector(points.begin(), points.begin() + K);
}
};

  1. Leetcode Official Solution for 973. K Closest Points to Origin

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

提交次数:1/1

题意

1, 2, ..., n分成两个集合,使得两个集合中的数之和的差的绝对值最小。

分析

这次做的531是div 3,题目相当之简单,我竟然都会做……


比赛的时候的第一直觉是,n(n+1) / 2模2余0时返回0(可以分成两个相等的集合),模2余1时返回1(大概只能凑成两个差最小为1的集合)。然后就这样交上去了。

题解里给出了证明。不妨考虑n, n-1, n-2, n-3这四个数:我们总可以把nn-3放到集合A中,把n-1n-2放到集合B中,两边的和是一样的;以此类推,这样我们就只需考虑n mod 4的情形。n mod 4等于0或3时,可以得到相同的和;等于1或2时只能得到相差为1。[1]

另一种方法是证明,对于1, 2, ..., n,我们总能得到任意从0到n(n+1) / 2的子集和。证明方法大概很简单,可以用数学归纳法,0到n的子集和易证,再多的话,减去一些就可以了。

我总觉得之前在CF上做过这道题,而且还认真考虑过分法,但是找不到题目了,真是魔幻。。

代码

1
2
3
4
5
6
7
8
9
10
11
#include <iostream>
using namespace std;
typedef long long int LL;
int main() {
LL n;
cin >> n;
LL prod = n * (n + 1) / 2;
if (prod % 2 == 0) cout << 0 << endl;
else cout << 1 << endl;
return 0;
}

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

题目来源:https://leetcode.com/problems/equal-rational-numbers/description/

标记难度:Hard

提交次数:2/4

代码效率:

  • 转成分数:4ms
  • 精度hack:4ms

题意

给定两个普通小数或循环小数的字符表示,问这两个小数是否相等。

分析

比赛的时候我没做出来,准确的说法是没做完(因为期间有其他的事情)。我的思路是这样的:

记小数的三个部分分别为ABC:则这个小数实际上就是A.BCCCCC...。记这个小数为x,在它两侧分别乘上10^B.length10^(B.length + C.length),则会得到

1
2
             10^B.length x =  AB.CCCC...
10^(B.length + C.length) x = ABC.CCCC...

下式减上式,得到

1
10^B.length (10^C.length - 1) x = ABC - AB

1
x = (ABC - AB) / (10^B.length (10^C.length - 1))

分别求出分子分母后化简,即可判断两个分数是否相同。


当然我知道,看到这道题的第一个思路一般是直接判断这两个数转成double之后是否相等。这样做显然可能有精度问题,不过因为题目要求中整数部分和非重复部分长度都很短,所以把重复部分多重复几次,还是有可能过的。[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
64
65
66
67
68
69
70
71
72
73
class Solution {
typedef long long int LL;

private:
LL pow10(int i) {
LL x = 1;
while (i--) x *= 10;
return x;
}

LL gcd(LL x, LL y) {
if (y == 0) return x;
return gcd(y, x % y);
}

pair<LL, LL> toFrac(LL A, LL lb, LL B, LL lc, LL C) {
if (lb == 0 && lc == 0) return {A, 1};
if (lc == 0) return {A * pow10(lb) + B, pow10(lb)};

LL up, down; // 分子和分母(我懒得记它们的英文了,就分数线上下好了)
LL ABC = (A * pow10(lb) + B) * pow10(lc) + C;
LL AB = A * pow10(lb) + B;
up = ABC - AB;
down = pow10(lb) * (pow10(lc) - 1);

LL g = gcd(up, down);
up /= g;
down /= g;
return {up, down};
}

// 将小数表示分成A(整数)、B(不重复部分小数)、C(重复部分小数)三个部分
// 虽然也许用stod和substr之类的函数会更快……
void parse(string S, LL& A, LL& lb, LL& B, LL& lc, LL& C) {
int flag = 0;
A = lb = B = lc = C = 0;
for (char ch: S) {
if (flag == 0) {
if ('0' <= ch && ch <= '9') A = A * 10 + ch - '0';
else if (ch == '.') {
flag = 1;
lb = B = 0;
}
}
if (flag == 1) {
if ('0' <= ch && ch <= '9') {
B = B * 10 + ch - '0';
lb++;
}
else if (ch == '('){
flag = 2;
lc = C = 0;
}
}
if (flag == 2) {
if ('0' <= ch && ch <= '9') {
C = C * 10 + ch - '0';
lc++;
}
}
}
}

public:
bool isRationalEqual(string S, string T) {
LL A, lb, B, lc, C;
parse(S, A, lb, B, lc, C);
pair<LL, LL> p1 = toFrac(A, lb, B, lc, C);
parse(T, A, lb, B, lc, C);
pair<LL, LL> p2 = toFrac(A, lb, B, lc, C);
return p1 == p2;
}
};

精度hack

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
private:
double convert(string S) {
int i = S.find('(');
if (i == -1) return stod(S);
string start = S.substr(0, i);
string rep = S.substr(i + 1, S.length() - i - 2);
for (int j = 0; j < 20; j++)
start += rep;
return stod(start);
}

public:
bool isRationalEqual(string S, string T) {
return convert(S) == convert(T);
}
};

  1. lee215's solution for Leetcode 972 - [C++/Python] Easy Cheat

题意

洛谷 P1218 [USACO1.5]特殊的质数肋骨 Superprime Rib

定义super prime为每个前缀都是质数的数。例:7,73,733,7331都是质数,所以7331是super prime。给定N,问在所有长度为N的数里,有哪些数是super prime?

分析

这其实是一道搜索题。先搜索出长度为N-1的所有super prime,然后在这些数后面分别加上1,3,7,9(去掉2和5的倍数),判断得到的数是否为质数,然后就得到了长度为N的super prime。super prime的总数并不多,所以直接这样搜就可以了,也没有更多需要剪枝的。

题解的方法比我还暴力。我先打了个1-10000的质数表;题解根本没管这个,直接DFS搜索树,然后对每个数暴力枚举2, 3, 5, 7, 9...是否是它的因子……

查了一下,这个数列是有正式定义的(只不过正式定义并不叫super prime,super-prime是别的东西),叫做Right-truncatable primes,在OEIS上的编号为A024770。好像没有什么特别有趣的性质。[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
64
65
/*
ID: zhanghu15
TASK: sprime
LANG: C++14
*/

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

using namespace std;
typedef long long int LL;

int N;

int prime[10000];
int n;
bool isPrime[10000];
void init() {
memset(isPrime, 1, sizeof(isPrime));
isPrime[1] = false;
for (int i = 2; i < 10000; i++) {
if (isPrime[i]) {
prime[n++] = i;
for (int j = i * i; j < 10000; j += i)
isPrime[j] = false;
}
}
}

bool checkIsPrime(int x) {
if (x < 10000) return isPrime[x];
for (int i = 0; i < n; i++)
if (x % prime[i] == 0)
return false;
return true;
}

int main() {
ofstream fout("sprime.out");
ifstream fin("sprime.in");

fin >> N;
init();

vector<int> sprimes = {2, 3, 5, 7};
for (int i = 2; i <= N; i++) {
vector<int> next;
for (int x: sprimes) {
for (int j = 1; j <= 9; j++) {
int y = x * 10 + j;
if (checkIsPrime(y))
next.push_back(y);
}
}
sprimes = next;
}

for (int x: sprimes) fout << x << endl;

return 0;
}

  1. OEIS - A024770 Right-truncatable primes: every prefix is prime.

题意

P1217 [USACO1.5]回文质数 Prime Palindromes

[a, b]5 <= a < b <= 100,000,000)中所有的质回文数。

分析

上次从Leetcode 906中学到的技巧是,在需要找出具有某种性质的回文数时,先生成回文数,再判断性质。这是因为生成回文数的方法实际上是很简单的,随便拿一个数,把它反过来再接到后面就行。当然,需要注意生成奇数和偶数长度两种回文数的方法。

还有就是,需要判断10^8范围内的数是否为质数时,只需要打10^4范围内的表,这是因为,10^8范围内的合数必然有10^4范围内的因子。

怎么确定上下界是一个问题。我的方法是分别计算出ab的长度,然后只生成在相应长度范围的回文数;生成之后再判断是否在范围内。


题解里更详细地叙述了从小到大生成回文数的过程:

  • 生成长度为1的回文数:用1..9进行翻转,重复中间字符,得到1..9
  • 生成长度为2的回文数:用1..9进行翻转,不重复中间字符,得到11..99
  • 生成长度为3的回文数:用10..99进行翻转,重复中间字符,得到101...999
  • 生成长度为4的回文数:用10..99进行翻转,不重复中间字符,得到1001...9999

由于回文数一共也只有10000个左右,直接全生成出来再判断是否在[a, b]范围内也可以。

另一个观察是,任何长度为偶数的回文数都是11的倍数,所以可以不管除了11之外的所有长度为偶数的回文数。[1]


质回文数也是一个被正式定义了的序列。[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
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
/*
ID: zhanghu15
TASK: pprime
LANG: C++14
*/

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

using namespace std;
typedef long long int LL;

int prime[10000];
int n;
bool isPrime[10000];
void init() {
memset(isPrime, 1, sizeof(isPrime));
isPrime[1] = false;
for (int i = 2; i < 10000; i++) {
if (isPrime[i]) {
prime[n++] = i;
for (int j = i * i; j < 10000; j += i)
isPrime[j] = false;
}
}
}

bool checkIsPrime(LL x) {
if (x < 10000) return isPrime[x];
for (int i = 0; i < n; i++) {
if (x % prime[i] == 0) return false;
}
return true;
}

LL getPalindrome(LL x, int isOdd) {
LL l = 0, d[10], y = x;
while (y > 0) {
d[l++] = y % 10;
y /= 10;
}
for (int i = isOdd; i < l; i++)
x = x*10 + d[i];
return x;
}

int getLen(LL x) {
int l = 0;
while (x > 0) {
l++;
x /= 10;
}
return l;
}

int pow10[10] = {1, 10, (int) 1e2, (int) 1e3, (int) 1e4, (int) 1e5, (int) 1e6,
(int) 1e7, (int) 1e8, (int) 1e9};

int main() {
ofstream fout("pprime.out");
ifstream fin("pprime.in");
int a, b;
fin >> a >> b;

// 算出[1, 10000]范围内所有的质数
init();

// 枚举奇数和偶数长度的回文数(注意long long int)
int len1 = getLen(a) / 2, len2 = ceil(getLen(b) / 2.0);
for (int l = len1; l <= len2; l++) {
for (LL i = pow10[l]; i < pow10[l+1]; i++) {
LL x = getPalindrome(i, 1);
if (a <= x && x <= b && checkIsPrime(x))
fout << x << endl;
}
for (LL i = pow10[l]; i < pow10[l+1]; i++) {
LL x = getPalindrome(i, 0);
if (a <= x && x <= b && checkIsPrime(x))
fout << x << endl;
}
}
return 0;
}

  1. stackexchange - Proving a palindromic integer with an even number of digits is divisible by 11

  2. OEIS - A002385 Palindromic primes: prime numbers whose decimal expansion is a palindrome.

题目来源:https://leetcode.com/problems/least-operators-to-express-number/

标记难度:Easy

提交次数:4/4

代码效率:

  • 模3法:84ms(19.17%)
  • 算log法:88ms(13.78%)
  • 打表法:80ms(30.44%)
  • 除法:84ms(19.38%)

题意

给定一个整数,判断它是否是3的幂。

追加:可以不用循环和递归吗?

分析

这可能确实是个水题,但是看到解法的数量[1]和testcase的数量时,我改变了想法。还是有值得一写的东西的。

21038个testcases??

最简单的想法就是把这个数不断除3,直到只剩1(是3的幂)或者除不尽(不是3的幂)为止。复杂度为O(log(N))

上述想法的一个升级版是,不妨直接计算出log(N)/log(3),然后判断结果是否为整数。显然需要考虑到运算精度的问题。我感觉可能专门有一些testcase是考察精度取多小的,最后我发现1e-10是比较合理的。事实上int范围内的3的幂最大是1162261467,而log(1162261467)/log(3) - log(1162261467 - 1)/log(3) = 7.83e-10log(1162261467 + 1)/log(3) - log(1162261467)/log(3) = 7.83e-10,能判断出这么小的精度就够了。

这不禁会让人想到打表这种方法,毕竟int范围内的3的幂一共也没几个,从1到1162261467(3^19)。

除了打表之外,还有一种更简单的方法。直接用1162261467去除N,能除尽就是3的幂,除不尽就不是……真是简单粗暴。

代码

模3法

1
2
3
4
5
6
7
8
9
10
11
class Solution {
public:
bool isPowerOfThree(int n) {
if (n <= 0) return false;
while (n > 1) {
if (n % 3 != 0) return false;
n /= 3;
}
return true;
}
};

算log法

1
2
3
4
5
6
7
8
9
class Solution {
public:
bool isPowerOfThree(int n) {
if (n <= 0) return false;
double pow = log(n) / log(3);
// cout << pow - floor(pow) << ' ' << ceil(pow) - pow << endl;
return pow - floor(pow) <= 1e-10 || ceil(pow) - pow <= 1e-10;
}
};

神奇的方法

非常简洁……

1
2
3
4
5
6
class Solution {
public:
bool isPowerOfThree(int n) {
return !(n <= 0) && 1162261467 % n == 0;
}
};

  1. LeetCode Official Solution - 326. Power of Three

题目来源:https://leetcode.com/problems/least-operators-to-express-number/

标记难度:Hard

提交次数:1/3

代码效率:93.04%

题意

给定正整数x,要求用x和运算符+-*/组成表达式,表达式值为target,问最少使用多少个运算符。

其中:

  1. /返回的是有理数
  2. 没有括号
  3. 优先级和平时相同
  4. 不允许使用单目运算符-

分析

比赛的时候看到这题,我感到非常懵逼。随便想了一下,大概只想到,这道题大概是要求a[0] + a[1]*x + a[2]*x^2 + ... = target。如果先不管运算符的数量,第一个问题是怎么把target拼出来。考虑到可以使用m/m=1target肯定可以拼出来,问题是怎么拼比较好。我没有多认真想,比赛就完了。

事后发现似乎需要用到类似于记忆化搜索的方法。


这道题在本质上非常类似于进制表示:

$$target = a_0 + a_1 x + a_2 x^2 + \cdots$$

但是很大的一个区别在于,它对系数(理论上)没有限制,也因此对$x$的最大幂次没有限制(因为系数可以是负的)。而且我们的目标是最小化代价。容易推断出,生成一个$x$的幂次的代价为(包含前面的+/-运算符):

$$ cost(x^e) = \begin{cases} 2 & e = 0\\ e & e \ge 1 \end{cases} $$

显然,如果要生成一个$a_e x^e$,最优的选择是都采用+或者都采用-运算符(因为同时用显然是浪费)。

因此整体的代价可以表示为

$$cost = 2 \cdot abs(a_0) + 2 \cdot abs(a_1) + 3\cdot abs(a_2) + \cdots$$

不妨首先把$target$表示成普通的$x$进制的形式:

$$target = b_0 + b_1 x + b_2 x^2 + \cdots + b_n x^n, , 0 \le b_i < x$$

可以认为$a_i$是在$b_i$的基础上得到的,例如:

$$target = (b_0 - x + x^2) + (b_1+1)x + (b_2-1) x^2 + \cdots$$

这个式子看起来好像借位,不过比实际中的借位要自由,因为现实的进制中不会出现$b_0$这一位向$b_2$借位的情况。

此时有$a_0 = b_0 - x + x^2, , a_1 = b_1 + 1, , a_2 = b_2 - 1$。显然此时整体的代价也变化了:

$$cost = 2b_0 + 2b_1 + 3b_2 + \cdots$$

$$cost' = 2\cdot |b_0 - x + x^2| + 2 \cdot |b_1 + 1| + 3 \cdot |b_2 - 1| + \cdots$$

显然我们希望整体代价最小。考虑到$x >= 2$,显然可以得出这样一个结论:从比前一位更往前的位借位是不值得的,而且一定是借一个负位。原因很简单:假定$b_i$从$b_j$借了$k$位($j \geq i+2$),则这两位的cost之和从$|b_i| (i+1) + |b_j|(j + 1)$变成了$|b_i + k x^{j-i}| (i+1) + |b_j-k|(j + 1)$。通过各种分类讨论可以发现,这个cost不可能减小。(懒得去讨论了……)

所以可以用递推的方法来考虑这个问题:令

$$ \begin{aligned} f[i][0] =& \min{cost(a_0 + a_1 x + a_2 x^2 + \cdots + a_i x^i)} \\ f[i][1] =& \min{cost(a_0 + a_1 x + a_2 x^2 + \cdots + (a_i - x) x^i)} \end{aligned} $$

也就是说$f[i][1]$是借了一个负位之后最小可能的表示的代价。则

$$ \begin{aligned} f[i+1][0] =& \min{cost(a_0 + a_1 x + a_2 x^2 + \cdots + a_i x^i + a_{i+1} x^{i+1})} \\ =& \min cost(a_0 + a_1 x + a_2 x^2 + \cdots + a_i x^i) + cost(a_{i+1}x^{i+1}), \\ & cost(a_0 + a_1 x + a_2 x^2 + \cdots + (a_i - x) x^i) + cost((a_{i+1} + 1)x^{i+1}) \\ =& \min{f[i][0] + a_{i+1}(i+1), \, f[i][1] + (a_{i+1} + 1)(i + 1)} \end{aligned} $$

同理:

$$f[i+1][1] = \min{f[i][0] + |a[i+1] - x|(i+1), \, f[i][1] + |a[i+1] - x + 1| (i + 1)}$$

然后就可以递推了,时间复杂度为O(log(N))

从借位的想法translate到递推还是不太容易啊……

代码

我也不知道我怎么会开大小到1000的数组的……

以及,考虑到有借位的可能,需要递推到f[n],而不是f[n-1]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
int leastOpsExpressTarget(int x, int target) {
int a[1000], n = 0;
memset(a, 0, sizeof(a));
int t = target;
while (t > 0) {
a[n++] = t % x;
t /= x;
}
int f[1000][2];
f[0][0] = 2 * a[0];
f[0][1] = 2 * abs(a[0] - x);
for (int i = 1; i <= n; i++) {
f[i][0] = min(f[i-1][0] + a[i] * i, f[i-1][1] + (a[i] + 1) * i);
f[i][1] = min(f[i-1][0] + abs(a[i] - x) * i, f[i-1][1] + abs(a[i] - x + 1) * i);
}
return f[n][0] - 1;
}
};

题目来源:

标记难度:Medium

提交次数:3/7

代码效率:

  • hash向量:120ms
  • 枚举三个点:32ms
  • 枚举圆心和半径:24ms(87.12%)

题意

给定平面上若干个(<=400个)整点,问能够组成的面积最小的矩形的面积是多少。

分析

我的做法听起来有点奇怪:用O(N^2)的时间把每两个点组成的向量算出来,然后对于相同的向量(也就是说它们对应的4个点可以组成平行四边形),判断对应的4个点能否组成矩形。我感觉时间复杂度大概是O(N^3),加上map应该算是O(log(N))。考试后我才开始思考,这道题和之前的Leetcode 939. Minimum Area Rectangle好像没什么区别,为什么我没有用那种直接O(N^3)枚举三个点,再直接算出第四个点的方法呢……

以及,这道题我好像因为不存在矩形时输出0和叉积结果有可能为负数错了好几次……


比较简单的一种方法:

  • 枚举矩形的三个点(注意顺序),判断组成的两条边是否相互垂直
  • 用哈希表查第四个点是否存在,如果存在则计算面积

这种方法是O(N^3)的。

另一种时间复杂度更小的方法是,枚举每两个点连线中点和长度,然后检查所有中点和长度相同的点对能否组成矩形。据说每种点对的数量是O(log(N))的,所以我感觉这种方法的复杂度应该是O(N^2*log(N)^2)?也可能我想错了。

这个方法调了我几个小时,核心在于两点,一是我居然把Point的构造函数写成int的了然后忘掉了,以为自己用的是double;二是傻逼了,忘记矩形的对角线不垂直了……(你在想什么)

也是好久没正经写过计算几何的题了……(说得就好像你正经写过一样)

代码

奇怪的方法

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
class Solution {
private:
struct Point {
int x, y;

Point(int _x, int _y) {
x = _x;
y = _y;
}

friend bool operator < (const Point& p1, const Point& p2) {
if (p1.x != p2.x) return p1.x < p2.x;
return p1.y < p2.y;
}

friend bool operator == (const Point& p1, const Point& p2) {
return p1.x == p2.x && p1.y == p2.y;
}

friend Point operator - (const Point& p1, const Point& p2) {
return Point(p1.x - p2.x, p1.y - p2.y);
}

friend int cross(const Point& p1, const Point& p2) {
return p1.x * p2.y - p2.x * p1.y;
}

friend int dot(const Point& p1, const Point& p2) {
return p1.x * p2.x + p1.y * p2.y;
}

void print() {
cout << '(' << x << ',' << y << ')';
}
};

typedef Point Vector;

public:
double minAreaFreeRect(vector<vector<int>>& points) {
vector<Point> a;
int N = points.size();
for (int i = 0; i < N; i++) {
a.emplace_back(points[i][0], points[i][1]);
}
sort(a.begin(), a.end());

int ans = 0;
map<Vector, vector<int>> vmap;
for (int i = 0; i < N; i++) {
for (int j = i + 1; j < N; j++) {
Vector v = a[j] - a[i];
for (int k: vmap[v]) {
// a[i].print(); a[j].print(); a[k].print(); cout << endl;
Vector v2 = a[k] - a[i];
if (dot(v, v2) != 0) continue;
int area = cross(v, v2);
if (area <= 0) continue;
ans = ans == 0 ? area : min(ans, area);
}
vmap[v].push_back(i);
}
}
return ans;
}
};

枚举三个点的方法

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
class Solution {
private:
struct Point {
int x, y;

Point(int _x, int _y) {
x = _x;
y = _y;
}

friend bool operator < (const Point& p1, const Point& p2) {
if (p1.x != p2.x) return p1.x < p2.x;
return p1.y < p2.y;
}

friend bool operator == (const Point& p1, const Point& p2) {
return p1.x == p2.x && p1.y == p2.y;
}

friend Point operator + (const Point& p1, const Point& p2) {
return Point(p1.x + p2.x, p1.y + p2.y);
}

friend Point operator - (const Point& p1, const Point& p2) {
return Point(p1.x - p2.x, p1.y - p2.y);
}

friend int cross(const Point& p1, const Point& p2) {
return p1.x * p2.y - p2.x * p1.y;
}

friend int dot(const Point& p1, const Point& p2) {
return p1.x * p2.x + p1.y * p2.y;
}
};

public:
double minAreaFreeRect(vector<vector<int>>& points) {
set<Point> s; // 不能用unordered_set……
vector<Point> p;
int N = points.size();
for (int i = 0; i < N; i++) {
p.emplace_back(points[i][0], points[i][1]);
s.insert(p.back());
}
int ans = -1;
for (int i = 0; i < N; i++)
for (int j = 0; j < N; j++) {
if (i == j) continue;
for (int k = 0; k < N; k++) {
if (i == k || j == k) continue;
if (dot(p[i] - p[j], p[k] - p[j]) != 0) continue;
Point p4 = p[k] + p[i] - p[j];
if (s.find(p4) != s.end()) {
int area = abs(cross(p[i] - p[j], p[k] - p[j]));
ans = ans == -1 ? area : min(ans, area);
}
}
}
return ans == -1 ? 0 : ans;
}
};

枚举圆心和半径

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
class Solution {
private:
struct Point {
double x, y;

Point(double _x, double _y) {
x = _x;
y = _y;
}

friend bool operator < (const Point& p1, const Point& p2) {
if (abs(p1.x - p2.x) > 1e-6) return p1.x < p2.x;
return p1.y < p2.y;
}

friend bool operator == (const Point& p1, const Point& p2) {
return abs(p1.x - p2.x) <= 1e-6 && abs(p1.y - p2.y) <= 1e-6;
}

friend Point operator + (const Point& p1, const Point& p2) {
return Point(p1.x + p2.x, p1.y + p2.y);
}

friend Point operator - (const Point& p1, const Point& p2) {
return Point(p1.x - p2.x, p1.y - p2.y);
}

friend Point operator / (const Point& p1, const double& a) {
return Point(p1.x / a, p1.y / a);
}

friend double cross(const Point& p1, const Point& p2) {
return p1.x * p2.y - p2.x * p1.y;
}

friend double dot(const Point& p1, const Point& p2) {
return p1.x * p2.x + p1.y * p2.y;
}

double length2() {
return x * x + y * y;
}

void print() {
cout << '(' << x << ',' << y << ')';
}
};

typedef Point Vector;

public:
double minAreaFreeRect(vector<vector<int>>& points) {
map<pair<Point, int>, vector<int>> mmap;
vector<Point> p;
int N = points.size();
for (int i = 0; i < N; i++)
p.emplace_back(points[i][0], points[i][1]);
sort(p.begin(), p.end());
for (int i = 0; i < N; i++)
for (int j = i + 1; j < N; j++) {
Vector v = p[j] - p[i];
mmap[make_pair((p[i] + p[j]) / 2, v.length2())].push_back(i);
}
double ans = -1;
for (const auto& pa: mmap) {
Point center = pa.first.first;
for (int i = 0; i < pa.second.size(); i++) {
// cout << pa.second[i] << ' ';
for (int j = i + 1; j < pa.second.size(); j++) {
int i1 = pa.second[i], j1 = pa.second[j];
double area = 2 * abs(cross(p[i1] - center, p[j1] - center));
ans = ans < 0 ? area : min(ans, area);
}
}
}
return max(ans, 0.0);
}
};

题目来源:https://leetcode.com/problems/largest-component-size-by-common-factor/description/

标记难度:Hard

提交次数:7/8

代码效率:

  • 埃式筛法,map存储分解结果,普通并查集:1324ms
  • 埃式筛法,map存储分解结果,size优化并查集:1452, 1848ms
  • 欧拉筛法,map存储分解结果,普通并查集:TLE, 1868ms
  • 埃式筛法(减少素数),map存储分解结果,普通并查集:144ms
  • 素数打表,map存储分解结果,普通并查集:132ms
  • 素数打表,手写链表,普通并查集:132ms

题意

给定一些结点,每个结点上有一个值,令两个结点有边相连当且仅当上面的值有大于1的公因子。问图中最大的连通分量的大小。

结点数量在[1, 20000]范围内,值的大小在[1, 100000]范围内。

分析

这道题有一个显然的做法:

  • 首先打一个质数表。
    • 我之前认为需要打[1, 100000]范围内的质数(事实证明,一共有九千多个),但事实上不需要,只要打[1, sqrt(100000)]范围内的素数就可以了。在做质因数分解的时候,如果用上述范围内的质数没能约到1,则剩下的数必然是个大素数,不需要打表打到这个范围。
    • 打表可以用埃式筛法或者欧拉筛法(我之前在某次模拟赛中做过类似的题)。
  • 然后对每个数值作质因数分解,对每个质数开一个链表(或者类似的结构),如果一个质数是某个数的因数,就把这个数(的index)放到链表中。
  • 然后对每条链表中的值在并查集中作合并操作。
  • 最后找出并查集中最大的集合。

然后可以进行一些优化:

  • 换成欧拉筛法(结果耗时反而变多了)
  • 对并查集进行size优化(结果耗时反而变多了)
  • 只打sqrt(100000)范围内的质数表(耗时骤降,变成约10%)
  • 手工打质数表(耗时稍微减少)
  • map换成手写链表(耗时居然没变)

想到算法的复杂度实际上是O(NP),少遍历质数表好像的确能降低复杂度……

以及我在评论区里看到一个直接在做欧拉筛的时候进行合并的方法[1],非常简洁(但好像没有我快?看来打整张质数表还是太耗费时间了)。

代码

这次提交了很多版本的代码,这里放两个最快的好了。

map版本

132ms。

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
class Solution {
private:
// 并查集
int _fa[20005];
int _size[20005];
int n;

void init() {
for (int i = 0; i < n; i++) {
_fa[i] = i;
_size[i] = 1;
}
}

int fa(int x) {
if (_fa[x] == x) return x;
_size[_fa[x]] += _size[x];
_size[x] = 0;
return _fa[x] = fa(_fa[x]);
}

int merge(int x, int y) {
x = fa(x);
y = fa(y);
if (_size[x] < _size[y]) swap(x, y);
_fa[y] = x;
return fa(y);
}

int size(int x) {
x = fa(x);
return _size[x];
}

public:
int largestComponentSize(vector<int>& A) {
int primes[] = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79,
83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167,
173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239, 241, 251, 257, 263,
269, 271, 277, 281, 283, 293, 307, 311, 313, 317};
int m = sizeof(primes) / sizeof(int);
// 质因数分解,插入对应的vector
map<int, vector<int>> primeMap;
n = A.size();
for (int i = 0; i < n; i++) {
int x = A[i];
int j = 0;
while (j < m) {
if (x == 1) break;
while (j < m && x % primes[j] != 0) j++;
if (j >= m) break;
while (x % primes[j] == 0) x /= primes[j];
primeMap[primes[j]].push_back(i);
j++;
}
if (x != 1) primeMap[x].push_back(i);
}
// 合并每个质因数对应的所有数
init();
for (auto const& p: primeMap) {
if (p.second.size() > 1) {
int fa0 = fa(p.second[0]);
for (int i = 1; i < p.second.size(); i++) {
fa0 = merge(fa0, p.second[i]);
}
}
}
// 找到最大的集合,输出结果
int maxn = -1;
for (int i = 0; i < n; i++)
maxn = max(maxn, size(i));
return maxn;
}
};

链表版本

也是132ms。

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
92
93
class Solution {
private:
// 并查集
int _fa[20005];
int _size[20005];
int n;

void init() {
for (int i = 0; i < n; i++) {
_fa[i] = i;
_size[i] = 1;
}
}

int fa(int x) {
if (_fa[x] == x) return x;
_size[_fa[x]] += _size[x];
_size[x] = 0;
return _fa[x] = fa(_fa[x]);
}

int merge(int x, int y) {
x = fa(x);
y = fa(y);
if (_size[x] < _size[y]) swap(x, y);
_fa[y] = x;
return fa(y);
}

int size(int x) {
x = fa(x);
return _size[x];
}

// 链表
struct Node {
int val;
Node* next;

Node(int x) {
val = x;
next = NULL;
}
};

Node* heads[100000];
inline void insert(int prime, int i) {
Node* node = new Node(i);
node->next = heads[prime];
heads[prime] = node;
}

public:
int largestComponentSize(vector<int>& A) {
int primes[] = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79,
83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167,
173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239, 241, 251, 257, 263,
269, 271, 277, 281, 283, 293, 307, 311, 313, 317};
int m = sizeof(primes) / sizeof(int);
// 质因数分解,插入对应链表
n = A.size();
memset(heads, 0, sizeof(heads));
for (int i = 0; i < n; i++) {
int x = A[i];
int j = 0;
while (j < m) {
if (x == 1) break;
while (j < m && x % primes[j] != 0) j++;
if (j >= m) break;
while (x % primes[j] == 0) x /= primes[j];
insert(primes[j], i);
j++;
}
if (x != 1) insert(x, i);
}
// 合并每个质因数对应的所有数
init();
for (int i = 2; i < 100000; i++) {
if (heads[i] != NULL) {
int fa0 = fa(heads[i]->val);
Node* p = heads[i]->next;
for (p != NULL; p != NULL; p = p->next) {
fa0 = merge(fa0, p->val);
}
}
}
// 找到最大的集合,输出结果
int maxn = -1;
for (int i = 0; i < n; i++)
maxn = max(maxn, size(i));
return maxn;
}
};

  1. groawr's Solution for Leetcode 952 - C++ Sieve of Erastosthenes