模拟赛
今天第一节课是历史，当然是不可能上的，一来到机房发现今天高二考试...
老师说以后可能还要给高一考...那还不如现在跟着做好了，毕竟在学长学姐中垫底显得没那么丢人
这套题风格挺奇怪的...为什么前面还是神牛后面直接成牛了...
题意概述：给出一个长度为$n$的数列,从某个地方把它分成两部分(均不为空),从前半部分选出一些数,后半部分选出一些数,使得前面这些数的$xor$和等于后面的$and$和,求方案数. $n<=10^3,0<=a_i<1024$
差点被题意杀,其实这个分割点只是限制前后分组顺序的,分割点不同但前后选的人均相同时视为不同的方案.选的人都相同但是分组不同,如$([2,2,3],[3]),([2],[2,2,3])$也算两种方案.
明确了题意就好做多了.可以发现数据范围并不是很大,所以可以枚举断点求方案数.又发现数据范围真的不是很大,所以也可以枚举$xor$和.又发现...再枚举真要超时了.
枚举了这些之后就只需要求出前$i$个中选出一些数使得$xor$和为$x$的方案数,后$i$个中选出一些数使得$and$和为$x$的方案数.这样就比较简单啦!随便$dp$转移一下就行.不过有可能会出现重复方案,对于这个问题固定第一个区间的右端点必选即可.
1 # include <cstdio> 2 # include <iostream> 3 # include <queue> 4 # include <cstring> 5 # include <string> 6 # define R register int 7 # define ll long long 8 # define mod 1000000007 9 10 using namespace std; 11 12 const int maxn=1003; 13 int n,m; 14 int a[maxn],xorr[maxn][1030],andd[maxn][1030],ans; 15 16 int main() 17 { 18 scanf("%d",&n); 19 for (R i=1;i<=n;++i) 20 scanf("%d",&a[i]),m=max(m,a[i]); 21 for (R i=1;i<=n;++i) 22 { 23 xorr[i][ a[i] ]=1; 24 for (R j=0;j<=m;++j) 25 xorr[i][ a[i]^j ]=(xorr[i][ a[i]^j ]+xorr[i-1][j])%mod; 26 for (R j=0;j<=m;++j) 27 xorr[i][j]=(xorr[i][j]+xorr[i-1][j])%mod; 28 } 29 for (R i=n;i>=1;--i) 30 { 31 andd[i][ a[i] ]=1; 32 for (R j=0;j<=m;++j) 33 andd[i][ a[i]&j ]=(andd[i][ a[i]&j ]+andd[i+1][j])%mod; 34 for (R j=0;j<=m;++j) 35 andd[i][j]=(andd[i][j]+andd[i+1][j])%mod; 36 } 37 for (R i=1;i<n;++i) 38 for (R j=0;j<=m;++j) 39 ans=(1LL*(xorr[i][j]-xorr[i-1][j]+mod)*andd[i+1][j]%mod+ans)%mod; 40 printf("%d",ans); 41 fclose(stdin); 42 fclose(stdout); 43 return 0; 44 }
题意概述：一个长度为$n$的序列,每个数的取值是$0-L$,求有多少种取值方案使得可以从这些数中取出一些数,且和为$k$.$n,k<=20,L<=10^9$
看起来挺像组合数学的,毕竟$l$非常大,好像只能用非常快的算法.首先用插板法算出把$k$个数分成$1->n$份的方案数,然后把这些数再组合数一番放进$n$个位置中,其他位置从$[1,L]$中任意取即可.听起来非常好,然而是不是有点太快了?如果真是这么做的话完全可以把$n,k$都放大一百倍,手玩一组发现这个做法会重复...而且我几乎不会容斥.
突然想到某一个讲座的时候:"我就打了$6$个$dp$,就……",其实这道题的$dp$思路不是特别难想,一开始想的是$dp[i][j]$表示前$i$个数,拼出来的数最大是$j$的方案数,这种方程特别好转移,然而一点实际意义也没有...所以能拼出来的数必须全表示出来,$dp[i][j]$表示前$i$个数,能拼出来的数的状态是$j$的方案数.转移的时候枚举上一位的状态以及这一位填什么即可.停!$L$不是$10^9$吗?其实我们只关心能不能拼出$k$,所以大于$k$的数对于状态是没有贡献的,这一部分直接乘起来就可以了.
注意...虽然$l$的范围非常大,$k$的范围非常小,但是这并不能说明$l<k$,转移的时候不能直接转移到$k$,而是$min(k,l)$,因为这个丢了$20$分,伤心.
对了,别忘了开滚动数组.
1 # include <cstdio> 2 # include <iostream> 3 # include <queue> 4 # include <cstring> 5 # include <string> 6 # define R register int 7 # define ll long long 8 # define mod 1000000007 9 10 using namespace std; 11 12 const int maxn=2100000; 13 int n,k,l,vis[50],viss[50],maxz; 14 int dp[3][maxn]; 15 ll ans=0; 16 17 int main() 18 { 19 scanf("%d%d%d",&n,&k,&l); 20 maxz=(1<<(k+1))-1; 21 dp[0][0]=1; 22 for (R i=0;i<n;++i) 23 { 24 int las=i&1; 25 int now=las^1; 26 memset(dp[now],0,sizeof(dp[now])); 27 for (R z=0;z<=maxz;++z) 28 { 29 if(i==1&&z==2) 30 i=1; 31 if(!dp[las][z]) continue; 32 vis[0]=true; 33 int t=z; 34 for (R x=1;x<=k;++x) 35 vis[x]=t%2,t/=2; 36 for (R x=0;x<=k;++x) 37 { 38 if(x>l) break; 39 for (R j=0;j<=k;++j) viss[j]=vis[j]; 40 for (R j=0;j<=k;++j) if(vis[j]) viss[j+x]=true; 41 int nexz=0; 42 for (R j=k;j>=1;--j) 43 nexz=nexz*2+viss[j]; 44 dp[now][nexz]=(dp[now][nexz]+dp[las][z])%mod; 45 } 46 if(l>k) dp[now][z]=(dp[now][z]+1LL*dp[las][z]*(l-k)%mod)%mod; 47 } 48 } 49 for (R i=0;i<=maxz;++i) 50 if(i&(1<<(k-1))) 51 ans=(ans+dp[n&1][i])%mod; 52 printf("%lld",ans); 53 return 0; 54 }
T3:一个数据范围消失了的分层图最短路...因为没有数据范围于是直接选择性失明不管那个限制了,竟然水了$70$...事实上因为限制点的数量非常小,直接$dfs$即可.
1 # include <cstdio> 2 # include <iostream> 3 # include <cstring> 4 # include <queue> 5 # include <string> 6 # define inf 10000000 7 # define R register int 8 9 using namespace std; 10 11 const int dx[]={-1,1,0,0}; 12 const int dy[]={0,0,-1,1}; 13 const int maxn=104; 14 char st[105]; 15 int n,m,ans=-1,bx,by,ex,ey; 16 int g[maxn][maxn],sx[10],sy[10],h; 17 int vis[maxn][maxn][10]; 18 struct z 19 { 20 int val,x,y,k; 21 }; 22 queue <z> q; 23 24 bool mw (int x,int y,int k,int d) 25 { 26 int xx=x+dx[d]; 27 int yy=y+dy[d]; 28 if(xx<=0||xx>n||yy<=0||yy>n) return false; 29 if(g[xx][yy]==-1) return false; 30 return true; 31 } 32 33 int dij (int ext) 34 { 35 memset(vis,-1,sizeof(vis)); 36 while (q.size()) q.pop(); 37 int x,y,k,xx,yy; 38 z a,b; 39 a.x=bx; 40 a.y=by; 41 a.val=0; 42 a.k=0; 43 q.push(a); 44 vis[ a.x ][ a.y ][0]=0; 45 while (q.size()) 46 { 47 a=q.front(); 48 q.pop(); 49 x=a.x; 50 y=a.y; 51 k=a.k; 52 for (R d=0;d<4;++d) 53 { 54 if(!mw(x,y,k,d)) continue; 55 xx=x+dx[d]; 56 yy=y+dy[d]; 57 b.x=xx; 58 b.y=yy; 59 if(g[xx][yy]==k+1) b.k=k+1; 60 else b.k=k; 61 b.val=a.val+1; 62 if(vis[xx][yy][b.k]!=-1) continue; 63 vis[xx][yy][b.k]=b.val; 64 q.push(b); 65 } 66 } 67 if(vis[ex][ey][m]!=-1) return vis[ex][ey][m]+ext; 68 return -1; 69 } 70 71 void dfs (int x,int ext) 72 { 73 if(x==h+1) 74 { 75 int t=dij(ext); 76 if(ans==-1) ans=t; 77 if(t!=-1) ans=min(ans,t); 78 } 79 else 80 { 81 g[ sx[x] ][ sy[x] ]=-1; 82 dfs(x+1,ext); 83 g[ sx[x] ][ sy[x] ]=0; 84 dfs(x+1,ext+1); 85 } 86 } 87 88 int main() 89 { 90 scanf("%d%d",&n,&m); 91 memset(vis,1,sizeof(vis)); 92 for (R i=1;i<=n;++i) 93 { 94 scanf("%s",st+1); 95 for (R j=1;j<=n;++j) 96 { 97 if(st[j]=='T') ex=i,ey=j; 98 else if(st[j]=='K') bx=i,by=j; 99 else if(st[j]=='#') g[i][j]=-1; 100 else if(st[j]=='.') g[i][j]=0; 101 else if(st[j]=='S') sx[++h]=i,sy[h]=j; 102 else g[i][j]=st[j]-'0'; 103 } 104 } 105 dfs(1,0); 106 if(ans!=-1) 107 printf("%d",ans); 108 else 109 printf("impossible"); 110 return 0; 111 }
---shzr