总结
根据灵神总结的规律，果然这周的周赛非常的难，Q1周常签到题不多赘述，Q2先看出来特殊数是平方数，但是大意了没仔细想只是质数平方才行，因此WA了一发。Q3考试的时候感觉是一个O(nn)或者O(nlogn)的做法，感觉是暴力但是带优化（剪枝？）,但是没想出来😂。考试最后的时间主要在攻克Q4，看出来规律是判定连通块+判定圆和边界是否相交，但是最后由于采用的是DFS判连通，RE了导致没过。
本次周赛只通过了前两题，但依然和之前一样排名600+，说明最后两题是非常有含金量的可以好好总结一下。
Q1：3232. 判断是否可以赢得数字游戏
题目传送门：3232. 判断是否可以赢得数字游戏 - 力扣（LeetCode）
周常签到题，遍历一遍即可。
最后实现代码如下：
1
2
3
4
5
6
7
8
9
10
11
12
| class Solution {
public:
bool canAliceWin(vector<int>& nums) {
int sum_num = 0,sum_sing = 0;
for(auto num : nums){
sum_num += num;
if (num < 10) sum_sing += num;
}
return sum_num - sum_sing == sum_sing?false:true;
}
};
|
Q2：3233. 统计不是特殊数字的数字数量
题目传送门：3233. 统计不是特殊数字的数字数量 - 力扣（LeetCode）
质数预处理+单次区间查询，这道题就开始上强度了，仔细理解题目后不难发现，满足特殊数字的要求是：当且仅当当前数是一个质数平方时，才能恰好有两个真因子。
质数预处理部分，由于数据范围是1e9，因此不能用暴力进行预处理，可以使用埃氏筛或者欧拉筛，质数筛法讲解详情见OI-Knowledge专题数学部分。
单次区间查询直接遍历一遍就可以了。
最后实现代码如下：
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 {
public:
int nonSpecialCount(int l, int r) {
int n = 100000;
vector<bool> is_prime(n+1, true);
vector<int> primes;
for (int i = 2; i <= n; ++i) {
if (is_prime[i]) {
primes.push_back(i);
}
for (int j = 0; j < primes.size() && i * primes[j] <= n; ++j) {
is_prime[i * primes[j]] = false;
if (i % primes[j] == 0) {
break;
}
}
}
vector<long long> speics;
for(auto prime : primes){
speics.push_back((long long)prime*prime);
}
int all_num = r-l+1;
int ll = 0;
while (speics[ll]<l)ll++;
int rr = ll;
while (speics[rr]<=r)rr++;
return all_num - (rr-ll);
}
};
|
Q3：3234. 统计 1 显著的字符串的数量
题目传送门：3234. 统计 1 显著的字符串的数量 - 力扣（LeetCode）
暴力优化，设字符串长为n，其中有cnt0个0，cnt1个1，要找的子串需要满足的条件是cnt0*cnt0 <= cnt1,又已知cnt1 <= n，所以不难推出cnt0 <= sqrt(n)。
再次观察n的取值范围，可以发现n<1e4可以承受一个sqrt(n)三次方时间复杂度的算法，不难想到优化暴力需要和0的个数牵扯上关系。
最后实现代码如下：
Q4：
题目传送门：
最后实现代码如下：