【连通块染色，双指针维护区间map，整除分块】CF616 CDE

迈不过友情╰ 2024-03-22 23:48 30阅读 0赞

[Dashboard - Educational Codeforces Round 5 - Codeforces][]

题意：

![49af3b0a152c44158d2bf750cb46f2c2.png][]

思路：

经典的给格子染色，直接dfs染色就行，不要用并查集，虽然也能做但是不好写

然后对于每一个\*，把周围的格子的颜色扔到set里去重统计就行

Code：

#include <bits/stdc++.h>
    
    #define int long long
    
    using namespace std;
    
    const int mxn=1e3+10;
    const int mxe=1e6+10;
    
    int N,M;
    int idx=0;
    
    int ans[mxn][mxn],a[mxn][mxn],mp[mxe],vis[mxn][mxn];
    int dx[4]={-1,0,1,0},dy[4]={0,-1,0,1};
    
    string s[mxn];
    
    int F(int x,int y){
        return (x-1)*M+y;
    }
    bool check(int x,int y){
        return x>=1&&x<=N&&y>=1&&y<=M;
    }
    void dfs(int x,int y,int c){
        for(int i=0;i<4;i++){
            int vx=x+dx[i];
            int vy=y+dy[i];
            if(check(vx,vy)&&s[vx][vy]=='.'&&!a[vx][vy]){
                a[vx][vy]=c;
                mp[c]++;
                dfs(vx,vy,c);
            }
        }
    }
    
    void solve(){
        cin>>N>>M;
        for(int i=1;i<=N;i++){
            cin>>s[i];
            s[i]=" "+s[i];
        }
        for(int i=1;i<=N;i++){
            for(int j=1;j<=M;j++){
                if(s[i][j]=='.'&&!a[i][j]){
                    a[i][j]=++idx;
                    mp[idx]++;
                    dfs(i,j,idx);
                }
            }
        }
        for(int i=1;i<=N;i++){
            for(int j=1;j<=M;j++){
                if(s[i][j]=='*'){
                    set<int> S;
                    for(int k=0;k<4;k++){
                        int vx=i+dx[k];
                        int vy=j+dy[k];
                        if(check(vx,vy)&&s[vx][vy]=='.'){
                            S.insert(a[vx][vy]);
                        }
                    }
                    int res=0;
                    for(auto u:S){
                        res+=mp[u];
                    }
                    ans[i][j]=res;
                }
            }
        }
        for(int i=1;i<=N;i++){
            for(int j=1;j<=M;j++){
                if(s[i][j]=='.') cout<<".";
                else cout<<(ans[i][j]+1)%10;
            }
            cout<<'\n';
        }
    }
    signed main(){
    	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    	int __=1;//cin>>__;
    	while(__--)solve();return 0;
    }

题意：

![c6a7ad52a20240849ef1ce3df1ff37af.png][]

思路：

很经典的双指针动态维护区间map，用set维护这个元素是否存在以及不同的种类个数，map维护每个元素的出现次数

Code：

#include <bits/stdc++.h>
    
    //#define int long long
    
    using namespace std;
    
    const int mxn=5e5+10;
    const int mxe=1e6+10;
    
    int N,K;
    int a[mxn],mp[mxe];
    
    void solve(){
        cin>>N>>K;
        for(int i=1;i<=N;i++) cin>>a[i];
        int r=1;
        set<int> S;
        int ans=0,ansl=1,ansr=1;
        for(int l=1;l<=N;l++){
            while(r<=N){
                mp[a[r]]++;
                S.insert(a[r]);
                if(S.size()>K){
                    mp[a[r]]--;
                    if(!mp[a[r]]) S.erase(a[r]);
                    break;
                }
                r++;
            }
            if(ans<r-1-l+1){
                ans=r-1-l+1;
                ansl=l;
                ansr=r-1;
            }
            mp[a[l]]--;
            if(!mp[a[l]]) S.erase(a[l]);
        }
        cout<<ansl<<" "<<ansr<<'\n';
    }
    signed main(){
    	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    	int __=1;//cin>>__;
    	while(__--)solve();return 0;
    }

题意：

![459868bdecf94204bf260ab1eae83749.png][]

思路：

整除分块板子

不懂的可以看这个：[整除分块 - 知乎][-]

Code：

#include <bits/stdc++.h>
    
    #define int long long
    
    using namespace std;
    
    const int mxn=5e5+10;
    const int mxe=1e6+10;
    const int mod=1e9+7;
    
    int N,M;
    
    int ksm(int a,int b,int mod){
        int res=1ll;
        while(b){
            if(b&1) res=(res*a)%mod;
            a=(a*a)%mod;
            b>>=1;
        }
        return res;
    }
    void solve(){
        cin>>M>>N;
        int r=1;
        int ans=(N%mod)*(M%mod)%mod;
        int inv2=ksm(2,mod-2,mod);
        for(int l=1;l<=min(N,M);l=r+1){
            r=min(M/(M/l),N);
            ans=(ans-(M/l)%mod*((l+r)%mod)%mod*((r-l+1)%mod)%mod*inv2%mod)%mod;
        }
        cout<<(ans+mod)%mod<<'\n';
    }
    signed main(){
    	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    	int __=1;//cin>>__;
    	while(__--)solve();return 0;
    }

[Dashboard - Educational Codeforces Round 5 - Codeforces]: https://codeforces.com/contest/616
[49af3b0a152c44158d2bf750cb46f2c2.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/14/ca60f8469bfb47ed95d7c669366897a4.png
[c6a7ad52a20240849ef1ce3df1ff37af.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/14/bc070dcdfa6a4d689b31d8ad76e03150.png
[459868bdecf94204bf260ab1eae83749.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/14/e569e76aa9784b96925611ca3c627ee9.png
[-]: https://zhuanlan.zhihu.com/p/617878247