woj4790~4792

状态不好，当庭GG

极好的问题

考场脑残，实际上是个很弱的sort二分题。题意告诉我们重复的不用多算，那直接加就行。

按%mod余数sort，对于同一个数，选择了，那cnt要-1，如果为0就说明用完了不能用。

注意二分边界，注意卡常。

#include<bits/stdc++.h> using namespace std; #define in read() #define int long long int in{ int cnt=0,f=1;char ch=0; while(ch<'0'||ch>'9'){ ch=getchar();if(ch=='-')f=-1; } while(ch>='0'&&ch<='9'){ cnt=(cnt<<3)+(cnt<<1)+ch-48; ch=getchar(); }return cnt*f; } int n,mod; int a[2335]; struct node{ int key,cnt,res; }t[2335];int cnt; int ksm(int a,int b){ int sum=1;while(b){ if(b&1)sum=sum*a%mod;b>>=1;a=a*a%mod; }return sum; } bool cmm(node a,node b){ return a.res<b.res; } int sum[2335];int ans; int A,B; void exgcd(int a,int b,int &x,int &y){ if(!b){ x=1;y=0;return; }exgcd(b,a%b,y,x); y-=a/b*x; } signed main(){ n=in;mod=in;for(register int i=1;i<=n;++i)a[i]=in; sort(a+1,a+n+1); for(register int i=1;i<=n;++i){ if(a[i]!=a[i-1]){ t[++cnt]={a[i],1,a[i]%mod}; }else t[cnt].cnt++; }int x,y,z; //for(register int i=1;i<=cnt;++i)cout<<t[i].key<<" "<<t[i].cnt<<endl; sort(t+1,t+cnt+1,cmm); for(register int i=1;i<=cnt;++i){ x=t[i].cnt;--t[i].cnt; for(register int j=i;j<=cnt;++j){ if(!t[j].cnt)continue; y=t[j].cnt--;//cout<<t[i].key<<" "<<t[j].key<<" "; int mul=t[i].res*t[j].res%mod; exgcd(mul,mod,A,B);mul=(A%mod+mod)%mod;//cout<<mul<<endl; int l=j;int r=cnt;int as1,as2; while(l<r){//大于等于给定值的最小值 int mid=(l+r)>>1; if(t[mid].res>=mul)r=mid; else l=mid+1; }as1=l; if(!t[as1].cnt)as1++; l=j;r=cnt;//cout<<l<<" "<<r<<endl; while(l<r){//大于给定值的最小值 int mid=(l+r+1)>>1; if(t[mid].res>mul)r=mid-1; else l=mid; } as2=l;//cout<<t[i].key<<" "<<t[j].key<<" "<<as1<<" "<<as2<<" "<<t[as1].res<<endl; if(t[as1].res!=mul){ ++t[j].cnt;continue; } if(as1>as2){t[j].cnt++;continue;} z=as2-as1+1;//cout<<t[i].key<<" "<<t[j].key<<" "<<t[as1].key<<" "<<t[as2].key<<endl; //cout<<t[i].key<<" "<<t[j].key<<" "<<t[as1].key<<" "<<t[as2].key<<endl; ans+=as2-as1+1; ++t[j].cnt; } }cout<<ans; return 0; }

背包问题

本质是个二维偏序最长不下降，但有个背包限制很恶心。这个不是考场脑残，只是太菜而想不到怎么解决限制。

我们发现，肯定选大的背包好。那在查询的时候，注意当前能用的背包数量和最长不下降序列长度取min。

为了方便，我们倒序sort。为了习惯，我给value赋的是rank。

#include<bits/stdc++.h> using namespace std; #define in read() #define int long long int in{ int cnt=0,f=1;char ch=0; while(!isdigit(ch)){ ch=getchar();if(ch=='-')f=-1; } while(isdigit(ch)){ cnt=cnt*10+ch-48;ch=getchar(); }return cnt*f; } struct node{ int w,v; }a[100003]; int bag[100003]; int b[100003],bcnt,ans; int n,m; struct bili{ int t[100003]; int lowbit(int x){ return x&(-x); } void modify(int x,int key){ while(x<=n){ t[x]=max(t[x],key);x+=lowbit(x); } } int query(int x){ int sum=0; while(x){ sum=max(sum,t[x]);x-=lowbit(x); }return sum; } }t; bool cm(int a,int b){ return a>b; } bool cmm(node a,node b){ if(a.w!=b.w)return a.w<b.w;return a.v>b.v; } signed main(){ int T=in; while(T--){bcnt=0; memset(t.t,0,sizeof(t.t));n=in; for(int i=1;i<=n;i++){ a[i].w=in;a[i].v=in;b[++bcnt]=a[i].v; }sort(b+1,b+bcnt+1);bcnt=unique(b+1,b+bcnt+1)-b-1; for(int i=1;i<=n;i++)a[i].v=lower_bound(b+1,b+bcnt+1,a[i].v)-b,a[i].v=bcnt-a[i].v+1; m=in;for(int i=1;i<=m;i++)bag[i]=in; sort(bag+1,bag+m+1,cm);sort(a+1,a+n+1,cmm); //for(int i=1;i<=n;i++)cout<<a[i].w<<" "<<a[i].v<<endl; // cout<<endl<<endl<<endl<<endl<<endl<<endl<<endl<<endl; // for(int i=1;i<=m;i++)cout<<bag[i]<<" ";cout<<endl; int pos=0;ans=0; for(int i=n;i>0;i--){ while(pos<m&&bag[pos+1]>=a[i].w)++pos; int key=t.query(a[i].v);key=min(key+1,pos); ans=max(ans,key);t.modify(a[i].v,key); }cout<<ans<<'\n'; } return 0; }

子树问题

唯一一道做出来的题，因为组合数位忘了取模而44滚粗了。

对于这类计数问题，为了不重不漏，我们很明显要寻找一个固定的子结构来转移状态。

我们发现，因为是个编号大根堆，所以次小序号，一定连着根节点。

那我们枚举次小点的子树大小，然后标号即可。

令表示i个点，深度为j的方案数。

表示……哎呀，发现一个问题。如果子树深度刚好是j-1，其它子树就没必要达到j。而如果其它子树达到了j，那次小子树就没必要达到j-1。

GG，选择修改状态定义。

令表示i个点，深度最大为j的方案数。

所以

组合数的意义是，去掉根节点和次小节点，我们还需要k-1个点去成为次小子树。因为本身有编号限制，所以直接选出来不需要在意顺序。

但是要注意，我们的状态设置是深度前缀和，我们必须从深度开始枚举，否则会有后效性。

//尝试列方程 //发现次小必须接自己的性质。 //发现方程列不动。次小可能深度为j，但别的子树也可能深度为j。 //考虑差分？，令j意义变为深度最大限制。 //合并子树最大j-1，其它子树最大j。方程可列。 //f[i][j]=\sum_{k=1}^{i-1} f[k][j-1]*f[i-k][j]*C(i,k)。 //从中选择一些号码出来做新子树。 #include<bits/stdc++.h> using namespace std; #define in read() #define int long long int in{ int cnt=0,f=1;char ch=0; while(!isdigit(ch)){ ch=getchar();if(ch=='-')f=-1; } while(isdigit(ch)){ cnt=cnt*10+ch-48; ch=getchar(); }return cnt*f; } int f[503][503]; int n,k,a[503]; int c[503][503]; int vis[503]; const int mod=998244353; signed main(){ // freopen("subtree.in","r",stdin); // freopen("subtree.out","w",stdout); n=in;k=in;for(int i=1;i<=k;i++)vis[a[i]=in]=1;sort(a+1,a+k+1); for(int i=0;i<=500;i++)c[i][0]=1; for(int i=1;i<=500;i++)for(int j=1;j<=i;j++)c[i][j]=(c[i-1][j]+c[i-1][j-1])%mod; // for(int i=0;i<=n;i++){ // for(int j=0;j<=i;j++)cout<<c[i][j]<<" ";cout<<endl; // } f[1][1]=1; for(int j=2;j<=n;j++){f[1][j]=1; for(int i=2;i<=n;i++){ for(int kk=1;kk<i;kk++){ f[i][j]=(f[i][j]+f[kk][j-1]*f[i-kk][j]%mod*c[i-2][kk-1]%mod)%mod; } } for(int i=1;i<=k;i++){ f[a[i]][j]=0; } } // for(int i=1;i<=n;i++){ // for(int j=1;j<=n;j++)cout<<f[i][j]<<" ";cout<<endl; // } int l=in;int r=in; // for(int i=l;i<=r;i++)cout<<f[n][i]<<" "; cout<<endl; for(int i=l;i<=r;i++)cout<<(f[n][i]-f[n][i-1]%mod+mod)%mod<<" "; return 0; }