最近有点头晕...........
T1 养花
考场我没想到正解，后来打的主席树，对于每个摸数查找1-(k-1),k-(2k-1)。。。的最大值，事实上还是很容易被卡的但是没有数据好像还比较友善，
对于求一段区间的最大值，因为建的是权值线段树，所以只需查找满足在查找的这段权值的区间内并且在L-R之内就好
在区间查询上稍改一下
正解分块咕了.....
***********************
查找mod某数的最大值，可以查1-(k-1)。。。拆开查询
1 #include<bits/stdc++.h> 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<<t)+1]); 49 } 50 void init(){ 51 for(int i=1;i<=n;++i)f[0][i]=a[i]; 52 for(int j=1;j<=29;++j){ 53 for(int i=1;i+(1<<j)-1<=n;++i){ 54 f[j][i]=max(f[j-1][i],f[j-1][i+(1<<(j-1))]); 55 } 56 } 57 } 58 int rt[MAXN];int mmm=0; 59 int voi(int l,int r,int k1,int k2,int k){ 60 int mt=0; 61 for(int i=l;i<=r;++i){ 62 if(a[i]>=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<bits/stdc++.h> 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<i;++j){ 31 if(e[j].b<=e[i].b)continue; 32 if(e[i].a==e[j].a)continue; 33 f[e[j].a]++; 34 if(e[i].a<e[j].a){ 35 f[e[j].a]=(f[e[j].a]+query(j,e[i].a-1))%mod; 36 } 37 else{ 38 f[e[j].a]=(f[e[j].a]+query(j,maxn)-query(j,e[i].a)+mod)%mod; 39 } 40 //printf("f[%d]=%d\n",e[j].a,f[e[j].a]); 41 } 42 for(int j=1;j<=maxn;++j){ 43 c[i][j]=(f[j]+c[i][j-1])%mod; 44 } 45 } 46 for(int i=1;i<=n;++i)ans=(ans+c[i][maxn])%mod; 47 printf("%d\n",(ans+n)%mod); 48 }
1 #include<bits/stdc++.h> 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<bb.a; 10 } 11 long long ans=0; 12 signed main(){ 13 //freopen("t2.in","r",stdin); 14 //freopen("bb.out","w",stdout); 15 scanf("%d",&n); 16 for(int i=1;i<=n;++i){scanf("%d%d",&e[i].a,&e[i].b);} 17 sort(e+1,e+n+1,cmp); 18 for(int i=1;i<=n;++i){ 19 //printf("e[%d].a=%d e[%d].b=%d\n",i,e[i].a,i,e[i].b); 20 f[i][0]=1,f[i][1]=1; 21 if(e[i].a==e[i-1].a)continue; 22 for(int j=i-1;j>=1;--j){ 23 if(e[j].b<e[i].b){ 24 f[i][0]=(f[i][0]%mod+f[j][1]%mod)%mod; 25 } 26 else 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
还没改过来，做的有点慢了