NOIP模拟赛-2018.10.22

模拟赛

　　今天第一节课是历史，当然是不可能上的，一来到机房发现今天高二考试...

　　老师说以后可能还要给高一考...那还不如现在跟着做好了，毕竟在学长学姐中垫底显得没那么丢人

　　这套题风格挺奇怪的...为什么前面还是神牛后面直接成牛了...

　　题意概述：给出一个长度为$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$转移一下就行.不过有可能会出现重复方案,对于这个问题固定第一个区间的右端点必选即可.

 # include <cstdio>

 # include <iostream>

 # include <queue>

 # include <cstring>

 # include <string>

 # define R register int

 # define ll long long

 # define mod 

 using namespace std;

 const int maxn=;

 int n,m;

 int a[maxn],xorr[maxn][],andd[maxn][],ans;

 int main()

 {

     scanf("%d",&n);

     for (R i=;i<=n;++i)

         scanf("%d",&a[i]),m=max(m,a[i]);

     for (R i=;i<=n;++i)

     {

         xorr[i][ a[i] ]=;

         for (R j=;j<=m;++j)

             xorr[i][ a[i]^j ]=(xorr[i][ a[i]^j ]+xorr[i-][j])%mod;

         for (R j=;j<=m;++j)

             xorr[i][j]=(xorr[i][j]+xorr[i-][j])%mod;

     }

     for (R i=n;i>=;--i)

     {

         andd[i][ a[i] ]=;

         for (R j=;j<=m;++j)

             andd[i][ a[i]&j ]=(andd[i][ a[i]&j ]+andd[i+][j])%mod;

         for (R j=;j<=m;++j)

             andd[i][j]=(andd[i][j]+andd[i+][j])%mod;

     }

     for (R i=;i<n;++i)

         for (R j=;j<=m;++j)

             ans=(1LL*(xorr[i][j]-xorr[i-][j]+mod)*andd[i+][j]%mod+ans)%mod;

     printf("%d",ans);

     fclose(stdin);

     fclose(stdout);

     return ;

 }

　　T2:http://hzwer.com/5042.html

　　题意概述：一个长度为$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$分,伤心.

　　对了,别忘了开滚动数组.

 # include <cstdio>

 # include <iostream>

 # include <queue>

 # include <cstring>

 # include <string>

 # define R register int

 # define ll long long

 # define mod 

 using namespace std;

 const int maxn=;

 int n,k,l,vis[],viss[],maxz;

 int dp[][maxn];

 ll ans=;

 int main()

 {

     scanf("%d%d%d",&n,&k,&l);

     maxz=(<<(k+))-;

     dp[][]=;

     for (R i=;i<n;++i)

     {

         int las=i&;

         int now=las^;

         memset(dp[now],,sizeof(dp[now]));

         for (R z=;z<=maxz;++z)

         {

             if(i==&&z==)

                 i=;

             if(!dp[las][z]) continue;

             vis[]=true;

             int t=z;

             for (R x=;x<=k;++x)

                 vis[x]=t%,t/=;

             for (R x=;x<=k;++x)

             {

                 if(x>l) break;

                 for (R j=;j<=k;++j) viss[j]=vis[j];

                 for (R j=;j<=k;++j) if(vis[j]) viss[j+x]=true;

                 int nexz=;

                 for (R j=k;j>=;--j)

                     nexz=nexz*+viss[j];

                 dp[now][nexz]=(dp[now][nexz]+dp[las][z])%mod;

             }

             if(l>k) dp[now][z]=(dp[now][z]+1LL*dp[las][z]*(l-k)%mod)%mod;

         }

     }

     for (R i=;i<=maxz;++i)

         if(i&(<<(k-)))

             ans=(ans+dp[n&][i])%mod;

     printf("%lld",ans);

     return ;

 }

　　T3:一个数据范围消失了的分层图最短路...因为没有数据范围于是直接选择性失明不管那个限制了,竟然水了$70$...事实上因为限制点的数量非常小,直接$dfs$即可.

 # include <cstdio>

 # include <iostream>

 # include <cstring>

 # include <queue>

 # include <string>

 # define inf

 # define R register int

 using namespace std;

 const int dx[]={-,,,};

 const int dy[]={,,-,};

 const int maxn=;

 char st[];

 int n,m,ans=-,bx,by,ex,ey;

 int g[maxn][maxn],sx[],sy[],h;

 int vis[maxn][maxn][];

 struct z

 {

     int val,x,y,k;

 };

 queue <z> q;

 bool mw (int x,int y,int k,int d)

 {

     int    xx=x+dx[d];

     int yy=y+dy[d];

     if(xx<=||xx>n||yy<=||yy>n) return false;

     if(g[xx][yy]==-) return false;

     return true;

 }

 int dij (int ext)

 {

     memset(vis,-,sizeof(vis));

     while (q.size()) q.pop();

     int x,y,k,xx,yy;

     z a,b;

     a.x=bx;

     a.y=by;

     a.val=;

     a.k=;

     q.push(a);

     vis[ a.x ][ a.y ][]=;

     while (q.size())

     {

         a=q.front();

         q.pop();

         x=a.x;

         y=a.y;

         k=a.k;

         for (R d=;d<;++d)

         {

             if(!mw(x,y,k,d)) continue;

             xx=x+dx[d];

             yy=y+dy[d];

             b.x=xx;

             b.y=yy;

             if(g[xx][yy]==k+) b.k=k+;

             else b.k=k;

             b.val=a.val+;

             if(vis[xx][yy][b.k]!=-) continue;

             vis[xx][yy][b.k]=b.val;

             q.push(b);

         }

     }

     if(vis[ex][ey][m]!=-) return vis[ex][ey][m]+ext;

     return -;

 }

 void dfs (int x,int ext)

 {

     if(x==h+)

     {

         int t=dij(ext);

         if(ans==-) ans=t;

         if(t!=-) ans=min(ans,t);

     }

     else

     {

         g[ sx[x] ][ sy[x] ]=-;

         dfs(x+,ext);

         g[ sx[x] ][ sy[x] ]=;

         dfs(x+,ext+);

     }

 }

 int main()

 {

     scanf("%d%d",&n,&m);

     memset(vis,,sizeof(vis));

     for (R i=;i<=n;++i)

     {

         scanf("%s",st+);

         for (R j=;j<=n;++j)

         {

             if(st[j]=='T') ex=i,ey=j;

             else if(st[j]=='K') bx=i,by=j;

             else if(st[j]=='#') g[i][j]=-;

             else if(st[j]=='.') g[i][j]=;

             else if(st[j]=='S') sx[++h]=i,sy[h]=j;

             else g[i][j]=st[j]-'';

         }

     }

     dfs(,);

     if(ans!=-)

         printf("%d",ans);

     else

         printf("impossible");

     return ;

 }

---shzr

巴特西

NOIP模拟赛-2018.10.22

最新文章

热门文章