Znzryb's Blog
0%

Posted on Edited on

思路讲解

简单来说，就是对

gcd递推方法。

1
2
3
4
5
6
7
8
9
10
11
12
13
FOR(i,0,blocksz){
    FOR(j,0,blocksz){
        if(i==0 || j==0){
            GCD[i][j]=i+j;
            continue;
        }
        if(i>j){
            GCD[i][j]=GCD[i-j][j];
        }else{
            GCD[i][j]=GCD[i][j-i];
        }
    }
}

这个块长也比较玄学，siz=NMsiz=\frac{N}{\sqrt M})是过不了的，siz=N2Msiz=\frac{N}{2\sqrt M} 就可以过了，siz=N4Msiz=\frac{N}{4\sqrt M} 更快？其实我感觉要正确生成块长，主要还是要根据这个真正需要这个块长的东西决定的。

在这一堆操作中，真正需要用到块长会增加复杂度的操作，比用块长可以减少复杂度的多，因此，取较小的块长可以加快速度。

可以看到，负担操作执行的更多，因此可以减少块长。

image

这个也是一个小技巧。

1
2
3
// 比如说d=2，其实我们就是想知道k有几个可以除以2的因数
// 求这个O(1)比较难，但可以求k先除以2，即k/2有几个因数
ismul[d]+=SZ(divv[k/d])*x;

AC代码

https://vjudge.net/solution/63198297

心路历程（WA，TLE，MLE……）

Posted on Edited on

思路讲解

呃，没什么好说的，主要就是一些细节问题

pushdown顺序放在这里了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
void pushdown(int o){
    int l=o<<1,r=l|1;   // 左儿子，右儿子
    if(tag2[o]!=initv){ 
        settag2(l, tag2[o]);
        settag2(r, tag2[o]);
        tag2[o]=initv;
    }
    if(tag3[o]!=1){
        settag3(l, tag3[o]);
        settag3(r, tag3[o]);
        tag3[o]=1;
    }
    if(tag[o]!=0){
        settag(l, tag[o]);
        settag(r, tag[o]);
        tag[o]=0;
    }
}

AC代码

https://vjudge.net/solution/63174043

心路历程（WA，TLE，MLE……）

Posted on Edited on

思路讲解

就是简单的东西。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
FOR(_,1,M){
    ll l,r;
    cin>>l>>r;
    ll ret=tr.query(l, r);
    tr.modify(l, r, 0);
    ll res=ret*binpow(r-l+1, mod-2)%mod;
    tr.add(l, r, res);
}
FOR(i,1,tr.sz-1){
    tr.pushdown(i);
}
FOR(i,1,N){
    ll res=tr.tr[i+tr.sz];
    if(res<0) res+=mod;
    cout<<res<<" ";
}

AC代码

心路历程（WA，TLE，MLE……）

Posted on Edited on

思路讲解

只要想到dp，那么写起来还是挺简单的。

这个dp的定义还是挺简单的，我的dp[i]的定义是以 i 的 mx 为结尾，所能得到的区间长度（计数），dp2[i] 的定义是以 i 的 mn 为结尾，所能得到的区间长度（计数）。

然后下划线部分注意初始化。

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
inline void __(){
    cin>>N;
    vll A(N+5),B(N+5);
    FOR(i,1,N){
        cin>>A[i];
    }
    FOR(i,1,N){
        cin>>B[i];
    }
    vll dp(N+5),dp2(N+5);
    FOR(i,1,N){
        ll mx=max(A[i],B[i]),mn=min(A[i],B[i]);
        dp[i]=1;
        if(mx>max(A[i-1],B[i-1])){
            dp[i]=dp[i-1]+1;
        }
        if(mx>min(A[i-1],B[i-1])){
            dp[i]=max(dp[i],dp2[i-1]+1);
        }
        dp2[i]=1;
        if(mn>max(A[i-1],B[i-1])){
            dp2[i]=dp[i-1]+1;
        }
        if(mn>min(A[i-1],B[i-1])){
            dp2[i]=max(dp2[i],dp2[i-1]+1);
        }
    }
    ll ans=0;
#ifdef LOCAL
    _print(dp);
    _print(dp2);
    cend;
#endif
    FOR(i,1,N){
        ans+=max(dp2[i],dp[i]);
    }
    cout<<ans<<"\n";
}

AC代码

https://www.codechef.com/viewsolution/1184464744

心路历程（WA，TLE，MLE……）

Posted on Edited on

思路讲解

https://www.hello-algo.com/chapter_divide_and_conquer/hanota_problem/#2

主要dfs代码。

image

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
void dfs(ll rem,vll &src,vll &buf,vll &tar,char s,char b,char t){
    if(ok) return;
    if(rem==1){
        move(src,tar);
        if(tot==M){
            cout<<s<<"--"<<t<<"\n";
            ok=true;
            return;
        }
        return;
    }
    // 利用B，将A移动至C
    dfs(rem-1,src,tar,buf,s,t,b);
    move(src,tar);
    if(tot==M){
        cout<<s<<"--"<<t<<"\n";
        ok=true;
        return;
    }
    dfs(rem-1,buf,src,tar,b,s,t);
}

AC代码

心路历程（WA，TLE，MLE……）