冲刺CSP联训模拟2
\(T1\) P294. 挤压 \(40pts\)
-
部分分
- \(20 \%\) ：爆搜，时间复杂度为 \(O(2^{n})\) 。
- 另外 \(20 \%\) ：观察到值域较小，将值域计入状态设计，时间复杂度为 \(O(nV)\) 。
点击查看代码
const ll mod=1000000007; ll a[100010],p[100010],pp[100010],q[100010],f[2][9000010],ans=0; ll qpow(ll a,ll b,ll p) { ll ans=1; while(b) { if(b&1) { ans=ans*a%p; } b>>=1; a=a*a%p; } return ans; } void dfs(ll pos,ll n,ll sum,ll mul) { if(pos==n+1) { sum%=mod; ans=(ans+(sum*sum%mod)*mul%mod)%mod; } else { dfs(pos+1,n,sum^a[pos],mul*p[pos]%mod); dfs(pos+1,n,sum,mul*pp[pos]%mod); } } int main() { freopen("a.in","r",stdin); freopen("a.out","w",stdout); ll n,m=0,inv=qpow(1000000000,mod-2,mod),i,j; cin>>n; for(i=1;i<=n;i++) { cin>>a[i]; m=max(m,a[i]); } for(i=1;i<=n;i++) { cin>>q[i]; p[i]=q[i]*inv%mod; pp[i]=(1000000000-q[i])*inv%mod; } if(n<=28) { dfs(1,n,0,1); } else { m*=2; f[0][0]=1; for(i=1;i<=n;i++) { for(j=0;j<=m;j++) { f[i&1][j]=(f[(i-1)&1][j]*pp[i]%mod+f[(i-1)&1][j^a[i]]*p[i]%mod)%mod; } } for(i=0;i<=m;i++) { ans=(ans+((i%mod)*(i%mod)%mod)*f[n&1][i]%mod)%mod; } } cout<<ans<<endl; fclose(stdin); fclose(stdout); return 0; } -
正解
- 按位做，考虑拆平方。
- 设最终的异或和在二进制表示下（空位补零）为 \((s_{32}s_{31} \dots s_{1}s_{0})_{2}\) ，其平方可以表示成 \(\sum\limits_{i=0}^{32}\sum\limits_{j=0}^{32}s_{i}s_{j}2^{i+j}\) 。
- 观察到每一项仅与两位有关，那么可以将 \(a_{x}\) 的第 \(i,j\) 位拿出来单独计算其期望。
- 设 \(f_{k,i,j,0/1,0/1}\) 表示处理到第 \(k\) 个数时，第 \(i\) 位 \(=0/1\) 且第 \(j\) 位 \(=0/1\) 的期望，枚举选或不选转移即可。
- 最终，有 \(\sum\limits_{i=0}^{32}\sum\limits_{j=0}^{32}f_{n,i,j,1,1}2^{i+j}\) 即为所求。
点击查看代码
const ll mod=1000000007; ll a[100010],p[100010],q[100010],f[2][35][35][2][2]; ll qpow(ll a,ll b,ll p) { ll ans=1; while(b) { if(b&1) { ans=ans*a%p; } b>>=1; a=a*a%p; } return ans; } int main() { freopen("a.in","r",stdin); freopen("a.out","w",stdout); ll n,inv=qpow(1000000000,mod-2,mod),ans=0,i,j,k,h,l; cin>>n; for(i=1;i<=n;i++) { cin>>a[i]; } for(i=1;i<=n;i++) { cin>>q[i]; p[i]=q[i]*inv%mod; } for(i=0;i<=32;i++) { for(j=0;j<=32;j++) { f[0][i][j][0][0]=1; } } for(k=1;k<=n;k++) { for(i=0;i<=32;i++) { for(j=0;j<=32;j++) { for(h=0;h<=1;h++) { for(l=0;l<=1;l++) { f[k&1][i][j][h][l]=(f[(k-1)&1][i][j][h][l]*(1-p[k]+mod)%mod+f[(k-1)&1][i][j][h^((a[k]>>i)&1)][l^((a[k]>>j)&1)]*p[k]%mod); } } } } } for(i=0;i<=32;i++) { for(j=0;j<=32;j++) { ans=(ans+f[n&1][i][j][1][1]*qpow(2,i+j,mod)%mod)%mod; } } cout<<ans<<endl; fclose(stdin); fclose(stdout); return 0; }
\(T2\) P295. 工地难题 \(25pts\)
-
当 \(n \ne m\) 时，对于 \(k> \frac{m}{2}\) ，答案显然为 \(2\dbinom{n-(k+1)}{m-k}+\dbinom{n-(k+2)}{m-k}A_{n-(k+2)+1}^{1}=2\dbinom{n-k-1}{m-k}+\dbinom{n-k-2}{m-k}(n-k-1)\) 。
-
部分分
- \(20 \%\) ：爆搜，递归枚举组合，并及时剪枝。
点击查看代码
const ll p=1000000007; ll inv[200010],jc[200010],jc_inv[200010],f[200010]; ll qpow(ll a,ll b,ll p) { ll ans=1; while(b) { if(b&1) { ans=ans*a%p; } b>>=1; a=a*a%p; } return ans; } ll C(ll n,ll m,ll p) { return (n>=m&&n>=0&&m>=0)?(jc[n]*jc_inv[n-m]%p)*jc_inv[m]%p:0; } void dfs(ll pos,ll n,ll sum0,ll sum1,ll maxx,ll pre,ll k) { maxx=max(maxx,pre); if(maxx<=k) { if(pos==n+1) { f[maxx]=(f[maxx]+1)%p; return; } else { if(sum0>=1) { dfs(pos+1,n,sum0-1,sum1,maxx,0,k); } if(sum1>=1) { dfs(pos+1,n,sum0,sum1-1,maxx,(pre!=0)*pre+1,k); } } } } int main() { freopen("a.in","r",stdin); freopen("a.out","w",stdout); ll n,m,i; cin>>n>>m; jc[0]=jc_inv[0]=1; for(i=1;i<=n;i++) { inv[i]=qpow(i,p-2,p); jc[i]=jc[i-1]*i%p; jc_inv[i]=jc_inv[i-1]*inv[i]%p; } if(n==m) { for(i=1;i<=n-1;i++) { cout<<0<<" "; } cout<<1<<endl; } else { dfs(1,n,n-m,m,0,0,m/2); for(i=1;i<=m/2;i++) { cout<<f[i]<<" "; } for(i=m/2+1;i<=m;i++) { cout<<(2*C(n-i-1,m-i,p)%p+C(n-i-2,m-i,p)*(n-i-1)%p)%p<<" "; } } fclose(stdin); fclose(stdout); return 0; } -
正解
\(T3\) P296. 星空遗迹 \(20pts\)
-
部分分
- \(20 \%\) ：模拟，时间复杂度为 \(O(qn^{2})\) 。
点击查看代码
char s[200010],tmp[200010]; char w(char x,char y) { if(x==y){return x;} if(x!='R'&&y!='R'){return 'S';} if(x!='S'&&y!='S'){return 'P';} if(x!='P'&&y!='P'){return 'R';} return 'A'; } void f(char s[],int len) { for(int i=1;i<=len-1;i++) { s[i]=w(s[i],s[i+1]); } } char ask(int l,int r) { for(int i=l,j=1;i<=r;i++,j++) { tmp[j]=s[i]; } for(int i=l,j=r-l+1;i<=r;i++,j--) { f(tmp,j); } return tmp[1]; } int main() { freopen("a.in","r",stdin); freopen("a.out","w",stdout); int n,q,pd,l,r,i; char c; cin>>n>>q>>(s+1); for(i=1;i<=q;i++) { cin>>pd; if(pd==1) { cin>>l>>c; s[l]=c; } else { cin>>l>>r; cout<<ask(l,r)<<endl; } } fclose(stdin); fclose(stdout); return 0; } -
正解
\(T4\) P297. 纽带 \(10pts\)
-
部分分
-
\(10 \%\) ：模拟。时间复杂度为 \(O(n! \times n^{3})\) 。
点击查看代码
const int mod=1000000007; int m[50],p[50],cnt[50],f[3000]; bool cmp(int l,int r) { memset(cnt,0,sizeof(cnt)); for(int i=l;i<=r;i++) { cnt[p[i]]++; } for(int i=l;i<=r;i++) { if(cnt[i]==0) { return false; } } return true; } int main() { freopen("a.in","r",stdin); freopen("a.out","w",stdout); int n,sum,flag,l,r,i; cin>>n; for(i=1;i<=n;i++) { cin>>m[i]; p[i]=i; } do { sum=0; flag=1; for(l=1;l<=n;l++) { for(r=l;r<=m[l];r++) { flag&=(cmp(l,r)==false); if(flag==0) { break; } } if(flag==0) { break; } } if(flag==1) { for(l=1;l<=n;l++) { for(r=max(l,m[l]+1);r<=n;r++) { sum+=(cmp(l,r)==true); } } f[sum]=(f[sum]+1)%mod; } }while(next_permutation(p+1,p+1+n)); for(i=1;i<=n*(n+1)/2;i++) { cout<<f[i]<<" "; } fclose(stdin); fclose(stdout); return 0; } -
\(20 \%\) ：模拟，枚举右端点和判断是否合法可以继承。时间复杂度为 \(O(n! \times n^{2})\) 。
-
-
正解
总结
- \(T2\) 数组开小挂了 \(5pts\) 。
- \(T4\) 没有意识到自己判断是否是排列和枚举右端点可以继承，所以写的是 \(O(n! \times n^{3})\) ，挂了 \(10pts\) 。