模拟赛
今天第一节课是历史，当然是不可能上的，一来到机房发现今天高二考试...
老师说以后可能还要给高一考...那还不如现在跟着做好了，毕竟在学长学姐中垫底显得没那么丢人
这套题风格挺奇怪的...为什么前面还是神牛后面直接成牛了...
题意概述：给出一个长度为$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 ;
}
T1
题意概述：一个长度为$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 ;
}
T2
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 ;
}
T3
---shzr