T1
代码难度: 入门
知识难度: 提高 -
思维难度: 普及
显然从 n 个位置中钦定 m 个是稳定位置之后, 其余的错排即可.
错排公式 $f[i]=(i-1)(f[i-1]+f[i-2])$ 的推导过程如下:
假设现在已经选好了 i-1 个元素, 那么第 i 个元素可能的位置是前 i-1 个, 然后假设被换掉的那个元素:
到了第 i 位, 那么就是 i-2 个元素的错排.
不在第 i 位, 那么被换掉的元素不能在第 i 位, 就相当于 i-1 个元素的错排了.
- #include <bits/stdc++.h>
- #define P 1000000007
- int T,fac[1000005],ifa[1000005],f[1000005],n,m;
- int ksm(int di,int mi){int res=1;for(;mi;mi>>=1,di=1ll*di*di%P) if(mi&1) res=1ll*res*di%P;return res;}
- int main()
- {
- f[2]=f[0]=1;for(int i=3;i<=1000000;i++) f[i]=1ll*(i-1)*(f[i-1]+f[i-2])%P;
- fac[0]=1;for(int i=1;i<=1000000;i++) fac[i]=1ll*fac[i-1]*i%P;
- ifa[1000000]=ksm(fac[1000000],1000000005);for(int i=999999;~i;i--) ifa[i]=1ll*ifa[i+1]*(i+1)%P;
- for(scanf("%d",&T);T--;) scanf("%d%d",&n,&m),printf("%d\n",1ll*fac[n]*ifa[m]%P*ifa[n-m]%P*f[n-m]%P);
- }
- T2
代码难度: 提高
知识难度: 提高
思维难度: 提高
首先因为是 $xor$ 操作并且是加权和, 所以我们可以按位处理并在最后把每一位的答案加起来.
如果确定了某一列的状态, 那么可以 $O(n)$ 算出这一列自身点和竖向边的贡献. 我们预处理 $v[i]$ 表示某一列和上一列异或值为 i 时, 横向边 S2 的贡献, 这个显然可以 $O(2^n)$ 处理出来. 然后我们 $O(4^n)$ 枚举这一列和上一列的状态, 并用处理好的 $v$ 直接计算横向贡献, 并更新这一列的答案.
所以我们可以直接这样表示状态:$f[i][s]$ 表示第 i 列, d 数组这一列当前枚举位的取值状态为 s 时的最小值, 转移的时候逐列转移即可. 复杂度 $O(mloga4^n)$, 但由于位运算的常数极小, 能够通过本题.
- #include <bits/stdc++.h>
- using namespace std;
- #define ll long long
- int n,m,w;ll t,ans,f[2][22][1005],v[1025],A[6][10005],B[6][10005],C1[6][10005],C2[6][10005];
- int main()
- {
- scanf("%d%d",&n,&m);
- for(int i=0;i<n;i++) for(int j=1;j<=m;j++) scanf("%lld",&A[i][j]);
- for(int i=0;i<n;i++) for(int j=1;j<=m;j++) scanf("%lld",&B[i][j]);
- for(int i=0;i<n;i++) for(int j=2;j<=m;j++) scanf("%lld",&C1[i][j]);
- for(int i=0;i<n;i++) for(int j=1;j<=m;j++) scanf("%lld",&C2[i][j]);
- for(int i=1;i<=m;i++)
- {
- w=i&1;memset(f[w],0,sizeof(f[w]));
- if(i>1) for(int s=0,j;s<(1<<n);s++) for(v[s]=0,j=0;j<n;j++) if(s>>j&1) v[s]+=C1[j][i];
- for(int j=0;j<=20;j++) for(int s=0;s<(1<<n);s++)
- {
- t=0;for(int k=0;k<n;k++) t+=((s>>k&1)^(A[k][i]>>j)&1)*B[k][i]+((s>>k&1)^(s>>((k+1)%n)&1))*C2[k][i];
- f[w][j][s]=1ll<<61;if(i==1) f[w][j][s]=t;
- else for(int g=0;g<(1<<n);g++) f[w][j][s]=min(f[w][j][s],t+v[g^s]+f[w^1][j][g]);
- }
- }
- for(int i=0,s;i<=20;ans+=t<<i,i++) for(s=0,t=1ll<<61;s<(1<<n);s++) t=min(t,f[m&1][i][s]);printf("%lld",ans);
- }
- T3
代码难度: 省选 -
知识难度: 省选 -
思维难度: 省选 -
假设某个区间 $[l,r]$ 的最大值的位置是 $m$, 那么我们发现, 对于且仅对于左端点在 $[l,m]$, 右端点在 $[m+1,r]$ 中的区间, m 这个位置有可能产生贡献. 我们可以考虑分治: 对于一个区间, 找到最大值, 计算区间跨最大值的贡献, 然后递归处理 $[l,m-1],[m+1,r]$. 对于一次跨最大值的统计贡献, 我们可以这样做: 暴力枚举长度小的那一边, 对于长度大的那一边我们用数据结构去统计合法的数字个数, 查询一个区间中一个区间的数字的出现个数, 显然离散化后主席树是最好的选择, 而查询最大值位置当然是 st 表.
这样的复杂度是不是看着不太对? 但是它就是 $O(nlog^2n)$ 的! 首先排除主席树的这一个 $log$, 考虑分治的过程. 每一层分治, 我们只遍历了数字少的那一边, 考虑某个下标对复杂度的贡献, 如果这个下标产生了贡献, 那么下次要是再产生贡献, 说明包含它的那个块的大小至少减少了一半. 所以每个下标最多产生 $logn$ 的贡献, 总复杂度就是 $nlogn$ 了. 实际上这就是启发式分治, 是启发式合并的逆过程.
实际上还可以非递归地做: 对每个数单调栈找 $L[i],R[i]$ 表示左右第一个比它大的位置, 那么对于一个 $[L[i]+1,R[i]-1]$, 按照上面说的方法统计即可. 这样的话还可以省略主席树, 而是离线之后用树状数组去做.
至此, 这个题就解决了. 不过有一些细节问题, 包括但不限于判断序列中是否有 0, 离散化之后的下标问题, 写的时候需要高度注意.
- #include <bits/stdc++.h>
- using namespace std;
- int n,m,tot,c[2],a[100005],t[100005],rt[100005],sm[8000005],ls[8000005],rs[8000005],st[20][100005],lg[100005];long long ans;
- inline const int Max(const int x,const int y){return a[x]>a[y]?x:y;}
- inline const int que(const int x,const int y){const int k=lg[y-x+1];return Max(st[k][x],st[k][y-(1<<k)+1]);}
- void ins(const int x,int &y,const int l,const int r,const int p)
- {
- y=++tot;sm[y]=sm[x]+1;if(l==r) return;const int mx=(l+r)>>1;
- if(p<=mx) rs[y]=rs[x],ins(ls[x],ls[y],l,mx,p);else ls[y]=ls[x],ins(rs[x],rs[y],mx+1,r,p);
- }
- const int que(const int x,const int y,const int l,const int r,const int b,const int e)
- {
- if(b>e) return 0;if(b<=l&&r<=e) return sm[y]-sm[x];const int mx=(l+r)>>1;
- return (b<=mx?que(ls[x],ls[y],l,mx,b,e):0)+(e>mx?que(rs[x],rs[y],mx+1,r,b,e):0);
- }
- void gao(const int l,const int r)
- {
- if(l>r) return;if(l==r){ans+=(a[l]==1||a[l]==0);return;}const int mx=que(l,r);
- if(c[0]) ans+=1ll*que(rt[l-1],rt[r],1,m,c[0],c[0]);if(c[1]) ans+=1ll*que(rt[l-1],rt[r],1,m,c[1],c[1]);
- if(mx-l>r-mx) for(int i=mx+1;i<=r;i++) ans+=a[i]==0?mx-l:que(rt[l-1],rt[mx-1],1,m,1,upper_bound(t+1,t+m+1,a[mx]/a[i])-t-1);
- else for(int i=l;i<mx;i++) ans+=a[i]==0?r-mx:que(rt[mx],rt[r],1,m,1,upper_bound(t+1,t+m+1,a[mx]/a[i])-t-1);
- if(mx-l>0) gao(l,mx-1);if(r-mx>0) gao(mx+1,r);
- }
- int main()
- {
- scanf("%d",&n);for(int i=1;i<=n;i++) scanf("%d",&a[i]),t[i]=a[i];sort(t+1,t+n+1);m=unique(t+1,t+n+1)-t-1;
- for(int i=1;i<=m;i++) if(t[i]<2) c[t[i]]=i;st[0][1]=1;for(int i=2;i<=n;i++) st[0][i]=i,lg[i]=lg[i>>1]+1;
- for(int i=1;(1<<i)<=n;i++) for(int j=1;j+(1<<i)-1<=n;j++) st[i][j]=Max(st[i-1][j],st[i-1][j+(1<<i-1)]);
- for(int i=1;i<=n;i++) ins(rt[i-1],rt[i],1,m,lower_bound(t+1,t+m+1,a[i])-t);gao(1,n);printf("%lld\n",ans);
- }
- (测试)
来源: http://www.bubuko.com/infodetail-2827388.html