书海扬帆的博客

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
#include <bits/stdc++.h>
using namespace std;
int n;
const int maxn=10010000;
int mu[maxn],prime[maxn],cnt;
bool not_prime[maxn];
inline void Get_Mu(int n) {
mu[1]=1;
for(int i=2;i<=n;i++) {
if(!not_prime[i]) prime[++cnt]=i,mu[i]=-1;
for(int j=1;prime[j]*i<=n;j++) {
not_prime[prime[j]*i]=1;
if(i%prime[j]==0) {
mu[prime[j]*i]=0;
break;
}
mu[prime[j]*i]=-mu[i];
}
}
}
int main() {
cin>>n;
Get_Mu(n);
for(int i=1;i<=n;i++) cout<<mu[i]<<' ';
return 0;
}

题意

给出n个数,找其中的众数,内存限制1M。

解题思路

“摩尔投票法”。

(此处内容待填坑…)

代码

照着hzw学长的标程写的,学习学习。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#include<cstdio>
int n,t,x,tot;
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
scanf("%d",&x);
if(x==t)tot++;
else if(!tot)
{t=x;tot=1;}
else tot--;
}
printf("%d",t);
return 0;
}

题意

$n$个数的序列,$m$个操作,要求支持:

  1. 将区间内每个数修改为其算术平方根;
  2. 区间求和。

解题思路

本题和刚才说过的CF920F很像。
典型的区间修改和求和当然能想到线段树啦。。。
那么如何进行区间修改呢?
遍历每个区间,递归到叶子节点暴力修改即可。
可发现一个特殊性质:平方根是下降很快的。
大家有没有过这样的经历呢?找来一个计算器,输入任意正数,不停地按$\sqrt{}$按钮,不一会儿这个数字就变成1了。这倒不是因为咱们的计算机出了问题,而是因为浮点数在运算和处理的过程中会产生精度误差,误差随着一次一次地按键不断升高,省略计算的部分也就越多,于是最后就逐渐减小,直到变成1。口说无凭,大家不妨亲自实践一下。
综上,一个数修改不了几次,就可以变成1。我们只需维护区间最大值,一旦发现区间最大值为1了,就直接跳过,否则暴力递归到叶子节点进行修改。
时间复杂度$O(m \log n).$
注意数据范围,本题需要开$long long$.


贴下代码。

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
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <cstring>
using namespace std;
#define ll long long
#define I inline
template<class T>void read(T &x) {
register ll c = getchar(), f = 1; x = 0;
while(!isdigit(c)) {if (c == '-') f = -1; c = getchar();}
while(isdigit(c)) x = x * 10 + c - '0', c = getchar();
x *= f;
}
const ll maxn=300300;
const ll maxm=1000100;
ll n,k,tot,cnt[maxm],prime[maxm],d[maxm];
bool vis[maxm];
ll a[maxn],mx[maxn<<2];
ll sum[maxn<<2];
void Get_Prime()
{
d[1]=1;cnt[1]=0;
for(ll i=2;i<=n;i++)
{
if(!vis[i]) {
prime[++tot]=i;
d[i]=2;
cnt[i]=1;
}
for(ll j=1;j<=tot && prime[j]<=n/i;j++)
{
vis[i*prime[j]]=1;
if(i%prime[j]==0)
{
cnt[i*prime[j]]=cnt[i]+1;
d[i*prime[j]]=d[i]/(cnt[i]+1)*(cnt[i*prime[j]]+1);
break;
}
cnt[i*prime[j]]=1;
d[i*prime[j]]=d[i]*2;
}
}
}
#define m ((l+r)>>1)
#define lson rt<<1,l,m
#define rson rt<<1|1,m+1,r
void build(ll rt,ll l,ll r)
{
if(l==r)
{
sum[rt]=mx[rt]=a[l];
return ;
}
build(lson);
build(rson);
mx[rt]=max(mx[rt<<1],mx[rt<<1|1]);
sum[rt]=sum[rt<<1]+sum[rt<<1|1];
}
void update(ll rt,ll l,ll r,ll L,ll R)
{
if(mx[rt]<=1) return ;
if(l==r)
{
sum[rt]=sqrt(sum[rt]);
mx[rt]=sqrt(mx[rt]);
return ;
}
if(m>=L) update(lson,L,R);
if(m<R) update(rson,L,R);
mx[rt]=max(mx[rt<<1],mx[rt<<1|1]);
sum[rt]=sum[rt<<1]+sum[rt<<1|1];
}
ll query(ll rt,ll l,ll r,ll L,ll R)
{
if(L<=l && r<=R) return sum[rt];
ll ret=0;
if(m>=L) ret+=query(lson,L,R);
if(m<R) ret+=query(rson,L,R);
return ret;
}
int main()
{
n=1000010;
Get_Prime();
read(n);
for(ll i=1;i<=n;i++) read(a[i]);
build(1,1,n);
read(k);
while(k--)
{
ll op;
read(op);
if(op==0)
{
ll L,R;
read(L);read(R);
if(L>R) swap(L,R);
update(1,1,n,L,R);
}
else
{
ll L,R;
read(L);read(R);
if(L>R) swap(L,R);
printf("%lld\n",query(1,1,n,L,R));
}
}
return 0;
}



本站使用 Material-X 作为主题 , 总访问量为 次 。
载入天数...载入时分秒... 字数统计:730.1k