CF1612

我是呆逼我是呆逼我是呆逼。

[A Divan and a Store]

solution

题面:$n$ 个物品,不能买价格超过 $r$ 或者小于 $l$ 的,你有 $k$ 元,问最多买几个。

做法:贪,时间复杂度 $O(n\log)$。

code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
//2021.11.26 by ljz
//email 573902690@qq.com
//if you find any bug in my code
//please tell me
const int N=100+10;
namespace MAIN{
int n,l,r,k;
int a[N];
inline void MAIN(){
n=read(),l=read(),r=read(),k=read();
res ax=0;
for(res i=1;i<=n;i++){
res x=read();
if(x>=l&&x<=r)a[++ax]=x;
}
sort(a+1,a+ax+1);
res ret=0;
for(res i=1;i<=ax;i++)if(k>=a[i])k-=a[i],ret++;
printf("%d\n",ret);
}
}

[B Divan and a New Project]

solution

题面:你可以设置 $x_0,…x_n$ 分别是多少,使得 $\sum 2a_i|x_0-x_i|$ 最小。

做法:按 $a$ 递减贪,一正一负构造即可。时间复杂度 $O(n\log)$。

code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
//2021.11.26 by ljz
//email 573902690@qq.com
//if you find any bug in my code
//please tell me
const int N=2e5+10;
namespace MAIN{
int n;
Pair a[N];
int b[N];
inline void MAIN(){
n=read();
for(res i=1;i<=n;i++)a[i]=mp(read(),i);
sort(a+1,a+n+1),reverse(a+1,a+n+1);
RG LL ans=0;
for(res i=1;i<=n;i++)if(i&1)b[a[i].se]=(i+1)>>1;else b[a[i].se]=-(i>>1);
for(res i=1;i<=n;i++)ans+=(LL)a[i].fi*abs(b[a[i].se]);
printf("%lld\n",ans<<1);
for(res i=0;i<=n;i++)printf("%d ",b[i]);puts("");
}
}

[C Divan and bitwise operations]

solution

题面:给你一些区间的 $\mathrm{or}$ ,问你所有子序列的 $\mathrm{xor}$ 和的和的可能值,输出一个即可。

做法:诈骗题,我们按位推一下式子就会发现这是个定值了。当然你可以直接构造出来,让有 $0$ 的地方摆放 $0$,其余地方放 $1$ 即可。时间复杂度 $O(n\log A)$。

code
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
//2021.11.26 by ljz
//email 573902690@qq.com
//if you find any bug in my code
//please tell me
const int N=2e5+10;
int pw[N];
namespace MAIN{
int n,m;
bool a[N][30];
struct P{
int l,r,x;
inline void init(){
l=read(),r=read(),x=read();
}
inline bool operator < (const RG P &A) const {
return l<A.l;
}
}b[N];
int fl[31];
inline void MAIN(){
n=read(),m=read();
memset(fl,0,sizeof(fl));
for(res i=1;i<=m;i++)b[i].init();
for(res i=1;i<=m;i++){
for(res x=0;x<=30;x++){
if(b[i].x&(1<<x))fl[x]=1;
}
}
res ans=0;
for(res i=0;i<=30;i++)if(fl[i])add(ans,mul(pw[n-1],pw[i]));
printf("%d\n",ans);
}
}

[D Divan and Kostomuksha]

solution

题面:给出一个长度为 $n$ 的序列 $a$,排列 $a$ 使得 $\sum \gcd_{i} (a_i)$ 最大。

做法:考虑对值域 $\mathrm{dp}$,设 $f_{i}$ 表示第一个数是 $i$ 时的最大值。注意到 $\gcd$ 一定是递减的,于是它转移来的都是它的因数。发现这个转移式中我们需要预处理的是每个数的因数是多少,直接暴力时间复杂度就是 $O(A\log A)$。发现实际上用的值没有那么多,只有 $O(A\log\log A)$ 个是有用的。所以时间复杂度可以优化到 $O(A\log\log A)$。

具体实现上,我偷了个懒,写了个 $O(n\sqrt{A}+A\log\log A)$,实际上是可以 $\mathrm{dfs}$ 分解质因数做到 $O(A\log\log A)$ 的。

code
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
//2021.11.26 by ljz
//email 573902690@qq.com
//if you find any bug in my code
//please tell me
const int N=2e7+10;
namespace MAIN{
LL s[N],f[N];
int n;
int a[N];
int mx;
int vis[N];
inline void MAIN(){
n=read();
for(res i=1;i<=n;i++){
res x=read();
for(res j=1;j*j<=x;j++){
if(x%j==0){
s[j]++;
if(j*j!=x)s[x/j]++;
vis[j]=vis[x/j]=1;
}
}
mx=max(mx,x);
}
for(res i=mx;i;i--){
if(!vis[i])continue;
for(res j=i;j<=mx;j+=i){
if(!vis[j])continue;
f[i]=max(f[i],f[j]-s[j]*i);
}
f[i]+=s[i]*i;
}
RG LL ans=0;
for(res i=1;i<=mx;i++)ans=max(ans,f[i]);
printf("%lld\n",ans);
}
}

[E Divan and a Cottage]

solution

题面:每天室内温度都会往更接近室外温度的方向加一。一共 $n$ 天,给出这 $n$ 天的室外温度,每天多次询问第一天温度为 $S$ 时,今天温度为多少。

做法:考虑同时维护第一天温度为 $i$ 的第 $j$ 天的情况。注意到这个答案一定是单调不减的,而每次更改的只是两段连续的区间,每次二分出这两个区间的左端点和右端点,然后在线段树上打标记即可。时间复杂度 $O(n\log^2n)$。注意到这个二分结构与线段树符合,所以直接在线段树上二分即可,时间复杂度 $O(n\log n)$。值域比较大,要动态开点线段树。空间复杂度也是 $O(n\log n)$。

code
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
//2021.11.27 by ljz
//email 573902690@qq.com
//if you find any bug in my code
//please tell me
const int N=4e7+10;
namespace MAIN{
int n;
int lastans;
int ls[N],rs[N],RT,tot,tagl[N],tagr[N],laz[N];
inline void change(res &rt,const res &v){
if(!rt)rt=++tot;
tagl[rt]+=v,tagr[rt]+=v,laz[rt]+=v;
}
inline void pushdown(const res &rt){
if(!laz[rt])return;
change(ls[rt],laz[rt]),change(rs[rt],laz[rt]),laz[rt]=0;
}
void modify(res &rt,res l,res r,const res &L,const res &R,const res &v){
if(!rt)rt=++tot;
if(L<=l&&r<=R){change(rt,v);return;}
pushdown(rt);
res mid=(l+r)>>1;
if(L<=mid)modify(ls[rt],l,mid,L,R,v);
if(R>mid)modify(rs[rt],mid+1,r,L,R,v);
tagl[rt]=tagl[ls[rt]],tagr[rt]=tagr[rs[rt]];
}
int query(res &rt,res l,res r,const res &p){
if(!rt)return 0;
if(l==r)return tagl[rt];
pushdown(rt);
res mid=(l+r)>>1;
tagl[rt]=tagl[ls[rt]],tagr[rt]=tagr[rs[rt]];
if(p<=mid)return query(ls[rt],l,mid,p);
return query(rs[rt],mid+1,r,p);
}
inline void MAIN(){
n=read(),RT=tot=1;
while(n--){
res T=read();
res rt=RT,l=0,r=1000000000,L=-1,R=1000000001;
while(233){
if(l==r){if(l+tagr[rt]<T)L=l;break;}
pushdown(rt);
res mid=(l+r)>>1;
if(mid+tagr[ls[rt]]<T)l=mid+1,L=mid,rt=rs[rt];
else r=mid,rt=ls[rt];
}
rt=RT,l=0,r=1000000000;
while(233){
if(l==r){if(l+tagl[rt]>T)R=l;break;}
pushdown(rt);
res mid=(l+r)>>1;
if(mid+1+tagl[rs[rt]]>T)r=mid,R=mid+1,rt=ls[rt];
else l=mid+1,rt=rs[rt];
}
if(0<=L)modify(RT,0,1000000000,0,L,1);
if(R<=1000000000)modify(RT,0,1000000000,R,1000000000,-1);
res k=read();
while(k--){
res x=read();
x=Add(x,lastans);
printf("%d\n",lastans=x+query(RT,0,1000000000,x));
}
}
}
}