最近有点头晕...........

T1 养花

考场我没想到正解，后来打的主席树，对于每个摸数查找1-(k-1),k-(2k-1)。。。的最大值，事实上还是很容易被卡的但是没有数据好像还比较友善，

对于求一段区间的最大值，因为建的是权值线段树，所以只需查找满足在查找的这段权值的区间内并且在L-R之内就好

在区间查询上稍改一下

正解分块咕了.....

 

***********************

查找mod某数的最大值，可以查1-(k-1)。。。拆开查询

 

1 #include
      
        2 #define MAXN 110000 3 using namespace std; 4 int tot=0;int a[MAXN],f[30][MAXN];int n,m; 5 int read(){ 6     int x=0;char c=getchar();int f=1; 7     while(c<'0'||c>'9'){
    if(c=='-')f=-1;c=getchar();} 8     while(c>='0'&&c<='9'){x=(x<<1)+(x<<3)+(c^48);c=getchar();} 9     return x;10 }11 struct node{
    int ls,rs,sum,me;}t[MAXN*100];12 void insert(int &now,int x,int L,int R){13      if(now==0)now=++tot;14      int mid=(L+R)>>1;15      if(L==R){t[now].sum++;t[now].me=x;return ;}16      if(x<=mid)insert(t[now].ls,x,L,mid);17      else insert(t[now].rs,x,mid+1,R);18      t[now].sum=t[t[now].ls].sum+t[t[now].rs].sum;     19 }20 int merge(int x,int y){21     if(!x||!y)return x+y;22     t[x].ls=merge(t[x].ls,t[y].ls);23     t[x].rs=merge(t[x].rs,t[y].rs);24     t[x].sum+=t[y].sum;25     return x;26 }27 int find(int now,int last){28     int nowls=t[now].ls;int nowrs=t[now].rs;29     int lastls=t[last].ls;int lastrs=t[last].rs;30     if(!nowls&&!nowrs){
    return t[now].me;}31     if(t[nowrs].sum-t[lastrs].sum>0){
    return find(nowrs,lastrs);}32     else if(t[nowls].sum-t[lastls].sum>0){
    return find(nowls,lastls);}33     else return 0;34 }35 int maxn=0;int ok=0;int logg[MAXN];36 void ask(int now,int last,int l,int r,int L,int R,int k){37     if(ok==1)return ;38     if(l<=L&&r>=R){39        if(t[now].sum>t[last].sum){maxn=max(maxn,find(now,last)%k);ok=1;}40        return ;41     }    42     int mid=(L+R)>>1;43     if(r>mid) ask(t[now].rs,t[last].rs,l,r,mid+1,R,k);44     if(l<=mid)ask(t[now].ls,t[last].ls,l,r,L,mid,k);45 }46 int RMB(int l,int r){47     int t=logg[r-l+1]/logg[2];48     return max(f[t][l],f[t][r-(1<
       
        =k1&&a[i]<=k2){63             mt=max(mt,a[i]%k);64          }65      }66      return mt;67 }68 signed main(){69 //freopen("t1.in","r",stdin);70 //freopen("aa.out","w",stdout);71     n=read();m=read();72     for(int i=1;i<=n;++i)logg[i]=log(i)/log(2);73     for(int i=1;i<=n;++i){74         a[i]=read();75         mmm=max(a[i],mmm);76     }77     init();78     for(int i=1;i<=n;++i)insert(rt[i],a[i],0,mmm);79     for(int i=1;i<=n;++i)rt[i]=merge(rt[i],rt[i-1]);80     for(int i=1;i<=m;++i){81         maxn=0;int l=0,r=0,k=0;ok=0;82         l=read();r=read();k=read();83         for(int pt=1;pt<=RMB(l,r)/k+1;++pt){84             ok=0;85             ask(rt[r],rt[l-1],(pt-1)*k,pt*k-1,0,mmm,k);86         }       87         printf("%d\n",maxn);88     }89 }
       
      

 

 

T2 折射

考场大概只看出了n^3DP，用树状数组优化一下成了n^2log(n),事实上快结束时看出可以改成n^2前缀和即可

但是内存炸了，考场有没看清内存，不然卡一卡能拿80

然后正解思路清奇

我们按x排序，然后f[i][0]表示以i为顶点，向左连边，f[i][1]表示以i为顶点，向右连边

然后对于j而言，如果b[j]>b[i]，则证明j才是折线的顶点，那么就是用i改j

如果b[i]>b[j]那么就是i为定点，用j改i

 

1 #include
      
        2 #define MAXN 6100 3 using namespace std; 4 const int mod=1e9+7; 5 int f[MAXN];struct node{
    int a,b;}e[MAXN]; 6 int n; 7 bool cmp(node aa,node bb){ 8      if(aa.b==bb.b)return aa.a>bb.a; 9      return aa.b>bb.b;10 }11 int c[MAXN][MAXN];int yuan[MAXN];int maxn=0;12 int query(int x,int ad){13     return c[x][ad]%mod;14 }15 int ans=0;16 signed main(){17     //freopen("t2.in","r",stdin);18     //freopen("bb.out","w",stdout);19     scanf("%d",&n);20     for(int i=1;i<=n;++i){scanf("%d%d",&e[i].a,&e[i].b);yuan[++yuan[0]]=e[i].a;}21     sort(yuan+1,yuan+yuan[0]+1);22     int kx=unique(yuan+1,yuan+yuan[0]+1)-yuan-1;23     for(int i=1;i<=n;++i){24         e[i].a=lower_bound(yuan+1,yuan+kx+1,e[i].a)-yuan;25         maxn=max(maxn,e[i].a);26     }27     sort(e+1,e+n+1,cmp);28     for(int i=2;i<=n;++i){29         memset(f,0,sizeof(f));30         for(int j=1;j
      

 

1 #include
      
        2 #define MAXN 6100 3 using namespace std; 4 const int mod=1e9+7; 5 int f[MAXN][2]; 6 int n; 7 struct node{
    int a,b;}e[MAXN]; 8 bool cmp(node aa,node bb){ 9      return aa.a
       
        =1;--j){23             if(e[j].b
        
         e[i].b){27                f[j][1]=(f[j][1]%mod+f[i][0]%mod)%mod;28             }29         }30     }31     for(int i=1;i<=n;++i){32         ans=(ans+f[i][0]%mod);33         ans=(ans+f[i][1]-1+mod)%mod;34     }35     printf("%lld\n",ans%mod);36 }
        
       
      

 

 

***************************

1.注意内存。

2.结合图像思路转化

 

 

T3

还没改过来，做的有点慢了