当前位置:编程学习 > C/C++ >>

NJUST 1746 Similar Number(南京邀请赛 J题)

 


没想法J题竟然这么水。。。。。
强制在线之后以为是一个神奇的数据结构题。。。
不过自己肯定是想不到。。。。感谢戴神的指导。。。
首先预处理出对于每一个数,右边最靠近的相似的数,用r[i]表示
将降序排列后,map搞定。。。


接下来戴神给了神奇的做法,大概是求出 >=1的区间数 减去  >=2的区间数
然后我还是不会。。。。
对于每一个点,求出右边最近的包括一个相似对的位置,one[i]
表示的是[i,one[i]]  …… [i,n] 所有的区间都至少有一个相似对。
而且[i,one[i]-1]不包括相似对。。。。


然后同理处理出two[i],表示区间内至少有两个相似对。。。


对于one[i]=min(one[i-1],r[i])  表示i当前这个位置形成一对,或者i-1之后形成一对。
对于two[i]=min(two[i-1], r[r[i]], max(r[i],one[i-1]))   表示i-1之后形成了两对,i当前这个位置形成两对,或者i-1之后形成一对,当前位置形成一对。。。。。


明显one,two具有非递增性质。。。
至于查询,暴力情况
for(int i=l;i<=r;i++)  if(one[i]<=r)   sum+=r-one[i]+1;
for(int i=l;i<=r;i++)  if(two[i]<=r)    sum-=r-two[i]+1;
由于非递增,那么就能二分,然后搞一下区间和。。。。


[cpp]
#include <iostream>  
#include <cstdio>  
#include <cstring>  
#include <algorithm>  
#include <map>  
#include <string>  
#define LL long long   
using namespace std; 
const int N = 100005; 
int n,m,a[N],r[N]; 
int one[N],two[N]; 
LL sum_one[N],sum_two[N]; 
char str[10]; 
map<string,int>mymap; 
bool cmp(char a,char b){ 
    return a>b; 

int main(){ 
    while(scanf("%d%d",&n,&m)!=EOF){ 
        mymap.clear(); 
        for(int i=1;i<=n;i++) 
            scanf("%d",&a[i]); 
        for(int i=n;i>=1;i--){ 
            string s=""; 
            int t=a[i]; 
            while(t){ 
                s+=(char)(t%10+'0'); 
                t/=10; 
            } 
            sort(s.begin(),s.end(),cmp); 
            if(mymap.find(s)==mymap.end()) 
                r[i]=n+1; 
            else r[i]=mymap[s]; 
            mymap[s]=i; 
        } 
        r[n+1]=n+1; 
        one[n+1]=two[n+1]=n+1; 
        for(int i=n;i>=1;i--){ 
            one[i]=min(one[i+1],r[i]); 
            two[i]=min(two[i+1],r[r[i]]); 
            two[i]=min(two[i+1],max(r[i],one[i+1])); 
        } 
        for(int i=1;i<=n;i++){ 
            sum_one[i]=sum_one[i-1]+one[i]; 
            sum_two[i]=sum_two[i-1]+two[i]; 
        } 
        LL ans=0; 
        while(m--){ 
            LL l,r;int pos; 
            scanf("%lld%lld",&l,&r); 
            l+=ans;r-=ans; 
            pos=upper_bound(one+l,one+r,r)-one-1; 
            ans=(pos-l+1)*r-(sum_one[pos]-sum_one[l-1])+(pos-l+1); 
            pos=upper_bound(two+l,two+r,r)-two-1; 
            ans-=(pos-l+1)*r-(sum_two[pos]-sum_two[l-1])+(pos-l+1); 
            printf("%lld\n",ans); 
        } 
    } 
    return 0; 

补充:软件开发 , C++ ,
CopyRight © 2022 站长资源库 编程知识问答 zzzyk.com All Rights Reserved
部分文章来自网络,