526互联

2023 Hubei Provincial Collegiate Programming Contest

发布时间 2023-10-16 00:07:32作者: EdGrass

\(B. Mode\)

利用数位 \(dp\) 求数字众数，那么在相同的位数下，相同的个数即为相同，用 \(map\) 记忆化搜索。

int num[20],len=0;
map<pair<int,vector<int> > ,int>mp;
int dfs(int pos,vector<int> v,bool lead,bool limit){
    if(!limit){
        sort(v.begin(),v.end());
    }
    if(pos==0){
        if(lead)return 1;
        return *max_element(v.begin(),v.end());
    }
    if(!limit&&!lead&&mp.count(make_pair(pos,v))) return mp[make_pair(pos,v)];
    int up=limit?num[pos]:9;
    int res=0;
    for(int i=0;i<=up;i++){
        if(!lead||i){
            v[i]++;
        }
        res+=dfs(pos-1,v,lead&&i==0,limit&&i==up);
        if(!lead||i){
            v[i]--;
        }
    }
    if(!limit&&!lead)mp[make_pair(pos,v)]=res;
    return res;
}
int num_dp(int x){
    len=0;
    while(x){
        num[++len]=x%10;
        x/=10;
    }
    vector<int>v(10);
    return dfs(len,v,1,1);
}
void solve(){
    int l=read(),r=read(),ans=0;
    if(r==1e18)r--,ans+=18;
    ans+=num_dp(r);
    if(l)ans-=num_dp(l-1);
    cout<<ans<<'\n';
    //puts(ans>0?"YES":"NO");
    //puts(ans>0?"Yes":"No");
}

\(D. Darkness II\)

将一个矩形的可以是他与别的矩阵相连的部分拆分成若干矩阵查询。然后对每个遍历一遍，能连的就连上，那么每个矩阵可以看做只会被扩展一次。
\(code from jiangly\)

vector<array<int,4> >rect;
vector<bool>vis;
vector<int>f[1<<20],g[1<<20];
void add(int p,int l,int r,int yl,int yr,int i){
    if(l>=yr||r<=yl){
        return;
    }
    f[p].push_back(i);
    if(l>=yl&&r<=yr){
        g[p].push_back(i);
        return ;
    }
    int m=(l+r)/2;
    add(2*p,l,m,yl,yr,i);
    add(2*p+1,m,r,yl,yr,i);
}
int query(int p,int l,int r,int yl,int yr,int xl){
    if(l>=yr||r<=yl){
        return -1;
    }
    while(!f[p].empty()&&vis[f[p].back()])
        f[p].pop_back();
    while(!g[p].empty()&&vis[g[p].back()])
        g[p].pop_back();
    if(!g[p].empty()&&xl<=rect[g[p].back()][1])
        return g[p].back();
    if(l>=yl&&r<=yr){
        if(!f[p].empty()&&xl<=rect[f[p].back()][1])
            return f[p].back();
        return -1;
    }
    int m=(l+r)/2;
    int res=query(2*p,l,m,yl,yr,xl);
    if(res==-1){
        res=query(2*p+1,m,r,yl,yr,xl);
    }
    return res;
}
void solve(){
    int n=read();
    vector<pair<int,int> >a(n);
    vector<int>v;
    for(int i=0;i<n;i++){
        int x=read(),y=read();
        a[i]=make_pair(x,y);
        v.push_back(y-1);
        v.push_back(y);
        v.push_back(y+1);
        v.push_back(y+2);
    }
    sort(a.begin(),a.end());
    sort(v.begin(),v.end());
    v.erase(unique(v.begin(),v.end()),v.end());
    int m=v.size();
    for(int i=0;i<n;i++){
        auto [x,y]=a[i];
        int yl=lower_bound(v.begin(),v.end(),y)-v.begin();
        int yr=lower_bound(v.begin(),v.end(),y+1)-v.begin();
        int xl=x,xr=x+1;
        while(1){
            int j=query(1,0,m,yl-1,yr+1,xl);
            if(j==-1){
                j=query(1,0,m,yl,yr,xl-1);
            }
            if(j==-1){
                j=query(1,0,m,yl-2,yr+2,xl+1);
            }
            if(j==-1){
                break;
            }
            vis[j]=true;
            xl=min(xl,rect[j][0]);
            yl=min(yl,rect[j][2]);
            yr=max(yr,rect[j][3]);
        }
        add(1,0,m,yl,yr,rect.size());
        rect.push_back({xl,xr,yl,yr});
        vis.push_back(false);
    }
    int ans=0;
    for(int i=0;i<rect.size();i++){
        if(!vis[i]){
            auto [xl,xr,yl,yr]=rect[i];
            ans+=(xr-xl)*(v[yr]-v[yl]);
        }
    }
    cout<<ans<<'\n';
    //puts(ans>0?"YES":"NO");
    //puts(ans>0?"Yes":"No");
}

\(E. Inverse Counting Path\)

这题采用六进制构造数字，对于每个需要的次数连接到总路线上，对于需要的当前位的个数，加粗相应的一段连接路的宽度。

int a[N][N];
void solve(){
    int n=read();
    vector<int>ans;
    while(n){
        ans.push_back(n%6);
        n/=6;
    }
    cout<<"30\n";
    for(int i=1;i<=30;i++){
        a[i][30]=a[30][i]=1;
    }
    for(int i=0;i<12;i++){
        for(int j=1;j<=3;j++){
            for(int k=1;k<=3;k++){
                a[i*2+j][i*2+k]=1;
            }
        }
    }
    for(int i=0;i<ans.size();i++){
        int k=i*2+1;
        if(i&1){
            if(ans[i]>0){
                for(int j=k;j<=30;j++){
                    a[j][k]=1;
                }
            }
            for(int j=30-ans[i]+1;j<=30;j++){
                a[j][k+1]=1;
            }
        }else{
            if(ans[i]>0){
                for(int j=k;j<=30;j++){
                    a[k][j]=1;
                }
            }
            for(int j=30-ans[i]+1;j<=30;j++){
                a[k+1][j]=1;
            }
        }
    }
    for(int i=1;i<=30;i++){
        for(int j=1;j<=30;j++){
            cout<<a[i][j]<<" ";
        }
        cout<<'\n';
    }
    //puts(ans>0?"YES":"NO");
    //puts(ans>0?"Yes":"No");
}