D - 250-like Number

题意

p和q是两个素数,如果k可以表示$k = p*q^3$且$q>p$,那么就称k为250-like Number。

输入n,求1到n之内有多少个250-like Number。

思考

一下结论显而易见

  • 根据算术基本定理,相当于计算满足一定条件的(p,q)数量
  • p < q < 1e6

素数筛。然后固定p,找到最大的q,使得$N >= p*q^3$,此时答案应该加上小于等于q的素数的个数。枚举所有p即可。

寻找q可以用二分或者双指针(随着p的增大,目标q递减)

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
#include<bits/stdc++.h>
using namespace std;
#define MAXP 1000005
vector<long long> prime_list;
void construct_plist(){
vector<bool> fl(MAXP,false);
for(int i=2;i<MAXP;i++){
if(fl[i]){continue;}
prime_list.push_back(i);
for(int j=i;j<MAXP;j+=i){fl[j]=true;}
}
}
long long f(long long p,long long q){
double est=1;
est=(q*q*q);
est*=p;
if(est>4e18){return 4e18;}
return p*q*q*q;
}
int main(){
construct_plist();
long long n;
cin >> n;
long long res=0;
int sz=prime_list.size();
int q=sz-1;
for(int p=0;p<sz;p++){
while(p<q && f(prime_list[p],prime_list[q])>n){q--;}
if(p>=q){break;}
res+=(q-p);
}
cout << res << '\n';
return 0;
}

E - Prefix Equality

题意

两个序列A,B。q次询问,每次询问给出x,y,判断序列A的前x个数的集合与序列B的前y个数的集合是否相等。

思考

方法一

首先考虑两个集合大小,如果不相等,一定是NO。如果相等的话:

维护一个新的集合S。假设两个集合大小都为k,从1到k,遍历第k个加入两个集合的元素,如果在S中就去除,如果不在就加入。集合大小为k时输出YES当且仅当S为空。

上述操作可以预处理。

方法二

哈希

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
#include<iostream>
#include<algorithm>
#include<cstring>
#include<vector>
#include<set>
#include<map>
using namespace std;
typedef unsigned long long ULL;
int pow=131;
int n,q,x,y;
int a,b;
ULL aa[200010],bb[200010];
map<int,int> mp;
set<int> st;
int get(int u){
if(mp[u]) return mp[u];
else return mp[u]=rand()%(1000000000+7);
}
int main(){
scanf("%d",&n);
for(int i=1;i<=n;i++){
aa[i]=aa[i-1];
scanf("%d",&a);
if(!st.count(a)){
aa[i]+=get(a);
st.insert(a);
}
}
st.clear();
for(int i=1;i<=n;i++){
bb[i]=bb[i-1];
scanf("%d",&b);

if(!st.count(b)){
bb[i]+=get(b);
st.insert(b);
}
}
scanf("%d",&q);
for(int i=1;i<=q;i++){
scanf("%d%d",&x,&y);
if(aa[x]==bb[y])
puts("Yes");
else
puts("No");
}
return 0;
}

方法三

对于每个x,想要输出YES的话,y必须位于某一范围 $[l,r]$ 中。找出l,r即可

X-Sum

题意

给定n*m的矩阵,每个格子都有一个权值。问怎样摆能使得棋子覆盖的权值和最大。

1≤𝑛≤200, 1≤𝑚≤200

思考

直接暴力枚举i j,确定棋子的位置后,计算的时间复杂度$O(max(n,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
53
#include <bits/stdc++.h>

using i64 = long long;

void solve() {
int n, m;
std::cin >> n >> m;

std::vector a(n, std::vector<int>(m)), f(a), g(a);
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
std::cin >> a[i][j];
f[i][j] = g[i][j] = a[i][j];
if (i > 0 && j > 0) {
f[i][j] += f[i - 1][j - 1];
}
if (i > 0 && j + 1 < m) {
g[i][j] += g[i - 1][j + 1];
}
}
}
for (int i = n - 1; i > 0; i--) {
for (int j = 0; j < m; j++) {
if (j > 0) {
f[i - 1][j - 1] = f[i][j];
}
if (j + 1 < m) {
g[i - 1][j + 1] = g[i][j];
}
}
}
int ans = 0;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
ans = std::max(ans, f[i][j] + g[i][j] - a[i][j]);
}
}
std::cout << ans << "\n";
}

int main() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);

int t;
std::cin >> t;

while (t--) {
solve();
}

return 0;
}